Rovinný graf

Rovinný graf  je graf , který lze nakreslit na rovinu bez křížení hran jinde než ve vrcholech. Nějaký konkrétní obraz rovinného grafu v rovině bez křížení hran ne u vertices je volán rovinný graf . Jinými slovy, rovinný graf je izomorfní k nějakému rovinnému grafu zobrazenému v rovině tak, že jeho vrcholy jsou body roviny a hrany jsou křivky v rovině, které, pokud se vzájemně protínají, pak pouze podél vrcholy. Oblasti, do kterých graf rozděluje rovinu, se nazývají její plochy . Neohraničená část roviny je také plocha, nazývaná vnější plocha. Jakýkoli rovinný graf lze narovnat, tedy překreslit na rovinu tak, že všechny jeho hrany jsou úsečky.

Vlastnosti

Eulerův vzorec

Pro spojený rovinný graf platí následující vztah mezi počtem vrcholů , hran a ploch (včetně vnější plochy):

Byl nalezen Eulerem v roce 1736 [1] při studiu vlastností konvexních mnohostěnů . Tento vztah platí i pro ostatní povrchy až do faktoru zvaného Eulerova charakteristika . Toto je povrchový invariant , pro rovinu nebo kouli je roven dvěma a například pro povrch torusu  je nulový.

Vzorec má mnoho užitečných důsledků. Za prvé, všechny rovinné vrstvení jednoho grafu mají stejný počet ploch. Za druhé, pokud je každá plocha ohraničena alespoň třemi hranami (za předpokladu, že graf má více než dvě hrany) a každá hrana odděluje dvě plochy , pak

Tudíž,

to znamená, že pro větší počet hran je takový graf zjevně nerovinný. Opak není pravdou: jako protipříklad lze vzít Petersenův graf . Z toho vyplývá, že v rovinném grafu lze vždy najít vrchol stupně nejvýše 5.

Obecný vzorec lze také snadno zobecnit na případ nespojeného grafu:

kde  je počet připojených komponent v grafu.

Dva příklady nerovinných grafů

Kompletní graf s pěti vrcholy

Lemma. Kompletní graf s pěti vrcholy (K 5 ) nelze zploštit.

Důkaz. Nefunguje mu to .

"Domy a studny"

Problém tří studní . Jsou zde tři domy a tři studny. Je možné položit cesty mezi domy a studnami tak, aby od každého domu ke každé studni vedla cesta a žádné dvě cesty by se nekřížily. Mosty nelze stavět.

Lemma. Kompletní bipartitní graf se třemi vrcholy v každé z částí (K 3,3 ) nelze položit na rovinu.

Důkaz. Podle Eulerova vzorce má graf 5 ploch.

Na druhou stranu: libovolná plocha (včetně vnější) obsahuje sudý počet hran, což znamená alespoň 4. Protože každá hrana je zahrnuta právě ve dvou plochách, dostaneme vztah , F  je počet ploch, E  je počet hran. Do této nerovnosti dosadíme F = 5 a E = 9 a vidíme, že není splněna.

Pontrjaginova-Kuratovského věta

Tvrzení je zřejmé: obsahuje-li graf G podgraf homeomorfní ke K 5 nebo K 3,3 , pak jej nelze v rovině rozložit. Ukazuje se, že to platí i naopak.

Graf je rovinný právě tehdy, když neobsahuje podgrafy homeomorfní k úplnému grafu pěti vrcholů (K 5 ) nebo ke grafu „domů a studní“ (K 3,3 ).

Větu lze uvést i v následující variantě (někdy nazývané " Wagnerova věta ").

Graf je rovinný právě tehdy, když neobsahuje podgrafy smršťující se na K 5 nebo K 3,3 .

Počítačová kontrola rovinnosti

První algoritmus k nalezení Kuratowského podgrafu v lineárním čase byl vyvinut v roce 1974 Hopcroftem a Tarjanem [2] .

Vlastnosti nerovinných grafů

Rovinné grafy v úlohách

Omalovánka . Plochou mapu je nutné vybarvit daným počtem barev tak, aby libovolné dvě země, které mají společný hraniční úsek, měly různé barvy. Ukazuje se, že při absenci enkláv vždy stačí čtyři barvy, ale toto tvrzení je extrémně obtížné dokázat, viz Problém čtyř barev .

Oprava grafu ( Fariho věta ). Jakýkoli rovinný graf lze překreslit tak, aby zůstal rovinný a hrany se staly úsečkami.

Zobecnění

Graf se hodí na nějaký povrch, pokud jej lze na něj nakreslit bez křížení hran. Skládaný graf se nazývá geometrický , jeho vrcholy jsou body povrchu a hrany jsou čáry na něm. Oblasti, na které graf rozděluje povrch, se nazývají plochy . Rovinný graf je graf položený na rovině.

Průsečíkové číslo grafu G  je nejmenší počet průsečíků hran ploché kresby grafu G . Graf je tedy rovinný právě tehdy, když je jeho průsečík číslo nula.

Toroidní graf  je graf, který lze položit na torus.

Viz také

Poznámky

  1. ↑ Harari F. Teorie grafů URSS str. 126
  2. ↑ Hopcroft, John & Tarjan, Robert E. (1974), Efficient planarity testing , Journal of the Association for Computing Machinery vol. 21 (4): 549–568 , DOI 10.1145/321850.321852  .

Odkazy