Vertex Connectivity - とどの日記

割りとメジャーだけど点連結度の計算方法．

辺連結度

u-v間の辺連結度は，「消すとu-v間が非連結になる辺集合の最小サイズ」．
これは，u->vの最大流に一致．

点連結度

uv間の辺連結度は，「消すとuv間が非連結になる頂点集合の最小サイズ」．

「点連結度 <= 辺連結度」は常に成り立つ（各辺の何れかの頂点を消せば良いから）．
下の図だと，st間の辺連結度は2，点連結度は1．

任意の2点間の点連結度を求めるためにはどうすればいいか．

無向グラフG=(V,E)に対して新しい有向グラフH=(V',E')を作る．
$V'=\{ v^{1}, v^{2} | v \in V \}$
$E' = \{ (v^{1}, v^{2}) | v \in V \} \cup \{ (u^{2}, v^{1}) | (u, v) \in E \}$
こんな感じ．各頂点は2つの頂点に分割される．E'の各辺は容量1とする．
uvが隣接していない時，Gのuv間の点連結度は，Hの $u^{2}v^{1}$ 間の辺連結度に一致する．

例題

SPOJ Cable TV Network http://www.spoj.com/problems/CABLETV/