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と呼んだりもする。