連結度 (グラフの)
【英】:connectivity of graph
概要
無向(有向)グラフの辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなるとき, 辺カットという. の点の部分集合は, それを除去すると残ったグラフが2点以上をもち, かつ連結(強連結)でなくなるとき, 点カットという. 辺カット(点カット)の大きさの最小値を辺連結度(点連結度)という.
詳説
無向グラフにおいて,上の二項関係を2点との間に路が存在するときと定めるとは同値関係となる.による各同値類の誘導する部分グラフは連結成分 (component) と呼ばれる.また,上の二項関係を2本の辺とを通る閉路が存在するときと定めるとは同値関係となる.による各同値類の誘導する部分グラフは2連結成分(biconnected component) と呼ばれる.2つ以上の2連結成分に属する点は関節点 (articulation point) と呼ばれる (グラフからこの点を除くと非連結となる).有向グラフにおいて,上の二項関係を2点との間にからへの有向路とからへの有向路とが存在するときと定めるとは同値関係となる.による各同値類の誘導する部分グラフは強連結成分 (strong component) と呼ばれる.無向(有向)グラフはそれ自体が1つの連結成分(強連結成分)であるとき連結 (connected)(強連結(strongly connected))であるという.
無向 (有向) グラフの2点に対し,からへの辺素である (すなわち互いに辺を共有しない) 路の本数の最大値を間の局所辺連結度 (local edge connectivity) という.この値は,からへの路をなくすために取り除くべき辺の本数の最小値に等しい(辺型のMengerの定理).また,からへの内素である(すなわち以外では点を共有しない)路の本数の最大値を間の局所点連結度 (local vertex connectivity) という.この値は,からへの辺が存在しないとき,からへの路をなくすために取り除くべき以外の点の個数の最小値に等しい(点型のMengerの定理).
無向(有向)グラフの辺の部分集合は,それを除去するとグラフが連結(強連結)でなくなるとき,辺カットという.の点の部分集合は,それを除去するとグラフが2点以上をもち,かつ連結(強連結)でなくなるとき,点カットという.辺カット(点カット)の大きさの最小値を辺連結度 (edge connectivity)(点連結度 (vertex connectivity))という.これらの値は辺(点)に重みが付いているときは重み和の最小値として定義することもある.辺連結度(点連結度)が以上であるグラフを辺連結(点連結)であるという.重みなし無向グラフの点連結度,辺連結度,最小次数の間には,次の不等式が成り立つ..
グラフの辺連結度(点連結度)は全点対間の局所辺連結度(局所点連結度)の最小値に一致する.局所辺連結度や局所点連結度は,最大フロー・最小カット定理の特別な場合であるメンガーの定理により特徴づけされるので,これらの連結度(および連結度を決めている辺カットや点カットの1つ)はフローアルゴリズムをもちいて多項式時間で計算できる [3].任意の無向グラフには2点間の局所辺連結度(局所点連結度)が一方の点の次数に等しい2点が存在し,そのような点対を線形時間で見つけることができる [8].このような点対を繰り返し縮約していくことで辺連結度を容易に求めることもできる [9].
指定点を持つ重みなし有向グラフに対し,を含む点の真部分集合から残りの点の集合へ向かう有向辺の集合を-カットと呼ぶとき,-カットの大きさの最小値は,を根とする有向全域出木(すなわち全域木に根から葉へ向かって辺に向きをつけたもの)の互いに辺素な集合の最大値に等しい(J.Edmondsの定理 [1] ).大きさ最小の-カットを多項式時間で求めることができる.
与えられた無向(有向)グラフの辺連結度,あるいは点連結度を指定された目標値まで大きくするためにグラフに最小費用の辺の集合を付加する問題を連結度増大問題 (connectivity augmentation problem)と呼ぶ.この問題はNP困難であるが [2] ,付加辺の本数を最小にする場合には,以下の問題に対して多項式時間の解法が知られている.無向(有向)グラフの辺連結度を目標値まで上げる問題,無向グラフの点連結度を4以下の目標値に上げる問題,有向グラフの点連結度を1だけ上げる問題.
無向(有向)グラフにおいて1つの点を選び,に接続する2本の (有向) 辺を1本の(有向)辺に取り替える操作を辺分離という.このとき,次の辺分離定理 (edge splitting theorem) が知られている.に接続する2本の辺をうまく選ぶと辺分離後も,グラフの辺連結度(正確には以外の2点間の局所辺連結度の最小値)を変化させずに保つことができる[5, 7].特に,無向グラフに対しては(特殊な場合を除き),辺分離後に以外のすべての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/
「connectivity of graph」の例文・使い方・用例・文例
- Microsoftがβ版をランチするのは「NetShow streaming server」で動画や音声をオンデマンドで提供する。
- 《主に米国で用いられる》 = 《主に英国で用いられる》 an admiral of the fleet 海軍元帥.
- 篏入的 r 音 《英音の India office /ndiərfɪs/の /r/の音》.
- =《口語》 These kind of stamps are rare. この種の[こういう]切手は珍しい.
- (英国の)運輸省. the Ministry of Education(, Science and Culture) (日本の)文部省.
- は of の誤植です.
- を off と誤植する.
- あいまい母音 《about, sofa などの /ə/》.
- 副詞的小詞 《on, in, out, over, off など》.
- 迂言的属格 《語尾変化によらず前置詞によって示す属格; たとえば Caesar's の代わりの of Caesar など》.
- çon of garlic [humor]. それにはガーリック[ユーモア]がちょっぴり必要だ.
- 《主に米国で用いられる》 = 《主に英国で用いられる》 the Speaker of the House of Commons 下院議長.
- 《主に米国で用いられる》 = 《主に英国で用いられる》 the Committee of Ways and Means 歳入委員会.
- 初めて読んだ英文小説は“The Vicar of Wakefield”
- (違法罪―a sin of commission―に対する)怠惰罪
- 『each』、『every』、『either』、『neither』、『none』が分配的、つまり集団の中の1つのものを指すのに対し、『which of the men』の『which』は分離的である
- 『hot off the press(最新情報)』は『hot(最新の)』の拡張感覚を示している
- 『Each made a list of the books that had influenced him』における制限節は、リストに載った本を制限節で定義された特定の本だけに制限する
- 臨床的鬱病を治療するのに用いられる三環系抗鬱薬(商品名ImavateとTofranil)
- 『sunshine-roof』は『sunroof(サンルーフ)』に対する英国の用語である
- connectivity of graphのページへのリンク