連結度 (グラフの)

【れんけつど (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) と呼ばれる．無向(有向)グラフはそれ自体が１つの連結成分(強連結成分)であるとき連結 (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|\,$．

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

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

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

　無向(有向)グラフにおいて１つの点$s\,$を選び，$s\,$に接続する２本の (有向) 辺$(u,s),(s,v)\,$を1本の(有向)辺$(u,v)\,$に取り替える操作を辺分離という．このとき，次の辺分離定理 (edge splitting theorem) が知られている．$s\,$に接続する２本の辺をうまく選ぶと辺分離後も，グラフの辺連結度(正確には$s\,$以外の２点間の局所辺連結度の最小値)を変化させずに保つことができる[5, 7]．特に，無向グラフに対しては(特殊な場合を除き)，辺分離後に$s\,$以外のすべての２点間の局所辺連結度を変化させない２本の辺の選択が存在する [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/