Adâncimea arborelui (teoria graficelor)

În teoria grafurilor, adâncimea arborelui unui graf nedirecționat conectat G este invariantul numeric al lui G , înălțimea minimă a arborelui Tremaux pentru un supergraf al lui G . Aceste concepte invariante și înrudite apar sub diferite nume în literatură, inclusiv numărul de clasare a vârfurilor, numărul cromatic ordonat și înălțimea minimă de eliminare a arborelui. Conceptul este, de asemenea, apropiat de concepte precum rangul ciclic al graficelor direcționate și înălțimea de iterație a limbajului limbajelor obișnuite [1] [2] ; [3] . În mod intuitiv, în timp ce lățimea arborelui unui grafic măsoară cât de departe este graficul de arbore, adâncimea arborelui măsoară cât de departe este graficul de stea.

Definiții

Adâncimea arborelui unui grafic G poate fi definită ca înălțimea minimă a unei păduri F cu proprietatea că orice margine a lui G conectează o pereche de vârfuri conectate printr-o relație părinte-copil în F [4] . Dacă G este conectat, această pădure trebuie să fie un singur copac. Pădurea nu trebuie să fie un subgraf al lui G , dar dacă este, atunci este un arbore Tremaux pentru G .

Setul de perechi părinte-copil din F formează un grafic trivial perfect , iar înălțimea lui F este dimensiunea celei mai mari clicuri a acestui grafic. Astfel, adâncimea arborelui poate fi definită alternativ ca dimensiunea celei mai mari clicuri din supergraful trivial perfect al lui G , care este o imagine în oglindă a lățimii arborelui , care este cu o mai mică decât dimensiunea celei mai mari clicuri din supergraful cordal al lui G [ 5]

O altă definiție este următoarea:

unde V este mulțimea vârfurilor graficului G și sunt componentele conexe ale lui G [6] . Această definiție reflectă definiția de rang ciclic a graficelor direcționate, care utilizează conectivitate puternică și componente puternic conectate în loc de conectivitate nedirecționată și componente conectate.

Adâncimea unui copac poate fi determinată folosind colorarea graficului . O colorare a unui graf centrat este o colorare a vârfurilor care are proprietatea că orice subgraf generat conectat are o culoare care apare exact o dată. Apoi, adâncimea arborelui este dimensiunea minimă a culorilor necesare pentru o colorare centrată a graficului. Dacă F este o pădure de înălțime d care are proprietatea că orice margine a lui G leagă un strămoș și un copil din copac, atunci se poate obține o colorare centrată a lui G cu d culori colorând fiecare vârf cu un număr de culoare egal cu distanta de la radacina in F [7 ] .

În cele din urmă, se poate defini în termeni de joc cu jetoane . Mai exact, exact ca jocul „polițiști-tâlhari” . Imaginează-ți următorul joc pe un grafic nedirecționat. Sunt doi jucători, un tâlhar și un polițist. Tâlharul are o singură piesă, pe care o deplasează de-a lungul marginilor graficului. Polițistul are un număr nelimitat de jetoane, dar vrea să minimizeze numărul de jetoane folosite. Polițistul nu își poate muta piesele plasate pe grafic. Jocul merge așa. Tâlharul își plasează piesa, apoi polițistul spune unde vrea să plaseze următoarea piesă și tâlharul își poate muta piesa de-a lungul marginilor, dar nu peste vârfurile ocupate. Jocul se termină când polițistul plasează următoarea piesă deasupra piesei de tâlhar. Adâncimea arborelui unui grafic dat determină numărul minim de jetoane necesare pentru un câștig garantat [8] [9] . Pentru stele , două jetoane sunt suficiente - plasați primul jetoane în centrul stelei, forțând tâlharul să se miște într-un fascicul, apoi plasați al doilea jetoane pe jetonul tâlharului. Pentru o cale cu vârfuri, polițistul folosește o strategie de căutare binară care garantează că nu mai sunt folosite jetoane.

Exemple

Adâncimea arborelui unui grafic complet este egală cu numărul de vârfuri ale acestuia, caz în care singura pădure posibilă F pentru care orice pereche de vârfuri trebuie să fie într-o relație strămoș-copil este o singură cale. În mod similar, adâncimea arborelui unui grafic bipartit complet K x , y este min( x , y ) + 1, și oricum poziționăm vârfurile, frunzele pădurii F trebuie să aibă cel puțin min( x , y ) strămoși în F . Pădurea pe care se ajunge la min( x , y ) + 1 poate fi construită prin formarea unei căi de la vârfurile părții mai mici a graficului, iar vârfurile părții mai mari formează frunzele copacului F legate de cea inferioară. vârful drumului.

Adâncimea unui arbore de căi cu n vârfuri este exact . O pădure F care reprezintă această cale cu această adâncime poate fi formată prin plasarea rădăcinii la mijlocul căii F și continuând recursiunea în două căi mai mici de fiecare parte a rădăcinii [10] .

Adâncimea copacilor și relația cu lățimea copacilor

Orice pădure cu n vârfuri are adâncimea copacului O(log  n ). Pentru o pădure, se poate găsi întotdeauna un număr constant de vârfuri, din îndepărtarea cărora rezultă o pădure care poate fi împărțită în două subpăduri mai mici, cu maximum 2 n /3 vârfuri fiecare. Împărțind recursiv aceste două tufișuri, se poate ajunge cu ușurință la o limită superioară logaritmică a adâncimii copacului. Aceeași tehnică, aplicată la descompunerea arborelui grafic , arată că dacă lățimea arborelui a unui grafic n -vertex G este t , atunci adâncimea arborelui G este O( t  log  n ). [11] [12] Deoarece graficele planare exterioare , graficele paralele-secvențiale și graficele Halin au o lățime de arbore mărginită, toate au, de asemenea, o adâncime maximă a arborelui logaritmic.

În cealaltă direcție, lățimea arborelui unui grafic nu depășește adâncimea arborelui său. Mai precis, lățimea arborelui nu depășește lățimea traseului graficului , care este cu cel mult cu una mai mică decât adâncimea arborelui său [11] [13] .

Numărați minorii

Un minor al unui graf G este un alt graf format dintr-un subgraf al lui G prin contractarea unor muchii. Adâncimea unui arbore este monotonă la minori — orice minor al unui grafic G are o adâncime a arborelui care nu depășește adâncimea arborelui a graficului G însuși [14] . Astfel, după teorema Robertson-Seymour , pentru orice d fix , mulțimea de grafice cu adâncimea arborelui care nu depășește d are un număr finit de minori interzise .

Dacă C este o clasă de grafice închise sub formarea minorilor, atunci graficele din C au adâncimea arborelui dacă și numai dacă C nu include toate căile [15] .

Subgrafe generate

Adâncimea arborelui are o relație strânsă cu teoria subgrafelor generate ale unui grafic. În clasa grafurilor cu adâncimea arborelui de cel mult d (pentru orice d natural fix ), proprietatea de a fi un subgraf generat este bine cvasi-ordonată [16] . Ideea principală din spatele dovezii că această conexiune este complet cvasi-ordonată este folosirea inducției pe d . Pădurile de înălțime d pot fi interpretate ca o succesiune de păduri de înălțime d  − 1 (formate din dezrădăcinarea arborilor de înălțime d ) și lema lui Higman poate fi folosită pentru a arăta că aceste secvențe sunt bine cvasi-ordonate.

Din bine-cvasi-ordonarea rezultă că orice proprietate a unui graf care este monotonă în subgrafele generate are un număr finit de subgrafe generate interzise și, prin urmare, poate fi verificată în timp polinomial pe grafice cu o adâncime de arbore mărginită. Graficele cu adâncimea arborelui de cel mult d au un număr finit de subgrafe interzise. Nexetril și Ossona de Mendez [17] au arătat 14 subgrafe interzise pentru graficele cu lățimea arborelui trei sau mai puțin (cu referire la tezele de disertație din 2007 de Zdenek Dvorak).

Dacă C este o clasă de grafice cu degenerare mărginită , graficele din C au lățime de arbore mărginită dacă și numai dacă există o cale care nu poate apărea ca subgraf generat în C [15] .

Dificultate

Determinarea adâncimii unui arbore este o problemă complexă de calcul - problema de recunoaștere corespunzătoare este NP-complet [18] . Problema rămâne NP-completă pentru grafurile bipartite [1] , precum și pentru grafurile cordale [19] .

Pe partea pozitivă, adâncimea unui arbore poate fi calculată în timp polinomial pentru grafice cu intervale [20] , precum și pentru grafice de permutare, grafice trapezoidale, grafice de intersecție cu arc de cerc, grafice de permutare ciclică și grafice de cocomparabilitate de dimensiuni mărginite [21]. ] . Pentru arborii nedirecționați, adâncimea arborelui poate fi calculată în timp liniar [22] [23] .

Bodlender, Gilbert, Hufsteinsson și Klox [11] au propus un algoritm de aproximare pentru găsirea adâncimii unui arbore cu un coeficient de aproximare . Algoritmul se bazează pe faptul că adâncimea unui arbore depinde logaritmic de lățimea arborelui a graficului.

Deoarece adâncimea unui copac este monotonă în minorele graficului, problema găsirii acestuia este fix-rezolvabilă parametric — există un algoritm pentru calcularea adâncimii unui copac care funcționează în timp , unde d este adâncimea al graficului dat și n este numărul de vârfuri. Astfel, pentru orice valoare fixă ​​a lui d , problema verificării dacă adâncimea unui arbore este mai mare decât d poate fi rezolvată în timp polinomial . Mai precis, dependența de n în acest algoritm poate fi făcută liniară în felul următor: construim un arbore de căutare depth-first și verificăm dacă adâncimea arborelui este mai mare de 2 d sau nu. Dacă este mai mare, adâncimea copacului este mai mare decât d și problema este rezolvată. Dacă nu, construcția arborelui de căutare superficială poate fi utilizată pentru a descompune arborele , iar tehnica standard de programare dinamică pentru graficele cu lățime de arbore mărginită poate fi utilizată pentru a calcula adâncimea în timp liniar [24] . Un algoritm de soluție în timp liniar mai sofisticat bazat pe planaritatea minorilor eliminați în căutarea în profunzime a fost propus mai devreme de Bodlander, Deogan, Jensen și Klox [1] . Pentru un algoritm parametric îmbunătățit, vezi Reidl, Rossmanite, Villamil și Sikdar [25] .

Este posibil să se calculeze exact adâncimea arborelui pentru grafice a căror valoare adâncime poate fi mare în timp O ( c n ) cu o constantă c puțin mai mică de 2. [26]

Note

  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, Definiția 6.1.
  5. ↑ David Eppstein. Parametrii graficului și clicurile în supergrafe. — 2012 (15 noiembrie). Arhivat din original pe 9 ianuarie 2014. .
  6. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 117, Lema 6.1.
  7. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 125–128, Secțiunea 6.5, „Colorări centrate”.
  8. ↑ Gruber și Holzer 2008 , p. Teorema 5.
  9. ↑ Hunter, 2011 , Teorema principală.
  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, Corolarul 6.1.
  13. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 123.
  14. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 117, Lema 6.2.
  15. ↑ 1 2 Nešetřil, Ossona de Mendez, 2012 , p. 122, Propunerea 6.4.
  16. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 137, Lema 6.13.
  17. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 138. Figura 6.6 la p. 139.
  18. ↑ Pothen, 1988 .
  19. ↑ Dereniowski, Nadolski, 2006 .
  20. ↑ Aspvall, Heggernes, 1994 .
  21. ↑ Deogun și colab., 1999 .
  22. ↑ Iyer și colab., 1988 .
  23. ↑ Schaffer, 1989 .
  24. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 138.
  25. ↑ Reidl et al, 2014 .
  26. ↑ Fomin et al, 2013 .

Literatură