Fa mélysége (gráfelmélet)

A gráfelméletben egy összefüggő irányítatlan G gráf famélysége G numerikus invariánsa , a Tremaux- fa minimális magassága G szupergráfjához . Ez az invariáns és rokon fogalmak különböző neveken fordulnak elő a szakirodalomban, beleértve a csúcsrangsorszámot, a rendezett kromatikus számot és a minimális fa eliminációs magasságot. A fogalom olyan fogalmakhoz is közel áll, mint az irányított gráfok ciklikus rangja és a reguláris nyelvek nyelvének iterációs magassága [1] [2] ; [3] . Míg a gráf faszélessége intuitív módon azt méri, hogy a gráf milyen messze van a fától, addig a fa mélysége azt méri, milyen messze van a gráf a csillagtól.

Definíciók

Egy G gráf famélysége egy F erdő minimális magasságaként definiálható azzal a tulajdonsággal, hogy G bármely éle összeköt egy olyan csúcspárt, amelyet szülő-gyermek kapcsolat köt össze F -ben [4] . Ha G kapcsolódik, akkor ennek az erdőnek egyetlen fának kell lennie. Az erdőnek nem kell G részgráfjának lennie , de ha igen, akkor G Tremaux- fája .

Az F -beli szülő-gyermek párok halmaza egy triviálisan tökéletes gráfot alkot, és F magassága ennek a gráfnak a legnagyobb klikkjének a mérete . Így a fa mélysége úgy is meghatározható, mint a legnagyobb klikk mérete G triviálisan tökéletes szupergráfjában, ami a faszélesség tükörképe , amely eggyel kisebb, mint a legnagyobb klikk mérete G akkordális szupergráfjában [ 5]

Egy másik definíció a következő:

ahol V a G gráf csúcsainak halmaza és G összefüggő komponensei [6] . Ez a definíció tükrözi az irányított gráfok ciklikus rangdefinícióját, amely erős összeköttetést és erősen összekapcsolt komponenseket használ az irányítatlan összeköttetés és az összekapcsolt komponensek helyett.

Egy fa mélysége grafikonszínezéssel határozható meg . A központosított gráf színezése egy csúcsszínezés, amelynek megvan az a tulajdonsága, hogy bármely összekapcsolt generált részgráf színe pontosan egyszer fordul elő. Ekkor a fa mélysége a színek minimális mérete a grafikon középre festéséhez. Ha F egy d magasságú erdő , amelynek az a tulajdonsága, hogy G bármely éle összeköti a fában az őst és a gyermeket, akkor G középpontos színezését kaphatjuk d színnel, ha minden csúcsot a távolság a gyöktől F -ben [7 ] .

Végül egy zsetonjátékkal is definiálhatjuk . Pontosabban, pontosan úgy, mint a "zsaruk-rablók" játékban . Képzeld el a következő játékot egy irányítatlan grafikonon. Két játékos van, egy rabló és egy rendőr. A rablónak van egy darabja, amelyet a gráf élei mentén mozgat. A rendőrnek korlátlan számú zsetonja van, de szeretné minimalizálni a felhasznált zsetonok számát. A rendőr nem tudja mozgatni a grafikonon elhelyezett darabjait. A játék így megy. A rabló elhelyezi a darabját, majd a rendőr megmondja, hova akarja elhelyezni a következő darabot, és a rabló ezután mozgathatja a darabját a szélek mentén, de nem az elfoglalt csúcsokon. A játék akkor ér véget, amikor a rendőr ráteszi a következő darabot a rablódarab tetejére. Egy adott gráf famélysége határozza meg a garantált győzelemhez szükséges minimális zsetonszámot [8] [9] . Csillagokhoz elég két jelző – helyezze az első jelzőt a csillag közepére, kényszerítve a rablót, hogy bemozduljon valamilyen sugárba, majd helyezze a második jelzőt a rabló jelzőjére. A csúcsokkal rendelkező útvonalak esetében a rendőr bináris keresési stratégiát használ, amely garantálja, hogy ne használjon több token.

Példák

Egy teljes gráf famélysége megegyezik a csúcsok számával, ebben az esetben az egyetlen lehetséges F erdő , amelynél bármely csúcspárnak ős-gyermek kapcsolatban kell lennie, az egyetlen út. Hasonlóképpen egy teljes kétrészes K x , y gráf famélysége min( x , y ) + 1, és bárhogyan is pozícionáljuk a csúcsokat, az F erdő leveleinek legalább min( x , y ) ősökkel kell rendelkezniük F -ben. . Azt az erdőt, amelyen a min( x , y ) + 1 elérjük, úgy szerkeszthetjük meg, hogy a gráf kisebbik részének csúcsaiból utat képezünk, a nagyobbik rész csúcsai pedig az F fa leveleit alkotják, amelyek az alsóhoz kapcsolódnak. az út csúcsa.

Egy n csúcsú pályafa mélysége pontosan . Ezt az ösvényt ilyen mélységgel reprezentáló F erdőt úgy lehet kialakítani, hogy a gyökeret az F út felezőpontjába helyezzük, és a rekurziót a gyökér két oldalán két kisebb útvonalon folytatjuk [10] .

A fák mélysége és a fa szélességéhez való viszony

Minden n csúcsú erdőnek O(log n ) famélysége  van . Egy erdőnél mindig találhatunk állandó számú csúcsot, amelyek eltávolításával két kisebb, egyenként maximum 2 n /3 csúcsos részerdőre osztható erdő keletkezik . E két aljnövényzet rekurzív felosztásával könnyen elérhető a famélység logaritmikus felső korlátja. Ugyanez a technika, amelyet a gráffa dekompozíciónál alkalmazunk , megmutatja , hogy ha egy n csúcsú G gráf faszélessége t , akkor G fa mélysége O( t  log  n ). [11] [12] Mivel a külső síkbeli gráfok , párhuzamos-szekvenciális gráfok és Halin-gráfok korlátos faszélességűek, mindegyiknek van egy maximális logaritmikus famélysége is.

A másik irányban egy gráf faszélessége nem haladja meg a fa mélységét. Pontosabban, a fa szélessége nem haladja meg a gráf útszélességét , ami legfeljebb eggyel kisebb a fa mélységénél [11] [13] .

Kiskorúak száma

A G gráf mollja egy másik gráf, amelyet G részgráfjából alakítunk ki néhány él összehúzásával. A fa mélysége mollokban monoton – a G gráf bármely minor famélysége nem haladja meg magának a G gráfnak a famélységét [14] . Így a Robertson-Seymour tétel szerint bármely rögzített d esetén a d -t meg nem haladó famélységű gráfok halmazában véges számú tiltott mellék van .

Ha C a gráfok egy osztálya, amely a minorok formációja alatt záródik, akkor a C -beli gráfoknak akkor és csak akkor van famélysége , ha C nem tartalmazza az összes utat [15] .

Generált részgráfok

A fa mélysége szoros kapcsolatban áll a gráf generált részgráfjainak elméletével. A legfeljebb d famélységű gráfok osztályában (bármilyen rögzített természetes d esetén) az a tulajdonság, hogy generált részgráf, jól kvázi rendezett [16] . A fő gondolat annak bizonyítása mögött, hogy ez a kapcsolat teljesen kvázi rendezett, az indukció használata d -n . A d magasságú erdők d − 1 magasságú erdők sorozataként értelmezhetők (amely a d  magasságú fák gyökeresedésével jön létre ), és a Higman-lemmával megmutathatjuk, hogy ezek a sorozatok jól kvázi rendezettek.

A jól kvázi rendezettségből következik, hogy egy gráf bármely tulajdonsága, amely monoton a generált részgráfokban, véges számú tiltott részgráfot tartalmaz, ezért polinomiális időben ellenőrizhető korlátos famélységű gráfokon. A legfeljebb d famélységű grafikonoknak véges számú tiltott gyermek részgráfja van. Nexetril és Ossona de Mendez [17] 14 tiltott részgráfot mutatott fel a három vagy annál kisebb faszélességű gráfokhoz (hivatkozás Zdenek Dvorak 2007-es disszertációjára).

Ha C gráfok osztálya korlátos degenerációval , akkor a C gráfjainak akkor és csak akkor van korlátos faszélessége, ha van olyan útvonal, amely nem jelenhet meg generált részgráfként C -ben [15] .

Nehézség

A fa mélységének meghatározása összetett számítási probléma – a megfelelő felismerési probléma NP-teljes [18] . A probléma NP-teljes marad a bipartit gráfok [1] , valamint az akkordgráfok [19] esetében .

Pozitívum, hogy a fa mélysége polinomiális időben számítható intervallumgráfokhoz [20] , valamint permutációs gráfokhoz, trapéz gráfokhoz, körív metszetgráfokhoz, ciklikus permutációs gráfokhoz és korlátos méretű összehasonlíthatósági gráfokhoz [21] ] . Irányítatlan fák esetén a fa mélysége lineáris időben számítható [22] [23] .

Bodlender, Gilbert, Hufsteinsson és Klox [11] közelítő algoritmust javasoltak egy közelítési együtthatóval rendelkező fa mélységének meghatározására . Az algoritmus azon a tényen alapul, hogy a fa mélysége logaritmikusan függ a gráf faszélességétől.

Mivel egy fa mélysége monoton a gráf molljaiban, a megtalálásának problémája fix-paraméteresen megoldható – van egy algoritmus a fa mélységének kiszámítására, amely időben működik , ahol d a mélység az adott gráf és n a csúcsok száma. Így d tetszőleges fix értékére polinomiális időben megoldható annak ellenőrzése, hogy a fa mélysége nagyobb -e d -nél . Pontosabban, az n -től való függést ebben az algoritmusban a következő módon tehetjük lineárissá: építünk egy mélységi keresési fát, és ellenőrizzük, hogy a fa mélysége nagyobb-e 2 d -nál vagy sem. Ha több, akkor a fa mélysége nagyobb, mint d , és a probléma megoldódott. Ha nem, akkor sekély keresőfa-építés használható a fa felbontására , és a korlátos faszélességű gráfok szabványos dinamikus programozási technikája használható a mélység lineáris időben történő kiszámítására [24] . Bodlander, Deogan, Jensen és Klox korábban javasolt egy kifinomultabb lineáris idejű megoldási algoritmust, amely a mélységi keresés során kizárt kiskorúak síkságán alapul [1] . A továbbfejlesztett parametrikus algoritmushoz lásd Reidl, Rossmanite, Villamil és Sikdar [25] .

Pontosan kiszámítható a fa mélysége olyan grafikonoknál, amelyek mélységértéke O ( c n ) időben nagy lehet 2-nél valamivel kisebb c állandóval . [26]

Jegyzetek

  1. ↑ 1 2 3 Bodlaender et al, 1998 .
  2. ↑ Rossman, 2008 .
  3. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 116.
  4. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 115. 6.1.
  5. ↑ David Eppstein. Grafikonparaméterek és klikkek szupergráfokban. — 2012 (november 15.). Az eredetiből archiválva : 2014. január 9. .
  6. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 117, Lemma 6.1.
  7. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 125–128. 6.5. szakasz, „Középpontos színezések”.
  8. ↑ Gruber és Holzer 2008 , p. 5. tétel.
  9. ↑ Hunter, 2011 , Főtétel.
  10. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 117, Formula 6.2.
  11. ↑ 1 2 3 Bodlaender et al, 1995 .
  12. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 124. Következmény 6.1.
  13. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 123.
  14. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 117, Lemma 6.2.
  15. ↑ 1 2 Nešetřil, Ossona de Mendez, 2012 , p. 122., 6.4.
  16. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 137, Lemma 6.13.
  17. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 6.6. ábra a 138. oldalon. 139.
  18. ↑ Pothen, 1988 .
  19. ↑ Dereniowski, Nadolski, 2006 .
  20. ↑ Aspvall, Heggernes, 1994 .
  21. ↑ Deogun et al, 1999 .
  22. ↑ Iyer et al, 1988 .
  23. ↑ Schaffer, 1989 .
  24. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 138.
  25. ↑ Reidl et al, 2014 .
  26. ↑ Fomin et al, 2013 .

Irodalom