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