2部グラフにおける最大マッチングの個数と最小点被覆の個数の一致

蟻本に載っていた事実だけど、理解するのに時間がかかった。
まず、前段階として|マッチング| <= |点被覆|であることを確認しよう(これは一般のグラフで成り立つ)。これは、マッチングに含まれる辺を被覆するのに最低限マッチングと同じだけの点が必要だから。なので|最大マッチング|<=|最小点被覆|となる。
具体的に最小点被覆を構成してみよう。2部グラフにsinkとsourceつなげて最大流を流し、最大マッチングを作る。このとき、残余グラフでsourceから到達不可能な左側の点集合と到達可能な右側の点集合の和集合Xが最小点被覆になっている。以下ではこれを示す。
もっと具体的に考えてみよう。図のように色を付ける。最大マッチングに含まれる辺は赤。そうでなければ黒。

左から右にいくときは黒だけ通れる。右から左にいくときは赤だけ通れる。赤い辺がついていない左の点を出発点にできる。
ここで次の2つを調べてやろう。

• 1.点集合Xが点被覆になっている
• 2.点集合Xの濃度は最大マッチングの濃度と一致する

1を示そう。Xで被覆できない辺が存在したとする。そのような辺は、(左側で到達可能な点=:v, 右側で到達不可能な点=:u)で、赤色をしているはず(でないとuに到達できてしまう)。さて、このときどうやってvに到達したんだろう？vには赤い辺が付いているので出発点には出来ない。右から左にいくには赤い辺を通らなければならないけど、赤い辺は各点に最大で1本しか付かないので(v,u)を通ってきたことになる。これはuに到達不可能であることと矛盾する。したがってXは全ての辺を被覆する。すなわち点被覆になっている。
2を示そう。右側で到達可能な点には必ず赤い辺がくっついている(最大マッチングなので増加パスは存在しないから)。それ以外の赤い辺を考える。左側の端点には到達不可能であることはすぐに分かる。出発点には選べないし、右側の端点は到達不可能だからその赤い辺を含むsourceからのパスは存在しない。さらに、赤い辺が付いていない左側の端点は出発点にできるので到達可能。したがって、全ての赤い辺とXの要素が1対1で対応したからXの濃度は最大マッチングの濃度と一致する。
最初に確認したように|最大マッチング|<=|最小点被覆|だからXの最小性も明らか。したがって|最大マッチング| = |最小点被覆|が成り立つ。