マッチング

交代パス

交代パスは、あるマッチングに含まれる辺と含まれない辺とが交互に現れるパスである。

交代パスの両端がマッチングに含まれない頂点であるとき、これを反転させることでより大きいマッチングを作ることができる。このようなパスを増加パスという。

頂点集合をX,Y,辺集合をEとする二部グラフを考える

X-完全マッチングとは、Xに含まれるすべての頂点をカバーするような辺集合

Wの近傍 $N_G(W)$ を以下のように定義する

N_G(W) = \lbrace v \in Y \quad | \quad \exists w \in W. (v,w) \in E \rbrace

X-完全マッチングが存在する必要十分条件は、

\forall W \sub X. \quad \lvert W \rvert \leq \lvert N_G(W) \rvert

である。

この条件の必要性は自明なので、以下、この条件の十分性を示す。対偶を考える:

もしX-完全マッチングが存在しないならば、ある $W \sub X$ が存在して、 $\lvert W \rvert \gt \lvert N_G(W) \rvert$ である。

最大マッチングMを考える。 X-完全マッチングが存在しないので、Xに属する頂点で、Mに使われていないものが存在し、それをuとする。

uを始点とするすべての交代パスを考えよう。これらのパスに属する頂点のうち、 Xに属するものの集合をW、Yに属するものの集合をZとおく。

Zのすべての頂点はMで使われている; もしZにMに使われていない頂点wが存在するならば、uからwへの交代パスは増加パスとなり、これはMが最大であることに反する。

$\lvert W \rvert \ge \lvert Z \rvert + 1$

すべてのv \in Wについて、それに隣接する頂点wを通るuからの交代パスが構成できる; Wの定義から、uからvへの交代パスが存在し、もしそのパスにwが含まれているなら(v, w)を取り除くことで、存在しないなら(v, w)を加えることで構成できる

$Z = N_G(W)$