雙寬度
無向圖的雙寬度是與圖相關的自然數，用於研究圖算法的參數化複雜性。直觀地，它測量了圖與Cograph的相似性，該圖可以通過反復將具有相同鄰居的頂點合併在一起，可以將其簡化為單個頂點。雙寬度是由一系列重複合併的序列定義的，其中不需要頂點是雙胞胎，而是具有幾乎相等的鄰居集。
定義
針對有限的簡單無向圖定義了雙寬度。這些具有有限的頂點，以及一組無序的頂點。任何頂點的開放社區是與圖形邊緣配對的其他頂點的集合。封閉的社區是由開放社區組成的，包括頂點本身。當有相同的封閉社區時，兩個頂點是真正的雙胞胎，而雙胞胎有相同的開放社區時。更一般而言，真正的雙胞胎和假雙胞胎都可以稱為雙胞胎，沒有資格。
這些Cographs具有許多等效的定義，但其中之一是這些圖可以通過反复找到任何兩個雙胞胎頂點並將它們合併到一個頂點的過程中將其簡化為單個頂點。對於Cograph來說，這種減少過程將始終成功，無論在每個步驟中都可以合併哪種雙胞胎。對於不是cograph的圖，它總是會陷入一個沒有雙胞胎的頂點的子圖中。
雙寬度模擬此還原過程的定義。在這種情況下，收縮序列是一系列步驟，從給定的圖開始，其中每個步驟用一個頂點替換一對頂點。這會產生一系列圖，邊緣為紅色和黑色。在給定的圖中，所有邊緣都被認為是黑色的。當兩個頂點被一個頂點替換時，新頂點的鄰居是替換頂點的鄰里的結合。在這個新的社區中，兩個頂點附近的黑色邊緣的邊緣仍然是黑色的。所有其他邊緣均為紅色。
收縮序列稱為
密集的圖仍然可能具有雙寬度；例如，Cographs包括所有完整的圖表。雙寬度，稀疏的雙寬度的變體適用於圖的家族，而不是單個圖。對於在誘發子圖中關閉並具有雙寬度的圖形家庭，以下特性是等效的：
- 家族中的圖形很少，這意味著它們具有許多邊緣的邊緣，其頂點數量的線性函數。
- 該家庭不包括所有完整的兩分圖。
- 給定家族中所有圖的所有子圖的家族都有雙寬度。
- 這個家庭的擴張有限，這意味著其所有淺未成年人都稀疏。
據說這樣的家庭有稀疏的雙寬度。
雙寬度的概念可以從圖形到各種完全有序的結構（包括配備了在其頂點上的總訂購）的概念，並且在許多方面，對於有序結構而言，與無序的圖相比，對有序結構更為簡單。也可以使用與界限不同的收縮序列為其他圖形序列制定其他圖形概念的等效定義。
有界雙寬度的圖
Cographs具有雙寬度為零。在減少Cographs的過程中，不會有紅色邊緣：當合併兩個頂點時，它們的鄰居相等，因此沒有一個邊緣來自兩個社區中的一個，即紅色。在任何其他圖中，任何收縮序列都會產生一些紅色邊緣，並且雙寬度將大於零。
最多三個頂點的路徑圖是Caphichs，但每個較大的路徑圖都具有雙寬度。對於反複合並路徑的最後兩個邊緣的收縮序列，只有向單個合併頂點的邊緣入射為紅色，因此這是1個序列。樹木最多具有雙寬度，而對於某些樹來說，這很緊。可以通過選擇一個根，然後反複合併兩個具有相同父母的葉子的葉子，或者如果不可能，將最深的葉子合併到其父母中，可以找到任何樹的2次收縮序列。唯一的紅色邊緣將葉子連接到父母，當兩個父母有兩個時，他們可以合併，最多保持紅色學位。
更一般地，以下圖的類別具有界限，並且在多項式時間內可以為它們找到有界寬度的收縮序列：
- 有界集團寬度或有界等級寬度的每個圖也都具有雙寬度。雙寬度最多是集團寬度的指數，在排名寬度中最多是雙重指數的。這些圖包括，例如，距離標記圖， k的有界值的k-葉冪以及有界樹寬的圖。
- 冷漠圖（等效地，單位間隔圖或正確的間隔圖）最多具有雙寬度。
- 由覆蓋平面每個點的單位磁盤集定義的單元磁盤圖a有界數的次數有界限。對於更高維度的單位球圖也是如此。
- 來自禁止排列模式的排列的置換圖具有雙寬度。這允許將雙寬度應用於禁止模式的排列算法問題。
- 禁止未成年人定義的每個圖表都有雙寬度。例如，通過瓦格納（Wagner）的定理，平面圖的禁止未成年人是兩個圖形
和
，因此平面圖具有雙寬度。
- 有限的堆棧號碼或有限的隊列號的每個圖也都具有界限雙寬度。存在沒有有限的堆棧數的有界稀疏雙寬度的圖形家庭，但隊列編號的相應問題仍然開放。
- 任何兩個有界雙寬度的圖形的強產物，其中一個具有有限的程度，再次界定了雙寬度。這可以用來證明將分解為強大的路徑和有界樹木圖的強產物（例如K-平面圖）的圖形類別的有界的雙寬度。對於圖的詞典產物，雙寬度正是兩個因子圖的寬度的最大值。在其他幾種標準圖產品下，雙寬度也表現得很好，而不是圖形的模塊化產品。
在每個有界雙寬度的圖表的遺傳家庭中，可以找到其圖形頂點的總訂單家庭，以便在誘導的子圖上的繼承訂購也是家庭中的訂購，以便家庭相對於這些命令很小。這意味著，總訂單
在以下圖中存在無界雙寬度的圖形：
在每種情況下，結果都取決於計數參數：給定類型的圖形多於有界的雙寬度圖。
特性
如果圖具有雙寬度，則可以找到一種通用的收縮樹。這是一個大型收縮序列，所有（較大的）有界寬度的所有（因此，在每個序列中的每個步驟中都有線性的許多分離對頂點，每個頂點都可以在序列的下一步中收縮。得出的是，任何一組都有界雙寬度的圖形數
演算法
最多可以在多項式時間識別雙寬度的圖。但是，確定給定的圖最多的四個寬度是NP完整的，而NP-HARD則以優於5/4的近似值比近似於雙寬度。在指數時間假設下，計算雙寬度需要至少時間指數
一旦給出或構建了收縮序列，就可以使用它來解決許多不同的算法問題，在許多情況下，與沒有有限的雙寬度的圖形相比，在許多情況下可以更有效地解決。如下所述，其中包括針對NP - 硬性問題的精確參數化算法和近似算法，以及一些具有經典多項式時間算法的問題，但可以使用有界雙寬度的假設加速。
參數化算法
具有關聯參數的圖形上的算法問題，如果它具有算法，則稱其為固定參數。 
具有給定收縮序列的有界雙寬度圖的固定參數可處理問題包括：
- 測試給定圖形是否在圖形的一階邏輯中模擬任何給定的屬性。在這裡，屬性的雙寬度和描述長度都是分析的參數。這種類型的問題包括針對有限尺寸的子圖的子圖同構，以及頂點覆蓋物和主導設置問題的覆蓋物或界限尺寸的主導集。這些一般方法對描述該屬性的邏輯公式長度的依賴性是四方的，但是對於獨立集，主導集和相關問題，可以將其減少為獨立或主導集的大小的指數，對於子學子構象構象。可以將其減少到子圖的頂點數量中。例如，是時候找到一個
，通過一種動態編程算法，該算法考慮了收縮序列的正向方向上的紅色圖的小連接子圖。在指數時間假設下，這些時間邊界是指數中最佳的，達到指數中的對數因素。為了將圖形的一階邏輯擴展到具有完全有序頂點的圖形，以及可以測試此順序的邏輯謂詞，模型檢查仍然是固定參數的固定參數，可用於有界雙寬的遺傳圖家族，但不在標準下（複雜性理論假設）對於無界雙寬的遺傳家庭。
- 有界雙寬度的著色圖，使用多種顏色，這些顏色受其雙寬度和最大群集大小的函數的界定。例如，雙寬度的三角形圖
- 由一種貪婪的著色算法顏色，該算法以收縮的順序為頂點著色。該結果表明，有界的雙寬度的圖是χ綁定的。對於有界稀疏雙寬度的圖形家族，廣義著色數是有界的。在這裡，廣義著色號碼
最多是
訂購中的早期頂點，通過長度路徑
通過訂購中的以後頂點。
經典算法的加速
在有界雙寬度的圖表中，可以在圖表上執行廣度優先搜索
近似算法
雙寬度也已用於近似算法。特別是，在有界雙寬度的圖中，可以找到具有有界近似比的最小主導設置的近似值。這與更通用的圖形相反，該圖是NP-獲得比對數更好的近似值比。
最大獨立集和圖形問題可以近似於
