Pontrjaginova-Kuratovského věta

Pontrjagin-Kuratovského teorém neboli Kuratovského teorém je teorém v teorii grafů , který dává nezbytnou a postačující podmínku pro to, aby byl graf rovinný . Má ekvivalentní formulaci v jazyce nezletilých, tzv. Wagnerův teorém .

Věta říká, že grafy K 5 ( úplný graf na 5 vrcholech) a K 3,3 ( úplný bipartitní graf se 3 vrcholy v každé části) jsou jediné minimální nerovinné grafy.

Historie

Dokázal to v roce 1930 polský matematik Kazimir Kuratovsky [1] a v roce 1927 sovětský matematik Lev Semjonovič Pontrjagin , který svůj důkaz nezveřejnil.

Předběžné definice

Graf se nazývá rovinný , pokud jej lze nakreslit na dvourozměrné rovině tak, že se jeho hrany neprotínají ve dvojicích.

Graf se nazývá poddělení grafu , pokud jej lze získat přidáním vrcholů k jeho hranám. $G'$ $G$ $G'$ $G$

Formulace

Graf je rovinný právě tehdy, když neobsahuje dělení úplného grafu s pěti vrcholy (K 5 ) a úplného bipartitního grafu se třemi vrcholy v každé části (K 3,3 ).

Důkaz

Vlastnost 'graph obsahuje podgraf homeomorfní ke grafu ' bude zkrácena jako ' '. Smazat hranu ' ', zmenšit hranu ' ' a smazat vrchol ' '. $G$ $H$ $G\supset H$ $Ge$ $G/e$ $Gx$

Dostatečnost v Kuratowského větě se dokazuje indukcí počtu hran v grafu. Krok indukce vyplývá z Příkazu, protože jestliže nebo nebo nebo pro nějakou hranu e grafu , pak nebo . Prohlášení „pro “ je zřejmé. If , then , a if , then or . $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}$

Pokud je souvislý graf izomorfní ani , ani , a pro jakoukoli hranu grafu jsou grafy i rovinné, pak rovinné.

G

K_{5}

K_{3,3}

E

G

Ge

G/e

G

Lemma o grafech Kuratowski

Pro libovolný graf jsou ekvivalentní následující tři podmínky: $K$

Pro žádnou hranu xy grafu graf neobsahuje θ-graf a z každého vrcholu grafu vystupují alespoň dvě hrany. $K$ $Kxy$ $Kxy$
Pro libovolnou hranu grafu xy je grafem cyklus (obsahující vrcholy). $K$ $Kxy$ $n\geq 3$
$K$ izomorfní nebo . $K_{5}$ $K_{3,3}$

Protože ani jeden není izomorfní ani , pak podle lemmatu Kuratowského grafu existuje hrana grafu , pro kterou graf obsahuje buď vrchol stupně menšího než 2 (in ) nebo θ-podgraf. $G$ $K_{5}$ $K_{3,3}$ $e=(xy)$ $G$ $Gxy$ $Gxy$

Pokud v grafu jedna nebo dvě jeho hrany vystupují z nějakého vrcholu, pak smrštěním jedné z nich vznikne rovinný graf, což znamená, že i graf G je rovinný. Proto dále předpokládáme, že z každého vrcholu grafu G vystupují alespoň tři jeho hrany. $G$

Proto v grafu nejsou žádné izolované vrcholy, a pokud existuje zavěšený vrchol p, pak je v grafu spojen s x i y . Nakreslete graf na rovině bez vlastních průniků. Protože z p v grafu vycházejí tři hrany, nejsou žádné hrany směřující „na jednu stranu“ cesty xpy od p. 'Malovat' hranu xy podél cesty xpy 'tato strana'. Dostaneme obrázek grafu G na rovině bez vlastních průniků. $Gxy$ $G$ $G-(xy)$ $G$

Zvažte nyní případ, kdy graf obsahuje θ-podgraf. $Gxy$

Z Jordanovy věty vyplývá, že libovolný rovinný graf rozděluje rovinu na konečný počet spojených částí. Tyto části se nazývají plochy rovinného grafu.

Nakreslete graf bez vlastních průniků na rovině . Obraz grafu v rovině získáme smazáním hran grafu vycházejících z vrcholu xy. Označme hranicí té plochy (obrázku) grafu , která obsahuje vrchol xy grafu . $G/xy$ $Gxy=G/xy-xy$ $G/xy$ ${\bar {C}}$ $G/xy-xy$ $G/xy$

Všimněte si, že hranice plochy nemůže obsahovat θ-podgraf.

(Toto tvrzení lze odvodit z Jordanovy věty. Další důkaz získáme kontradikcí: jestliže hranice plochy obsahuje θ-podgraf, pak vezmeme bod uvnitř této plochy a spojíme jej třemi hranami se třemi body na třech 'obloucích ' θ-podgrafu. Získáme obraz grafu na rovinách bez sebeprůniků, což je rozpor.) $K_{3,3}$

Proto . Potom jsou okraje grafu v líci (obrázku) grafu , který neobsahuje vrchol xy. Takže graf rozdělí rovinu. Existuje tedy cyklus , vůči kterému leží vrchol xy (bez ztráty obecnosti) uvnitř a nějaká hrana grafu leží vně. $Gxy\neq {\bar {C}}$ $Gxy-{\bar {C}}$ $Gxy=G/xy-xy$ ${\bar {C}}$ $C\subset {\bar {C))$ $Gxy-{\bar {C}}$

Označme sjednocením všech hran grafu ležících mimo cyklus . (Možná, .) Můžeme předpokládat, že jde o podgraf v (a nejen v ). $R$ $G/xy$ $C$ $Gxy-{\bar {C}}\neq R$ $R$ $G$ $Gxy$

Graf lze nakreslit na rovině bez průsečíků. Můžeme předpokládat, že hrany grafu G, vycházející z x nebo y, na obrázku grafu leží uvnitř cyklu . $GR$ $GR$ $C$

Každá spojená složka grafu se protíná nejvýše jedním bodem. $GxyRC$ $C$

(Pokud tomu tak není, pak existuje cesta, která spojuje dva body na . Na obrázku grafu leží odpovídající cesta uvnitř cyklu . Tato cesta tedy rozděluje vnitřek cyklu na dvě části, jednu z nichž obsahuje xy a druhá neleží na hraně, ohraničená ... Proto rozpor.) $GxyRC$ $C$ $G/xy$ $C$ $C$ ${\bar {C}}$ $C\nsubseteq {\bar {C))$

Proto můžeme každou připojenou složku grafu hodit dovnitř cyklu . Takže graf může být nakreslen uvnitř smyčky . Pojďme kreslit venku , jako pro obrázek grafu . Získáme obraz grafu na rovině bez vlastních průniků. $C$ $GxyRC$ $GRC$ $C$ $R$ $C$ $G/xy$ $G$

Variace a zobecnění

Wagnerův teorém je další formulací Pontryagin-Kuratovského teorému, přes nezletilé .
Robertsonova-Seymourova věta .

Poznámky

↑ Kuratowski, Kazimierz (1930), Sur le problème des courbes gauches en topologie , Fund. Matematika. T. 15: 271–283 , < http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf > Archivováno 23. července 2018 na Wayback Machine .

Odkazy

A. B. Skopenkov. Kolem Kuratovského kritéria pro rovinnost grafů // Matematické vzdělávání ser. 3. - 2005. - T. 9 . - S. 116-128 . /arXiv:0802.3820 __ _
Yu. Makarychev, Krátký důkaz Kuratowského kritéria rovinnosti grafu, J. of Graph Theory, 25 (1997) 129-131.