Разлагање стабла
У теорији графова, разлагање стабла је мапирање граф у стабло како би могл ода се користи како би се одредила ширина стабла од графа у како би се убрзао решавање одређених компјутерских проблема на графу.
У машинском учењу, стабло разлагања се такође зове стабло раскрсница, клика стабло, или спојена стабла, што значи да играју важну улогу у проблемима попут вероватноће закључака, задовољство ограничења, оптимизација упита и матрица разлагања.
Концепт стабла разлагања је првобитно увео Шаблон:Harvs. Касније је поново откривена од стране Нила Робертсона и Павла СимураШаблон:Harvs и од тада је проучаван од стране многих других аутора.
Дефиниција
Интуитивно, стабло разлагања представља темена датог графа G као подстабла главног стабла, тако да темена у датом графу су суседни само када одговарајућа подстабла секу. Дакле, G чини подграф од раскрснице графа од подстабала. Пун пресек граф хордални граф.
Сваки подстабло повезује графова темена са скупом чворова стабла. Да би дефинисали ово формално, што представићемо сваки чвор стабла као скуп темена у вези са њим.
Дакле, с обзиром на граф G = ( V, Е), стабло разлагања је пар (X, Т), где је X= {X1, .. Xn} је фамилија подскупа od V, и T је стабло чији чворови су подскупови Xi, задовољавајући следеће карактеристике:
- Унија свих скупова X i једнако V. То јест, свако темене графа је повезано са најмање једним чворем стабла.
- За сваку ивицу (v, w) на графу, постоји подскуп X i који садржи и v и w. То јест, чворови су суседна у графу само када одговарајућа подстабла имају заједнички чвор.
- Ако Xi и Xj обе садрже теме v, тад сви чворови Xk од стабла у (јединственој) путањи између Xi и Xj такође садрже v. То јест, чворови повезани са теменом v формирају подскуп од T. Ово је познато и као повезаност, или својство раскрснице. Једнако се може рећи да, ако су , и чворови, и је на путањи од до , па је .
Стабло разлагања графа је далеко од јединственог, на пример, тривијалано стабло разлагања садржи све чворове графа у једном свом основном чвору.
Стабло разлагања у којој основни стабла је путања графа се зове пут разлагања, а параметар ширине потиче из ових специјалних врста стабала разлагања познат као ширина путање.
Ширина стабла
Ширина стабла разлагања је величина њеног највећег скупа Xi минус један. Ширина стабла tw(G) графа G је минимална ширина међу свим могућим стабала разлагања од Г. У овој дефиницији, величина највећег скупа је смањена за један како би се ширина стабла од стабла била једнак један. Ширина може се дефинисати из других структура осим стабла разлагања, укључујући и преко хордални граф...
То је NP-комплетан проблем да се одреди да ли дати граф G има највишу ширину у датој променљивој k.
Међутим, кад јеk било која фиксиран вредност, граф са шириномk може бити преознат, и са k стаблом разлагања формираним за њега, у линеарном времену.[1] Време извршавања алгоритма за вредност k је експоненцијална.
Динамичко програмирање
Шаблон:Превод Почетком 1970-их година, уочено је да се велика класа проблема комбинаторне оптимизације дефинисаних на графовма може ефикасно решити нелинеарним динамичким програмирањем, докле год граф има везану димензију,Шаблон:Sfnp што је параметар везан за ширину графа. Касније, крајем 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: