最大マッチングとケーニヒの定理

増加道を探して、最大マッチングの大きさ $ν (G)$ を求められる。2 部グラフでは $ν (G) = τ (G)$ （ケーニヒの定理）を使って、最小頂点被覆と最大独立集合の大きさを求められる

前提

2 部グラフと奇閉路（大学数学グラフ理論）
最大独立集合と最小頂点被覆（大学数学グラフ理論）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
グラフの次数と握手補題（大学数学グラフ理論）
2 部グラフと奇閉路（大学数学グラフ理論）
最大独立集合と最小頂点被覆（大学数学グラフ理論）

説明

グラフ $G$ の辺の集合で、どの 2 本も端点を共有しないものをマッチングといいます。辺の本数が最大のマッチングを最大マッチングといい、その本数を $ν (G)$ と書きます。この技能では、「増加道」を探してマッチングを 1 本ずつ大きくし、 $ν (G)$ を求めます。さらに 2 部グラフでは $ν (G) = τ (G)$ （ケーニヒの定理）が成り立つので、最小頂点被覆の大きさ $τ (G)$ と、 $α (G) = ∣ V ∣ - τ (G)$ から最大独立集合の大きさ $α (G)$ も求められます。仕事の割り当てやペア作りの問題で使います。

なぜそうしてよいのか

マッチング $M$ に対して、 $M$ のどの辺の端点にもなっていない頂点を自由頂点とよびます。 $M$ に入らない辺と $M$ の辺が交互に並ぶ道を交互道といいます。両端が（異なる）自由頂点である交互道を増加道といいます。増加道 $P$ は「入らない辺・入る辺・…・入らない辺」と並ぶので、入らない辺が入る辺より 1 本多くなります。そこで $P$ の上だけで、 $M$ に入る辺と入らない辺を入れ替えます。式で書くと $M^{'} = M △ P$ で、 $△$ は「どちらか一方だけに属する辺」の集合を表します。このとき $M^{'}$ もマッチングのままで、 $∣ M^{'} ∣ = ∣ M ∣ + 1$ になります。道の内部の頂点は入替え後もちょうど 1 本の辺に使われ、両端の頂点はもともと自由だったからです。逆に、 $M$ より大きいマッチング $N$ があるとします。 $M △ N$ の各頂点の次数は 2 以下なので、 $M △ N$ は交互の道と偶数長の閉路に分かれます。 $N$ の辺のほうが多いので、 $N$ の辺が多い成分が少なくとも 1 つあり、それは $M$ の増加道になります。よって 「 $M$ が最大 $⟺$ $M$ の増加道が存在しない」（ベルジュの定理）が成り立ちます。

次に頂点被覆との関係です。頂点被覆は、どの辺も少なくとも一方の端点がその集合に入るような頂点の集合でした。マッチングの各辺を覆うには、それぞれに別々の頂点が要ります。マッチングの辺は端点を共有しないからです。したがって、どんなグラフでも $∣ M ∣ \leq τ (G)$ 、つまり $ν (G) \leq τ (G)$ です。一般には等号は成り立ちません。たとえば $C_{5}$ では $ν = 2$ 、 $τ = 3$ です。

2 部グラフ（頂点を $A$ と $B$ に分ける）では等号が成り立ちます。これがケーニヒの定理です。理由の概略を示します。最大マッチング $M$ をとり、 $A$ の自由頂点から交互道でたどれる頂点全体を $Z$ とします。このとき $C = (A ∖ Z) \cup (B \cap Z)$ は頂点被覆になり、 $M$ の各辺の端点をちょうど 1 つずつ含みます。 $B \cap Z$ の頂点はすべて $M$ で使われています（自由なら増加道ができてしまうからです）。そのため $∣ C ∣ = ∣ M ∣$ となります。よって $τ (G) \leq ν (G)$ も成り立ち、 $ν (G) = τ (G)$ です。さらに前提の技能 $α (G) + τ (G) = ∣ V ∣$ と合わせると、2 部グラフでは $α (G) = ∣ V ∣ - ν (G)$ となります。

手順

手順1: 適当なマッチング $M$ を 1 つ作る。端点が重ならないように、辺を貪欲に選べばよい。
手順2: 増加道を探す。自由頂点から出発し、「 $M$ に入らない辺 → $M$ の辺 → $M$ に入らない辺 → …」と交互にたどり、別の自由頂点に着けば増加道である。2 部グラフで $A$ 側から探すときは、 $A$ の自由頂点から出発すれば十分である。
手順3: 増加道 $P$ が見つかったら、 $P$ 上の辺の入る・入らないを入れ替えて $M \leftarrow M △ P$ とする。マッチングは 1 本増える。そのあと手順2に戻る。
手順4: どの自由頂点から探しても増加道がなければ、 $M$ は最大で $ν (G) = ∣ M ∣$ である。確認として、大きさ $∣ M ∣$ の頂点被覆を 1 つ示せれば $ν (G) \leq τ (G) \leq ∣ M ∣$ から確定する。
手順5: 2 部グラフなら、ケーニヒの定理より $τ (G) = ν (G)$ であり、さらに $α (G) = ∣ V ∣ - ν (G)$ と求める。

例題

頂点集合 $V = {a_{1}, a_{2}, a_{3}, a_{4}, b_{1}, b_{2}, b_{3}, b_{4}}$ 、辺集合 $E = {a_{1} b_{1}, a_{1} b_{2}, a_{2} b_{2}, a_{3} b_{1}, a_{3} b_{3}, a_{3} b_{4}, a_{4} b_{1}, a_{4} b_{2}}$ のグラフ $G$ について、独立数 $α (G)$ を求めよ。

例題の解答

どの辺も $a_{i}$ と $b_{j}$ を結ぶので、 $A = {a_{1}, \dots, a_{4}}$ と $B = {b_{1}, \dots, b_{4}}$ に塗り分けられます。よって $G$ は 2 部グラフです。

手順1: 貪欲に $M = {a_{3} b_{1}, a_{1} b_{2}}$ をとります（ $∣ M ∣ = 2$ ）。自由頂点は $a_{2}, a_{4}, b_{3}, b_{4}$ です。

手順2: $A$ の自由頂点 $a_{4}$ から探します。 $a_{4} b_{1}$ （ $M$ 外）→ $b_{1} a_{3}$ （ $M$ の辺）→ $a_{3} b_{3}$ （ $M$ 外）とたどると、自由頂点 $b_{3}$ に着きます。これで増加道 $P : a_{4} - b_{1} - a_{3} - b_{3}$ が得られます。

手順3: $P$ 上で入替えを行います。 $a_{3} b_{1}$ を外し、 $a_{4} b_{1}$ と $a_{3} b_{3}$ を加えます。結果は $M = {a_{4} b_{1}, a_{3} b_{3}, a_{1} b_{2}}$ で、 $∣ M ∣ = 3$ になります。

手順2（再び）: $A$ の自由頂点は $a_{2}$ だけです。 $a_{2}$ の隣は $b_{2}$ のみで、 $b_{2}$ は $M$ で $a_{1}$ と組んでいます。 $a_{1}$ から $M$ 外の辺で行けるのは $b_{1}$ で、 $b_{1}$ は $a_{4}$ と組んでいます。 $a_{4}$ の隣 $b_{1}, b_{2}$ はどちらもすでにたどった頂点です。自由な $b$ 頂点には着けないので、増加道はありません。

手順4: よって $ν (G) = 3$ です。確認として ${a_{3}, b_{1}, b_{2}}$ を見ると、8 本の辺のすべてがこの 3 頂点のどれかを端点にもちます。したがってこれは大きさ 3 の頂点被覆で、 $ν (G) = 3$ が確定します。

手順5: ケーニヒの定理より $τ (G) = ν (G) = 3$ です。よって $α (G) = ∣ V ∣ - τ (G) = 8 - 3 = 5$ となります。実際、被覆の補集合 ${a_{1}, a_{2}, a_{4}, b_{3}, b_{4}}$ の頂点どうしを結ぶ辺はなく、大きさ 5 の独立集合になっています。

答え: $5$

よくある誤り

これ以上辺を足せないマッチング（極大マッチング）を、最大マッチングとしてしまう誤り。例題で $M = {a_{3} b_{1}, a_{1} b_{2}}$ に $a_{2}, a_{4}$ の辺は足せませんが、 $∣ M ∣ = 2$ は最大ではありません。正しくは、増加道がないことまで確かめて初めて最大といえます（例題では $ν = 3$ ）。
ケーニヒの定理を 2 部グラフでないグラフにも使ってしまう誤り。たとえば $C_{5}$ で $τ = ν = 2$ とするのは誤りです。正しくは $ν (C_{5}) = 2$ ですが $τ (C_{5}) = 3$ です。一般のグラフで言えるのは $ν (G) \leq τ (G)$ だけです。
交互道でありさえすれば増加道だとしてしまう誤り。例えば $a_{4} - b_{1} - a_{3}$ のように端が自由頂点でない道や、 $M$ の辺で始まる道で入れ替えると、マッチングが大きくならないか、マッチングでなくなります。正しくは、両端がどちらも自由頂点で、最初と最後の辺が $M$ に入らない道だけが増加道です。
$α (G) = ν (G)$ と取り違える誤り。例題で $α = 3$ とするのは誤りです。正しくは、2 部グラフでは $τ (G) = ν (G)$ であり、独立数は $α (G) = ∣ V ∣ - ν (G) = 8 - 3 = 5$ です。

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

入口の問題

この技能を使う問題

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

辺彩色数とヴィジングの定理（大学数学グラフ理論）
割当問題（ハンガリー法）（大学数学オペレーションズ・リサーチ）