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

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

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