h1. Tree decompositions

(Categoria _Algoritmi_, autor _Marius Stroe_)

(Categoria _Algoritmi_, Autor _Marius Stroe_)

(toc){width: 20em}*{text-align:center} *Conţinut:*
* '{*} Liniarizare':heavy-path-decomposition#liniarizare
** 'Solutie $O((M+N)*log(N))$':heavy-path-decomposition#solutie-liniarizare
* '{*} Descompunere in lanturi':heavy-path-decomposition#descompunere-in-lanturi
** 'Solutie $O(M*N)$':heavy-path-decomposition#solutie-descompunere-brute
** 'Solutia $O(M*log(N)*sqrt(N))$':heavy-path-decomposition#solutie-log-sqrt
** 'Solutie $O(M*log^2^(N))$':heavy-path-decomposition#solutie-log-log
* '{*} Aplicatii':heavy-path-decomposition#aplicatii
* '{*} Bibliografie':heavy-path-decomposition#bibliografie

(toc){width: 20em}*{text-align:center} *Continut:*
* '{*} Liniarizare':tree-decompositions#liniarizare
** 'Solutie $O((M+N)*log(N))$':tree-decompositions#solutie-liniarizare
* '{*} Descompunere in lanturi':tree-decompositions#descompunere-in-lanturi
** 'Solutie $O(M*N)$':tree-decompositions#solutie-descompunere-brute
** 'Solutia $O(M*log(N)*sqrt(N))$':tree-decompositions#solutie-log-sqrt
** 'Solutie $O(M*log^2^(N))$':tree-decompositions#solutie-log-log
* '{*} Aplicatii':tree-decompositions#aplicatii
* '{*} Bibliografie':tree-decompositions#bibliografie

Acest articol prezinta studiul transformarii unui arbore pentru calcularea eficienta a unei insumari si a valorii maxime/minime aflata pe lantul elementar dintre doua noduri. Mentionez ca, in acest articol, $lant$ va insemna intotdeauna $lant elementar$ (un nod poate aparea cel mult odata).

_Fig. 1: Pentru arborele din figura de mai jos si vectorul de valori_ <tex> value[] = \{3, 5, 7, 1, 2, 4\} </tex>, <tex> seq[] </tex> _construit este ilustrat mai jos. Se observa usor ca tot subarborele unui nod se anuleaza cand este explorat in intregime._

p=. !heavy-path-decomposition?fig1.jpg!

p=. !tree-decompositions?fig1.jpg!

Astfel, s-a construit vectorul <tex> seq[] </tex> care are urmatoarea proprietate: &#34;daca <tex> \Delta = \displaystyle\sum_{i = firstPos[x]}^{firstPos[y]} seq[i] </tex>, <tex> x </tex> fiind un stramos al lui <tex> y </tex>, atunci <tex> \Delta </tex> reprezinta <tex> \Delta = \displaystyle\sum_{u \in P} value[u] </tex>, <tex> P = (x_{0}, x_{1}, x_{2}, ..., x_{n}), x_{0} = x, x_{n} = y </tex>&#34;. Conform acesteia, daca vom determina cel mai apropiat stramos comun dintre doua noduri, atunci nu va fi nevoie decat de o structura de date ce permite calcularea intr-un mod eficient a sumei pe un interval din <tex> seq[] </tex> si modificarea unei valori din acest vector. Putem obtine complexitatea $O(log(N))$ pe fiecare din cele doua operatii folosind structura de date numita arbori de intervale. Pentru determinarea eficienta a celui mai apropiat stramos comun si pentru detalii despre arborii de intervale consultati 'bibliografia':heavy-path-decomposition#bibliografie.

Astfel, s-a construit vectorul <tex> seq[] </tex> care are urmatoarea proprietate: &#34;daca <tex> \Delta = \displaystyle\sum_{i = firstPos[x]}^{firstPos[y]} seq[i] </tex>, <tex> x </tex> fiind un stramos al lui <tex> y </tex>, atunci <tex> \Delta </tex> reprezinta <tex> \Delta = \displaystyle\sum_{u \in P} value[u] </tex>, <tex> P = (x_{0}, x_{1}, x_{2}, ..., x_{n}), x_{0} = x, x_{n} = y </tex>&#34;. Conform acesteia, daca vom determina cel mai apropiat stramos comun dintre doua noduri, atunci nu va fi nevoie decat de o structura de date ce permite calcularea intr-un mod eficient a sumei pe un interval din <tex> seq[] </tex> si modificarea unei valori din acest vector. Putem obtine complexitatea $O(log(N))$ pe fiecare din cele doua operatii folosind structura de date numita arbori de intervale. Pentru determinarea eficienta a celui mai apropiat stramos comun si pentru detalii despre arborii de intervale consultati 'bibliografia':tree-decompositions#bibliografie.

h2(#descompunere-in-lanturi). Descompunere in lanturi

h3(#solutie-log-sqrt). Solutia $O(M*log(N)*sqrt(N))$

Tehnica liniarizarii arborelui nu ne este de folos, deoarece modul de reprezentare a informatiilor nu permite obtinerea unei complexitati mai bune fata de 'solutia lenta':heavy-path-decomposition##solutie-descompunere-brute prezentata mai sus.

Tehnica liniarizarii arborelui nu ne este de folos, deoarece modul de reprezentare a informatiilor nu permite obtinerea unei complexitati mai bune fata de 'solutia lenta':tree-decompositions##solutie-descompunere-brute prezentata mai sus.

Aceasta solutie foloseste asa numita tehnica $longest path decomposition$, tehnica ce necesita cunostine minime despre grafuri si cu care vom obtine complexitatea $O(M*sqrt(N)*log(N))$ urmand pasii de mai jos:

_Fig. 2: Cazul defavorabil cand sunt $O(sqrt(N))$ lanturi elementare._

!heavy-path-decomposition?Figura2.jpg!

!tree-decompositions?Figura2.jpg!

Fie  <tex> x, y \in V </tex>, <tex> x </tex> stramos al lui <tex> y </tex>. Functia care determina valoarea maxima pe lantul dintre <tex> x </tex> si <tex> y </tex> este prezentata in urmatorul pseudocod:

==
Functia $QUERYAi(Path[], lo, hi)$ returneaza in $O(log(N))$, cu ajutorul structurii de date arbori de intervale, maximul dintre valorile cuprinse in intervalul $[lo, hi]$.
Raspunsul cerintei de primul tip va fi  {$Maxim(QUERY (lca, x), QUERY (lca, y))$}, variabila <tex> lca </tex> fiind cel mai apropiat stramos comun al lui <tex> x </tex> si <tex> y </tex>.

Pentru rezolvarea cerintei de tipul doi, vom folosi aceiasi arbori de intervale care vor obtine un cost de $O(log(N))$ pe operatie. Nu voi prezenta aceasta functie, ea fiind in detaliu prezentata in una din sursele afisate in 'bibliografie':heavy-path-decomposition#bibliografie.

Pentru rezolvarea cerintei de tipul doi, vom folosi aceiasi arbori de intervale care vor obtine un cost de $O(log(N))$ pe operatie. Nu voi prezenta aceasta functie, ea fiind in detaliu prezentata in una din sursele afisate in 'bibliografie':tree-decompositions#bibliografie.

Complexitatea finala: $O(M*sqrt(N)*log(N))$. Cel mai rau caz pentru un query este cand se trece prin toate lanturile (in numar de $sqrt(N)$) efectuandu-se cate un query pe fiecare arbore de intervale asociat ({$O(log(N))$}).
h3(#solutie-log-log). Solutia $O(M*log^2^(N))$

O imbunatatire la solutia 'precedenta':heavy-path-decomposition#solutie-log-sqrt o reprezinta $heavy path decomposition$, care se foloseste de acelasi algoritm, cu exceptia faptului ca fiul ales pentru determinarea unui lant este cel cu numar maxim de noduri in subarborele sau (heavy) si nu cel cu inaltimea maxima (longest). Prin urmare, numarul maxim de lanturi prin care se trece pentru a ajunge de la un nod la radacina este cel mult $O(log(N))$ dupa cum se poate vedea si din figura urmatoare:

O imbunatatire la solutia 'precedenta':tree-decompositions#solutie-log-sqrt o reprezinta $heavy path decomposition$, care se foloseste de acelasi algoritm, cu exceptia faptului ca fiul ales pentru determinarea unui lant este cel cu numar maxim de noduri in subarborele sau (heavy) si nu cel cu inaltimea maxima (longest). Prin urmare, numarul maxim de lanturi prin care se trece pentru a ajunge de la un nod la radacina este cel mult $O(log(N))$ dupa cum se poate vedea si din figura urmatoare:

_Fig. 3: Fiecare nod apartine unui singur lant. Lanturile sunt reprezentate de muchii solide._

!heavy-path-decomposition?Figura3.jpg!

!tree-decompositions?Figura3.jpg!

Complexitatea finala: $O(M log^2^(N))$. In practica, aceasta tehnica se comporta foarte bine si poate fi folosita cu succes. Singurul inconvenient este numarul mare de linii de cod scrise.