cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
|
証明: マッチングに属する辺を全て使うと独立パス被覆ができる。
任意のグラフでの「≦」の証明と逆向きに考えて、マッチングなので元のグラフに戻したときに枝分かれや合流はできてない。また、元がDAGなのでサイクルもできてない。よってマッチングを元のグラフに戻すとパスがたくさんという形になっている。
辺をe本使うパス被覆のパスの本数は、|V| - e なので、大きくとも|V|-|最大マッチ|のパス被覆は↑このようにして作れている。
注意: "独立"が重要。5頂点のXの字のようなDAGを考えると、独立でないパス被覆なら2パスでカバーできるが、独立パスだと3パス必要だし最大マッチングは2=|V|-3。
注意: 推移性では|V|-|最大マッチ|と等しくはならない。DAGであることが重要。反例として、N点の完全グラフを考えると、最大マッチはNなので|V|-|最大マッチ|は0になってしまうけれど、最小パス被覆が0ってことはない。
presented by
cafelier/k.inaba
under
