Planar graf
Frå Wikipedia – det frie oppslagsverket
Ein planar graf er i grafteori ein graf som kan teiknast i planet utan at nokre av kantane skjer kvarandre. Ein ikkje-planar graf kan ikkje teiknast på ein sånn måte. Ein plan graf er ein planar graf som er teikna i planet. Ein kan definere ein plan graf som ein planar graf med ein avbildning frå kvart hjørne til eit punkt i det todimesjonale rommet, og frå kvar kant til ein plan kurve, slik at endepunkta til kvar kurve samsvarer med posisjonane til endehjørna, og alle kurvene er disjunkte bortsett frå i endepunkta.
[endre] Kuratowskis sats
Den polske matematikaren Kazimierz Kuratowski ga ei karakterisering av planare grafar, nå kjend som Kuratowskis sats:
Ein endeleg graf er planar viss og berre viss den ikkje inneheld ein undergraf som er ein subdivisjon av K5 (den komplette grafen med fem hjørne) eller K3,3 (den komplette bipartite grafen med tre hjørne i kvar del).
En subdivisjon av ein graf får ein ved å leggje til eit eller fleire hjørne i ein kant, (til dømes ved å endre kanten •——• til •—•—•) og gjenta dette null eller fleire gonger.
[endre] Eigenskapar
Viss ein teiknar ein planar graf i planet, rammar han inn eitt eller fleire område. Viss n er talet på hjørne, m er talet på kantar og f er talet på område, seier Eulers formel at n - m + f = 2. Av dette kan ein vise at m ≤ 3n - 6 for alle planare grafar.
Firefargersatsen seier at hjørna i ein planar graf alltid kan verte farga med fire farger sånn at to naboar alltid har ulike farger.
