單純分解(simplicial decomposition)是圖的一種分解，單純樹分解是單純分解的一種。
基本介紹
- 中文名：單純分解
- 外文名：simplicial decomposition
- 所屬學科：數學
- 所屬問題：組合學(圖與超圖)
- 簡介：圖的一種分解
基本介紹,樹分解與樹寬,
基本介紹
1.
；
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)和(b)描述同一個圖的兩種不同畫法，(b)中的畫法強調它由10個互鎖的三角形組成，(c)說明這10個三角形如何結合在一起。)
因此，如果不是(像通常那樣)把G看做由12個結點組成的，而是由10個三角形組成的，則G是樹形的，儘管G明顯地包含許多圈，但是，如果在這10個三角形的水平上看直觀上好像沒有圈，從而它有樹的許多良好的分解性質。
我們要給出這些三角形的樹形結構，每一個三角形對應樹的一個結點，像圖1(c)中所示的那樣，直觀上，這個圖中的樹對應圖G，每一個結點對應一個三角形，但是要注意，G的同一個結點出現在多個三角形中，甚至出現在樹結構中不相鄰的結點中；在樹結構中離得很遠的三角形中的結點之間可能有邊，例如，中心的三角形有邊與其他每一個三角形的結點連線，怎么準確地對應這棵樹和圖G?為此我們介紹圖G的樹分解，這個名字來自我們將試圖按照樹形模式分解G．。
形式地，
的樹分解由樹T(在G的不同的結點集合上)和T的每一個結點t關聯的子集
構成。(我們稱這些子集Vt是樹分解的“片斷”)有時把它寫成有序對
，樹T和片斷集
必須滿足下述3個條件：
1.(結點覆蓋)G的每一個結點至少屬於一個片斷Vt。
2.(邊覆蓋)對G的每一條邊e，存在一個片斷Vt包含e的兩個端點。
3.(一致性)設
和t3是T的3個結點，t2在t1到t3的路徑上，那么，如果G的結點v屬於
，則它也屬於
。
驗證一下用10個三角形作為片斷，圖1(c)中的樹是(b)(和(a))中圖的樹分解。
下面考慮圖G是一棵樹的情況，可以如下構造它的樹分解。對G的每一個結點v，樹分解T有一個結點
，對G的每一條邊e，T有一個結點
，當v是e的一個端點時，樹T有一條邊
。最後，如果v是一個結點，則定義片斷
；如果
是一條邊，則定義片斷
，可以驗證樹分解定義中的3條性質都滿足。
