二部グラフの最大マッチング＝最小頂点被覆

nyaasanに教えてもらった「最大流-最小カット定理」を使うということを元に、昨日わからなかった二部グラフにおいて最大マッチングが最小頂点被覆と等しいということを証明してみようと思う。
正直これを聞いても自分の中で納得するまでに大分時間かかってしまったけど。頭悪い俺・・・。

証明の流れ的には、二部グラフにおいて、
「最大マッチング＝最大流＝最小カット＝最小頂点被覆」
というのを使う。

例えば以下のような二部グラフがあるとする。(簡単な例ですいません)

○　○
　Ｘ　
○　○
　Ｘ　
○　○

最大流に直すためにソースSとシンクTをつける。

　　○　○　　
　／　Ｘ　＼　
Ｓ−○　○−Ｔ
　＼　Ｘ　／　
　　○　○　　

このときの最大流は２。
最大流-最小カット定理より最大流＝最小カットになるため、どっかを２つ切ればS,Tを二２つのグラフに分けることができる。そのような場所は下の「＠」である。

　　○　○　　
　／　Ｘ　＼　
Ｓ＠○　○＠Ｔ
　＼　Ｘ　／　
　　○　○　　

＠で切ると下のように分離できる。

　　○　　　　　○　　
　／　＼　　　／　＼　
Ｓ　　　○　○　　　Ｔ
　＼　／　　　＼　／　
　　○　　　　　○　　

カットした＠の隣のノードをとれば最小頂点被覆になる。

○　○
　Ｘ　
●　●
　Ｘ　
○　○

これは、＠でカットした隣の●に被覆される枝は全て、分割されたグラフにおいて●と同じ側のグラフにあることから言える。

　　○　　
　／　＼　← ●に被覆される枝
Ｓ　　　●
　＼　／　← ●に被覆される枝
　　○　　

(この例だと●がひとつずつだからわかりにくいけど・・・これ以上文字で図描くのがきつい・・・)

ちなみに、カットする枝が○と○の間の枝だったらどうするんだよ！って話だが、SかTのどちらかに接続する枝でカットできることが言える。
間をカットするということはどこかに、

Ｓ−○＠○−Ｔ

という部分があるということである。このとき

Ｓ＠○−○−Ｔ
Ｓ−○−○＠Ｔ

のどちらかにカットする場所を移すことが可能である。つまり真ん中でぶった切る時は左右のどちらの頂点で被覆してもよいということになる。

てなわけで、最小カットと最小頂点被覆というのが１対１対応して、最初の目的である「最大マッチング＝最小頂点被覆」が示せたわけだ。
もっと頭の良い方法があったらごめんなさい。

ところで最小カットでカットする場所ってアルゴリズム的に簡単にわかるのかな？？？