Pontrjagin-Kuratovszkij tétel

A Pontrjagin-Kuratovszkij-tétel vagy Kuratovszkij - tétel a gráfelmélet olyan tétele, amely szükséges és elégséges feltételt ad ahhoz, hogy egy gráf sík legyen . Van egy ekvivalens megfogalmazása a kiskorúak nyelvén, az úgynevezett Wagner-tétel .

A tétel kimondja, hogy a K 5 ( teljes gráf 5 csúcson) és a K 3,3 ( teljes bipartit gráf , mindegyik részben 3 csúcstal) az egyetlen minimális nem síkbeli gráf.

Történelem

1930-ban Kazimir Kuratovsky lengyel matematikus [1] , 1927-ben pedig Lev Szemjonovics Pontrjagin szovjet matematikus bizonyította be, aki nem tette közzé a bizonyítékát.

Előzetes meghatározások

Egy gráfot síkbelinek nevezünk, ha kétdimenziós síkra úgy rajzolható meg, hogy élei nem metszik egymást páronként.

A gráfot akkor nevezzük a gráf felosztásának , ha az éleihez csúcsokat adunk. $G'$ $G$ $G'$ $G$

Megfogalmazás

Egy gráf akkor és csak akkor sík, ha nem tartalmazza egy öt csúcsú teljes gráf (K 5 ) és egy teljes kétrészes gráf osztásait, amelyek mindegyikében három csúcs van (K 3,3 ).

Bizonyíték

A 'graph a gráfnak homeomorf részgráfot tartalmaz ' tulajdonság rövidítése " " lesz. Törölje a " " élt, zsugorítsa a " " élt és törölje a " " csúcsot . $G$ $H$ $G\supset H$ $Ge$ $G/e$ $Gx$

A Kuratowski-tétel elégségességét a gráf éleinek számára vonatkozó indukció bizonyítja. Az indukció lépése az Állításból következik, hiszen ha vagy vagy vagy a gráf valamely e élére , akkor vagy . A „for ” kijelentés nyilvánvaló. Ha , akkor , és ha , akkor vagy . $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}$

Ha egy összefüggő gráf nem izomorf sem -re, sem -re , és a gráf bármely élére mind a gráfok , mind a gráfok síkbeliek, akkor síkbeli.

G

K_{5}

K_{3,3}

e

G

Ge

G/e

G

Lemma a Kuratowski-gráfokról

Egy tetszőleges gráf esetén a következő három feltétel egyenértékű: $K$

A gráf bármely xy élére a gráf nem tartalmaz θ-gráfot, és a gráf minden csúcsából legalább két él jön ki. $K$ $Kxy$ $Kxy$
Bármely xy gráfél esetén a gráf egy ciklus (amely csúcsokat tartalmaz). $K$ $Kxy$ $n\geq 3$
$K$ izomorf vagy . $K_{5}$ $K_{3,3}$

Mivel sem nem izomorf, sem nem , ezért a Kuratowski gráflemmánál létezik a gráfnak olyan éle , amelyre a gráf vagy egy 2-nél kisebb fokú csúcsot (in ), vagy egy θ-részgráfot tartalmaz. $G$ $K_{5}$ $K_{3,3}$ $e=(xy)$ $G$ $Gxy$ $Gxy$

Ha egy gráfban egy vagy két éle kilép valamelyik csúcsból, akkor az egyiknek összehúzódása síkgráfot eredményez, ami azt jelenti, hogy a G gráf is síkbeli. Ezért feltételezzük továbbá, hogy legalább három éle a G gráf minden csúcsából származik. $G$

Ezért a gráfban nincsenek elszigetelt csúcsok, és ha van p függő csúcs, akkor az x-hez és y-hoz is kapcsolódik a gráfban . Rajzoljunk grafikont önmetszéspontok nélküli síkra. Mivel a gráfban három él jön ki p-ből, nincs olyan él, amely a p-ből induló xpy útvonal „egyik oldalára” megy. Fesd be az xy élt az xpy útvonal mentén, ennek az oldala mentén. Nézzük meg a G gráf képét a síkon önmetszéspontok nélkül. $Gxy$ $G$ $G-(xy)$ $G$

Tekintsük most azt az esetet, amikor a gráf tartalmaz egy θ-részgráfot. $Gxy$

A Jordan-tételből az következik, hogy bármely síkgráf véges számú összefüggő részre osztja fel a síkot. Ezeket a részeket síkgráf lapjainak nevezzük.

Rajzoljunk önmetszéspontok nélküli gráfot a síkra . A gráf síkon lévő képét az xy csúcsból kilépő gráf éleinek törlésével kapjuk. Jelölje a gráf azon lapjának (képének) a határát, amely a gráf xy csúcsát tartalmazza . $G/xy$ $Gxy=G/xy-xy$ $G/xy$ ${\bar {C}}$ $G/xy-xy$ $G/xy$

Vegye figyelembe, hogy egy lap határa nem tartalmazhat θ-részgráfot.

(Ez az állítás levezethető Jordan tételéből. Egy másik bizonyítást kapunk az ellentmondásból: ha egy lap határa tartalmaz egy θ-részgráfot, akkor veszünk egy pontot ezen a lapon belül, és összekötjük három éllel, három ponttal három íven. ' a θ-részgráfból. A gráf képét önmetszés nélküli síkon kapjuk, ez ellentmondás.) $K_{3,3}$

Ezért . Ekkor a gráf élei a gráf azon lapjában (képében) vannak , amelyik nem tartalmazza az xy csúcsot. Tehát a grafikon felosztja a síkot. Ezért van egy ciklus , amelyen belül az xy csúcs (az általánosság elvesztése nélkül) belül van, és a gráf valamely éle kívül van. $Gxy\neq {\bar {C}}$ $Gxy-{\bar {C}}$ $Gxy=G/xy-xy$ ${\bar {C}}$ $C\subset {\bar {C))$ $Gxy-{\bar {C}}$

Jelölje a gráf minden, a cikluson kívül eső élének uniójával . (Lehetséges, .) Feltételezhetjük, hogy ez egy részgráf -ben (és nem csak -ben ). $R$ $G/xy$ $C$ $Gxy-{\bar {C}}\neq R$ $R$ $G$ $Gxy$

Egy gráf önmetszéspontok nélkül rajzolható síkra. Feltételezhetjük, hogy a G gráf x-ből vagy y-ból kilépő élei a gráf képén a cikluson belül helyezkednek el . $GR$ $GR$ $C$

A gráf minden összekapcsolt komponense legfeljebb egy ponttal metszi egymást . $GxyRC$ $C$

(Ha nem ez a helyzet, akkor van egy út, amely két pontot köt össze a -n . A gráf képén a megfelelő út a cikluson belül van . Ezért ez az út a ciklus belsejét két részre osztja, az egyik amelynek xy-t tartalmaz, a másik pedig nem a szélén fekszik, korlátos ... Ezért ellentmondás.) $GxyRC$ $C$ $G/xy$ $C$ $C$ ${\bar {C}}$ $C\nsubseteq {\bar {C))$

Ezért a gráf minden összekapcsolt komponensét bedobhatjuk a ciklusba . Így a gráf a hurkon belül rajzolható meg . Rajzoljunk kívülre , mint a grafikon képénél . Önmetszéspontok nélküli síkon egy gráf képét kapjuk . $C$ $GxyRC$ $GRC$ $C$ $R$ $C$ $G/xy$ $G$

Változatok és általánosítások

A Wagner -tétel a Pontrjagin-Kuratovszkij-tétel egy másik megfogalmazása a mollokon keresztül .
A Robertson-Seymour tétel .

Jegyzetek

↑ Kuratowski, Kazimierz (1930), Sur le problème des courbes gauches en topologie , Fund. Math. T. 15: 271–283 , < http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf > Archiválva : 2018. július 23. a Wayback Machine -nél .

Linkek

A. B. Szkopenkov. A gráfok síkbeliségének Kuratovsky-kritériuma körül // Matematikai oktatás ser. 3. - 2005. - T. 9 . - S. 116-128 . /arXiv:0802.3820 __ _
Yu. Makarychev, Kuratowski gráf síkossági kritériumának rövid bizonyítéka, J. of Graph Theory, 25 (1997) 129-131.