Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2012-10-11

推移性のあるグラフで成り立つ性質

21:08 | はてなブックマーク -  推移性のあるグラフで成り立つ性質 - cafelier@SRM

推移性(Transitivity)がある、とは

「頂点aからbに辺があってbからcに辺があるなら、必ずaからcにも辺がある」こと。

推移性のあるグラフなら、|最大独立点集合| ≦ |最小パス被覆|

証明: 一般に、独立点集合の頂点同士は直接辺で結ばれていない。推移性がある場合は、パスで結ばれてもいない。よって、このようなグラフをパス被覆するには全ての独立頂点を別々のパスでカバーしないといけない。

系: 推移性のあるグラフなら、|最大独立点集合| = |最小パス被覆|

系: [Dilworth 1950] 推移性のあるDAGなら、|最大独立点集合| = |最小パス被覆|

注意: DAGというだけでは |最大独立点集合| = |最小パス被覆|は成立しない。

a -> b -> c

というグラフの最大独立点集合は{a,c}だが、パス被覆は{a->b->c}の1本でカバーできてしまう。

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/cafelier/20121011
 | 

presented by cafelier/k.inaba under CC0