Descompunerea arborilor

În teoria graficelor, descompunerea arborelui este o mapare a unui grafic într- un arbore care poate fi utilizată pentru a determina lățimea arborelui unui grafic și pentru a accelera rezolvarea anumitor probleme de calcul pe grafice.

În domeniul învățării automate, o descompunere a arborelui este numită și arbore de joncțiune , arbore de clică sau arbore de adiacență . Descompunerea arborelui joacă un rol important în probleme precum inferența probabilistică , găsirea valorilor valide , optimizarea interogărilor DBMS și descompunerea matricei .

Conceptul de descompunere a arborilor a fost propus inițial de Halin [1] . A fost redescoperit ulterior de Robertson și Seymour [2] și de atunci conceptul a fost studiat de mulți alți autori [3] .

Definiție

Intuitiv, descompunerea arborelui reprezintă vârfurile unui graf dat G ca subarbori ai unui arbore în așa fel încât vârfurile graficului să fie adiacente numai atunci când subarborii corespunzători se intersectează. Apoi G formează un subgraf al graficului de intersecție subarboresc . Graficul de intersecție complet este un grafic cordal .

Fiecare subarbore leagă un vârf de grafic la un set de noduri de arbore. Pentru a defini acest lucru în mod formal, vom reprezenta fiecare nod de arbore ca un set de vârfuri asociate cu acesta. Atunci pentru un grafic dat G = ( V , E ) descompunerea arborelui este o pereche ( X , T ), unde X = { X 1 , ..., X n } este o familie de submulțimi ale mulțimii V și T este un arbore ale cărui noduri sunt submulțimi X i care satisfac următoarele proprietăți: [4]

Unirea tuturor mulțimilor X i este egală cu V . Astfel, orice vârf al graficului este conectat la cel puțin un nod al arborelui.
Pentru orice muchie ( v , w ) a graficului, există o submulțime X i care conține atât v cât și w . Astfel, vârfurile sunt adiacente într-un graf numai dacă corespund subarborilor care au un nod comun.
Dacă X i și X j conțin v , atunci toate nodurile X k ale arborelui din calea (unica) între X i și X j conțin și v . Adică, nodurile asociate cu vârful v formează o submulțime conexă în T . Această proprietate poate fi formulată în mod echivalent — dacă , și sunt noduri și este pe drum de la , atunci . $X_{i}$ $X_{j}$ $X_{k}$ $X_{k}$ $X_{i}$ $X_{j}$ $X_{i}\cap X_{j}\subseteq X_{k)$

Descompunerea arborescentă a unui grafic este departe de a fi unică. De exemplu, o descompunere trivială a arborelui conține toate vârfurile graficului la nodul rădăcină.

O descompunere a arborelui în care arborele este o cale se numește descompunere a căii, iar lățimea arborelui acestui tip special de descompunere a arborelui este cunoscută sub numele de lățime a căii .

O descompunere a arborelui ( X , T = ( I , F )) cu lățimea k este netedă dacă pentru toți și pentru toți [5] . $i\in I:|X_{i}|=k+1$ $(i,j)\in F:|X_{i}\cap X_{j}|=k$

Lățimea lemnului

Lățimea descompunerii unui arbore este mărimea setului său cel mai mare X i fără unitate. Lățimea arborelui tw( G ) a lui G este lățimea minimă dintre toate descompunerea posibilă a lui G . În această definiție, dimensiunea celui mai mare set este redusă cu unu pentru a face lățimea arborioară a copacului egală cu unu. Lățimea arborelui poate fi determinată din alte structuri decât descompunerea copacilor. Aceasta include numărătoarea de acorduri , mărăcini și porturi .

Determinarea dacă lățimea arborelui unui grafic dat G nu depășește k este o problemă NP-completă [6] . Totuși, dacă k este o constantă fixă, un grafic cu lățimea k arborelui poate fi recunoscut și o descompunere arborescentă de lățime k poate fi construită în timp liniar [5] . Timpul de rulare al acestui algoritm depinde exponențial de k .

Programare dinamică

La începutul anilor 1970, s-a observat că problemele dintr-o clasă mare de probleme de optimizare combinatorie pe grafice pot fi rezolvate eficient folosind programarea dinamică non-serială , dacă graficul are o dimensiune mărginită [7] , un parametru legat de lățimea arborelui. Mai târziu, unii autori au descoperit în mod independent până la sfârșitul anilor 1980 [8] că multe probleme algoritmice NP-complete pentru grafice arbitrare pot fi rezolvate eficient folosind programarea dinamică pentru grafice cu lățime limitată a arborelui utilizând descompunerea în arbore a acestor grafice.

Ca exemplu, imaginați-vă problema de a găsi cea mai mare mulțime independentă pe un grafic cu lățimea k a arborelui . Pentru a rezolva această problemă, alegem mai întâi un nod de descompunere a arborelui ca rădăcină (în mod arbitrar). Pentru un nod de descompunere arborescent X i , fie D i uniunea mulțimilor X j moștenite de la X i . Pentru o mulțime independentă S ⊂ X i , fie A ( S , i ) să desemneze dimensiunea celei mai mari submulțimi independente I a lui D i astfel încât I ∩ X i = S . În mod similar, pentru o pereche adiacentă de noduri Xi și X j cu X i mai departe de rădăcină decât X j și o mulțime independentă S ⊂ X i ∩ X j , fie B ( S , i , j ) să desemneze dimensiunea celui mai mare submulțime independentă I în D i astfel încât I ∩ X i ∩ X j = S . Putem calcula aceste valori A și B mergând arborele de jos în sus:

A(S,i)=|S|+\sum _{j}\left(B(S\cap X_{j},j,i)-|S\cap X_{j}|\dreapta)

B(S,i,j)=\max _{S'\subset X_{i} \atop S=S'\cap X_{j}}A(S',i)

Unde suma din formula pentru este preluată descendenții nodului . $A(S,i)$ $X_{i}$

La fiecare nod sau margine, există cel mult 2k seturi S pentru care trebuie calculate aceste valori, astfel încât, în cazul în care k este o constantă, toate calculele au timp constant pentru fiecare muchie sau nod. Mărimea celui mai mare set independent este cea mai mare valoare stocată în nodul rădăcină, iar cel mai mare set independent în sine poate fi găsit (așa cum este standard în programarea dinamică) prin urmărirea acestor valori stocate, începând cu cea mai mare valoare. Astfel, în graficele cu lățimea arborelui mărginit, problema găsirii celei mai mari mulțimi independente poate fi rezolvată în timp liniar. Algoritmi similari sunt aplicabili la multe alte probleme de grafic.

Această abordare de programare dinamică este aplicată în domeniul învățării automate folosind algoritmul arborelui de articulare pentru a propaga încrederea pe grafice cu lățime limitată a arborelui. Abordarea joacă, de asemenea, un rol cheie în algoritmii pentru calcularea lățimii arborelui și construirea unei descompunere a arborelui. În mod obișnuit, astfel de algoritmi au un prim pas care aproximează lățimea arborelui și construiește o descompunere a arborelui cu această lățime aproximativă, iar al doilea pas folosește programarea dinamică a descompunerii arborelui rezultat pentru a calcula valoarea exactă a lățimii arborelui [5] .

Vezi și

Blackberry și port , două tipuri de structuri care pot fi folosite ca alternativă la descompunerea copacilor în determinarea lățimii arborelui unui grafic
Descompunerea graficului ramurilor , o structură strâns legată a cărei lățime este liniar legată de lățimea arborelui
Metoda de descompunere .

Note

↑ Halin, 1976 .
↑ Robertson, Seymour, 1984 .
↑ Diesel, 2005 , p. 354–355.
↑ Diesel, 2005 , p. secțiunea 12.3.
↑ 1 2 3 Bodlaender, 1996 .
↑ Arnborg, Corneil, Proskurowski, 1987 .
↑ Bertelé, Brioschi, 1972 .
↑ Arnborg, Proskurowski, 1989 ; Berna, Lawler, Wong, 1987 ; Bodlaender, 1988 .

Literatură

S. Arnborg, D. Corneil, A. Proskurowski. Complexitatea găsirii înglobărilor într-un arbore k // SIAM Journal on Matrix Analysis and Applications. - 1987. - T. 8 , nr. 2 . — S. 277–284 . - doi : 10.1137/0608024 . .
S. Arnborg, A. Proskurowski. Algoritmi de timp liniar pentru probleme NP-hard limitate la k -arbori parțiali // Matematică aplicată discretă. - 1989. - T. 23 , nr. 1 . — S. 11–24 . - doi : 10.1016/0166-218X(89)90031-0 . .
MW Bern, EL Lawler, AL Wong. Calcul liniar în timp al subgrafelor optime ale graficelor descomponabile // Journal of Algorithms. - 1987. - T. 8 , nr. 2 . — S. 216–235 . - doi : 10.1016/0196-6774(87)90039-3 . .
Umberto Bertele, Francesco Brioschi. Programare dinamică non-serială. - Academic Press, 1972. - ISBN 0-12-093450-7 . .
Hans L. Bodlaender. Proc. Al 15-lea Colocviu Internațional despre Automate, Limbaje și Programare. - Springer-Verlag, 1988. - T. 317. - S. 105-118. — (Note de curs în Informatică). - doi : 10.1007/3-540-19488-6_110 . .
Hans L. Bodlaender. Un algoritm de timp liniar pentru găsirea descompozițiilor arborelui de lățime mică a arborilor // SIAM Journal on Computing. - 1996. - T. 25 , nr. 6 . - S. 1305-1317 . - doi : 10.1137/S0097539793251219 . .
Reinhard Diesel. teoria grafurilor. — al 3-lea. - Springer , 2005. - ISBN 3-540-26182-6 . .
Rudolf Halin. S -funcții pentru grafice // Journal of Geometry. - 1976. - T. 8 . — S. 171–186 . - doi : 10.1007/BF01917434 . .
Neil Robertson, Paul D. Seymour. Graph minors III: Planar tree-width // Journal of Combinatorial Theory, Seria B. - 1984. - V. 36 , nr. 1 . — p. 49–64 . - doi : 10.1016/0095-8956(84)90013-3 . .