Pontryagin-Kuratovskys teorem

Pontryagin-Kuratovskys sats , eller Kuratovskys sats , är en sats inom grafteorin som ger ett nödvändigt och tillräckligt villkor för att en graf ska vara plan . Den har en likvärdig formulering på mindreåriga språk, den så kallade Wagner-satsen .

Satsen säger att graferna K 5 ( komplett graf på 5 hörn) och K 3,3 ( komplett tvådelad graf med 3 hörn i varje del) är de enda minimala icke-planära graferna.

Historik

Det bevisades 1930 av den polske matematikern Kazimir Kuratovsky [1] och 1927 av den sovjetiske matematikern Lev Semyonovich Pontryagin , som inte publicerade hans bevis.

Preliminära definitioner

En graf kallas plan om den kan ritas på ett tvådimensionellt plan så att dess kanter inte skär varandra i par.

En graf kallas en underavdelning av en graf om den kan erhållas genom att lägga till hörn till dess kanter. $G'$ $G$ $G'$ $G$

Formulering

En graf är plan om och endast om den inte innehåller divisioner av en komplett graf med fem hörn (K 5 ) och en komplett tvådelad graf med tre hörn i varje del (K 3,3 ).

Bevis

Egenskapen 'grafen innehåller en subgraf som är homeomorf till grafen ' kommer att förkortas till ' '. Ta bort kant ' ', krymp kant ' ' och radera vertex ' '. $G$ $H$ $G\supset H$ $Ge$ $G/e$ $Gx$

Tillräcklighet i Kuratowskis sats bevisas genom induktion på antalet kanter i en graf. Induktionssteget följer av uttalandet, eftersom om eller eller eller för någon kant e av grafen , då eller . "för " uttalandet är uppenbart. Om , då , och om , då eller . $Ge\supset K_{5}$ $Ge\supset K_{3,3}$ $G/e\supset K_{5}$ $G/e\supset K_{3,3}$ $G$ $G\supset K_{5}$ $G\supset K_{3,3}$ $Ge$ $G/xy\supset K_{3,3}$ $G\supset K_{3,3}$ $G/xy\supset K_{5}$ $G\supset K_{5}$ $G\supset K_{3,3}$

Om en ansluten graf är isomorf till varken , eller , och för någon kant av grafen både grafer och är plana, då planar.

G

{\displaystyle K_{5))

K_{3,3}

e

G

Ge

G/e

G

Lemma om Kuratowski-grafer

För en godtycklig graf är följande tre villkor likvärdiga: $K$

För någon kant xy på grafen innehåller grafen ingen θ-graf, och minst två kanter kommer fram från varje hörn av grafen. $K$ $Kxy$ $Kxy$
För varje grafkant xy är grafen en cykel (som innehåller hörn). $K$ $Kxy$ $n\geq 3$
$K$ isomorf eller . ${\displaystyle K_{5))$ $K_{3,3}$

Eftersom varken är isomorf eller , så finns det enligt Kuratowski-graflemmat en kant på grafen för vilken grafen antingen innehåller en vertex av grad mindre än 2 (in ) eller en θ-subgraf. $G$ ${\displaystyle K_{5))$ $K_{3,3}$ $e=(xy)$ $G$ $Gxy$ $Gxy$

Om i en graf en eller två av dess kanter kommer ut från någon vertex, resulterar sammandragning av en av dem i en plan graf, vilket betyder att grafen G också är plan. Därför antar vi vidare att minst tre av dess kanter kommer ut från varje hörn av grafen G. $G$

Därför finns det inga isolerade hörn i grafen, och om det finns en hängande vertex p, så är den kopplad till både x och y i grafen . Låt oss rita en graf på ett plan utan självkorsningar. Eftersom det finns tre kanter som kommer ut från p i grafen, finns det inga kanter som går "på ena sidan" av banan xpy från p. 'Måla' kanten xy längs vägen xpy 'den här sidan' av den. Låt oss få bilden av grafen G på planet utan självkorsningar. $Gxy$ $G$ $G-(xy)$ $G$

Betrakta nu fallet när grafen innehåller en θ-subgraf. $Gxy$

Det följer av Jordansatsen att vilken plan graf som helst delar upp planet i ett ändligt antal sammankopplade delar. Dessa delar kallas ytor av en plan graf.

Låt oss rita en graf utan självskärningar på planet . Bilden av grafen på planet erhålls genom att radera kanterna på grafen som kommer ut från vertex xy. Beteckna med gränsen för den yta (bild) av grafen , som innehåller vertex xy för grafen . $G/xy$ $Gxy=G/xy-xy$ $G/xy$ ${\bar {C}}$ $G/xy-xy$ $G/xy$

Observera att gränsen för ett ansikte inte kan innehålla en θ-subgraf.

(Detta påstående kan härledas från Jordans teorem. Ett annat bevis erhålls genom motsägelse: om gränsen för en yta innehåller en θ-subgraf, så tar vi en punkt inuti denna yta och kopplar den med tre kanter med tre punkter på tre 'bågar ' av θ-subgrafen. Vi får en bild av grafen på plan utan självkorsningar, en motsägelse.) $K_{3,3}$

Därför . Då är kanterna på grafen i ansiktet (bilden) på grafen som inte innehåller vertex xy. Så grafen delar upp planet. Därför finns det en cykel med avseende på vilken vertex xy ligger (utan förlust av allmänhet) inuti, och någon kant av grafen ligger utanför. $Gxy\neq {\bar {C}}$ $Gxy-{\bar {C}}$ $Gxy=G/xy-xy$ ${\bar {C}}$ $C\subset {\bar {C))$ $Gxy-{\bar {C}}$

Beteckna med föreningen av alla kanter på grafen som ligger utanför cykeln . (Möjligen .) Vi kan anta att det är en subgraf i (och inte bara i ). $R$ $G/xy$ $C$ $Gxy-{\bar {C}}\neq R$ $R$ $G$ $Gxy$

En graf kan ritas på ett plan utan självskärningar. Vi kan anta att kanterna på grafen G, utgående från x eller y, på bilden av grafen ligger inuti cykeln . $GR$ $GR$ $C$

Varje ansluten komponent i grafen skär med högst en punkt. $GxyRC$ $C$

(Om så inte är fallet, så finns det en väg i som förbinder två punkter på . På bilden av grafen ligger motsvarande väg inuti cykeln . Därför delar denna väg upp cykelns inre i två delar, en som innehåller xy, och den andra inte ligger på kanten, avgränsad ... Därför en motsägelse.) $GxyRC$ $C$ $G/xy$ $C$ $C$ ${\bar {C}}$ $C\nsubseteq {\bar {C))$

Därför kan vi kasta varje ansluten komponent i grafen in i cykeln . Så grafen kan ritas inuti slingan . Låt oss rita utanför , som för grafbilden . Vi får en bild av en graf på ett plan utan självkorsningar. $C$ $GxyRC$ $GRC$ $C$ $R$ $C$ $G/xy$ $G$

Variationer och generaliseringar

Wagner-satsen är en annan formulering av Pontryagin-Kuratovsky-satsen, genom biämnen .
Robertson-Seymour-satsen .

Anteckningar

↑ Kuratowski, Kazimierz (1930), Sur le problème des courbes gauches en topologie , Fund. Matematik. T. 15: 271–283 , < http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf > Arkiverad 23 juli 2018 på Wayback Machine .

Länkar

A. B. Skopenkov. Runt Kuratovsky-kriteriet för planaritet av grafer // Matematisk utbildning ser. 3. - 2005. - T. 9 . - S. 116-128 . /arXiv:0802.3820 __ _
Yu. Makarychev, Ett kort bevis på Kuratowskis grafplanaritetskriterium, J. of Graph Theory, 25 (1997) 129-131.