Разлагање стабла

С Википедије, слободне енциклопедије
Граф са осам темена, и његово разлагање на стабло са шест чворова. Сваки ивица графа спаја два темена који се налазе заједно у неком чвору стабла, и свако теме графа је наведен у чворовима суседних подстабала дрвета. Сваки чвор стабла садржи највише три темена, па је ширина овог разлагања два.

У теорији графова, разлагање стабла је мапирање граф у стабло како би могл ода се користи како би се одредила ширина стабла од графа у како би се убрзао решавање одређених компјутерских проблема на графу.

У машинском учењу, стабло разлагања се такође зове стабло раскрсница, клика стабло, или спојена стабла, што значи да играју важну улогу у проблемима попут вероватноће закључака, задовољство ограничења, оптимизација упита и матрица разлагања.

Концепт стабла разлагања је првобитно увео Рудолф Халин (1976). Касније је поново откривена од стране Нила Робертсона и Павла Симура (1984) и од тада је проучаван од стране многих других аутора.

Дефиниција[уреди | уреди извор]

Интуитивно, стабло разлагања представља темена датог графа G као подстабла главног стабла, тако да темена у датом графу су суседни само када одговарајућа подстабла секу. Дакле, G чини подграф од раскрснице графа од подстабала. Пун пресек граф хордални граф.

Сваки подстабло повезује графова темена са скупом чворова стабла. Да би дефинисали ово формално, што представићемо сваки чвор стабла као скуп темена у вези са њим.

Дакле, с обзиром на граф G = ( V, Е), стабло разлагања је пар (X, Т), где је X= {X1, .. Xn} је фамилија подскупа od V, и T је стабло чији чворови су подскупови Xi, задовољавајући следеће карактеристике:

  1. Унија свих скупова X i једнако V. То јест, свако темене графа је повезано са најмање једним чворем стабла.
  2. За сваку ивицу (v, w) на графу, постоји подскуп X i који садржи и v и w. То јест, чворови су суседна у графу само када одговарајућа подстабла имају заједнички чвор.
  3. Ако Xi и Xj обе садрже теме v, тад сви чворови Xk од стабла у (јединственој) путањи између Xi и Xj такође садрже v. То јест, чворови повезани са теменом v формирају подскуп од T. Ово је познато и као повезаност, или својство раскрснице. Једнако се може рећи да, ако су , и чворови, и је на путањи од до , па је .

Стабло разлагања графа је далеко од јединственог, на пример, тривијалано стабло разлагања садржи све чворове графа у једном свом основном чвору.

Стабло разлагања у којој основни стабла је путања графа се зове пут разлагања, а параметар ширине потиче из ових специјалних врста стабала разлагања познат као ширина путање.

Ширина стабла[уреди | уреди извор]

Ширина стабла разлагања је величина њеног највећег скупа Xi минус један. Ширина стабла tw(G) графа G је минимална ширина међу свим могућим стабала разлагања од Г. У овој дефиницији, величина највећег скупа је смањена за један како би се ширина стабла од стабла била једнак један. Ширина може се дефинисати из других структура осим стабла разлагања, укључујући и преко хордални граф...

То је NP-комплетан проблем да се одреди да ли дати граф G има највишу ширину у датој променљивој k.

Међутим, кад јеk било која фиксиран вредност, граф са шириномk може бити преознат, и са k стаблом разлагања формираним за њега, у линеарном времену.[1] Време извршавања алгоритма за вредност k је експоненцијална.

Динамичко програмирање[уреди | уреди извор]

Почетком 1970-их година, уочено је да се велика класа проблема комбинаторне оптимизације дефинисаних на графовма може ефикасно решити нелинеарним динамичким програмирањем, докле год граф има везану димензију,[2] што је параметар везан за ширину графа. Касније, крајем 1980-их, неколико аутора је независно уочило да се многи алгоритамски проблеми који су НП-комплетани за произвољне графове могу ефикасно решити динамичким програмирањем за графове ограничене ширине коришћењем стабла разлагања графова.

Као пример, размотрите проблем налажења максимума независног скупа у графу ширине k. Да би решили проблем, прво одаберите један

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 Xi of the tree decomposition, let Di be the union of the sets Xj descending from Xi. For an independent set SXi, let A(S,i) denote the size of the largest independent subset I of Di such that IXi = S. Similarly, for an adjacent pair of nodes Xi and Xj, with Xi farther from the root of the tree than Xj, and an independent set SXiXj, let B(S,i,j) denote the size of the largest independent subset I of Di such that IXiXj = S. We may calculate these A and B values by a bottom-up traversal of the tree:

Референце[уреди | уреди извор]

Литература[уреди | уреди извор]

  • 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, стр. 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 изд.), 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 .