Pontryagin-Kuratovsky lause

Pontrjagin-Kuratovsky-lause eli Kuratovskin lause on graafiteorian lause, joka antaa tarpeellisen ja riittävän ehdon graafin tasolle . Sillä on vastaava muotoilu alaikäisten kielellä, niin kutsuttu Wagnerin teoreema .

Lauseen mukaan graafit K 5 ( täydellinen graafi 5 pisteellä) ja K 3,3 ( täydellinen kaksiosainen graafi , jossa on 3 kärkeä kussakin osassa) ovat ainoat minimaaliset ei-tasomaiset graafit.

Historia

Sen todisti vuonna 1930 puolalainen matemaatikko Kazimir Kuratovsky [1] ja vuonna 1927 Neuvostoliiton matemaatikko Lev Semjonovich Pontryagin , joka ei julkaissut todistustaan.

Alustavat määritelmät

Graafia kutsutaan tasomaiseksi , jos se voidaan piirtää kaksiulotteiselle tasolle siten, että sen reunat eivät leikkaa pareittain.

Graafia kutsutaan graafin alajaoksi , jos se saadaan lisäämällä pisteitä sen reunoihin. $G'$ $G$ $G'$ $G$

Sanamuoto

Graafi on tasomainen silloin ja vain, jos se ei sisällä viiden kärjen (K 5 ) ja täydellisen kaksiosaisen graafin , jossa on kolme kärkeä kussakin osassa (K 3,3 ) jakoja.

Todiste

Ominaisuus 'graafi sisältää graafille homeomorfisen aligraafin ' lyhennetään nimellä ' '. Poista reuna ' ', kutista reuna ' ja poista kärki ' '. $G$ $H$ $G\supset H$ $Ge$ $G/e$ $Gx$

Kuratowskin lauseen riittävyys todistetaan graafin reunojen lukumäärän induktiolla. Induktiovaihe seuraa lauseesta, koska jos tai tai tai graafin jollekin reunalle e , niin tai . "For "-lauseke on ilmeinen. Jos , niin ja jos , sitten tai . $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}$

Jos yhdistetty graafi ei ole isomorfinen , eikä , ja millekään graafin reunalle sekä graafit että ovat tasomaisia, niin tasomainen.

G

K_{5}

K_{3,3}

e

G

Ge

G/e

G

Lemma Kuratowskin kaavioista

Mielivaltaiselle kuvaajalle seuraavat kolme ehtoa ovat yhtäläisiä: $K$

Graafin millekään reunalle xy graafi ei sisällä θ-graafia, ja graafin kustakin kärjestä tulee vähintään kaksi reunaa. $K$ $Kxy$ $Kxy$
Minkä tahansa graafin reunan xy kohdalla graafi on sykli (sisältää kärkipisteitä). $K$ $Kxy$ $n\geq 3$
$K$ isomorfinen tai . $K_{5}$ $K_{3,3}$

Koska kumpikaan ei ole isomorfinen eikä , niin Kuratowskin graafilemman mukaan graafissa on reuna , jolle graafi sisältää joko alle 2 asteen kärjen (in ) tai θ-aligraafin. $G$ $K_{5}$ $K_{3,3}$ $e=(xy)$ $G$ $Gxy$ $Gxy$

Jos graafissa yksi tai kaksi sen reunaa nousee jostakin kärjestä, niin yhden niistä supistuminen johtaa tasograafiin, mikä tarkoittaa, että graafi G on myös tasomainen. Siksi oletetaan edelleen, että vähintään kolme sen reunaa tulee graafin G jokaisesta kärjestä. $G$

Siksi graafissa ei ole eristettyjä kärkipisteitä, ja jos on riippuva kärki p, niin se on kytketty sekä x:ään että y:ään graafissa . Piirretään graafi tasolle ilman itseleikkauksia. Koska graafissa p:stä tulee kolme reunaa, ei ole yhtään reunaa, joka menee 'yhdelle puolelle' polkua xpy p:stä. 'Maalaa' reuna xy polkua xpy pitkin sen 'tämä puoli'. Otetaan graafin G kuva tasolle ilman itseleikkauksia. $Gxy$ $G$ $G-(xy)$ $G$

Tarkastellaan nyt tapausta, jossa graafi sisältää θ-aligraafin. $Gxy$

Jordan-lauseesta seuraa, että mikä tahansa tasograafi jakaa tason äärelliseen määrään toisiinsa liittyviä osia. Näitä osia kutsutaan tasograafin kasvoiksi.

Piirretään kuvaaja ilman itseleikkauksia tasolle . Kuvaajan kuva tasossa saadaan pyyhkimällä graafin kärjestä xy ulos tulevat reunat. Merkitään graafin sen pinnan (kuvan) rajalla , joka sisältää graafin kärjen xy . $G/xy$ $Gxy=G/xy-xy$ $G/xy$ ${\bar {C}}$ $G/xy-xy$ $G/xy$

Huomaa, että kasvojen raja ei voi sisältää θ-aligraafia.

(Tämä väite voidaan päätellä Jordanin lauseesta. Toinen todiste saadaan ristiriitaisesti: jos kasvojen raja sisältää θ-osagraafin, niin otamme pisteen tämän pinnan sisällä ja yhdistämme sen kolmeen reunaan, joissa on kolme pistettä kolmella kaarella ' θ-osagraafista. Saamme kuvan graafista tasoilla, joissa ei ole itseleikkauksia, ristiriita.) $K_{3,3}$

Siksi . Tällöin graafin reunat ovat graafin pinnassa (kuvassa), joka ei sisällä kärkeä xy. Joten kuvaaja jakaa tason. Siksi on olemassa sykli , jonka suhteen kärki xy on (ilman yleisyyden menetystä) sisällä, ja jokin graafin reuna on ulkopuolella. $Gxy\neq {\bar {C}}$ $Gxy-{\bar {C}}$ $Gxy=G/xy-xy$ ${\bar {C}}$ $C\subset {\bar {C))$ $Gxy-{\bar {C}}$

Merkitään syklin ulkopuolella olevien graafin kaikkien reunojen liitolla . (Mahdollisesti, .) Voimme olettaa, että se on aligraafi muodossa (eikä vain ). $R$ $G/xy$ $C$ $Gxy-{\bar {C}}\neq R$ $R$ $G$ $Gxy$

Graafi voidaan piirtää tasolle ilman itseleikkauksia. Voidaan olettaa, että graafin G:stä lähtevät reunat graafin kuvassa ovat syklin sisällä . $GR$ $GR$ $C$

Kukin kaavion yhdistetty komponentti leikkaa enintään yhden pisteen. $GxyRC$ $C$

(Jos näin ei ole, siinä on polku, joka yhdistää kaksi pistettä kohdassa . Kuvaajan kuvassa vastaava polku on syklin sisällä . Siksi tämä polku jakaa syklin sisäosan kahteen osaan, josta on xy, ja toinen ei makaa reunalla, rajattu ... Siksi ristiriita.) $GxyRC$ $C$ $G/xy$ $C$ $C$ ${\bar {C}}$ $C\nsubseteq {\bar {C))$

Siksi voimme heittää jokaisen kaavion yhdistetyn komponentin syklin sisään . Kuvaaja voidaan siis piirtää silmukan sisään . Piirretään ulkopuolelle , kuten kaaviokuvalle . Saamme kuvan graafista tasossa ilman itseleikkauksia. $C$ $GxyRC$ $GRC$ $C$ $R$ $C$ $G/xy$ $G$

Muunnelmia ja yleistyksiä

Wagnerin teoreema on toinen Pontryagin-Kuratovsky-lauseen muotoiltu alaikäisten kautta .
Robertson-Seymourin lause .

Muistiinpanot

↑ Kuratowski, Kazimierz (1930), Sur le problème des courbes gauches en topologie , Fund. Matematiikka. T. 15: 271–283 , < http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf > Arkistoitu 23. heinäkuuta 2018 Wayback Machinessa .

Linkit

A. B. Skopenkov. Graafisten tasomaisuuden Kuratovsky-kriteerin ympärillä // Matemaattinen koulutus ser. 3. - 2005. - T. 9 . - S. 116-128 . /arXiv:0802.3820 __ _
Yu. Makarychev, lyhyt todiste Kuratowskin graafin tasoisuuskriteeristä, J. of Graph Theory, 25 (1997) 129-131.