Razlaganje stabla

Ovaj članak je o stablima kao strukturama grafova. Za dekompoziciju grafova u stablu pogledajte stranicu Teorija grafova.

U teoriji grafova, razlaganje stabla je mapiranje graf u stablo kako bi mogl oda se koristi kako bi se odredila širina stabla od grafa u kako bi se ubrzao rešavanje određenih kompjuterskih problema na grafu.

Graf sa osam temena, i njegovo razlaganje na stablo sa šest čvorova. Svaki ivica grafa spaja dva temena koji se nalaze zajedno u nekom čvoru stabla, i svako teme grafa je naveden u čvorovima susednih podstabala drveta. Svaki čvor stabla sadrži najviše tri temena, pa je širina ovog razlaganja dva.

U mašinskom učenju, stablo razlaganja se takođe zove stablo raskrsnica, klika stablo, ili spojena stabla, što znači da igraju važnu ulogu u problemima poput verovatnoće zaključaka, zadovoljstvo ograničenja, optimizacija upita i matrica razlaganja.

Koncept stabla razlaganja je prvobitno uveo Rudolf Halin (1976). Kasnije je ponovo otkrivena od strane Nila Robertsona i Pavla Simura (1984) i od tada je proučavan od strane mnogih drugih autora.

Definicija

Intuitivno, stablo razlaganja predstavlja temena datog grafa G kao podstabla glavnog stabla, tako da temena u datom grafu su susedni samo kada odgovarajuća podstabla seku. Dakle, G čini podgraf od raskrsnice grafa od podstabala. Pun presek graf hordalni graf.

Svaki podstablo povezuje grafova temena sa skupom čvorova stabla. Da bi definisali ovo formalno, što predstavićemo svaki čvor stabla kao skup temena u vezi sa njim.

Dakle, s obzirom na graf G = ( V, E), stablo razlaganja je par (X, T), gde je X= {X₁, .. X_n} je familija podskupa od V, i T je stablo čiji čvorovi su podskupovi X_i, zadovoljavajući sledeće karakteristike:

1. Unija svih skupova X _i jednako V. To jest, svako temene grafa je povezano sa najmanje jednim čvorem stabla.
2. Za svaku ivicu (v, w) na grafu, postoji podskup X _i koji sadrži i v i w. To jest, čvorovi su susedna u grafu samo kada odgovarajuća podstabla imaju zajednički čvor.
3. Ako X_i i X_j obe sadrže teme v, tad svi čvorovi X_k od stabla u (jedinstvenoj) putanji između X_i i X_j takođe sadrže v. To jest, čvorovi povezani sa temenom v formiraju podskup od T. Ovo je poznato i kao povezanost, ili svojstvo raskrsnice. Jednako se može reći da, ako su $X_{i}$, $X_{j}$ i $X_{k}$ čvorovi, i $X_{k}$ je na putanji od $X_{i}$ do $X_{j}$, pa je $X_{i}\cap X_{j}\subseteq X_{k}$.

Stablo razlaganja grafa je daleko od jedinstvenog, na primer, trivijalano stablo razlaganja sadrži sve čvorove grafa u jednom svom osnovnom čvoru.

Stablo razlaganja u kojoj osnovni stabla je putanja grafa se zove put razlaganja, a parametar širine potiče iz ovih specijalnih vrsta stabala razlaganja poznat kao širina putanje.

Širina stabla

Širina stabla razlaganja je veličina njenog najvećeg skupa X_i minus jedan. Širina stabla tw(G) grafa G je minimalna širina među svim mogućim stabala razlaganja od G. U ovoj definiciji, veličina najvećeg skupa je smanjena za jedan kako bi se širina stabla od stabla bila jednak jedan. Širina može se definisati iz drugih struktura osim stabla razlaganja, uključujući i preko hordalni graf...

To je NP-kompletan problem da se odredi da li dati graf G ima najvišu širinu u datoj promenljivoj k.

Međutim, kad jek bilo koja fiksiran vrednost, graf sa širinomk može biti preoznat, i sa k stablom razlaganja formiranim za njega, u linearnom vremenu. Vreme izvršavanja algoritma za vrednost k je eksponencijalna.

Dinamičko programiranje

Početkom 1970-ih godina, uočeno je da se velika klasa problema kombinatorne optimizacije definisanih na grafovma može efikasno rešiti nelinearnim dinamičkim programiranjem, dokle god graf ima vezanu dimenziju, što je parametar vezan za širinu grafa. Kasnije, krajem 1980-ih, nekoliko autora je nezavisno uočilo da se mnogi algoritamski problemi koji su NP-kompletani za proizvoljne grafove mogu efikasno rešiti dinamičkim programiranjem za grafove ograničene širine korišćenjem stabla razlaganja grafova.

Kao primer, razmotrite problem nalaženja maksimuma nezavisnog skupa u grafu širine k. Da bi rešili problem, prvo odaberite jedan

As an example, consider the problem of finding the maximum independent set in a graph of treewidth k. To solve this problem, first choose one of the nodes of the tree decomposition to be the root, arbitrarily. For a node X_i of the tree decomposition, let D_i be the union of the sets X_j descending from X_i. For an independent set S ⊂ X_i, let A(S,i) denote the size of the largest independent subset I of D_i such that I ∩ X_i = S. Similarly, for an adjacent pair of nodes X_i and X_j, with X_i farther from the root of the tree than X_j, and an independent set S ⊂ X_i ∩ X_j, let B(S,i,j) denote the size of the largest independent subset I of D_i such that I ∩ X_i ∩ X_j = S. We may calculate these A and B values by a bottom-up traversal of the tree:

Literatura

• Arnborg, S.; Corneil, D.; Proskurowski, A. (1987), „Complexity of finding embeddings in a k-tree”, SIAM Journal on Matrix Analysis and Applications, 8 (2): 277—284, doi:10.1137/0608024 .
• Arnborg, S.; Proskurowski, A. (1989), „Linear time algorithms for NP-hard problems restricted to partial k-trees”, Discrete Applied Mathematics, 23 (1): 11—24, doi:10.1016/0166-218X(89)90031-0 .
• Bern, M. W.; Lawler, E. L.; Wong, A. L. (1987), „Linear-time computation of optimal subgraphs of decomposable graphs”, Journal of Algorithms, 8 (2): 216—235, doi:10.1016/0196-6774(87)90039-3 .
• Bertelé, Umberto; Brioschi, Francesco (1972), Nonserial Dynamic Programming, Academic Press, ISBN 978-0-12-093450-8 .
• Bodlaender, Hans L. (1988), „Dynamic programming on graphs with bounded treewidth”, Proc. 15th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, 317, Springer-Verlag, str. 105—118, doi:10.1007/3-540-19488-6_110 .
• Bodlaender, Hans L. (1996), „A linear time algorithm for finding tree-decompositions of small treewidth”, SIAM Journal on Computing, 25 (6): 1305—1317, doi:10.1137/S0097539793251219 .
• Diestel, Reinhard (2005), Graph Theory (3rd izd.), Springer, ISBN 978-3-540-26182-7 .
• Halin, Rudolf (1976), „S-functions for graphs”, Journal of Geometry, 8: 171—186 .
• Robertson, Neil; Seymour, Paul D. (1984), „Graph minors III: Planar tree-width”, Journal of Combinatorial Theory, Series B, 36 (1): 49—64, doi:10.1016/0095-8956(84)90013-3 .