cafelier@SRM

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

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のパスの本数| サイズのマッチングが少なくとも得られた。