cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
|
推移性(Transitivity)がある、とは
「頂点aからbに辺があってbからcに辺があるなら、必ずaからcにも辺がある」こと。
証明： 一般に、独立点集合の頂点同士は直接辺で結ばれていない。推移性がある場合は、パスで結ばれてもいない。よって、このようなグラフをパス被覆するには全ての独立頂点を別々のパスでカバーしないといけない。
注意: DAGというだけでは |最大独立点集合| ＝ |最小パス被覆|は成立しない。
a -> b -> c
というグラフの最大独立点集合は{a,c}だが、パス被覆は{a->b->c}の1本でカバーできてしまう。
presented by
cafelier/k.inaba
under
