Kőnig の定理と最大流最小カット定理

最近組み合わせ最適化を勉強中なので、考えたことをメモ

任意の二部グラフ について、次の Kőnig の定理が成り立ちます。

König の定理 の最大マッチングと の最小点被覆は同じサイズを持つ。

この定理の証明はマッチングに関する増加路(augmenting path)を用いたものが有名ですが、より強い定理である最大流最小カット定理の系としても示せます。

説明のため、 の例として次のグラフを考えます。

まずは から次のような有向グラフ を作ります。

つまり は に頂点 を追加し、向きと辺容量 をつけたものです。
競プロではマッチングをフローで求める際によく出てきますね。

の最大マッチング＝ の最大流

これは馴染み深いと思います。

のマッチングと のフローには一対一の対応が作れます。

具体的には、 のマッチングにその辺と に繋がる辺のみを使うフローを対応させればよいです。
マッチングでは各頂点は高々一つの辺にしか含まれないので、 の作り方からこのような対応は可能です。

さらにこの対応では、マッチングのサイズとフローの流量が等しいです。
これはフローの流量がフローで使われた中央の辺の本数に等しいことからわかります。

の最小点被覆＝ の最小カット

二方向に分けて示します。

の最小点被覆 の最小カット

の点被覆 を任意に取ります。

● が の点

において、 の点と のいずれかを端点とする辺の集合を とします。

そして、 から の辺以外を辿って到達可能な頂点の集合を 、到達不可能な頂点の集合を とします。

縦線が引かれているのが の辺

明らかに は の頂点集合を二分割します。

加えて、 が成り立ちます。もし から への の辺を使わないパス があったと仮定すると、 となり、 が の点被覆であることに矛盾するからです。

よって は カットとなっています。

さらにこのカットのコストは 以下です。これは から への辺が全て に入っていることからわかります。

以上より任意の点被覆 について、コスト 以下のカットを作ることができました。

(2022/11/01 追記：SSRS さんとだれさんに指摘を頂き修正しました。ありがとうございます！)

の最小点被覆 の最小カット

逆に今度は カット を任意に取ります。

カット

において、 または と繋がっている辺の でない方の端点の集合を とします。

● が の点

の から誘導されるグラフ を考えます。

に の点のうち出次数 以上のものを全て追加した集合 は点被覆になります。

さらに、

• のサイズは の左右の辺の本数に等しい
• と のサイズの差分は の中央の辺の本数以下
• の辺（に対応する の辺）は全て に入っている（カットなので）

ことから、 のサイズは のコスト以下であるとわかります。

まとめ

最大流最小カット定理から、

の最大マッチング＝ の最大流＝ の最小カット＝ の最小点被覆

となり、無事 Kőnig の定理が示せました。