二部グラフと最大マッチング

左右2グループを結ぶ。重ならない辺を最大何本選べるか＝最大マッチング。

グラフを選ぶ

キャンバスの灰色の辺をクリックするとマッチングに入れる／外せます。端点を共有する辺は同時に選べません（自動で排他）。
頂点をドラッグすると縦位置を動かして辺の交差を整理できます。

マッチング数

最大マッチング

—

完全マッチング

—

左集合 L 右集合 R マッチング辺未選択の辺増加道

二部グラフは頂点を 2 グループ（左 L・右 R）に分け、辺は必ず L と R の間にだけ張るグラフです。例えば「応募者 ⟷ 仕事」「学生 ⟷ 研究室」のような割当問題が当てはまります。
マッチングとは、どの頂点も 2 回使わない（端点を共有しない）ように選んだ辺の集合のこと。そのなかで本数が最大のものが最大マッチングです。灰色の辺をクリックして自分で組んでみたり、「増加道」ボタンで 1 本ずつ増やしたりして、なぜそれ以上増やせないのかを確かめましょう。

いま何が起きている？

ここがポイント

マッチング＝端点を共有しない辺集合 ── どの頂点も高々 1 本の選んだ辺にしか触れない。
増加道で 1 本増やせる ── 未マッチ頂点から始まり「未選択辺→選択辺→未選択辺→…」と交互にたどって別の未マッチ頂点で終わる道。選択／未選択を入れ替えるとマッチングが 1 本増える。
増加道がもう無ければ最大 ── ベルジュの定理。これが「これ以上増やせない」ことの証明になる（最大フローの手順を踏まなくても判定できる）。
ホールの結婚定理 ── 左の任意の部分集合 S について「S の近傍 N(S) の大きさ ≥ |S|」が成り立つとき、かつそのときに限り L 全体を覆う完全マッチングが存在する。1 つでも |N(S)| < |S| となる S（ボトルネック）があれば不可能。