Robertson-Seymourin teoreema (kutsutaan myös graafin sivulauseeksi [1] ) sanoo, että mikä tahansa graafiperhe , joka on suljettu reunanpoisto- ja supistusoperaatioiden vuoksi, voidaan määrittää rajallisella kiellettyjen graafien joukolla .
Esimerkiksi tasograafien joukko suljetaan reunojen poisto- ja supistamisoperaatioissa; kielletyt graafit ovat tässä tapauksessa täydellinen graafi K 5 ja täydellinen kaksiosainen graafi K 3,3 . Viimeistä väitettä kutsutaan Wagnerin lauseeksi ja se liittyy läheisesti Pontryagin-Kuratovsky-lauseeseen .
Lause on laajalti tunnettu alkeellisesta muotoilustaan yksinkertaisen todisteen puuttuessa. Häntä kutsutaan nimellä Neil Robertson.ja Paul Seymour , joka osoitti sen 20 artikkelin sarjassa, yhteensä 500 sivua, jotka julkaistiin vuosina 1983–2004 [2] [3] [4] . Ennen todistetta lauseen väite tunnettiin Wagnerin arveluna , vaikka Wagner itse väitti, ettei hän koskaan esittänyt tätä olettamusta [5] .
Kruskalin puulauseesta seuraa heikompi väite puille. Lausunnon esitti hypoteesin muodossa vuonna 1937 unkarilainen matemaatikko Andrew Vazonyi.ja Joseph Kruskal todisti sen itsenäisesti vuonna 1960ja S. Tarkovski [6] [7] .
Suuntaamattoman graafin G molli on mikä tahansa graafi, joka voidaan saada G :stä (mahdollisesti tyhjällä) reunan supistumissekvenssillä ja G:n reunojen ja kärkien poistamisella . Vähemmistörelaatio muodostaa osittaisjärjestyksen kaikkien erillisten äärellisten suuntaamattomien graafien joukossa, koska tämä relaatio täyttää kolme osittaisen järjestyksen aksioomaa — relaatio on refleksiivinen (jokainen graafi on itsensä molli), transitiivinen (graafin G molli on itse graafin G molli ) ja antisymmetrinen (jos kaksi graafia G ja H ovat toistensa molliarvoja, niiden on oltava isomorfisia ). Jos graafit ovat kuitenkin isomorfisia, niitä voidaan silti pitää eri objekteina, silloin alaikäisten järjestys muodostaa ennakkojärjestyksen , suhteen, joka on refleksiivinen ja transitiivinen, mutta ei välttämättä antisymmetrinen [1] .
Ennakkotilauksen sanotaan muodostavan täysin näennäisesti järjestetyn suhteen, jos se ei sisällä kumpaakaan äärettömästi pienenevää ketjua, eikä ääretöntä antiketjua [8] . Esimerkiksi tavallinen ei-negatiivisten kokonaislukujen suhde on täysin kvasijärjestetty, mutta sama järjestys kaikkien kokonaislukujen joukossa ei ole sellainen, koska se sisältää äärettömän laskevan ketjun 0, −1, −2, −3…
Robertson-Seymour-lause sanoo, että äärelliset suuntaamattomat graafit ja graafin molliarvot (relaationa) ovat täysin kvasijärjestettyinä. Ilmeisesti vähemmistörelaatio ei sisällä mitään ääretöntä laskevaa ketjua, koska mikä tahansa supistuminen tai poistaminen vähentää graafin reunojen tai kärkien määrää (ei-negatiiviset kokonaisluvut) [9] . Lauseen ei-triviaali osa on, että ei ole olemassa äärettömiä antiketjuja, eli äärettömiä graafien joukkoja, jotka eivät liity toisiinsa vähemmistösuhteen kautta. Jos S on graafien joukko ja M on S :n osajoukko, joka sisältää yhden edustavan graafin kullekin minimialkioiden ekvivalenssiluokalle (graafit, jotka kuuluvat S :ään, mutta mikään niistä ei kuulu S :ään ), M muodostaa antiketjun. Siten lauseen ekvivalentti väite on, että missä tahansa äärettömässä graafien joukossa S saa olla vain äärellinen määrä ei-isomorfisia minimielementtejä.
Lauseen toinen vastaava muotoilu sanoo, että missä tahansa äärettömässä graafien joukossa S täytyy olla graafipari, joista toinen on toisesta sivuarvo [9] . Väite, että missä tahansa äärettömässä joukossa on äärellinen määrä minimielementtejä, tarkoittaa tätä viimeistä lausetta, koska kaikki muut (ei-minimaaliset) graafit muodostavat tällaisen parin. Toisessa suunnassa tästä lauseen muotoilusta seuraa, että äärettömiä antiketjuja ei voi olla, koska ääretön antiketju ei sisällä vähemmistösuhteen yhdistämiä elementtejä.
Graafiperheen F sanotaan olevan suljettu mollin ottamisen operaatiossa, jos jokin F:n graafin molli kuuluu myös F :ään . Jos F on pieni-suljettu perhe, niin olkoon S niiden graafien joukko, jotka eivät kuulu F :hen ( joukon F komplementti ). Robertson-Seymour-lauseen mukaan S :ssä on äärellinen joukko H minimialkuaineita . Nämä minimielementit muodostavat joukon F kielletyn graafisen karakterisoinnin — graafit F :stä ovat juuri niitä graafia, joissa ei ole yhtään graafia H :stä sivuaineena [10] [11] . Joukon H jäseniä kutsutaan perheelle F kelpaamattomiksi alaikäisiksi (tai kiellettyiksi alaikäisiksi ) ja itse joukkoa H kutsutaan estäväksi joukoksi.
Esimerkiksi tasograafit suljetaan muodostamalla minor - tasograafin reunan supistaminen tai reunan tai kärjen poistaminen ei voi tuhota tasomaisuutta. Tasograafit ovat siis karakterisoivia kielletyillä alaväreillä, jotka tässä tapauksessa määritellään Wagnerin lauseella - vähäisten minimaalisten epätasomaisten graafien joukko H sisältää täsmälleen kaksi graafia, täydellisen graafin K 5 ja täydellisen kaksiosaisen graafin K 3,3 . Tasograafit ovat juuri niitä kaavioita, joissa ei ole alkioita joukosta { K 5 , K 3,3 } sivuarvona.
Kiellettyjen alaikäisten karakterisointien olemassaolo kaikille vähäisesti suljetuille graafiperheille on Robertson-Seymourin lauseen ekvivalentti muotoilu. Oletetaan, että millä tahansa vähäisesti suljetulla perheellä F on äärellinen joukko H minimikiellettyjä alaikäisiä, ja olkoon S mikä tahansa ääretön joukko kaavioita. Määrittelemme F for S :n graafiperheeksi, jolla ei ole ala-arvoja S :ssä . Tällöin joukko F on molli suljettu ja sillä on äärellinen joukko H minimikielletyistä moleista. Olkoon C F: n komplementti . S on C :n osajoukko, koska S ja F eivät leikkaa toisiaan. Joukko H sisältää minimaaliset graafit C :stä . Ota kuvaaja G kohdasta H . G :llä ei voi olla kunnon alaikäisiä S :ssä, koska G on minimaalinen C :ssä . Samalla G : ssä täytyy olla molli S :ssä , koska muuten G olisi F :n alkio . Siten G on S : n alkio , mikä tarkoittaa, että H on S:n osajoukko ja kaikilla muilla S :n grafeilla on alajoukot graafijoukosta H , joten H on S :n minimialkioiden äärellinen joukko.
Toisaalta oletetaan, että millä tahansa kaaviojoukolla on äärellinen minimaalisten graafien osajoukko ja olkoon F vähäinen suljettu joukko . Haluamme löytää joukon H graafisia, jotka sisältävät graafin F , jos ja vain, jos siinä ei ole sivumerkkejä H :ssä . Olkoon E niiden graafien joukko, jotka eivät ole minkään F :n graafin sivuja , ja olkoon H äärellinen joukko E :n minimielementtejä . Olkoon nyt mielivaltainen graafi G . Kuuluuko G ryhmään F . G :llä ei voi olla alaikäisiä H :stä, koska G kuuluu F :ään ja H on E :n osajoukko . G ei nyt kuulu F :ään . Tällöin G ei ole minkään F :n graafin molli, koska F on molliarvoissa suljettu. G kuuluu siis E :hen , joten G :llä on molli H :ssa.
Seuraavat äärellisten graafien joukot ovat suljettuja molleissa, ja siksi (Robertson-Seymour-lauseen mukaan) niillä on karakterisointi kiellettyjen graafien avulla:
Joitakin esimerkkejä äärellisistä obstruktiivisista joukoista tunnettiin joillekin luokille jo ennen Robertson-Seymour-lauseen todistetta. Esimerkiksi kaikkien metsien este on silmukka (tai jos rajoitamme yksinkertaisiin kaavioihin , sykli, jossa on kolme kärkeä). Tämä tarkoittaa, että graafi on metsä silloin ja vain, jos yksikään sen ala-arvoista ei ole silmukka (tai sykli, jossa on vastaavasti kolme kärkeä). Ainoa este joukolle polkuja on puu, jossa on neljä kärkeä, joista yksi on aste 3. Näissä tapauksissa este koostuu yhdestä elementistä, mutta yleensä elementtejä voi olla useampia. Wagnerin lause sanoo, että graafi on tasomainen silloin ja vain, jos se ei sisällä K 5 :tä eikä K 3,3 :a mollina. Toisin sanoen joukko { K 5 , K 3,3 } on kaikkien tasograafien estejoukko, ja se on pienin estejoukko. Samanlainen lause sanoo, että K 4 ja K 2,3 ovat kiellettyjä alaikäisiä ulkotason graafien joukossa.
Vaikka Robertson-Seymour-lause laajentaa nämä tulokset mielivaltaisiin pienimuotoisiin suljettuihin graafiperheisiin, se ei korvaa näitä tuloksia, koska se ei kuvaile eksplisiittisesti minkään perheen estojoukkoa. Lause esimerkiksi osoittaa, että toroidigraafien joukolla on äärellinen estejoukko, mutta se ei anna sellaista joukkoa. Kiellettyjen alaikäisten täydellinen joukko toroidikaavioille on edelleen tuntematon ja sisältää vähintään 16 000 kuvaajaa [13] .
Robertson–Seymour-lauseella on tärkeä seuraus laskennallisen monimutkaisuuden teoriassa, koska Robertson ja Seymour osoittivat, että jokaiselle kiinteälle graafille G on olemassa polynomiaikaalgoritmi , jolla tarkistetaan, onko suuremmalla graafilla G molli. Tämän algoritmin ajoaika ilmaistaan kuutiopolynomilla suuremman graafin koossa (vaikka tässä polynomissa on vakiotekijä, joka riippuu superpolynomiaalisesti G :n koosta ), ja Kawarabayashi paransi tämän ajan neliömäiseksi. , Kobayashi ja Reid [14] . Siten jokaiselle alaikäisissä suljetulle perheelle F on olemassa algoritmi polynomisella käyntiajalla, joka tarkistaa, kuuluuko graafi perheeseen F — vain kaikille F :n kielletyille alaikäisille tarkastetaan, sisältääkö annettu graafi tämän kielletyn alaikäisen [15] [16] [17 ] .
Kuitenkin, jotta tämä menetelmä toimisi, tarvitaan estävä äärellinen joukko, jota lause ei anna. Lause osoittaa, että tällainen joukko on olemassa, ja jos sellainen joukko tunnetaan, ongelmasta tulee polynomi. Käytännössä algoritmia voidaan soveltaa vain, kun meillä on estojoukko. Tämän seurauksena lause osoittaa, että ongelma voidaan ratkaista polynomiajassa, mutta se ei tarjoa erityistä polynomiaikaalgoritmia. Tällainen polynomialismin todiste on ei-konstruktiivinen [18] [19] . Monissa erityistapauksissa voidaan tehokkaammin tarkistaa, että kaavio kuuluu tiettyyn alaikäisten suljettuun perheeseen. Esimerkiksi graafin tasoisuus voidaan tarkistaa lineaarisessa ajassa.
Samaa menetelmää voidaan soveltaa graafin invarianteihin , joilla on ominaisuus, että mille tahansa k :lle graafiperhe, jonka invariantti ei ylitä k :tä, on vähäinen suljettu. Esimerkiksi tämän tuloksen mukaan puunleveys, haaranleveys, polunleveys, kärjen peitto ja vähimmäispesävyyssuku sopivat tähän lähestymistapaan, ja mille tahansa kiinteälle k :lle on olemassa polynomiaikaalgoritmi, joka tarkistaa, ettei tietty invariantti ylitä k , ja eksponentti algoritmin ajoajassa ei riipu k :stä. Tehtäviä, jotka koskevat minkä tahansa kiinteän k :n polynomin ratkaisuaikaa ja k :stä riippumatonta eksponenttia käyntiajassa , tunnetaan kiinteiden parametrien ratkaistaviksi ongelmiksi..
Tämä menetelmä ei kuitenkaan tarjoa suoraan kiinteä-parametrisesti päätettävissä olevaa algoritmia parametrin arvon laskemiseksi tietylle graafille, jonka k :lla on tuntematon , johtuen kiellettyjen alaikäisten joukon löytämisen vaikeuksista. Lisäksi tuloksena olevat valtavat vakiotekijät tekevät algoritmista vähän hyötyä käytännössä. Siten eksplisiittisten kiinteiden parametrien ratkaistavien algoritmien kehittäminen näille ongelmille, joilla on parannettu riippuvuus k :stä, on edelleen tärkeä tutkimuslinja.
Friedman, Robertson ja Seymour [20] ovat osoittaneet, että seuraava lause osoittaa riippumattomuusilmiön , koska se on todistamaton useissa muodollisissa järjestelmissä, jotka ovat vahvempia kuin Peanon aritmetiikka , mutta se on todistettavissa järjestelmissä, jotka ovat huomattavasti heikompia kuin Zermelo-Fraenkelin joukkoteoria :
Lause : Jokaiselle positiiviselle kokonaisluvulle n on sellainen kokonaisluku m , että jos G 1 , …, G m on äärellisten suuntaamattomien graafien sarja, jossa kunkin graafin G i koko on enintään n + i , niin G j ≤ G k jollekin j < k .(Tässä graafin koko on sen kärkien kokonaismäärä ja ≤ tarkoittaa alaikäisten järjestystä. )