Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/87-affb762a
この記事にトラックバックする(FC2ブログユーザー)

2部グラフの最大流問題と最大マッチング問題と最小点被覆問題 (この記事を編集する[管理者用])

最大流と最大マッチングが同値なのはほぼ自明で,最小カットと同値なのまでは説明しているWebページも沢山あるけども,最小点被覆との関係(König-Egervary theorem)をちゃんと書いてる(日本語の)Webページが少なかったのでメモしておく.

Flowは左から右に流れる.左側の節点とか右側の節点とかいう言葉の意味はなんとか理解してもらう.
点被覆とは,節点集合で,グラフからその節点集合を除くと枝が全くなくなるものをいう.
最小点被覆は,点被覆の中で,節点の数が最も少ないもの.

2部グラフの最小点被覆の節点数は,2部グラフの最大マッチングに一致する.
2部グラフの最大マッチングが与えられたとき,どのようにして,最小点被覆を得るかと言うと,
 左側の節点のうち,最大マッチングの枝に繋がっていないもの
を全部取ってきて,それから到達できる節点の集合を求める.
ただし,到達できるというのは,左側の節点から右側の節点に移動する際は,最大マッチングに含まれていない枝しか通ってはいけなくて,右側の節点から左側の節点に移動する際は,最大マッチングに含まれている枝しか通ってはいけない.
で,到達できる節点の集合が求まったら,最小点被覆は,左側の節点の中で到達できなかったものと右側の節点のうち到達できたものを合わせたものである.

そうやって作られた節点集合が点被覆になっていることはほぼ自明.
それの節点数が最大マッチングと一致することも最大マッチングであることを考えれば簡単に理解できる.
最大マッチングより少ない節点数の点被覆が存在しないこともほぼ自明.

到達できる節点集合とか言っているのだけど,それが最大マッチングの意味ではごちゃごちゃしててわかりにくいのだけども,最大流問題で考えれば簡単になる.
到達できる節点集合は,ソースからFlowを流すことができる向きにのみ移動して到達できる節点集合(からソースを除いたもの)に一致する.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/87-affb762a
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。