基本介紹
單純分解
單純分解
單純分解
單純分解設 是一個圖， 為一個序數，對於任何 ，記B為G的導出子圖，一個圖族 若滿足下列三個條件，則稱為G的一個 單純分解：
單純分解1. ；
單純分解
單純分解
單純分解
單純分解
單純分解
單純分解
單純分解2.對任何 ， 是一個完全圖，其中，兩個圖 和 的交 (當 時簡記為 )；
單純分解3.對任何 ，S既不包含B又不包含B。
單純分解G的一個由它的導出子圖組成的圖族 ，若除了以上三個條件，它還滿足下列條件，則稱F是G的一個 樹-分解。
單純分解
單純分解4.對任何 ，S包含在某 中，和上面的條件1(注意，不一定滿足條件2或3)。
單純分解
單純分解
單純分解若 是圖G的一個單純分解並且它還滿足條件4，則稱之為G的 單純樹分解。或者說，G的一個單純樹分解就是滿足條件2和3的樹-分解，一個樹分解 的寬度就是 ，其中，|B|為B的階，所謂G的樹寬就是G的所有可能樹分解的寬度的最小值；或者說，這樣的最小整數k使得G有一個樹分解，其中的每個導出子圖至多是k+1階，G的分解中的導出子圖稱為因子 。
樹分解與樹寬
說圖1中畫的圖G可以用樹形方式分解，我們一直在沿著這樣的線索考慮。如果我們遇到像圖1(a)中那樣畫的G，可能不能馬上看出它為什麼能這樣分解，但是用圖1(b)中的畫法，我們看到G確實由10個互鎖的三角形組成，其中有7個三角形具有這樣的性質，如果刪去它們，則G剩餘的部分分成不連線的片斷，這些片斷遞歸地具有這種互鎖三角形的結構，其他3個三角形附加在末端，刪去它們有些像刪去樹的樹葉 。
 圖1（a） |  圖1（b） |  圖1（c） |
(*圖1 (a)和(b)描述同一個圖的兩種不同畫法，(b)中的畫法強調它由10個互鎖的三角形組成，(c)說明這10個三角形如何結合在一起。)
因此，如果不是(像通常那樣)把G看做由12個結點組成的，而是由10個三角形組成的，則G是樹形的，儘管G明顯地包含許多圈，但是，如果在這10個三角形的水平上看直觀上好像沒有圈，從而它有樹的許多良好的分解性質。
我們要給出這些三角形的樹形結構，每一個三角形對應樹的一個結點，像圖1(c)中所示的那樣，直觀上，這個圖中的樹對應圖G，每一個結點對應一個三角形，但是要注意，G的同一個結點出現在多個三角形中，甚至出現在樹結構中不相鄰的結點中；在樹結構中離得很遠的三角形中的結點之間可能有邊，例如，中心的三角形有邊與其他每一個三角形的結點連線，怎么準確地對應這棵樹和圖G?為此我們介紹圖G的樹分解，這個名字來自我們將試圖按照樹形模式分解G．。
單純分解
單純分解
單純分解
單純分解形式地， 的樹分解由樹T(在G的不同的結點集合上)和T的每一個結點t關聯的子集 構成。(我們稱這些子集V是樹分解的“片斷”)有時把它寫成有序對，樹T和片斷集必須滿足下述3個條件：
1.(結點覆蓋)G的每一個結點至少屬於一個片斷V。
2.(邊覆蓋)對G的每一條邊e，存在一個片斷V包含e的兩個端點。
單純分解
單純分解
單純分解3.(一致性)設和t是T的3個結點，t₂在t₁到t₃的路徑上，那么，如果G的結點v屬於，則它也屬於。
驗證一下用10個三角形作為片斷，圖1(c)中的樹是(b)(和(a))中圖的樹分解。
單純分解
單純分解
單純分解
單純分解
單純分解
單純分解下面考慮圖G是一棵樹的情況，可以如下構造它的樹分解。對G的每一個結點v，樹分解T有一個結點，對G的每一條邊e，T有一個結點，當v是e的一個端點時，樹T有一條邊。最後，如果v是一個結點，則定義片斷；如果是一條邊，則定義片斷，可以驗證樹分解定義中的3條性質都滿足 。
