cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
cafelier2010/04/21 09:47証明こんな面倒くさくする必要なかったなー・点被覆（＝どの辺もどっちかの頂点はカバーされてる）の補集合は独立点集合（＝どの辺もどっちかの頂点はカバーされてない）・独立点集合の補集合は点被覆・よって、 最小点被覆←補集合→最大独立点集合・二部グラフの場合は、|最小点被覆| = |最大マッチング|・よって二部グラフの場合は、|最大独立点集合|＝|V|-|最大マッチング|
presented by cafelier/k.inaba under
・点被覆（＝どの辺もどっちかの頂点はカバーされてる）の補集合は独立点集合（＝どの辺もどっちかの頂点はカバーされてない）
・独立点集合の補集合は点被覆
・よって、 最小点被覆←補集合→最大独立点集合
・二部グラフの場合は、|最小点被覆| = |最大マッチング|
・よって二部グラフの場合は、|最大独立点集合|＝|V|-|最大マッチング|