Puun syvyys (kaavioteoria)

Graafiteoriassa yhdistetyn suuntaamattoman graafin G puun syvyys on G :n numeerinen invariantti, Tremaux-puun minimikorkeus G : n supergraafille . Tämä muuttumaton ja siihen liittyvät käsitteet esiintyvät kirjallisuudessa useilla nimillä, mukaan lukien kärkipisteiden järjestysnumero, järjestetyt kromaattiset numerot ja puun vähimmäiskorkeus. Käsite on myös lähellä sellaisia ​​käsitteitä kuin suunnattujen graafien syklinen arvo ja säännöllisten kielten kielen iteraatiokorkeus [1] [2] ; [3] . Intuitiivisesti, kun kaavion puun leveys mittaa kuinka kaukana kaavio on puusta, puun syvyys mittaa kuinka kaukana kuvaaja on tähdestä.

Määritelmät

Graafin G puun syvyys voidaan määritellä metsän F minimikorkeudeksi sillä ominaisuudella, että mikä tahansa G :n reuna yhdistää F :n ylä-lapsi-suhteella yhdistetyn kärkiparin [4] . Jos G on yhdistetty, tämän metsän on oltava yksi puu. Metsän ei tarvitse olla G : n osagraafi , mutta jos on, niin se on Tremaux-puu G :lle .

F :n vanhempi-lapsi-parien joukko muodostaa triviaalisen täydellisen graafin ja F :n korkeus on tämän graafin suurimman klikkin koko. Siten puun syvyys voidaan vaihtoehtoisesti määritellä G :n triviaalisen täydellisen supergraafin suurimman klikkin kooksi, joka on peilikuva puunleveydestä , joka on yksi pienempi kuin G :n jänne- supergraafin suurimman klikkin koko [ 5]

Toinen määritelmä on seuraava:

missä V on graafin G kärkijoukko ja ovat G:n yhdistetyt komponentit [ 6] . Tämä määritelmä heijastaa suunnattujen graafien syklistä järjestysmäärittelyä , jossa käytetään vahvaa liitettävyyttä ja vahvasti kytkettyjä komponentteja ohjaamattoman yhteyden ja yhdistettyjen komponenttien sijaan.

Puun syvyys voidaan määrittää kuvaajavärjäyksellä . Keskitetty graafin väritys on kärkiväri, jolla on ominaisuus, että missä tahansa yhdistetyssä luodussa aligraafissa on väri, joka esiintyy tasan kerran. Tällöin puun syvyys on värien vähimmäiskoko, joka tarvitaan graafin keskitettyyn väritykseen. Jos F on metsä, jonka korkeus on d ja jolla on ominaisuus, että mikä tahansa G :n reuna yhdistää esi-isän ja lapsen puussa, voidaan G :n keskitetty väritys saada d värillä värittämällä jokainen kärki värinumerolla, joka on yhtä suuri kuin etäisyys juuresta F :ssä [7 ] .

Lopuksi voidaan määritellä se pelimerkkipelinä . Tarkemmin sanottuna aivan kuten "poliisi-ryöstäjät" -peli . Kuvittele seuraava peli ohjaamattomalla kaaviolla. Pelaajia on kaksi, rosvo ja poliisi. Ryöstäjällä on yksi pala, jota hän liikuttaa kaavion reunoja pitkin. Poliisilla on rajaton määrä pelimerkkejä, mutta hän haluaa minimoida käytettyjen pelimerkkien määrän. Poliisi ei voi siirtää kuvaajalle asetettuja nappuloitaan. Peli menee näin. Ryöstäjä asettaa palansa, sitten poliisi kertoo mihin hän haluaa sijoittaa seuraavan palan ja rosvo voi sitten siirtää nappulansa reunoja pitkin, mutta ei miehitettyjen kärkien yli. Peli päättyy, kun poliisi asettaa seuraavan nappulan ryöstöpalan päälle. Tietyn kaavion puun syvyys määrittää taatun voiton saavuttamiseen vaadittavien merkkien vähimmäismäärän [8] [9] . Tähdille riittää kaksi merkkiä - aseta ensimmäinen merkki tähden keskelle pakottaen rosvon siirtymään johonkin säteeseen ja aseta sitten toinen merkki rosvon merkin päälle. Polulle , jossa on kärkipisteet, poliisi käyttää binaarihakustrategiaa , joka takaa, ettei enää käytetä tokeneita.

Esimerkkejä

Täydellisen graafin puun syvyys on yhtä suuri kuin sen kärkien lukumäärä, jolloin ainoa mahdollinen metsä F , jossa minkä tahansa pisteparin on oltava esi-lapsi-suhteessa, on yksi polku. Vastaavasti täydellisen kaksiosaisen graafin K x , y puun syvyys on min( x , y ) + 1, ja vaikka sijoitamme kärjet, metsän F lehdillä tulee olla vähintään min( x , y ) esivanhemmat F :ssä . Metsä, johon min( x , y ) + 1 saavutetaan, voidaan rakentaa muodostamalla polku graafin pienemmän osan pisteistä ja suuremman osan kärjet muodostavat puun F lehdet, jotka ovat yhteydessä alempaan. polun kärki.

Polkupuun, jossa on n kärkeä, syvyys on täsmälleen . Tätä polkua edustava metsä F tällä syvyydellä voidaan muodostaa sijoittamalla juuri polun F keskipisteeseen ja jatkamalla rekursiota kahdella pienemmällä polulla juuren kummallakin puolella [10] .

Puiden syvyys ja suhde puun leveyteen

Jokaisella metsällä , jossa on n kärkeä, on puun syvyys O(log  n ). Metsälle löytyy aina vakio määrä pisteitä, joiden poistamisesta saadaan metsä, joka voidaan jakaa kahteen pienempään osametsään, joissa kummassakin on enintään 2 n /3 kärkeä. Jakamalla nämä kaksi aluskasvillisuutta rekursiivisesti, puun syvyyden logaritminen yläraja voidaan saavuttaa helposti. Sama tekniikka, jota käytetään graafipuun hajotukseen , osoittaa, että jos n - pisteisen graafin G puun leveys on t , niin G :n puun syvyys on O( t  log  n ). [11] [12] Koska ulompien tasojen , rinnakkaisten peräkkäisten graafien ja Halinin graafien puun leveys on rajoitettu, niillä kaikilla on myös suurin logaritminen puun syvyys.

Toisessa suunnassa graafin puun leveys ei ylitä sen puun syvyyttä. Tarkemmin sanottuna puun leveys ei ylitä graafin polun leveyttä , joka on enintään yhden pienempi kuin sen puun syvyys [11] [13] .

Laske alaikäiset

Graafin G molli on toinen graafi, joka on muodostettu G :n osagraafista supistamalla joitain reunoja. Puun syvyys on molleissa monotoninen – minkä tahansa graafin G mollilla on puun syvyys, joka ei ylitä itse graafin G puun syvyys [14] . Siten Robertson-Seymour-lauseen mukaan mille tahansa kiinteälle d :lle graafien joukossa, jonka puun syvyys ei ylitä d :tä, on rajallinen määrä kiellettyjä alaikäisiä .

Jos C on mollimuodostelman alle suljettu graafien luokka, niin C :n graafilla on puun syvyys silloin ja vain, jos C ei sisällä kaikkia polkuja [15] .

Luodut osagraafit

Puun syvyydellä on läheinen yhteys graafin generoitujen osagraafien teoriaan . Graafeiden luokassa, joiden puun syvyys on enintään d (mikä tahansa kiinteä luonnollinen d ), ominaisuus olla generoitu aligraafi on hyvin kvasijärjestetty [16] . Pääajatuksena todistuksessa siitä, että tämä yhteys on täysin kvasijärjestetty, on käyttää induktiota d :ssä . Metsät, joiden korkeus on d , voidaan tulkita metsien sarjaksi, jonka korkeus on d  − 1 (joka muodostuu kaatumalla korkuisten d puiden juurelta ), ja Higmanin lemmaa voidaan käyttää osoittamaan, että nämä sekvenssit ovat hyvin kvasijärjestyneitä.

Hyvästä kvasijärjestyksestä seuraa, että millä tahansa graafin ominaisuudella, joka on monotoninen generoiduissa osagraafissa, on rajallinen määrä kiellettyjä generoituja aligrafioita, ja siksi ne voidaan tarkistaa polynomiajassa graafisissa, joissa on rajoitettu puun syvyys. Kaavioissa, joiden puun syvyys on enintään d , on itsellään äärellinen määrä kiellettyjä aligraafia. Nexetril ja Ossona de Mendez [17] osoittivat 14 kiellettyä aligraafia kaavioille, joiden puunleveys oli kolme tai vähemmän (viitaten Zdenek Dvorakin vuoden 2007 väitöstutkimukseen).

Jos C on graafien luokka, jolla on rajoitettu rappeutuminen , C :n graafit ovat rajallisia puunleveyksiä silloin ja vain, jos on polku, joka ei voi esiintyä generoituna osagraafina C :ssä [15] .

Vaikeus

Puun syvyyden määrittäminen on monimutkainen laskennallinen ongelma - vastaava tunnistusongelma on NP-täydellinen [18] . Ongelma on edelleen NP-täydellinen kaksiosaisille graafeille [1] sekä sointukaavioille [19] .

Positiivinen puoli on se, että puun syvyys voidaan laskea polynomiajassa intervallikaavioille [20] , samoin kuin permutaatiokaavioille, puolisuunnikkaan muotoisille kaavioille, ympyrän kaarileikkauskaavioille, syklisille permutaatiokaavioille ja rajallisten mittojen vertailtavuuskaavioille [21] ] . Suuntaamattomille puille puun syvyys voidaan laskea lineaarisessa ajassa [22] [23] .

Bodlender, Gilbert, Hufsteinsson ja Klox [11] ehdottivat approksimaatioalgoritmia puun syvyyden löytämiseksi approksimaatiokertoimella . Algoritmi perustuu siihen, että puun syvyys riippuu logaritmisesti graafin puun leveydestä.

Koska puun syvyys on monotoninen graafin molereissa, sen löytämisongelma on kiinteä-parametrisesti ratkaistava — puun syvyyden laskemiseen on olemassa algoritmi, joka toimii ajassa , missä d on syvyys annetusta graafista ja n on pisteiden lukumäärä. Siten minkä tahansa d :n kiinteän arvon kohdalla ongelma, jolla tarkistetaan, onko puun syvyys suurempi kuin d , voidaan ratkaista polynomiajassa . Tarkemmin sanottuna riippuvuus n :stä voidaan tässä algoritmissa tehdä lineaariseksi seuraavasti: rakennetaan syvyys-ensimmäinen hakupuu ja tarkistetaan onko puun syvyys suurempi kuin 2 d vai ei. Jos enemmän, puun syvyys on suurempi kuin d ja ongelma on ratkaistu. Jos ei, matalaa etsintäpuurakennusta voidaan käyttää puun hajottamiseen , ja tavanomaista dynaamista ohjelmointitekniikkaa rajatun puunleveyden kuvaajille voidaan käyttää syvyyden laskemiseen lineaarisessa ajassa [24] . Bodlander, Deogan, Jensen ja Klox ehdottivat aiemmin kehittyneempää lineaariaikaista ratkaisualgoritmia, joka perustuu eliminoitujen alaikäisten tasoon syvähaussa [1] . Parannettu parametrinen algoritmi, katso Reidl, Rossmanite, Villamil ja Sikdar [25] .

Puun syvyys voidaan laskea tarkasti kaavioille, joiden syvyysarvo voi olla suuri O ( c n ) -ajassa vakiolla c hieman alle 2. [26]

Muistiinpanot

  1. ↑ 1 2 3 Bodlaender et al, 1998 .
  2. ↑ Rossman, 2008 .
  3. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 116.
  4. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 115, määritelmä 6.1.
  5. ↑ David Eppstein. Kuvaajan parametrit ja klikit supergraafissa. – 2012 (15. marraskuuta). Arkistoitu alkuperäisestä 9. tammikuuta 2014. .
  6. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 117, Lemma 6.1.
  7. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 125–128, kohta 6.5, "Keskivärjäys".
  8. ↑ Gruber ja Holzer 2008 , s. Lause 5.
  9. ↑ Hunter, 2011 , Päälause.
  10. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 117, kaava 6.2.
  11. ↑ 1 2 3 Bodlaender et al, 1995 .
  12. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 124, Seuraus 6.1.
  13. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 123.
  14. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 117, Lemma 6.2.
  15. ↑ 1 2 Nešetřil, Ossona de Mendez, 2012 , s. 122, kohta 6.4.
  16. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 137, Lemma 6.13.
  17. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 138. Kuva 6.6 sivulla 138. 139.
  18. ↑ Pothen, 1988 .
  19. ↑ Dereniowski, Nadolski, 2006 .
  20. ↑ Aspvall, Heggernes, 1994 .
  21. ↑ Deogun et ai, 1999 .
  22. ↑ Iyer et ai, 1988 .
  23. ↑ Schaffer, 1989 .
  24. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 138.
  25. ↑ Reidl et al, 2014 .
  26. ↑ Fomin et al, 2013 .

Kirjallisuus