2007-10-09から1日間の記事一覧

最大マッチングと最小頂点被覆

Algorithm

二部グラフにおいて最大マッチングと最小頂点被覆は等しいらしい。 実際にいくつかの例で試してみたら確かにそうなるから正しいんだろう。でも理由がわからない。 そもそもこの事実は二部グラフ以外でも成り立つのだろうか。 誰か教えてください。まじめに。