若圖 $G$ 上面的點集合存在一種方法被拆成一個（可能為空的）完全子圖與一個（可能為空）的獨立集，那麼我們說圖 $G$ 是一個分割圖（split graph）。
§9.1 分割圖的辨認
這件事情可以透過觀察度序列來得知：
換句話說，度數大的點都會屬於完全子圖、而度數小的點都會屬於獨立集。
§9.2 分割圖的性質
| 演算法問題 | On Split Graphs |
|---|---|
| Clique Number / 找出所有極大完全子圖 | 簡單 |
| Chromatic Number / 圖著色 | 簡單 |
| HamiltonianCycle | $\textsf{NP}$-complete |
| MinimumDominatingSet | $\textsf{NP}$-complete (從 SetCover reduce) |
§9.3 分割圖的計數
有標號的分割圖很簡單，這個大家自己算就可以了。
無標號的分割圖 (non-isomorphic)
無標號分割圖的數量，在 2000 年由 UWA 西澳大學數學統計系的 Gordon Royle 教授提出了一個「$n$ 個點的分割圖」與「$n$ 個物件的非同構極小覆蓋集合」之間的一對一對應關係。所謂的極小覆蓋集合，就是考慮若干非空集合 $S_1, \ldots, S_k \subseteq [n]$，它們聯集包含所有 $[n]={1, 2, \ldots, n}$，但拿掉任何一個集合都湊不齊 $[n]$。
關於將 $n$ 個物件使用 $k$ 個集合最小覆蓋的方法數，已由當年在阿德萊德大學現在在澳洲伍倫貢大學的 Rodney J. Clarke 教授在 1990 年寫下其公式：
$$ t(n, k) = \frac{1}{n!k!}\sum_{\alpha\in \mathcal{P}_n, \beta\in\mathcal{P}k} {n\choose \alpha}{k\choose \beta} \prod_i \left(\left( \prod{j} 2^{\gcd(\alpha_i, \beta_j)}\right) - 1 \right) $$
有興趣的朋友可以直接從 OEIS A048194 查看 Split Graph 的計數。
練習題
- 程設題 [UOJ 1974] Into Darkness
- 程設題 [POI 18 Stage 1] Conspiracy
- 程設題 [NAIPC 2018 pB] Double Clique
- 證明題 證明圖 $G$ 是分割圖若且唯若 $G$ 與 $\overline{G}$ 都是弦圖(Chordal)。