Planar graf

Frå Wikipedia – det frie oppslagsverket
Gå til: navigering, søk

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 ei avbilding frå kvart hjørne til eit punkt i det todimesjonale rommet, og frå kvar kant til ei plan kurve, slik at endepunkta til kvar kurve samsvarer med posisjonane til endehjørna, og alle kurvene er disjunkte bortsett frå i endepunkta.

Kuratowskis sats[endre | endre wikiteksten]

K5
K3,3

Den polske matematikaren Kazimierz Kuratowski gav 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.

Eigenskapar[endre | endre wikiteksten]

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.

Text document with red question mark.svg Denne artikkelen manglar kjelder eller referansar. Hjelp Wikipedia med å finna truverdige kjelder!