はむ。日記

離散数学とか解析学とかアニメについてつぶやきます。

マッチング

グラフ理論

単純無向グラフ $G=(V,E)$ を考える。

[Def](マッチング)

$M \subseteq E$ のどの2辺も互いに隣接しないとき、 $M$ を $G$ のマッチングという。

マッチング $M$ に属する辺の両端点は $M$ でマッチングされているという。

点 $v$ がマッチング $M$ に属する辺の端点のとき、 $M$ は $v$ を飽和しているといい、 $v$ を $M$ 飽和点という。

$G$ の全ての点が $M$ 飽和点のときマッチング $M$ は完全マッチングという。

$|M^{'} |＞|M|$ となるマッチング $M^{'}$ が存在しないとき、 $M$ を最大マッチングという。

[Def](交互道)

$M$ を $G$ のマッチングとする。

$M$ に関する交互道とは $G$ における道 $v_{0}-...-v_{k}(k \geqq1)$ で $M$ の辺と $E \setminus M$ の辺が交互に現れるもの。

[Def](増加道)

$M$ に関する増加道とは、 $M$ に関する交互道 $v_{0}-...-v_{k}(k \geqq1)$ で $v_{0}$ と $v_{k}$ が $M$ 非飽和なものである。

[Thm](Berge,1957)

$M \subseteq E$ が $G$ の最大マッチング $\Leftrightarrow$ $M$ に関する増加道が存在しない。

[証明]

( $\Rightarrow$ )

対偶:

$M$ に関する増加道が存在 $\Rightarrow$ $M$ は最大マッチングでない

を示す。

$M$ に関する増加道があると仮定し、 $v_{0}-v_{1}-...-v_{2m+1}$ を増加道とする。

辺 $v_{1}v_{2},...,v_{2m-1}v_{2m}$ は $M$ の辺であり、これらを $M$ から取り除き、新たに辺 $v_{0}v_{1},...,v_{2m}v_{2m+1}$ を加えたものを $M^{'}$ とする。

このとき交互道の定義から $M^{'}$ がマッチングであることがすぐにわかる。

さらに $|M^{'}| = |M|+1$ から $M$ が最大マッチングでないことがわかる。

( $\Leftarrow$ )

対偶:

$M$ が最大マッチングでない $\Rightarrow$ $M$ に関する増加道が存在

を示す。

$M$ が $G$ の最大マッチングでないとする。

$M^{'}$ を $G$ の最大マッチングとする。

つまり $|M^{'}| ＞|M|$ が成り立つ。

グラフ $H = (V,M△M^{'})$ を考える。(△は対称差であり $M△M^{'}=(M\cup M^{'})\setminus (M \cap M^{'})$ )

このとき $H$ の各点の次数は高々2である。

よって $H$ の各連結成分は孤立点か $M$ と $M^{'}$ の辺を交互にとる偶サイクルか $M$ と $M^{'}$ の辺が交互に現れる道である。

偶サイクルにおいてそれに含まれる $M$ の辺の数と $M^{'}$ の辺の数は等しい。

$|M^{'}| ＞|M|$ より、( $M$ の辺の数)<( $M^{'}$ の辺の数)を満たす $H$ の道 $P$ が存在する。このとき $P$ の始まりも終わりも $M^{'}$ の辺になる。

つまり $P$ の始点と終点は $H$ では $M^{'}$ 飽和であるが、 $G$ では $M$ 非飽和である。

よって $P$ は $G$ の $M$ に関する増加道である。■