Apex Count

Graafiteoriassa kärkigraafi on graafi , joka voidaan tehdä tasomaiseksi poistamalla yksi kärki. Poistettua kärkeä kutsutaan graafin huipuksi. Huomaa, että kärkeä voi olla useampi kuin yksi. Esimerkiksi minimaalisessa epätasomaisessa graafissa K 5 tai K 3,3 kukin kärki on kärkipiste. Huippugraafit sisältävät aluksi tasomaisia ​​graafisia kaavioita, joissa jokainen kärki on kärkipiste. Nollagraafia pidetään myös apikaalisena, vaikka sillä ei ole poistettavaa kärkeä.

Apex-graafit suljetaan alaikäisten luomisen yhteydessä ja niillä on suuri rooli useissa muissa graafisen molliteorian näkökohdissa, mukaan lukien linkittämätön upottaminen [1] , Hadwiger- oletus [2] , YΔY-pelkistyvät graafit [3] ja puun leveys ja kuvaajan halkaisija [4] [5] .

Kuvaus ja tunnustus

Huippugraafit suljetaan alareunojen luomisen yhteydessä - minkä tahansa reunan pienentäminen tai kärjen tai reunan poistaminen johtaa toiseen huippugraafiin. Todellakin, jos G on kärkigraafi, jossa on kärki v , niin supistuminen tai poisto, joka ei vaikuta kärkeen v , säilyttää muun graafin tasomaisuuden (ilman kärkeä v ). sama pätee, kun poistetaan kaikki v :n kanssa sattuvat reunat . Jos v :n kanssa kohtaava reuna supistuu , vaikutus on sama kuin reunan vastakkaisen pään poistaminen. Jos itse kärki v poistetaan , mitä tahansa muuta kärkeä voidaan pitää kärjenä [6] .

Koska kärkigraafit suljetaan generoimalla ala-arvoja, niille on Robertson-Seymourin lauseen mukaan karakterisointi kiellettyjen graafien avulla . On vain rajallinen määrä kaavioita, jotka eivät ole huippukaavioita ja jotka eivät sisällä toista ei-huippugraafia. Nämä graafit ovat kiellettyjä ala -arvoja vertex graph -ominaisuudelle. Mikä tahansa muu graafi G on huippu, jos ja vain jos yksikään kielletyistä alaikäisistä ei ole G :n molli . Kiellettyihin alaikäisiin kuuluvat seitsemän Petersen-perheen graafia, kolme irrotettua graafia, jotka on muodostettu K 5 :n ja K 3,3 :n hajautuneista liitoista , sekä monia muita graafisia kaavioita. Täydellinen luettelo kaikista kielletyistä alaikäisistä on edelleen epätäydellinen [6] [7] .

Huolimatta siitä, että täydellistä listaa kielletyistä alaikäisistä ei tunneta, voidaan lineaarisessa ajassa tarkistaa, onko tietty graafi huippukohta, ja jos on, löytää kaavion huippu. Yleisemmin millä tahansa kiinteällä vakiolla k , k -kärkisten graafit (kuvaajat, joissa huolellisesti valitun enintään k kärkeä sisältävän joukon poistaminen johtaa tasograafiin [8] ) voidaan tunnistaa lineaarisessa ajassa . Jos k : ta ei kuitenkaan korjata, ongelmasta tulee NP-täydellinen [9] .

Kromaattinen numero

Minkä tahansa kärkigraafin kromaattinen luku ei ylitä viittä - tasograafi ilman kärkeä vaatii enintään neljä väriä neljän värin lauseen mukaan ja yksi lisäväri riittää kärkeen. Robertson, Seymour ja Thomas [2] käyttivät tätä tosiasiaa todistaakseen Hadwigerin olettamuksen k  = 6 tapauksen , väitteen, jonka mukaan missä tahansa 6-kromaattisessa graafissa on täydellinen graafi K 6 sivuarvona – he osoittivat, että mikä tahansa minimaalinen vastaesimerkki Oletuksen täytyy olla huippugraafi, mutta 6-pisteen kromaattisia graafia ei ole, joten sellaista vastaesimerkkiä ei ole.

Ratkaisemattomat matematiikan ongelmat : Onko jokainen 6-pisteeseen yhdistetty graafi ilman ala- arvoja?

Jorgensen [10] arveli, että minkä tahansa kärkeen 6 kytketyn graafin, jossa ei ole K 6 :ta sivuarvona, on oltava huippu. Jos tämä todistettaisiin, Robertson-Seymour-Thomas-tulos Hadwiger-oletuksella olisi suora seuraus [2] . Jorgensenin olettamusta ei ole vielä todistettu [11] . Jos olettamus on kuitenkin epätosi, sillä on vain äärellinen määrä vastaesimerkkejä [12] .

Paikallinen puunleveys

Kuvaajaperheellä F on rajoitettu paikallinen puunleveys, jos F :n graafit noudattavat funktionaalista suhdetta halkaisijan ja puunleveyden välillä — on olemassa funktio ƒ, jonka mukaan F :n graafin, jonka halkaisija on d , puunleveys ei ylitä ƒ( d ). Huippukaavioilla ei ole rajoitettua paikallista puunleveyttä – graafilla, joka muodostetaan yhdistämällä piste jokaiseen n  ×  n hilan kärkeen, on puun leveys n ja halkaisija 2, joten puun leveyttä ei rajoita jokin näiden graafien halkaisijan funktio. . Huippugraafit liittyvät kuitenkin läheisesti graafisiin, joilla on rajoitettu paikallinen puunleveys – paikallista puunleveyttä rajoittavien graafien F pienet suljetut perheet ovat täsmälleen perheitä, joiden kiellettyjä sivuja ovat jokin huippugraafi [4] [5] . Graafisten sivuperheiden, joiden sivuarvona on huippugraafi, tiedetään olevan apex-mollivapaita . Tämän terminologian mukaan kärkigraafien ja paikallisen puunleveyden välinen suhde voidaan muotoilla uudelleen seuraavasti: graafiperheet, joissa ei ole vertex-molleja, ovat samat kuin molleihin suljetut graafiperheet, joilla on rajoitettu paikallinen puunleveys.

Rajatun paikallisen puunleveyden käsite muodostaa perustan kaksiulotteisuuden teorialle ja mahdollistaa monien algoritmisten ongelmien ratkaisemisen graafisissa kaavioissa, joissa ei ole ylimmäisiä molliarvoja täsmälleen polynomiaikaisella algoritmilla tai kiinteän parametrin ratkaistavalla algoritmilla , tai ongelma voidaan approksimoida käyttämällä likimääräistä kaaviopolynomiaikaa [4] [13] [14] . Graafiperheille, joissa ei ole apikaalisia molliarvoja, rakenteellisen graafin lauseen vahvistettu versio täyttyy , mikä johtaa ylimääräisiin approksimaatioalgoritmeihin graafin värjäykseen ja liikkuvan myyjän ongelmaan [15] . Jotkut näistä tuloksista voidaan kuitenkin laajentaa mielivaltaisiin vähämerkityksisiin suljetuihin graafiperheisiin käyttämällä rakennelauseita graafiin, jotka liittyvät perheisiin, joissa ei ole kärkeen molliarvoja [16] .

Liitteet

Jos graafi G on huippugraafi, jossa on huippu v ja se on yhtä suuri kuin pintojen vähimmäismäärä, joka tarvitaan peittämään kaikki kärjen v naapurit tasomaisen upotuksen G \{ v } alla, niin G voidaan upottaa kaksiulotteiseen suvun pintaan lisäämällä monia siltoja tasomaiseen upotukseen yhdistämällä näin kaikki pinnat, joihin v on liitettävä. Esimerkiksi yhden kärjen lisääminen ulkotason graafiin (kuvaaja, jossa on ) tuottaa tasograafin. Jos graafi G \{ v } on 3-kytketty, sen raja ei poikkea optimaalisesta enempää kuin vakiokertoimella — G :n upottaminen pintaan vaatii vähintään suvun . Kuitenkin ongelma optimaalisen suvun määrittämisessä upotuspinnalle kärkigraafia varten on NP-kova ongelma [17] .

Käytettäessä SPQR -puita koodaamaan huippugraafin tasomaisen osan mahdollisia upotuksia, on mahdollista laskea polynomiajassa graafin upotus tasolle, jossa leikkauspisteet aiheuttavat vain kärjen kärjestä lähtevät reunat, ja kokonaissumma risteysten määrä on minimaalinen [18] . Jos mielivaltaiset leikkauspisteet sallitaan, leikkauspisteiden määrän minimointiongelmasta tulee NP-kova, jopa siinä erikoistapauksessa, jossa huippugraafit muodostetaan lisäämällä yksi reuna tasograafiin [19] .

Vertex- graafit ovat upotettavissa ilman linkittämistä kolmiulotteiseen avaruuteen - ne voidaan upottaa siten, että mikä tahansa kaavion sykli on levyn raja, jota mikään muu graafin osa ei leikkaa [20] . Tämän tyyppinen piirros saadaan piirtämällä kaavion tasomainen osa tasolle, asettamalla kuvaajan yläosa tason yläpuolelle ja yhdistämällä se naapuriinsa segmenteillä. Linkkittömät upotettavat graafit muodostavat alaikäisen suljetun perheen, jossa on seitsemän Petersenin suvun graafia minimaalisina kiellettyinä alaikäisinä [1] . Siten nämä graafit ovat kiellettyjä sivuja myös kärkigrafioissa. On kuitenkin kaavioita, jotka voidaan upottaa ilman linkkiä eivätkä ole huippuja.

YΔY-reducibility

Yhdistetty graafi on YΔY-pelkistävä, jos se voidaan pelkistää yhdeksi pisteeksi vaiheiden sarjalla, joista jokainen on Δ-Y tai Y-Δ muunnos , joka poistaa silmukan tai useita reunoja, poistaa kärjen yhden naapurin kanssa, ja korvataan toisen asteen kärki ja sen kaksi vierekkäistä reunaa yhdellä reunalla [3] .

Kuten kärkikuvaajat ja upotettavat graafit ilman linkkejä, YΔY-pelkistettävät graafit suljetaan alaikäisten luomisen yhteydessä. Kuten upotettavat graafit ilman linkittämistä, YΔY-pelistetyissä kaavioissa on seitsemän Petersen-perheen graafia vähimmäiskiellettyinä alaikäisinä, mikä herättää kysymyksen siitä, ovatko nämä graafit ainoita kiellettyjä alaikäisiä ja ovatko YΔY-pelistettävien ja ilman linkittämistä upotettavien graafien perheet samat. . Neil Robertson antoi kuitenkin esimerkin huippugraafista, joka ei ole YΔY-pelkistävä. Koska mikä tahansa kärkigrafiikka on upotettava ilman linkkiä, tämä osoittaa, että on olemassa upotettavat graafit ilman linkkiä, jotka eivät ole YΔY-pelkistäviä, ja siksi YΔY-pelkistävissä graafisissa on muita kiellettyjä alavärejä [3] .

Apex Robertson -graafi on esitetty kuvassa. Se voidaan saada yhdistämällä kärki kaikkiin kolmannen asteen rombisen dodekaedrin kärkiin tai yhdistämällä neliulotteisen hyperkuutiograafin kaksi vastakkaista kärkeä . Koska rombisen dodekaedrin kuvaaja on tasomainen, Robertsonin graafi on huippu. Kuvaaja ei sisällä kolmioita ja sen vähimmäisaste on neljä, joten siihen ei voida soveltaa YΔY-pelkistysoperaatiota [ 3] .

Melkein tasokaaviot

Jos graafi on huippu, sillä ei välttämättä ole yhtä huippua. Esimerkiksi minor-minimaalisissa ei-tasomaisissa graafisissa K 5 ja K 3,3 pisteissä voidaan valita mikä tahansa kärkipiste. Wagner [21] [22] määritteli lähes tasomaisen graafin ei-tasomaiseksi huippugraafiksi, jossa mikä tahansa kärki voi toimia huippuna. Siten K 5 ja K 3,3 ovat lähes tasomaisia ​​graafia. Hän antoi tällaisten kaavioiden luokituksen jakamalla ne neljään perheeseen. Yksi perhe koostuu graafeista, jotka (kuten Möbius-tikkaat ) voidaan upottaa Möbius-nauhaan siten, että nauhan reuna osuu yhteen graafin Hamiltonin syklin kanssa. Jo ennen neljän värin lauseen todistamista hän osoitti, että mikä tahansa lähes tasomainen graafi voidaan värjätä korkeintaan neljällä värillä, lukuun ottamatta kuvaajia, jotka on muodostettu pyörästä , jolla on pariton ulkoinen sykli korvaamalla keskipiste kahdella vierekkäisellä kärjellä - tällainen kaavio tarvitsee viisi väriä. Lisäksi hän osoitti, että yhtä poikkeusta ( kuution kahdeksan kärjen komplementtia ) lukuun ottamatta missä tahansa lähes tasomaisessa graafissa on upotus projektiivitasoon .

Ilmaus "melkein tasograafi" on kuitenkin erittäin moniselitteinen - samaa termiä on käytetty kärkigraafista [20] [4] , graafista, joka on muodostettu lisäämällä yksi reuna tasograafiin [23] , graafista, joka on muodostettu tasomaisesta upotuksesta kuvaajasta korvaamalla rajoitetun määrän kasvoja "pyörteitä", joiden polun leveys on rajoitettu [24] , sekä joitain muita vähemmän tiukasti määriteltyjä kaaviojoukkoja.

Muistiinpanot

  1. ↑ 12 Robertson, Seymour, Thomas, 1993b .
  2. ↑ 1 2 3 Robertson, Seymour, Thomas, 1993a .
  3. ↑ 1 2 3 4 Truemper, 1992 .
  4. ↑ 1 2 3 4 Eppstein, 2000 .
  5. ↑ 1 2 Demaine, Hajiaghayi, 2004 .
  6. ↑ 1 2 Gupta, Impagliazzo, 1991 .
  7. ↑ Pierce, 2014 .
  8. ↑ Kawarabayashi, 2009 .
  9. ↑ Lewis, Yanakakis, 1980 .
  10. ↑ Jørgensen, 1994 .
  11. ↑ Jorgensenin olettamus , < http://www.openproblemgarden.org/op/jorgensens_conjecture > . Haettu 13. marraskuuta 2016. Arkistoitu 14. marraskuuta 2016 Wayback Machinessa . 
  12. ↑ Kawarabayashi, Norine, Thomas, Wollan, 2012 .
  13. ↑ Frick, Grohe, 2001 .
  14. ↑ Demaine, Hajiaghayi, 2005 .
  15. ↑ Demaine, Hajiaghayi, Kawarabayashi, 2009 .
  16. ↑ Grohe, 2003 .
  17. ↑ Mohar, 2001 .
  18. ↑ Chimani, Gutwenger, Mutzel, Wolf, 2009 .
  19. ↑ Cabello, Mohar, 2010 .
  20. ↑ 12 Robertson, Seymour, Thomas, 1993c .
  21. ↑ Wagner, 1967 .
  22. ↑ Wagner, 1970 .
  23. ↑ Archdeacon, Bonnington, 2004 .
  24. ↑ Abraham, Gavoille, 2006 .

Kirjallisuus