Plan graf

En plan graf er en graf , der kan tegnes på et plan uden at krydse kanter andet end ved hjørnerne. Ethvert specifikt billede af en plan graf i et plan uden krydsende kanter uden for hjørner kaldes en plan graf . Med andre ord er en plan graf isomorf i forhold til en plan graf afbildet på en plan på en sådan måde, at dens toppunkter er punkter på planet, og kanterne er kurver på planet, som, hvis de skærer hinanden, så kun langs hjørnerne. De områder, som en graf opdeler et plan i, kaldes dets flader . Den ubundne del af planet er også et ansigt, kaldet det ydre ansigt. Enhver plan graf kan rettes ud, det vil sige gentegnes på planet, så alle dens kanter er linjestykker.

Egenskaber

Eulers formel

For en forbundet plan graf gælder følgende forhold mellem antallet af spidser , kanter og flader (inklusive den ydre flade): $|V(G)|$ $|E(G)|$ $|F(G)|$

\ |V(G)|-|E(G)|+|F(G)|=2.

Det blev fundet af Euler i 1736 [1] mens han studerede egenskaberne af konvekse polyedre . Denne relation er også gyldig for andre overflader op til en faktor kaldet Euler-karakteristikken . Dette er overfladeinvarianten , for et plan eller en kugle er det lig med to, og for eksempel for overfladen af en torus er det nul.

Formlen har mange nyttige implikationer. For det første har alle plane stabler af én graf det samme antal flader. For det andet, hvis hver flade er afgrænset af mindst tre kanter (forudsat at grafen har mere end to kanter), og hver kant adskiller to flader , så

3|F(G)|\leq 2|E(G)|,

Følgelig,

|E(G)|\leq 3|V(G)|-6,

det vil sige, for et større antal kanter er en sådan graf åbenlyst ikke-plan. Det modsatte er ikke sandt: man kan tage Petersen-grafen som et modeksempel . Det følger heraf, at det i en plan graf altid er muligt at finde et toppunkt på højst 5.

Den generelle formel er også let generaliseret til tilfældet med en afbrudt graf:

|V(G)|-|E(G)|+|F(G)|=1+|C(G)|,

hvor er antallet af tilsluttede komponenter i grafen. $|C(G)|$

To eksempler på ikke-planære grafer

Komplet graf med fem hjørner

Lemma. En komplet graf med fem spidser (K 5 ) kan ikke udjævnes.

Bevis. Det virker ikke for ham . $E\leqslant 3V-6$

"Huse og brønde"

Problemet med tre brønde . Der er tre huse og tre brønde. Er det muligt at lægge stier mellem huse og brønde på en sådan måde, at en sti fører fra hvert hus til hver brønd, og ikke to stier ville krydse hinanden. Broer kan ikke bygges.

Lemma. En komplet todelt graf med tre spidser i hver af delene (K 3,3 ) kan ikke lægges på et plan.

Bevis. Ifølge Euler-formlen har grafen 5 flader.

På den anden side: enhver flade (inklusive den ydre) indeholder et lige antal kanter, hvilket betyder mindst 4. Da hver kant er inkluderet i præcis to flader, får vi relationen , F er antallet af flader, E er antallet af kanter. Vi erstatter F = 5 og E = 9 i denne ulighed og ser, at den ikke er opfyldt. $4F\leqslant 2E$

Pontryagin-Kuratovsky-sætningen

Udsagnet er indlysende: hvis en graf G indeholder en subgraf , der er homøomorf til K 5 eller K 3,3 , så kan den ikke nedbrydes på planet. Det viser sig, at det modsatte også er tilfældet.

En graf er plan, hvis og kun hvis den ikke indeholder subgrafer, der er homøomorfe til en komplet graf med fem hjørner (K 5 ) eller til en "huse og brønde"-graf (K 3,3 ).

Sætningen kan også angives i følgende variant (nogle gange kaldet " Wagners sætning ").

Grafen er plan, hvis og kun hvis den ikke indeholder undergrafer , der trækker sig sammen til K 5 eller K 3,3 .

Computertjek for planaritet

Den første algoritme til at finde Kuratowski-undergrafen i lineær tid blev udviklet i 1974 af Hopcroft og Tarjan [2] .

Funktioner ved ikke-plane grafer

en tilstrækkelig betingelse er, at hvis en graf indeholder en komplet todelt undergraf K 3,3 eller en komplet undergraf K 5 , så er den ikke-plan;
en nødvendig betingelse er, at hvis grafen er ikke-plan, skal den indeholde mere end 4 spidser, hvis grad er større end 3, eller mere end 5 spidser af grad større end 2.

Plane grafer i problemer

Farvelægningskort . Det er nødvendigt at farvelægge et fladt kort med et givet antal farver, så to lande, der har et fælles grænseafsnit, har forskellige farver. Det viser sig, at i mangel af enklaver er fire farver altid nok, men denne erklæring er ekstremt svær at bevise, se Fire farver problem .

Grafrettelse ( Faris sætning ). Enhver plan graf kan tegnes om, så den forbliver plan, og kanterne bliver til linjestykker.

Generaliseringer

En graf passer på en overflade, hvis den kan tegnes på den uden at krydse kanter. Den stablede graf kaldes geometrisk , dens toppunkter er overfladens punkter, og kanterne er linjerne på den. De områder, som en graf opdeler en overflade i, kaldes flader . En plan graf er en graf lagt ud på et plan.

Skæringsnummeret for grafen G er det mindste antal skæringspunkter af kanterne på den flade tegning af grafen G . En graf er således plan, hvis og kun hvis dens skæringsnummer er nul.

En toroidal graf er en graf, der kan lægges på en torus.

Se også

Ordliste over grafteoretiske termer
grafteori
Celle (grafteori)
Faris sætning
Gamma-algoritme - en algoritme til at kontrollere en graf for planaritet og dens flade lægning

Noter

↑ Harari F. Graph Theory URSS s. 126
↑ Hopcroft, John & Tarjan, Robert E. (1974), Efficient planarity testing , Journal of the Association for Computing Machinery bind 21 (4): 549–568 , DOI 10.1145/321850.321852 .