Laske alaikäinen

Graafiteorian sivuaine on  tietyn graafin graafi , joka voidaan muodostaa poistamalla reunoja ja pisteitä sekä supistamalla reunoja .

Graafin molliteoria alkoi Wagnerin lauseella , jonka mukaan graafi on tasomainen silloin ja vain, jos sen sivumerkit eivät kuulu täydelliseen graafiin K 5 tai täydelliseen kaksiosaiseen graafiin K 3,3 [1] [2] . Robertson-Seymourin teoreemasta seuraa, että kielletyn vähämerkityksisen karakterisoinnin analogeja on olemassa mille tahansa graafien ominaisuudelle, joka säilyy reunan poiston ja supistumisen aikana [3] [4] .

Minkä tahansa graafin H kohdalla voidaan tarkistaa, onko H tulograafin G alari polynomiajassa [5] . Yhdessä kiellettyjen alaikäisten luonnehdinnan kanssa tästä seuraa, että mikä tahansa graafin ominaisuus, joka säilyy poistojen ja supistojen alla, voidaan tunnistaa polynomiajassa [6] .

Muita graafimooreja käyttäviä tuloksia ja olettamuksia ovat muun muassa graafin rakennelause , jonka mukaan graafit, jotka eivät sisällä H :tä mollina, voidaan muodostaa liimaamalla yhteen yksinkertaisempia osia, sekä Hadwiger-oletus , joka yhdistää graafin värityksen mahdottomuuden olemassaoloon. suuren täydellisen kaavion sivuaineenaan. Tärkeitä muunnelmia graafista molliarvoista ovat topologiset mollit ja upotetut mollit.

Määritelmät

Reunan supistuminen on toimenpide, joka poistaa graafista reunan ja yhdistää reunan päät yhdeksi kärjeksi. Suuntaamaton graafi H on toisen suuntaamattoman graafin G molli, jos H :n kanssa isomorfinen graafi voidaan saada G :stä supistamalla reunoja, poistamalla joitain reunoja ja poistamalla joitain eristettyjä huippuja. Järjestys, jossa supistukset ja poistot tehdään G :ssä , ei vaikuta tuloksena olevaan kuvaajaan H .

Graafi-molleja tutkitaan usein yleisemmässä matroid -mollissa . Tässä yhteydessä oletetaan yleensä, että graafit ovat yhteydessä toisiinsa, niillä voi olla silmukoita ja useita reunoja (eli katsotaan monigraafit , ei yksinkertaiset graafit). Silmukan vetäminen ja leikkuureunan poistaminen on kielletty. Tällä lähestymistavalla reunan poistaminen jättää graafin arvon ennalleen, kun taas reunan supistaminen vähentää aina arvoa yhdellä.

Muissa yhteyksissä (kuten esimerkiksi pseudometsien tutkimuksessa ) on järkevää sallia leikkaavien reunojen poistaminen ja graafien irrottaminen, mutta on myös järkevää kieltää monigraafit. Tässä graafisen alareunojen teorian versiossa graafia yksinkertaistetaan aina jokaisen reunan supistumisen jälkeen silmukoiden ja useiden reunojen eliminoimiseksi [7]

Esimerkki

Seuraavassa esimerkissä graafi H on graafin G molli :

H.

G.

Seuraava kuva havainnollistaa tätä. Ensin rakennetaan G :n aligraafi poistamalla katkoviivat (ja tuloksena oleva eristetty kärki) ja sitten supistamalla harmaa reuna (liittämällä kaksi kärkeä, jotka reuna yhdistää):

Tärkeimmät tulokset ja olettamukset

Voidaan helposti todentaa, että graafimollien relaatio muodostaa osittaisen järjestyksen suuntaamattomien graafien isomorfismiluokassa - relaatio on transitiivinen (graafin G molli on itse G:n molli ) ja graafit G ja H voivat olla toistensa molliarvoja, jos ne ovat isomorfisia, koska mikä tahansa ei-triviaali operaatio mollin kanssa poistaa reunat tai kärjet. Neil Robertsonin ja Paul Seymourin syvällinen tulos toteaa, että tämä osittaisjärjestys on itse asiassa täysin näennäisjärjestetty  – äärettömän listan G 1 , G 2 ,… äärellisistä graafista on aina kaksi indeksit i < j , jolloin G i on graafin G j molli . Vastaava lauseke on, että missä tahansa graafijoukossa voi olla vain äärellinen määrä minimaalisia alkioita pienellä suhteella [8] . Tämä tulos todistaa oletuksen, joka tunnettiin tähän asti Wagnerin arveluna. Wagner arveli paljon aikaisemmin, mutta julkaisi sen vasta vuonna 1970 [9] .

Todistuksen aikana Seymour ja Robertson todistivat myös graafirakennelauseen , jossa he määrittelivät mille tahansa kiinteälle graafille H karkean rakenteen mille tahansa graafille, joka ei sisällä H :ta sivuarvona. Lauseen lause on pitkä ja mutkikas, mutta lyhyesti sanottuna lause sanoo, että tällaisella graafilla on oltava summan rakenne pienempien graafien klikkeihin nähden, jotka saadaan muuttamalla rajoitetun suvun pintoihin upotettuja graafia . Siten heidän teoriansa muodostaa perustavanlaatuisen yhteyden graafien molliarvojen ja graafien topologisten upotusten välille [10] [11] .

Jokaiselle graafille H yksinkertaisten H-minorivapaiden graafien on oltava harvat , mikä tarkoittaa, että reunojen määrä on pienempi kuin jokin vakio kertaa kärkien lukumäärä [12] . Tarkemmin sanottuna, jos H :lla on h kärkiä, niin yksinkertaisella n -pisteen H -sivuvapaalla graafilla voi olla korkeintaan reunoja, ja joissakin K h -vähäisvapaissa grafeissa on vähintään tämä määrä kulmia [13] . Siten, jos H :lla on h kärkeä , niin H -vähäisvapailla graafeilla on keskimääräinen aste ja lisäksi degeneraatio . Lisäksi H -minorivapailla graafeilla on tasograafin osiointilauseen kaltainen osiointilause - mille tahansa kiinteälle H :lle ja mille tahansa n -pisteelle H - minorivapaalle graafille G , löytyy osajoukko kooltaan pisteistä poisto jakaa graafin G kahteen (mahdollisesti irti) aligraafiin, joissa kummassakin on korkeintaan 2 n /3 kärkeä [14] . Vielä tiukemmin, minkä tahansa kiinteän H , H -minor- vapaan graafin puun leveys on [15] .

Hadwigerin arvelussa oletetaan, että jos graafi G ei sisällä vähäistä isomorfista täydellistä graafia , jossa on k pistettä , niin graafilla G on säännöllinen väritys k  − 1 värissä [16] . Tapaus k  = 5 on neljän värin ongelman uudelleenmuotoilu . Hadwigerin olettamus on todistettu arvolle k  ≤ 6 [17] , mutta ei yleisesti. Bolobas, Katlin ja Erdős [18] kutsuivat ongelmaa "yhdeksi graafiteorian syvimmistä ratkaisemattomista ongelmista". Toinen tulos, joka liittyy neljän värin teoreemaan kuvaamaan alavärejä, on snark-lause , jonka ilmoittivat Robertson, Sanders, Seymour ja Thomas [19] . Lause on neljän värin teoreeman vahvistus ja sen esitti (oletuksena) Tutt ja se väittää, että minkä tahansa 3-säännöllisen siltaattoman graafin , joka vaatii neljän värin värjäykseen, täytyy sisältää Petersenin graafi sivuaineena [20 ] [21] .

Alaikäisille suljettujen kaavioiden perheet

Monilla graafiperheillä on ominaisuus, että mikä tahansa graafin sivuarvo F :ssä on myös F :ssä . Tässä tapauksessa graafien luokan sanotaan olevan vähäinen suljettu . Esimerkiksi missä tahansa tasokuvaajassa tai graafin upotuksessa kiinteään topologiseen pintaan , reunojen poistaminen tai reunojen supistuminen ei voi lisätä upotuksen määrää. Siten tasokuvaajat ja mihin tahansa kiinteään pintaan upotettavat kuvaajat muodostavat vähän suljettuja perheitä.

Jos F on vähäsuljettu perhe, niin (johtuen alaikäisten täydellisen kvasijärjestyksen ominaisuudesta) F :een kuulumattomien graafien joukossa on äärellinen joukko X vähäisemmät minimaaliset graafit. Nämä kaaviot ovat kiellettyjä alavärejä F :lle  — graafi kuuluu F :lle silloin ja vain, jos se ei sisällä yhtään graafia X :stä alaikäisinä . Siten mikä tahansa mollisuljettu perhe F voidaan luonnehtia mollivapaiden graafien perheeksi X :stä jollekin kiellettyjen alaikäisten äärelliselle joukolle X [3] [4] .

Tunnettu esimerkki tämäntyyppisestä karakterisoinnista on Wagnerin lause , joka luonnehtii tasograafit graafeiksi, joissa ei ole K 5 eikä K 3,3 sivuarvoina [1] [2] .

Joissakin tapauksissa vähäisesti suljetun perheen graafien ominaisuudet voivat olla läheisesti sukua poissuljettujen alaikäisten ominaisuuksiin. Esimerkiksi pienellä suljetulla graafiperheellä F on rajattu polku silloin ja vain, jos suvun kiellettyyn perheeseen kuuluu metsä [22] , F :llä on rajoitettu puun syvyys , jos ja vain, jos kielletyt alaikäiset sisältävät irrotetun polkuliiton , F :llä on rajoitettu puun leveys silloin ja vain, jos sen kielletyt sivumerkit sisältävät tasograafin [23] ja F :llä on rajoitettu paikallinen puunleveys ( halkaisijan ja puun leveyden välinen funktionaalinen suhde ) silloin ja vain, jos sen kielletyt alamerkit sisältävät huippugraafin ( a graafi, joka tulee tasomaiseksi, kun yksi kärkipiste) [24] [25] . Jos H voidaan piirtää tasolle yhdellä leikkauspisteellä (eli graafin leikkauspisteiden lukumäärä on yksi), niin H -minorista vapaille kuvaajille pätee yksinkertaistettu rakennelause, jonka mukaan tällaiset graafit ovat tasograafien ja rajatun puuleveyden omaavien graafien klikkaussumma [26] [27] . Esimerkiksi sekä K 5 :n että K 3,3 :n leikkausnumero on yksi, ja kuten Wagner osoitti, K 5 :stä vapaat graafit ovat täsmälleen tasograafien ja kahdeksan kärjen Wagner-graafin 3-klikin summat , kun taas vapaat graafista K 3,3 -graafit ovat täsmälleen tasograafien ja K 5 :n 2-klikin summat [28] .

Muunnelmia

Topologiset alaikäiset

Graafia H kutsutaan graafin G topologiseksi sivuksi , jos H :n osagraafi on isomorfinen G : n aligraafin kanssa [29] . On helppo nähdä, että mikä tahansa topologinen molli on molli (tavallisessa merkityksessä). Päinvastoin ei kuitenkaan yleensä pidä paikkaansa (esimerkiksi Petersen-graafin koko graafi K 5 on molli, mutta ei ole topologinen molli), mutta pätee graafille, jonka maksimiaste on enintään kolme [30] .

Topologisten molliarvojen relaatio ei ole täysin kvasijärjestetty äärellisten graafien joukossa [31] , joten Robertsonin ja Seymourin tulos ei sovellu topologisiin molliarvoihin. On kuitenkin helppo konstruoida rajallisten kiellettyjen topologisten alaikäisten karakterisoinnit rajallisten kiellettyjen alaikäisten karakterisoinnista.

Upotettu alaikäinen

Kuvaajaoperaatio, jota kutsutaan nostoksi , on keskeinen käsite immersion käsitteessä . Nosto on toimenpide vierekkäisillä reunoilla. Kun on annettu kolme kärkeä v , u ja w , joissa (v, u) ja (u, w)  ovat graafin reunoja, nostaa vuw , tai vastaavasti (v, u), (u, w)  on operaatio, joka poistaa kaksi reunaa (v , u) ja (u, w) ja lisää reunan (v, w) . Siinä tapauksessa, että reuna (v, w) on jo olemassa, v ja w yhdistetään toisella reunalla, joten operaatio on olennaisesti monigrafioperaatio.

Tapauksessa, jossa graafi H saadaan graafista G nostooperaatioiden sarjalla ( G :n yli ) ja sitten isomorfisen aligraafin löytämisellä, sanotaan, että H on graafin G upotettu molli .

On olemassa toinen tapa määritellä upotetut alaikäiset, joka vastaa nostotoimintoa. Sanomme, että H on graafin G upotettu molli, jos on olemassa injektiivinen mappaus H :n pisteistä G :n kärkiin siten, että H :n vierekkäisten elementtien kuvat on yhdistetty G :ssä poluilla, joilla ei ole yhteisiä reunoja.

Upotettujen alaikäisten suhde on täysin kvasijärjestetty äärellisten graafien joukossa, ja siksi Roebrtsonin ja Seymourin tuloksia voidaan soveltaa upotettuihin alaikäisiin. Lisäksi tämä tarkoittaa, että jokaiselle perheelle, joka on suljettu alaikäisiin, on ominaista rajallinen kiellettyjen alaikäisten perhe.

Graafisten visualisoinnissa upotetut alamerkit näkyvät ei-tasomaisten graafien planarisoinneina  – graafin piirroksesta tasolle, jossa on leikkauspisteitä, voidaan muodostaa upotettu molli korvaamalla jokainen leikkauspiste uudella kärjellä ja jakamalla jokainen ylitetty reuna. polulle. Tämä mahdollistaa tasograafien piirustusmenetelmien laajentamisen ei-tasomaisille kuvaajille [32] .

Matalat alaikäiset

Graafin G matala molli on molli, jossa graafin G  reunat, jotka on tiivistetty molliin saamiseksi, muodostavat halkaisijaltaan pieniä disjunktoituja aligraafia . Matala-molli muodostaa eräänlaisen sillan graafisen mollien ja aligraafien välillä siinä mielessä, että syvät matalat molaarit ovat samoja kuin tavalliset mollityypit, kun taas nollasyvyydet matalat alagraafit ovat täsmälleen aligraafia [33] . Ne mahdollistavat myös graafisen alaikäisten teorian laajentamisen graafiluokkiin, kuten 1-tasokaavioihin , joita ei ole suljettu alaikäisten ottamisessa [34] .

Algoritmit

Ratkaisevuusongelma siitä , sisältyykö graafi H graafiin G sivuaineena, on yleensä NP-täydellinen. Esimerkiksi, jos H on sykli , jossa on sama määrä pisteitä kuin G , niin H on G :n molli silloin ja vain jos G sisältää Hamiltonin graafin . Kuitenkin, jos G on syöte ja H on kiinteä, ongelma voidaan ratkaista polynomiajassa. Tarkemmin sanottuna ajoaika tarkastettaessa, onko H G :n molli tässä tapauksessa on O ( n 3 ), missä n  on G :n kärkien lukumäärä ja O iso piilottaa vakion, joka riippuu supereksponentiaalisesti H :sta [5] . Johtuen tuloksesta graafin sivuilla, tämä algoritmi paranee O ( n 2 ) [35] . Siten, kun käytetään polynomiaikaista algoritmia tarkistamaan, sisältääkö tietty graafi kiellettyjä alaikäisiä, on mahdollista tunnistaa minkä tahansa alaikäisen suljetun perheen jäsenet polynomiajassa . Kuitenkin, jotta tätä tulosta voidaan soveltaa rakentavasti, on tiedettävä graafiperheen kielletyt alaikäiset [6] .

Muistiinpanot

  1. ↑ 12. Lovász , 2006 , s. 77.
  2. ↑ 12 Wagner, 1937a .
  3. ↑ 1 2 Lovász, 2006 , Vol. 4, s. 78.
  4. ↑ 12 Robertson , Seymour, 2004 .
  5. ↑ 12 Robertson , Seymour, 1995 .
  6. ↑ 12 Fellows , Langston, 1988 .
  7. ↑ Lovász (2006 ) on ristiriidassa itsensä kanssa. Sivulla 76 hän kirjoittaa, että "rinnakkaiset reunat ja silmukat ovat sallittuja", mutta sivulla 77 hän toteaa, että "graafi on metsä silloin ja vain, jos se ei sisällä kolmiota K 3 sivuarvona", mikä pätee vain yksinkertaisille. kaavioita.
  8. ↑ Diestel (2005 ), luku 12: Alaikäiset, puut ja WQO; Robertson, Seymour (2004 ).
  9. ↑ Lovász, 2006 , s. 76.
  10. ↑ Lovász, 2006 , s. 80-82.
  11. ↑ Robertson, Seymour, 2003 .
  12. ↑ Mader, 1967 .
  13. ↑ Kostochka, 1984 ; Thomason, 1984 ; Thomason, 2001 .
  14. ↑ Alon, Seymour, Thomas, 1990 ; Plotkin, Rao, Smith, 1994 ; Reed, puu, 2009 .
  15. ↑ Grohe, 2003 .
  16. ↑ Hadwiger, 1943 .
  17. ↑ Robertson, Seymour, Thomas, 1993 .
  18. ↑ Bollobás, Catlin, Erdős, 1980 .
  19. ↑ Vuodesta 2012 lähtien todistetta ei kuitenkaan ole vielä julkaistu.
  20. ↑ Thomas, 1999 .
  21. ↑ Pegg, 2002 .
  22. ↑ Robertson, Seymour, 1983 .
  23. ↑ Lovász (2006 ), Lause 9, s. 81; Robertson, Seymour (1986 ).
  24. ↑ Eppstein, 2000 .
  25. ↑ Demaine, Hajiaghayi, 2004 .
  26. ↑ Robertson, Seymour, 1993 .
  27. ↑ Demaine, Hajiaghayi, Thilikos, 2002 .
  28. ↑ Wagner, 1937a ; Hall, 1943 .
  29. ↑ Diestel, 2005 , s. kaksikymmentä.
  30. ↑ Diestel, 2005 , s. 22.
  31. ↑ Ding, 1996 .
  32. ↑ Buchheim, Chimani, Gutwenger, Jünger, Mutzel, 2014 .
  33. ↑ Nešetřil, de Mendez, 2012 .
  34. ↑ Nešetřil, de Mendez, 2012 , s. 319-321.
  35. ↑ Kawarabayashi, Kobayashi, Reed, 2012 .

Kirjallisuus

Linkit