Кіріспе
Графты ағашқа бейнелеу. Графтардың ағаш құрылымы.
tree structure of graphs
Графтар теориясында, ағаш ыдырауы – графты ағашқа бейнелеу, оны графтың ағаш енін анықтауға және графтардағы белгілі бір есептеу мәселелерін жылдам шешуге пайдалануға болады. Ағаш ыдыраулары түйіспе ағаштар, клика ағаштар немесе қосылу ағаштар деп те аталады. Олар ықтималдық қорытынды, шектеулерді қанағаттандыру, сұранысты оңтайландыру және матрица ыдырау сияқты мәселелерде маңызды рөл атқарады. Ағаш ыдырау концепциясы алғаш рет [автор аты] енгізген, кейін [автор аты] қайта ашты және содан бері көптеген авторлар зерттеп келеді.
Ағаш ені
Ағаш бөлшегінің ені – ең үлкен жиынның мөлшерінен бір кем. Граф G-нің ағаш ені tw(G) – G-нің барлық мүмкін ағаш бөлшектері арасындағы ең төменгі ен. Бұл анықтамада ең үлкен жиынның мөлшері бірге кемітіледі, себебі ағаштың ағаш ені біреуге тең болсын деген талап бар. Ағаш ені ағаш бөлшектерінен өзге де құрылымдар арқылы анықталуы мүмкін, олардың ішінде хордалық графтар, бұталар және отарлар бар. Берілген граф G-нің ағаш ені k-дан аспайтынын анықтау NP-толық мәселе. Дегенмен, егер k кез келген тұрақты сан болса, онда k ағаш ені бар графтарды тануға болады және олар үшін сызықтық уақытта k ені бар ағаш бөлшегін құруға болады. Көптеген алгоритмдік мәселелер, кездейсоқ графтар үшін NP-толық болса, шектелген ағаш ені бар графтар үшін осы графтардың ағаш бөлшектерін пайдаланып, динамикалық бағдарламалау арқылы тиімді шешілуі мүмкін. Мысалы, ағаш ені k болатын графтағы ең үлкен тәуелсіз жиынды табу мәселесін қарастырайық. Бұл мәселені шешу үшін, ең алдымен ағаш бөлшегінің бір түйінін тамыр ретінде кездейсоқ таңдаңыз. Ағаш бөлшегінің түйіні үшін, S жиынынан басталатын ең үлкен тәуелсіз I жиынтығының мөлшерін A(S,i) деп белгілейік. Сол сияқты, екі іргелес түйін үшін, және , егер түйін тамырдан түйінден алыс болса, және тәуелсіз жиын үшін B(S,i,j) ең үлкен тәуелсіз I жиынтығының мөлшерін білдірсін. Біз осы A және B мәндерін ағаштың төменгі жағынан жоғары қарай есептей аламыз: мұнда есептеудегі сома түйіннің барлық балалары бойынша алынады. Әр түйінде немесе жиекте, осы мәндерді есептеуге қажетті ең көп S жиыны болады, сондықтан егер k тұрақты болса, онда бүкіл есептеу әр жиекке немесе түйінге тұрақты уақыт алады. Ең үлкен тәуелсіз жиынның мөлшері – тамыр түйінінде сақталған ең үлкен мән, ал ең үлкен тәуелсіз жиынның өзін осы ең үлкен мәннен басталатын сақталған мәндер арқылы кері қарай іздеу арқылы табуға болады (динамикалық бағдарламалау алгоритмдеріндегідей). Осылайша, шектелген ағаш ені бар графтарда ең үлкен тәуелсіз жиынды табу мәселесі сызықтық уақытта шешіледі. Осыған ұқсас алгоритмдер басқа да көптеген графтардағы мәселелерге қолданылады. Бұл динамикалық бағдарламалау тәсілі машиналық оқытуда, торап ағашы алгоритмі арқылы, шектелген ағаш ені бар графтарда сенім тарату үшін қолданылады. Ол сондай-ақ ағаш енін есептеу және ағаш бөлшегін құру алгоритмдерінде маңызды рөл атқарады: әдетте, мұндай алгоритмдерде ағаш енін жуықтап бағалаудың бірінші қадамы болады, осы жуықталған ені бар ағаш бөлшегін құрастырады, содан кейін ағаш енінің нақты мәнін есептеу үшін жуықталған ағаш бөлшегінде динамикалық бағдарламалауды орындайтын екінші қадам болады.
However, when k is any fixed constant, the graphs with treewidth k can be recognized, and a width k tree decomposition constructed for them, in linear time. that many algorithmic problems that are NP complete for arbitrary graphs may be solved efficiently by dynamic programming for graphs of bounded treewidth, using the tree decompositions of these graphs. 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 of the tree decomposition, let be the union of the sets descending from For an independent set let A(S,i) denote the size of the largest independent subset I of such that Similarly, for an adjacent pair of nodes and , with farther from the root of the tree than , and an independent set let B(S,i,j) denote the size of the largest independent subset I of such that We may calculate these A and B values by a bottom up traversal of the tree:
where the sum in the calculation of is over the children of node
At each node or edge, there are at most sets S for which we need to calculate these values, so if k is a constant then the whole calculation takes constant time per edge or node. The size of the maximum independent set is the largest value stored at the root node, and the maximum independent set itself can be found (as is standard in dynamic programming algorithms) by backtracking through these stored values starting from this largest value. Thus, in graphs of bounded treewidth, the maximum independent set problem may be solved in linear time. Similar algorithms apply to many other graph problems. This dynamic programming approach is used in machine learning via the junction tree algorithm for belief propagation in graphs of bounded treewidth. It also plays a key role in algorithms for computing the treewidth and constructing tree decompositions: typically, such algorithms have a first step that approximates the treewidth, constructing a tree decomposition with this approximate width, and then a second step that performs dynamic programming in the approximate tree decomposition to compute the exact value of the treewidth.