樹分解

樹分解是圖子式理論中發展起來的一個重要概念。圖的樹分解由於其本身的特性使得它在算法設計中有著極其重要的意義。

基本介紹

• 中文名：樹分解
• 套用領域：計算機圖形學

研究概述

無論是在網路還是人工智慧套用中，抑或社會經濟領域，都存在著大量的組合最佳化問題，其中很多都是NP完全問題。求解這些NP完全問題，還沒有有效的確定性算法。過去在套用領域多採用近似算法求解，某些近似算法在實際套用中也確實能取得非常好的效果。近年來發展起來的參數計算理論對一些NP問題的求解提供了一些新的思路。伴隨著參數計算理論的發展，也產生了一些新的算法設計技巧和方法，如核心化、有限搜尋樹等。而在20世紀80年代發展起來的圖子式理論也為參數算法的研究提供了有力的支持。圖子式理論從一開始就與算法理論密切相關，並對算法研究產生了深遠的影響。一方面藉助圖子式理論可以用一種非構造的方式從理論上證明某些問題的參數算法的存在性；另一方面圖子式理論也發展出一些有效的算法設計技術，其中圖的樹寬和圖的樹分解是圖子式理論中引入的兩個重要概念。圖的樹寬和樹分解的引入給算法的分析和設計帶來了一些新的思路。某些NP問題，若將其限定在有限樹寬的圖中，則其求解是可行的。也就是說，通過對圖進行樹分解，若圖的樹寬是有限的，則存在有效的多項式求解算法，這對於很多場合的實際套用問題有著重要的意義。

圖的樹寬定義

圖子式理論是20世紀80年代發展起來的一個重要的圖理論分支，其理論體系散見於從1983年開始直至20餘篇論文中。從一開始，圖子式理論就受到了算法研究者的密切關注。參數計算研究的先驅Fellows等人在20世紀80年代末就研究了圖子式理論在算法設計和分析中的套用，藉助於該理論對眾多組合最佳化問題的判定問題給出了其多項式判定算法的存在性證明，並研究了如何將判定算法轉化為求最優解的構造性算法的方法。例如，對於最多葉子生成樹問題，給定一個圖集F，若F中的圖沒有哪一個具有一棵生成樹，使得該生成樹有大於等於k個葉子節點，則根據子式運算的規則，圖集F中任意圖的子式也不會有葉子節點數大於等於k的生成樹，這種特性稱為圖集F關於子式運算封閉。那么根據圖子式定理，圖集F的障礙集是有限的，而且可以在多項式時間內識別出這些障礙集，因此最多葉子生成樹問題可以在多項式時間內判定。

圖的樹分解算法

第一類是利用消元順序來構造樹分解的啟發式算法。所謂消元就是在無向圖G中刪除一個節點v以及與節點v關聯的邊，同時在剩下的圖中補充一些邊，使得v原來的鄰節點能構成一個團。通過在初始的圖G中逐個消元圖G的所有節點，就可以得到一個消元順序，根據這個消元順序便能構造出圖G的一個樹分解。問題的關鍵在於不同的消元順序可以得到不同的樹分解，而求解最優消元順序也是NP難的，所以也需要採用啟發式方法，如最大勢搜尋及其改進算法、詞典廣度優先搜尋、最小缺邊搜尋，以及其它一些利用消元順序的啟發式算法。

第二類是利用割集來構造樹分解的啟發式算法，即通過在初始圖中尋找一些割集來構造樹分解。所謂割集就是連通圖G的節點集的一個子集，記為S，若在原圖G中刪除S所包含的節點和關聯的邊，則剩餘圖變為至少兩個連通分量。這樣的節點集S稱為圖G的一個割集。