樹寬
在圖理論中，無向圖的樹寬是一個整數編號，它非正式地指定該圖與樹的距離。最小的樹寬是1；帶有樹寬1的圖形恰好是樹木和森林。具有樹寬的圖最多為2個是串聯 - 並行圖。帶有樹寬的最大圖被稱為k樹，最多k的w寬度為k -樹被稱為部分k樹。許多其他良好的圖形家庭也具有界限。
樹寬可以以幾種等效的方式正式定義：根據圖中最大的頂點的大小，以圖形完成的最大集團的大小，就圖表的弦完成而言，就最大值而言避風港的順序描述了圖表上的追捕 - 逃避遊戲的策略，或者是在Bramble的最大順序上描述了一系列相互接觸的連接子圖的集合。
樹寬通常用作圖形算法的參數化複雜性分析中的參數。許多是通用圖的NP-算法的算法，當樹寬受常數界限時，變得更加容易。
Treewidth的概念最初是由UmbertoBertelè和Francesco Brioschi（ 1972 ）以Dimension的名義提出的。後來，它是由魯道夫·哈林（ Rudolf Halin ， 1976 ）重新發現的，它基於與不同的圖參數（ Hadwiger編號）共享的屬性。後來，尼爾·羅伯遜（Neil Robertson）和保羅·西摩（ Paul Seymour ， 1984 ）再次重新發現了它，此後已被許多其他作者研究。
定義
圖g =（ v ， e ）的樹分解是帶有nodes x 1 ，…， x n的樹t ，其中每個x i是v的子集，滿足以下屬性（該術語節點用於參考t的頂點，以避免與g的頂點混淆）：
- 所有集合的結合x i等於v 。也就是說，每個圖頂點至少包含一個樹節點。
- 如果X I和X J都包含一個頂點V ，則在X I和X J之間的（唯一）路徑中的所有節點X K也包含V。同等地，包含頂點v的樹節點形成了t的連接子樹。
- 對於圖中的每個邊緣（ v ， w ） ，都有一個子集x i同時包含v和w 。也就是說，僅當相應子樹具有共同點時，頂點才在圖中相鄰。
樹分解的寬度是其最大的集合x i負的大小。圖G的樹寬度TW（ g ）是G的所有可能樹分解的最小寬度。在此定義中，最大集的大小會減小一個，以使樹的樹寬等於一體。
同等地， G的樹寬比包含最小集團數字的G弦圖中最大集團的大小小。可以通過在每兩個屬於至少一個集合x i之一的每個兩個頂點之間添加g的邊緣來獲得帶有此集團大小的弦圖。
樹寬也可能是根據避風港的特徵來描述的，描述了在圖上定義的某些追求 - 逃避遊戲的逃避策略。 Graph G具有樹寬k ，並且僅當它具有k + 1訂單的天堂，但沒有更高順序，其中k + 1的天堂是一個函數β ，該函數β映射了g中的最多k個x的每個集合x G \ X的連接組件之一，並遵守每當x y時β （ y ） ⊆β （ x ）的單調性能。
也可以使用荊棘，連接的子圖的家族來進行類似的表徵，這些子圖都相互接觸（這意味著它們共享頂點或通過邊緣連接）。 Bramble的順序是用於子圖系列的最小擊球設置，並且圖的樹寬度比Bramble的最大順序小。
例子
每個完整的圖k n都有樹寬n - 1 。使用弦圖的定義，最容易看出這一點：完整的圖形已經是弦，並且添加更多的邊緣無法減少其最大集團的大小。
至少兩個頂點的連接圖具有樹寬1，並且僅當它是樹時。一棵樹具有與完整圖的相同推理（即，它是弦琴，並且具有最大列表尺寸）的相同推理。相反，如果圖具有循環，則該圖的每個和弦完成至少包含一個由三個連續的循環頂點組成的三角形，從而遵循其樹寬至少兩個。
有限的樹寬
圖形家庭有界限
對於任何固定常數k ，大多數k的樹寬圖稱為部分k樹。其他具有有界樹寬的圖的家族包括仙人掌圖，偽索，串聯 - 並聯圖，外平面圖， Halin圖和Apollonian網絡。在結構化程序的彙編中產生的控制流圖還具有有界的樹寬，它允許在它們上有效執行某些任務，例如寄存器分配。
平面圖沒有界限的樹寬，因為N × N網格圖是一個完全n的平面圖。因此，如果F是具有有界樹寬的次要圖形家族，則不能包括所有平面圖。相反，如果某些平面圖不能以family F中的圖形為輔助圖，則有一個恆定的k ，因此F中的所有圖最多都具有k 。也就是說，以下三個條件相當於彼此：
- f是一個有界樹的次要家族；
- 有限的眾多禁忌未成年人之一是平面。
- F是一個次要的圖形家族，不包括所有平面圖。
禁止的未成年人
對於K的每個有限值，最多K的TreeWidth圖的特徵是有限的禁止未成年人。 （也就是說，treewidth > k的任何圖都包含該集合中的一個圖形。）這些禁止的未成年人中的每一個都至少包含一個平面圖。
- 對於k = 1 ，唯一的禁止小調是一個3 vertex循環圖。
- 對於k = 2 ，獨特的禁止小調是4 vertex完整圖k 4 。
- 對於k = 3 ，有四個禁止的未成年人： k 5 ，八面體的圖，五邊形棱鏡圖和瓦格納圖。其中，兩個多面體圖是平面。
對於較大的K值，禁止未成年人的數量至少與K的平方根的指數一樣快地增長。但是，關於禁止未成年人的大小和數量的已知上限遠高於該下限。
演算法
計算樹寬
確定給定的圖G是否具有最多給定的變量k的NP完整。但是，當k是任何固定常數時，可以識別帶有樹寬k的圖，並在線性時間內為它們構建的寬度k樹分解。該算法對k的時間依賴性是指數的。
由於樹寬在大量字段中的作用，因此開發了計算圖形寬度的不同實用和理論算法。根據手頭上的應用程序，可以從輸入或樹寬寬度的大小中更喜歡更好的近似值，或者在運行時間內更依賴依賴性。下表提供了一些樹寬算法的概述。這裡k是樹寬， n是輸入圖g的頂點數。每種算法在時間f （ k ） β （ n ）時輸出近似柱中給出的寬度分解。例如， Bodlaender（1996）的算法在時間2 O （ k 3 ）中， n構建了寬度寬度的輸入圖G的樹分解，或者報告G的樹寬度大於k 。同樣， Bodlaender等人的算法。 （2016年）在時間2 O （ k ）中， n構建最多5 k + 4的輸入圖G的樹分解，或者報告G的樹寬大於k 。 Korhonen（2021）在同一運行時間將其提高到2 K + 1 。
| 近似 | f （ k ） | g （ n ） | 參考 |
|---|---|---|---|
| 精確的 | O(1) | o （ n k +2 ） | Arnborg，Corneil＆Proskurowowski（1987） |
| 4 K + 3 | O （3 3 K ） | O （ n 2 ） | Robertson＆Seymour（1995） |
| 8 K + 7 | 2 O （ k log k ） | n log 2 n | Lagergren（1996） |
| 5 K + 4 （或7 K + 6 ） | 2 O （ k log k ） | n log n | 里德（1992） |
| 精確的 | 2 O （ K 3 ） | 在） | Bodlaender（1996） |
 |
O(1) | n o （1） | Feige，Hajiaghayi＆Lee（2008） |
| 4.5 K + 4 | 2 3 k | n 2 | 阿米爾（2010） |
| 11/3 K + 4 | 2 3.6982 k | n 3 log 4 n | 阿米爾（2010） |
| 精確的 | O(1) | o （1.7347 N ） | Fomin，Todinca＆Villanger（2015） |
| 3 K + 2 | 2 O （ K ） | o （ n log n ） | Bodlaender等。 （2016） |
| 5 K + 4 | 2 O （ K ） | 在） | Bodlaender等。 （2016） |
| K 2 | O （ K 7 ） | o （ n log n ） | Fomin等。 （2018） |
| 5 K + 4 | 2 8.765 k | o （ n log n ） | Belbasi＆Fürer（2021a） |
| 2 K + 1 | 2 O （ K ） | 在） | Korhonen（2021） |
| 5 K + 4 | 2 6.755 k | o （ n log n ） | Belbasi＆Fürer（2021b） |
| 精確的 | 2 O （ K 2 ） | n 4 | Korhonen＆Lokshtanov（2022） |
（1+  ） k |
k o （ k / ） |
n 4 | Korhonen＆Lokshtanov（2022） |
尚不清楚確定平面圖的樹寬是NP庫的，還是可以在多項式時間內計算其樹寬。
在實踐中， Shoikhet＆Geiger（1997）的算法可以確定圖形的樹寬，最多100個頂點和最高11個寬度，並找到具有最佳樹寬的這些圖形的串聯完成。
對於較大的圖表，可以使用基於搜索的技術，例如分支和綁定搜索（BNB）以及最佳優先搜索來計算樹寬。這些算法是隨時隨地的，當它們提早停止時，它們將在樹寬上輸出上限。
Gogate和Dechter提出了用於計算樹寬的第一種BNB算法，稱為QuickBB算法。由於任何BNB算法的質量都高度依賴於所使用的下限的質量，因此Gogate和Dechter還提出了一種新型算法，用於計算較低的樹寬範圍，稱為次要最小程度。在高水平上，次要寬度算法結合了一個事實，即圖的樹寬永遠不會大於其最小程度或小型程度，以產生在樹寬的下限。次要寬度算法通過在最低度頂點和其一個鄰居之一之間收縮邊緣來反复構建圖形小調，直到僅保留一個頂點。這些構造的未成年人的最小程度的最大程度保證是圖表的樹寬的下限。
Dow和Korf使用最佳優先搜索改進了QuickBB算法。在某些圖上，這種最佳優先搜索算法比QuickBB快的數量級。
在小樹寬的圖表上解決其他問題
在1970年代初，觀察到，只要該圖具有有界的維度，就可以通過非序列動力學編程有效地解決一大批組合優化問題，可以有效地求解，這是Bodlaender所顯示的參數等於TreeWidth的參數。 （1998） 。後來，幾位作者在1980年代末獨立觀察到，使用這些圖的樹木分解，可以通過動態編程來有效地求解許多NP完整圖的算法問題。
例如，可以通過在圖表的樹分解上使用動態編程算法來求解樹寬k的圖。對於樹的分解的每組X I ，以及x i的頂點的每個分區中的每個分區，算法確定該顏色是否有效，可以通過結合類似信息的信息來擴展到樹分解中的所有後代節點計算並存儲在這些節點上的類型。所得算法在時間O （ k k + o （1） n ）中找到了n -vertex圖的最佳著色，這是使此問題固定參數可觸犯的時間結合。
Courcelle的定理
對於大量的問題，如果提供了具有恆定有界樹寬的樹狀分類，則有一個線性時間算法可以從類中解決問題。具體而言， Courcelle的定理指出，如果可以使用Monadic二階邏輯以圖形邏輯表達圖形問題，則可以在具有界面寬的圖形上以線性時間求解。 Monadic二階邏輯是一種描述使用以下結構的圖形屬性的語言：
- 邏輯操作，例如
- 會員測試，例如e∈E ， v∈V
- 對頂點，邊緣，頂點集和/或邊緣的定量，例如∀v∈V ， ∃e∈E ， ∃
- 鄰接測試（ U是E的端點），以及一些允許優化諸如事物的擴展。
例如，考慮圖形的三色問題。對於圖G =（ V ， e ） ，此問題詢問是否可以分配每個頂點V∈V3種顏色之一，因此沒有兩個相鄰的頂點分配給相同的顏色。該問題可以用單層次二階邏輯表示如下：
-
,
其中w 1 ， w 2 ， w 3表示具有3種顏色中每種的頂點的子集。因此，根據Courcelle的結果，可以在線性時間內解決三色問題，以給定圖形分解有界的恆定樹寬。
相關參數
路徑寬
圖的路徑通過樹通過樹的分解具有非常相似的定義，但僅限於樹分解，其中分解的基礎樹是路徑圖。另外，可以從間隔圖定義路徑寬，類似於弦圖的樹寬定義。結果，圖的路徑始終至少與其樹寬一樣大，但是只能通過對數因素更大。另一個參數是圖帶寬，具有適當的間隔圖的類似定義，並且至少與路徑寬一樣大。其他相關參數包括樹的深度，當且僅當家族排除路徑和退化時，該數字是針對次要閉合圖系列的數字，這是圖形的稀疏度的度量，最多等於其圖形樹寬。
網格小尺寸
由於N × N網格圖的樹寬為n ，因此圖G的樹寬始終大於或等於G的最大正方形網格小調的大小。在另一個方向上，羅伯遜（Robertson ）和西摩（ Seymour）的網格小學定理表明，存在一個無限的函數f ，使得最大的正方形網格小調的大小至少具有f （ r ） ，其中r是theewidth 。 F上已知的最佳界限是F對於某些固定常數d > 0 ，F必須至少為ω（ r d ） ，最多必須是
有關下限中的ω表示法，請參見大o符號。更緊密的界限以受限的圖表家庭而聞名，從而通過二維性理論為這些家族的許多圖形優化問題提供了有效的算法。 Halin的網格定理提供了無限圖的樹寬和網格小尺寸之間的關係的類似物。
直徑和局部樹寬
如果家族的圖中的圖形在上面的函數上，則據說在攝取子圖下關閉的圖形f構成了局部樹寬或直徑- 樹的屬性。如果假定該類在未成年人中也關閉，則F在且僅當F的未被禁止的未成年人是Apex圖的情況下，F具有本地樹寬的界限。該結果的原始證據表明，無頂點的圖中的樹寬家族在直徑的函數上最大程度地增長了。後來，這被簡化為單一指數，最後是線性結合。有界的本地樹寬與二維性算法理論密切相關，並且可以在只有略微超級線性的時間內確定一個無需頂級少量的圖形家族，以一階邏輯定義的每個圖形屬性。
一類未在未成年人中關閉的圖形也可以具有界限的本地樹寬。特別是，對於一類有界度圖的類別，這在界面直徑子圖中具有界限。另一個示例是由1平面圖給出的，可以在平面中以每個邊緣的一個交叉繪製的圖形，更通常是在可以在有界屬的表面上繪製的圖形，每個邊緣有一個有界數的交叉數。與有界局部樹寬的次要圖形家族一樣，此屬性指向了這些圖的有效近似算法的方式。
Hadwiger編號和S符號
Halin（1976）定義了他稱之為S-函數的一類圖形參數，其中包括樹寬。這些功能從圖到整數的函數必須在沒有邊緣的圖上為零，為少量 - 單酮（如果h是g是g的少數，一個函數f被稱為“次要單調”，則一個人具有f （ h ） ≤f （ g ） ），當添加與所有以前的頂點相鄰的新頂點時增加一個，並從集團分離器的兩側的兩個子圖中獲取更大的值。所有此類功能的集合在元素最小化和最大化的操作下形成了一個完整的晶格。該晶格中的最高元素是樹寬，底部元素是hadwiger編號，是給定圖中最大的完整未成年人的大小。