拆分圖
在圖理論中，數學的分支，一個拆分圖是一個圖形，可以將頂點分配到一個集團和獨立集中。首先研究了拆分圖，由Földes和Hammer （ 1977a ， 1977b ）研究，並由Tyshkevich和Chernyak（ 1979 ）獨立引入，在那裡他們稱這些圖為“極地圖”（俄語：μby：μbian：μbly：μby 。
拆分圖可能將一個以上的分區分為一個集團和獨立集。例如，路徑A - B - C是一個拆分圖，其頂點可以通過三種不同的方式進行分區：
- 集團{ a ， b }和獨立集{ C }
- 集團{ b ， c }和獨立集{ a }
- 集團{ b }和獨立集{ a ， c }
可以根據其禁止誘導的子圖表來表徵拆分圖：當且僅當沒有誘導的子圖是四個或五個頂點上的一個循環時，圖形是分開的，或一對脫節邊緣（4個週期的補充）。
與其他圖表家庭的關係
從定義來看，拆分圖在互補下明顯關閉。拆分圖的另一個表徵涉及互補：它們是和弦圖，其互補也是弦。正如弦圖是樹的子樹的相交圖一樣，拆分圖是恆星圖的不同物質的相交圖。幾乎所有的和弦圖都是拆分圖。也就是說，在n到達無限的極限中， n- vertex弦圖的分數分為一個接近一個。
因為弦圖是完美的，因此分式圖也是如此。雙拆分圖是一個從拆分圖中得出的一系列圖形，通過將每個頂點加倍（因此，該集團來誘導反場合，獨立集來誘導匹配），這是五個基本的完美圖中的五個基本類別之一。所有其他都可以在Chudnovsky等人的證明中形成。 （2006年）的強度完美理論定理。
如果圖既是拆分圖和間隔圖，則其補充既是拆分圖，又是可比性圖，反之亦然。拆分可比性圖以及拆分間隔圖也可以通過三個禁止誘導的子圖表來表徵。分裂的塞施儀正是閾值圖。拆分置換圖完全是具有間隔圖互補的間隔圖。這些是偏斜置換的排列圖。拆分圖具有凝膠數字2。
算法問題
令G為拆分圖，將分區分為集團C和一個獨立的集合i 。然後，拆分圖中的每個最大集團都是C本身，也可以是i中的頂點的鄰域。因此，很容易識別最大集團，並在拆分圖中補充最大獨立集。在任何拆分圖中，以下三種可能性之一必須為真：
- 在i中存在一個頂點X ，使得c∪ { x }已完成。在這種情況下， c∪ { x }是一個最大集團，我是最大獨立集。
- 在C中存在一個頂點X ，使得我是獨立的。在這種情況下， i∪ { x }是最大獨立集， C是最大集團。
- C是最大集團，我是最大獨立集。在這種情況下， g在一個集團中具有獨特的分區（ c ， i ） ，而獨立的集合C是最大組合，而我是最大獨立集。
在包括圖形上色在內的更通用的圖形家族上NP完整的一些其他優化問題同樣直接在拆分圖上。即使對於強烈的和弦圖的拆分圖，找到哈密頓循環仍然是NP完整的。眾所周知，最小主導設置問題仍然是分裂圖的NP完整問題。
度序列
拆分圖的一個顯著特性是，它們只能從其度序列中識別。讓圖G的度序列為d1≥d2≥ … ≥d n ，讓m為i的最大值，以使di≥i - 1 。然後，當g是一個拆分圖時，僅當
如果是這種情況，則最大程度的M頂點在G中形成最大集團，其餘頂點構成獨立集。
任意圖的分佈衡量這種不平等的程度未能實現。如果圖不是拆分圖，則可以通過在最大程度的M頂點之間添加所有缺少的邊緣來獲得最小的邊緣插入和移除序列的序列，並將其刪除所有邊緣之間的所有丟失的邊緣，並刪除所有邊緣之間的所有邊緣剩餘的頂點；分組計算此序列中的操作數量。
計數拆分圖
Royle（2000）表明（未標記的） n -vertex拆分圖與某些sperner家族一對一。利用這一事實，他確定了N頂點上非形態拆分圖的數量的公式。對於n的小值，從n = 1開始，這些數字為
Tyshkevich＆Chernyak（1990）也早些時候證明了這一枚舉結果。