cafelier@SRM

Path Cover のいろいろ

21:08 |

パス (今回使う定義) / Path

有向グラフ G=(V,E) 上のパスとは

Vの重複を含まないリスト v[1], v[2], ..., v[k] であって (v[i],v[i+1])∈E なもの)。

k=1 の場合、つまり単独の頂点一個でもパスとみなす

パス被覆 / Path Cover

有向グラフ G=(V,E) のパス被覆とは

パスの集合 P であって、P に属すパスに属す頂点を全部集めると V になるもの。

独立パス被覆

有向グラフ G=(V,E) の独立パス被覆とは

パス被覆 P であって、P に属すパス同士の間に頂点の共有がないもの。

(証明のために後で使う概念) 端点集合 ter(P)

パスの集合 P={p1,p2,...,pn}

p1 = v11 -> v12 -> ... -> u1
p2 = v21 -> v22 -> ... -> u2
...
pn = vn1 -> vn2 -> ... -> un

に対してその末端の頂点の集合 {u1,u2,...,un} をter(P)と書く。

(証明のために後で使う概念) 極小端点独立パス被覆

Pが独立パス被覆で、ter(Q) ⊊ ter(P) となるような他の独立パス被覆が存在しないとき、Pは極小端点独立パス被覆であるという。最小独立パス被覆は当然必ず極小端点独立パス被覆である（が、逆は必ずしもそうでもないかも。）

(証明のために後で使う概念) 無理矢理二部グラフ化

有向グラフ G=(V,E) の無理矢理二部グラフ化とは１個の頂点 v∈V を v<入口> と v<出口> の２個にわけて、辺v→uがあったらv<出口>→u<入口>に辺を引くようにしたグラフ。出口同士、入口同士に辺がないので二部グラフである。

独立点集合 / Independent Set

有向グラフ G=(V,E) の独立点集合とは

頂点集合 X ⊆ V であって、X に属する異なる頂点同士を結ぶ辺がまったくないもの。安定集合と呼んだりもする。推移性のあるDAGでは反鎖/antichainと呼んだりもする。

任意のグラフで成り立つ性質

21:08 |

|最小パス被覆| ≦ |最小独立パス被覆|

独立パス被覆はすべてパス被覆なので当然。

[Gallai & Milgram 1960] |最小独立パス被覆| ≦ |最大独立点集合|

以下の補題より。

補題: |極小端点独立パス被覆| ≦ |最大独立点集合|

証明：数学的帰納法。頂点数 1 のグラフでは両辺共に 1 なので成立する。

頂点数 k のグラフで成立したとする。頂点数 k+1 のグラフ G の極小端点独立パス被覆P={p1,p2,...,pn}を1つ適当に選ぶ。

p1 = v11 -> v12 -> ... -> v1' -> u1
p2 = v21 -> v22 -> ... -> v2' -> u2
...
pn = vn1 -> vn2 -> ... -> vn' -> un

ter(P) = {u1, ..., un} 同士を結ぶ辺が１個もなかったら、これが独立点集合なので証明終わり。u1 -> u2 という辺があった場合は、ややこしくなる。

Fact: u1 -> u2 という辺がある場合、p2は単一頂点パスp2={u2} ではない（仮にそうだとするとp1の後ろにu2を繋げてみるとPの極小端点性に反する）

主張: u2を除いたグラフを考えると、さっきのパス被覆Pからu2を除いたP'

p1 = v11 -> v12 -> ... -> v1' -> u1
p2'= v21 -> v22 -> ... -> v2'
...
pn = vn1 -> vn2 -> ... -> vn' -> un

これも、u2除去後のグラフの極小端点独立パス被覆になっている。

これを認めると、帰納法の仮定より、u2除去後のグラフにはサイズ n の独立点集合がある。u2を入れ直してもこれは独立点集合である。

主張の証明: 極小じゃなかったとする。ter(Q)⊊ter(P')な被覆があったことになる。場合分け

• v2'∈Q かつ ter(Q)⊊ter(P') なパス被覆Qがあった → Qのv2'の後ろにu2を繋げるとPの極小性に反する
• u1∈Q かつ v2'∉Q かつ ter(Q)⊊ter(P') なパス被覆Qがあった → Qのu1の後ろにu2を繋げるとPの極小性に反する
• u1もv2'もQに入ってないかつ ter(Q)⊊ter(P') なパス被覆Qがあった → Qにもう一個{u2}というパスを足すとPの極小性に反する

証明終。

|V| - |最小独立パス被覆| ≦ |無理矢理二部グラフ化したものの最大マッチング|

証明: 独立パス被覆の辺を全部使うとそれはマッチングになっている。つまり、各vについて、v<出口>から出てる辺は高々１本しか選んでないし、v<入口>に入る辺は１本しか選んでない。

独立パス被覆 P について |Pのパスの本数| + |Pに含まれる辺の数| = |V| なので、↑この作り方で |V|-|Pのパスの本数| サイズのマッチングが少なくとも得られた。

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

21:08 |

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

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

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

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

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

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

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

a -> b -> c

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

DAGで成り立つ性質

21:08 |

DAGなら、|V| - |無理矢理二部グラフ化したものの最大マッチング| ≧ |最小独立パス被覆|

証明: マッチングに属する辺を全て使うと独立パス被覆ができる。

任意のグラフでの「≦」の証明と逆向きに考えて、マッチングなので元のグラフに戻したときに枝分かれや合流はできてない。また、元がDAGなのでサイクルもできてない。よってマッチングを元のグラフに戻すとパスがたくさんという形になっている。

辺をe本使うパス被覆のパスの本数は、|V| - e なので、大きくとも|V|-|最大マッチ|のパス被覆は↑このようにして作れている。

系： DAGなら、|V| - |無理矢理二部グラフ化したものの最大マッチング| ＝ |最小独立パス被覆|

注意: "独立"が重要。5頂点のXの字のようなDAGを考えると、独立でないパス被覆なら2パスでカバーできるが、独立パスだと3パス必要だし最大マッチングは2=|V|-3。

系：推移性のあるDAGなら、|最大独立点集合| ＝ |最小独立パス被覆| = |最小パス被覆| ＝ |V| - |無理矢理二部グラフ化したものの最大マッチング|

注意: 推移性では|V|-|最大マッチ|と等しくはならない。DAGであることが重要。反例として、N点の完全グラフを考えると、最大マッチはNなので|V|-|最大マッチ|は0になってしまうけれど、最小パス被覆が0ってことはない。