最大独立集合と最小頂点被覆

小さなグラフの独立数 $α (G)$ を、2 つの評価を合わせて求められる。下からは独立集合を構成し、上からは頂点を辺・クリーク・閉路で覆って評価する。さらに $α (G) + τ (G) = ∣ V ∣$ から、最小頂点被覆の大きさ $τ (G)$ を求められる

前提

グラフの次数と握手補題（大学数学グラフ理論）

この技能までの道筋（6 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
グラフの次数と握手補題（大学数学グラフ理論）

説明

グラフ $G = (V, E)$ の頂点の部分集合 $S$ で、 $S$ のどの 2 頂点も辺で結ばれていないものを独立集合といいます。独立集合の最大の大きさを独立数 $α (G)$ と書きます。また、すべての辺について少なくとも一方の端点を含む頂点の部分集合を頂点被覆といい、その最小の大きさを $τ (G)$ と書きます。この技能では、「独立集合を実際に作る（下からの評価）」と「頂点をクリークや閉路で覆う（上からの評価）」を組み合わせて小さなグラフの $α (G)$ を確定させ、さらに $α (G) + τ (G) = ∣ V ∣$ を使って $τ (G)$ も求めます。

なぜそうしてよいのか

$α (G) = a$ を示すには、2 つのことが必要です。(1) 大きさ $a$ の独立集合が実際にある（だから $α (G) \geq a$ ）。(2) どんな独立集合も大きさ $a$ 以下である（だから $α (G) \leq a$ ）。(1) は例を 1 つ挙げれば済みます。(2) には次の考え方を使います。頂点集合を部分 $P_{1}, \dots, P_{k}$ で覆い（ $V = P_{1} \cup \dots \cup P_{k}$ ）、各 $P_{i}$ に独立集合 $S$ の頂点が高々 $c_{i}$ 個しか入らないことがわかれば、 $∣ S ∣ \leq ∣ S \cap P_{1} ∣ + \dots + ∣ S \cap P_{k} ∣ \leq c_{1} + \dots + c_{k}$ です。部分として便利なのは次の 3 種類です。
・クリーク（どの 2 頂点も隣接している頂点の集まり。 $1$ 本の辺の両端や三角形もこれにあたります）：独立集合は高々 $1$ 頂点しか含めません。
・閉路 $v_{1} v_{2} \dots v_{k} v_{1}$ （ $v_{i}$ と $v_{i + 1}$ 、 $v_{k}$ と $v_{1}$ が隣接）：独立集合が $v_{i}$ を含めば、その次の $v_{i + 1}$ （ $v_{k}$ の次は $v_{1}$ ）は含みません。「選んだ頂点 → その次の頂点」は異なる頂点を異なる選ばれていない頂点に移すので、選んだ個数 $\leq$ 選ばれていない個数。よって $2∣ S \cap C ∣ \leq k$ 、すなわち $∣ S \cap C ∣ \leq ⌊ k /2 ⌋$ です（例えば $5$ 頂点の閉路なら $2$ 個まで）。
・どこにも入らない残りの $1$ 頂点：もちろん高々 $1$ 個です。

次に $α (G) + τ (G) = ∣ V ∣$ の理由です。 $S \subseteq V$ とその補集合 $T = V ∖ S$ について、「 $T$ が頂点被覆」⇔「どの辺も $T$ に端点をもつ」⇔「両端点がともに $S$ に入る辺がない」⇔「 $S$ が独立集合」です。つまり独立集合と頂点被覆は補集合をとることで 1 対 1 に対応し、 $∣ T ∣ = ∣ V ∣ - ∣ S ∣$ なので、 $∣ S ∣$ を最大にすることと $∣ T ∣$ を最小にすることは同じです。よって $τ (G) = ∣ V ∣ - α (G)$ となります。

手順

独立集合をうまく 1 つ作り、その大きさ $a$ を得る： $α (G) \geq a$ （作った集合のどの 2 頂点も辺で結ばれていないことを辺の一覧で確認する）
頂点全体をクリーク（辺・三角形など）・閉路・残りの 1 頂点で覆う： $V = P_{1} \cup \dots \cup P_{k}$
各部分の上限 $c_{i}$ を書く（クリークは $1$ 、 $k$ 頂点の閉路は $⌊ k /2 ⌋$ 、1 頂点は $1$ ）。合計して $α (G) \leq c_{1} + \dots + c_{k}$
下からの値と上からの値が一致すれば $α (G)$ が確定。一致しなければ独立集合か覆い方を作り直す
必要なら $τ (G) = ∣ V ∣ - α (G)$ を計算する。最小頂点被覆は最大独立集合の補集合として得られる

例題

頂点集合 $V = {1, 2, 3, 4, 5, 6, 7, 8}$ 、辺集合 $E = {12, 23, 34, 45, 51, 67, 78, 86, 16, 37}$ のグラフ $G$ について（ $ij$ は頂点 $i$ と $j$ を結ぶ辺）、最小頂点被覆の大きさ $τ (G)$ を求めよ。

例題の解答

【手順 1：下からの評価】 $S = {1, 3, 8}$ を考える。頂点 $1$ の隣は $2, 5, 6$ 、頂点 $3$ の隣は $2, 4, 7$ 、頂点 $8$ の隣は $6, 7$ なので、 $1, 3, 8$ のどの 2 つも隣接しない。よって $S$ は独立集合で $α (G) \geq 3$ 。
【手順 2：覆う】辺 $12, 23, 34, 45, 51$ より $1 - 2 - 3 - 4 - 5 - 1$ は $5$ 頂点の閉路 $C$ 。辺 $67, 78, 86$ より ${6, 7, 8}$ は三角形（クリーク） $K$ 。 $V = C \cup K$ で全頂点を覆えている。
【手順 3：上限の合計】 $C$ には独立集合の頂点が高々 $⌊ 5/2 ⌋ = 2$ 個、 $K$ には高々 $1$ 個。よって $α (G) \leq 2 + 1 = 3$ 。
【手順 4：確定】下からも上からも $3$ なので $α (G) = 3$ 。
【手順 5】 $τ (G) = ∣ V ∣ - α (G) = 8 - 3 = 5$ 。実際、 $S$ の補集合 ${2, 4, 5, 6, 7}$ は 10 本の辺すべての端点を少なくとも 1 つ含む頂点被覆になっている。

答え: $5$

よくある誤り

これ以上頂点を付け加えられない独立集合を見つけただけで最大だと決めてしまう誤り。例えば星 $K_{1, 3}$ で中心 ${c}$ は付け加えられない独立集合だが大きさ $1$ で、葉 3 つの独立集合の方が大きい。正しくは、上からの評価（覆い）で同じ値が出たときに初めて $α (G)$ が確定する。
奇数頂点の閉路の上限を切り上げてしまう誤り。 $5$ 頂点の閉路に独立な頂点を $3$ 個置けるとするのは誤りで、正しくは $⌊ 5/2 ⌋ = 2$ 個まで（ $2∣ S \cap C ∣ \leq 5$ より）。
覆いから漏れた頂点を数え忘れる誤り。例えば三角形 ${1, 2, 3}$ だけで ${1, 2, 3, 4}$ を評価して $α \leq 1$ とするのは誤りで、正しくは残りの頂点 $4$ の分 $1$ を足して $α \leq 1 + 1 = 2$ 。
頂点被覆の大きさを辺の数から引いて $τ (G) = ∣ E ∣ - α (G)$ としてしまう誤り。独立集合の補集合が頂点被覆なので、正しくは頂点数を使って $τ (G) = ∣ V ∣ - α (G)$ （例題なら $10 - 3$ ではなく $8 - 3 = 5$ ）。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

最大マッチングとケーニヒの定理（大学数学グラフ理論）
頂点彩色と彩色数（大学数学グラフ理論）
整数計画の線形計画緩和と整数性（大学院数学凸最適化・組合せ最適化）