Plan graf

En plan graf  är en graf som kan ritas på ett plan utan att korsa kanter annat än vid hörnen. Varje specifik bild av en plan graf i ett plan utan korsande kanter utanför hörn kallas en plan graf . Med andra ord, en plan graf är isomorf till någon plan graf avbildad på ett plan på ett sådant sätt att dess hörn är punkter i planet, och kanterna är kurvor på planet, som, om de skär varandra, då endast längs hörnen. De områden som en graf delar upp ett plan i kallas dess ytor . Den obegränsade delen av planet är också ett ansikte, kallat det yttre ansiktet . Vilken plan graf som helst kan rätas ut, det vill säga ritas om på planet så att alla dess kanter är linjesegment.

Egenskaper

Eulers formel

För en sammankopplad plan graf gäller följande förhållande mellan antalet hörn , kanter och ytor (inklusive den yttre ytan):

Den hittades av Euler 1736 [1] när han studerade egenskaperna hos konvexa polyedrar . Detta förhållande gäller även för andra ytor upp till en faktor som kallas Euler-karaktäristiken . Detta är ytans invariant , för ett plan eller en sfär är det lika med två, och till exempel för ytan på en torus  är det noll.

Formeln har många användbara konsekvenser. För det första har alla plana staplar av en graf samma antal ytor. För det andra, om varje yta avgränsas av minst tre kanter (förutsatt att grafen har fler än två kanter), och varje kant separerar två sidor , då

Följaktligen,

det vill säga för ett större antal kanter är en sådan graf uppenbarligen icke-plan. Det omvända är inte sant: man kan ta Petersen-grafen som ett motexempel . Det följer att i en plan graf är det alltid möjligt att hitta en spets med grad som högst 5.

Den allmänna formeln är också lätt generaliserad till fallet med en frånkopplad graf:

var  är antalet anslutna komponenter i grafen.

Två exempel på icke-planära grafer

Komplett graf med fem hörn

Lemma. En komplett graf med fem hörn (K 5 ) kan inte plattas ut.

Bevis. Det fungerar inte för honom .

"Hus och brunnar"

Problemet med tre brunnar . Det finns tre hus och tre brunnar. Går det att lägga stigar mellan hus och brunnar på ett sådant sätt att en stig leder från varje hus till varje brunn, och inte två stigar skulle korsa varandra. Broar kan inte byggas.

Lemma. En komplett tvådelad graf med tre hörn i var och en av delarna (K 3,3 ) kan inte läggas på ett plan.

Bevis. Enligt Eulerformeln har grafen 5 ytor.

Å andra sidan: vilken yta som helst (inklusive den yttre) innehåller ett jämnt antal kanter, vilket betyder minst 4. Eftersom varje kant ingår i exakt två sidor får vi relationen , F  är antalet sidor, E  är antalet kanter. Vi ersätter F = 5 och E = 9 i denna olikhet och ser att den inte är uppfylld.

Pontryagin-Kuratovsky-teoremet

Påståendet är uppenbart: om en graf G innehåller en subgraf som är homeomorf till K 5 eller K 3,3 , så kan den inte brytas ner på planet. Det visar sig att det motsatta också är sant.

En graf är plan om och endast om den inte innehåller subgrafer som är homeomorfa till en komplett graf med fem hörn (K 5 ) eller till en "hus och brunnar"-graf (K ​​3,3 ).

Satsen kan också anges i följande variant (ibland kallad " Wagners sats ").

Grafen är plan om och endast om den inte innehåller subgrafer som drar ihop sig till K 5 eller K 3,3 .

Datorkontroll för planaritet

Den första algoritmen för att hitta Kuratowski-subgrafen i linjär tid utvecklades 1974 av Hopcroft och Tarjan [2] .

Funktioner i icke-planära grafer

Plana grafer i problem

Målarkort . Det är nödvändigt att färglägga en platt karta med ett givet antal färger så att två länder som har en gemensam gränssektion har olika färger. Det visar sig att i avsaknad av enklaver räcker det alltid med fyra färger, men detta påstående är extremt svårt att bevisa, se Fyra färger problem .

Grafrättning ( Faris sats ). Vilken plan graf som helst kan ritas om så att den förblir plan och kanterna blir linjesegment.

Generaliseringar

En graf passar på någon yta om den kan ritas på den utan att korsa kanter. Den staplade grafen kallas geometrisk , dess hörn är punkterna på ytan och kanterna är linjerna på den. De områden som en graf delar upp en yta i kallas ytor . En plan graf är en graf som läggs ut på ett plan.

Skärningsnumret för grafen G  är det minsta antalet skärningar av kanterna på den platta ritningen av grafen G . Således är en graf plan om och endast om dess skärningsnummer är noll.

En toroidgraf  är en graf som kan läggas på en torus.

Se även

Anteckningar

  1. ↑ Harari F. Graph Theory URSS s. 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  .

Länkar