OR事典

連結度 (グラフの)

読み方：れんけつど
【英】：connectivity of graph

概要

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

詳説

無向グラフにおいて，上の二項関係を2点との間に路が存在するときと定めるとは同値関係となる．による各同値類の誘導する部分グラフは連結成分 (component) と呼ばれる．また，上の二項関係を2本の辺とを通る閉路が存在するときと定めるとは同値関係となる．による各同値類の誘導する部分グラフは2連結成分(biconnected component) と呼ばれる．2つ以上の2連結成分に属する点は関節点 (articulation point) と呼ばれる (グラフからこの点を除くと非連結となる)．有向グラフにおいて，上の二項関係を2点との間にからへの有向路とからへの有向路とが存在するときと定めるとは同値関係となる．による各同値類の誘導する部分グラフは強連結成分 (strong component) と呼ばれる．無向(有向)グラフはそれ自体が１つの連結成分(強連結成分)であるとき連結 (connected)(強連結(strongly connected))であるという．

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

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

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

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

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

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

「OR事典」の他の用語

組合せ最適化：	組合せ的爆発  計算の複雑さ  貪欲アルゴリズム  連結度  集合被覆問題  離散最適化問題  非線形計画
グラフ･ネットワーク：	輸送問題  辺分離定理  辺連結度  連結度  連結度増大問題  配送計画問題  階数関数