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

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

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

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

Концепт стабла разлагања је првобитно увео Рудолф Халин (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. This is also known as coherence, or the running intersection property. It can be stated equivalently that if X_i, X_j и X_k су чворови, и X_k је на путањи од X_i до X_j, па је X_i \cap X_j \subseteq X_k.

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

Ширина стабла[уреди]

Ширина стабла разлагања је величина њеног највећег скупа 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 S ⊂ Xi, let A(S,i) denote the size of the largest independent subset I of Di such that I ∩ Xi = 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 S ⊂ Xi ∩ Xj, let B(S,i,j) denote the size of the largest independent subset I of Di such that I ∩ Xi ∩ Xj = 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 0-12-093450-7 .
  • 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, pp. 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 ed.), Springer, ISBN 3-540-26182-6 .
  • 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 .