連結度 (グラフの)

提供:ORWiki
移動: 案内, 検索

【れんけつど (connectivity of graph)】

概要

無向(有向)グラフG\,の辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなるとき, 辺カットという. G\,の点の部分集合は, それを除去すると残ったグラフが2点以上をもち, かつ連結(強連結)でなくなるとき, 点カットという. 辺カット(点カット)の大きさの最小値を辺連結度(点連結度)という.

詳説

 無向グラフG=(V,E)\, において,V\, 上の二項関係R_1\, を2点u\, v\, の間に路が存在するときuR_1 v\, と定めるとR_1\, は同値関係となる.R_1\, による各同値類の誘導する部分グラフは連結成分 (component) と呼ばれる.また,e\, 上の二項関係R_2\, を2本の辺e\, e'\, を通る閉路が存在するときeR_2 e'\, と定めるとR_2\, は同値関係となる.R_2\, による各同値類の誘導する部分グラフは2連結成分(biconnected component) と呼ばれる.2つ以上の2連結成分に属する点は関節点 (articulation point) と呼ばれる (グラフからこの点を除くと非連結となる).有向グラフG=(V,E)\, において,V\, 上の二項関係R_3\, を2点u\, v\, の間にu\, からv\, への有向路とv\, からu\, への有向路とが存在するときuR_3 v\, と定めるとR_3\, は同値関係となる.R_3\, による各同値類の誘導する部分グラフは強連結成分 (strong component) と呼ばれる.無向(有向)グラフはそれ自体が1つの連結成分(強連結成分)であるとき連結 (connected)(強連結(strongly connected))であるという.

 無向 (有向) グラフの2点s,t\, に対し,s\, からt\, への辺素である (すなわち互いに辺を共有しない) 路の本数の最大値をs,t\, 間の局所辺連結度 (local edge connectivity) という.この値は,s\, からt\, への路をなくすために取り除くべき辺の本数の最小値に等しい(辺型のMengerの定理).また,s\, からt\, への内素である(すなわちs,t\, 以外では点を共有しない)路の本数の最大値をs,t\, 間の局所点連結度 (local vertex connectivity) という.この値は,s\, からt\, への辺が存在しないとき,s\, からt\, への路をなくすために取り除くべきs,t\, 以外の点の個数の最小値に等しい(点型のMengerの定理).

 無向(有向)グラフG\, の辺の部分集合は,それを除去するとグラフが連結(強連結)でなくなるとき,辺カットという.G\, の点の部分集合は,それを除去するとグラフが2点以上をもち,かつ連結(強連結)でなくなるとき,点カットという.辺カット(点カット)の大きさの最小値を辺連結度 (edge connectivity)(点連結度 (vertex connectivity))という.これらの値は辺(点)に重みが付いているときは重み和の最小値として定義することもある.辺連結度(点連結度)がk\, 以上であるグラフをk\, 辺連結(k\, 点連結)であるという.重みなし無向グラフG=(V,E)\, の点連結度\kappa(G)\, ,辺連結度\lambda(G)\, ,最小次数\delta(G)\, の間には,次の不等式が成り立つ.\kappa(G)\leq \lambda(G)\leq \delta(G)\leq 2|E|/|V|\,

 グラフの辺連結度(点連結度)は全点対間の局所辺連結度(局所点連結度)の最小値に一致する.局所辺連結度や局所点連結度は,最大フロー・最小カット定理の特別な場合であるメンガーの定理により特徴づけされるので,これらの連結度(および連結度を決めている辺カットや点カットの1つ)はフローアルゴリズムをもちいて多項式時間で計算できる [3].任意の無向グラフには2点間の局所辺連結度(局所点連結度)が一方の点の次数に等しい2点が存在し,そのような点対を線形時間で見つけることができる [8].このような点対を繰り返し縮約していくことで辺連結度を容易に求めることもできる [9].

 指定点s\, を持つ重みなし有向グラフに対し,s\, を含む点の真部分集合から残りの点の集合へ向かう有向辺の集合をs\, -カットと呼ぶとき,s\, -カットの大きさの最小値は,s\, を根とする有向全域出木(すなわち全域木に根から葉へ向かって辺に向きをつけたもの)の互いに辺素な集合の最大値に等しい(J.Edmondsの定理 [1] ).大きさ最小のs\, -カットを多項式時間で求めることができる.

 与えられた無向(有向)グラフの辺連結度,あるいは点連結度を指定された目標値まで大きくするためにグラフに最小費用の辺の集合を付加する問題を連結度増大問題 (connectivity augmentation problem)と呼ぶ.この問題はNP困難であるが [2] ,付加辺の本数を最小にする場合には,以下の問題に対して多項式時間の解法が知られている.無向(有向)グラフの辺連結度を目標値まで上げる問題,無向グラフの点連結度を4以下の目標値に上げる問題,有向グラフの点連結度を1だけ上げる問題.

 無向(有向)グラフにおいて1つの点s\, を選び,s\, に接続する2本の (有向) 辺(u,s),(s,v)\, を1本の(有向)辺(u,v)\, に取り替える操作を辺分離という.このとき,次の辺分離定理 (edge splitting theorem) が知られている.s\, に接続する2本の辺をうまく選ぶと辺分離後も,グラフの辺連結度(正確にはs\, 以外の2点間の局所辺連結度の最小値)を変化させずに保つことができる[5, 7].特に,無向グラフに対しては(特殊な場合を除き),辺分離後にs\, 以外のすべての2点間の局所辺連結度を変化させない2本の辺の選択が存在する [6].辺分離定理は連結度増大問題を解くアルゴリズムに使われている[4].



参考文献

[1] J. Edmonds "Edge-disjoint branchings," Combinatorial Algorithms, R. Rustin, eds., Algorithmics Press, New York (1973) 91-96.

[2] K. P. Eswaran and R. E. Tarjan, "Augmentation problems," SIAM Journal on Computing, 5 (1976), 653-665.

[3] S. Even and R. E. Tarjan, "Network flow and testing graph connectivity," SIAM Journal on Computing, 4 (1975), 507-518.

[4] A. Frank, "Augmenting graphs to meet edge-connectivity requirements," SIAM Journal on Discrete Mathematics, 5 (1992), 25-53.

[5] L. Lovász, Combinatorial Problems and Exercises, North-Holland 1979.

[6] W. Mader, "A reduction method for edge-connectivity in graphs," Ann. Discrete Math., 3 (1978), 145-164.

[7] W. Mader, "Konstruktion aller n-fach kantenzusammenhängenden Digraphen," Europ. J. Combinatorics, 3 (1982), 63-67.

[8] H. Nagamochi, "Graph algorithms for network connectivity problems," Journal of the Operations Research Society of Japan, 47 (2004) , 199-223.

[9] H. Nagamochi and T. Ibaraki, "A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph," Algorithmica, 7 (1992), 583-596.

[10] H. Nagamochi and T. Ibaraki, "Computing edge-connectivity in multigraphs and capacitated graphs," SIAM Journal on Discrete Mathematics, 5 (1992), 54-66.

[11] アルゴリズムデータベース http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/

個人用ツール