連結度 (グラフの) - 版の履歴

2008年11月14日 (金) 00:47にAlbeit-Kunによる

2008-11-14T00:47:11Z

2008年8月6日 (水) 02:55にImahoriによる

2008-08-06T02:55:32Z

Imahori: 基礎編と用語編のマージ

2008-03-13T14:16:53Z

基礎編と用語編のマージ

2007年8月8日 (水) 11:50にKanda.kによる

2007-08-08T11:50:12Z

Orsjwiki: "連結度 (グラフの)" を保護しました。 [edit=sysop:move=sysop]

2007-07-20T00:56:34Z

"連結度 (グラフの)" を保護しました。 [edit=sysop:move=sysop]

2007年7月11日 (水) 07:59に211.9.146.139による

2007-07-11T07:59:51Z

122.17.2.240: 新しいページ: ''''【れんけつど (connectivity of graph)】''' 無向(有向)グラフ$G$の辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなると...'

2007-07-09T07:57:08Z

新しいページ: ''''【れんけつど (connectivity of graph)】''' 無向(有向)グラフ$G$の辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなると...'

新規ページ

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

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

← 古い版		2008年11月14日 (金) 00:47時点における版
46行目:		46行目:
	[11] アルゴリズムデータベース　http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/		[11] アルゴリズムデータベース　http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/

−	[[Category:グラフ･ネットワーク\|~~ぐらふのれんけつど~~]]	+	[[Category:グラフ･ネットワーク\|れんけつど]]
		+
		+	[[Category:組合せ最適化\|れんけつど]]

@@ 5行目: / 5行目: @@
 === 詳説 ===
-　無向グラフ<math>G=(V,E)\, </math>において，<math>V\, </math>上の二項関係<math>R_1\, </math>を2点<math>u\, </math>と<math>V\, </math>の間に路が存在するとき<math>uR_1 v\, </math>と定めると<math>R_1\, </math>は同値関係となる．<math>R_1\, </math>による各同値類の誘導する部分グラフは連結成分 (component) と呼ばれる．また，<math>e\, </math>上の二項関係<math>R_2\, </math>を2本の辺<math>e\, </math>と<math>e'\, </math>を通る閉路が存在するとき<math>eR_2 e'\, </math>と定めると<math>R_2\, </math>は同値関係となる．<math>R_2\, </math>による各同値類の誘導する部分グラフは2連結成分(biconnected component) と呼ばれる．2つ以上の2連結成分に属する点は関節点 (articulation point) と呼ばれる (グラフからこの点を除くと非連結となる)．有向グラフ<math>G=(V,E)\, </math>において，<math>V\, </math>上の二項関係<math>R_3\, </math>を2点<math>u\, </math>と<math>V\, </math>の間に<math>u\, </math>から<math>V\, </math>への有向路と<math>V\, </math>から<math>u\, </math>への有向路とが存在するとき<math>uR_3 v\, </math>と定めると<math>R_3\, </math>は同値関係となる．<math>R_3\, </math>による各同値類の誘導する部分グラフは強連結成分 (strong component) と呼ばれる．無向(有向)グラフはそれ自体が１つの連結成分(強連結成分)であるとき連結 (connected)(強連結(strongly connected))であるという．
+　無向グラフ<math>G=(V,E)\, </math>において，<math>V\, </math>上の二項関係<math>R_1\, </math>を2点<math>u\, </math>と<math>v\, </math>の間に路が存在するとき<math>uR_1 v\, </math>と定めると<math>R_1\, </math>は同値関係となる．<math>R_1\, </math>による各同値類の誘導する部分グラフは連結成分 (component) と呼ばれる．また，<math>e\, </math>上の二項関係<math>R_2\, </math>を2本の辺<math>e\, </math>と<math>e'\, </math>を通る閉路が存在するとき<math>eR_2 e'\, </math>と定めると<math>R_2\, </math>は同値関係となる．<math>R_2\, </math>による各同値類の誘導する部分グラフは2連結成分(biconnected component) と呼ばれる．2つ以上の2連結成分に属する点は関節点 (articulation point) と呼ばれる (グラフからこの点を除くと非連結となる)．有向グラフ<math>G=(V,E)\, </math>において，<math>V\, </math>上の二項関係<math>R_3\, </math>を2点<math>u\, </math>と<math>v\, </math>の間に<math>u\, </math>から<math>v\, </math>への有向路と<math>v\, </math>から<math>u\, </math>への有向路とが存在するとき<math>uR_3 v\, </math>と定めると<math>R_3\, </math>は同値関係となる．<math>R_3\, </math>による各同値類の誘導する部分グラフは強連結成分 (strong component) と呼ばれる．無向(有向)グラフはそれ自体が１つの連結成分(強連結成分)であるとき連結 (connected)(強連結(strongly connected))であるという．
 　無向 (有向) グラフの2点<math>s,t\, </math>に対し，<math>s\, </math>から<math>t\, </math>への辺素である (すなわち互いに辺を共有しない) 路の本数の最大値を<math>s,t\, </math>間の[[局所辺連結度]] (local edge connectivity) という．この値は，<math>s\, </math>から<math>t\, </math>への路をなくすために取り除くべき辺の本数の最小値に等しい(辺型のMengerの定理)．また，<math>s\, </math>から<math>t\, </math>への内素である(すなわち<math>s,t\, </math>以外では点を共有しない)路の本数の最大値を<math>s,t\, </math>間の[[局所点連結度]] (local vertex connectivity) という．この値は，<math>s\, </math>から<math>t\, </math>への辺が存在しないとき，<math>s\, </math>から<math>t\, </math>への路をなくすために取り除くべき<math>s,t\, </math>以外の点の個数の最小値に等しい(点型のMengerの定理)．
@@ 11行目: / 11行目: @@
 　無向(有向)グラフ<math>G\, </math>の辺の部分集合は，それを除去するとグラフが連結(強連結)でなくなるとき，辺カットという．<math>G\, </math>の点の部分集合は，それを除去するとグラフが2点以上をもち，かつ連結(強連結)でなくなるとき，点カットという．辺カット(点カット)の大きさの最小値を[[辺連結度]] (edge connectivity)([[点連結度]] (vertex connectivity))という．これらの値は辺(点)に重みが付いているときは重み和の最小値として定義することもある．辺連結度(点連結度)が<math>k\, </math>以上であるグラフを<math>k\, </math>辺連結(<math>k\, </math>点連結)であるという．重みなし無向グラフ<math>G=(V,E)\, </math>の点連結度<math>\kappa(G)\, </math>，辺連結度<math>\lambda(G)\, </math>，最小次数<math>\delta(G)\, </math>の間には，次の不等式が成り立つ．<math>\kappa(G)\leq \lambda(G)\leq \delta(G)\leq 2|E|/|V|\, </math>．
-　グラフの辺連結度(点連結度)は全点対間の局所辺連結度(局所点連結度)の最小値に一致する．局所辺連結度や局所点連結度は，最大フロー・最小カット定理の特別な場合であるメンガーの定理により特徴づけされるので，これらの連結度(および連結度を決めている辺カットや点カットの１つ）はフローアルゴリズムをもちいて多項式時間で計算できる [3]．任意の無向グラフには２点間の局所辺連結度(局所点連結度)が一方の点の次数に等しい２点が存在し，そのような点対を線形時間で見つけることができる [8]．このような点対繰り返し縮約していくことで辺連結度を容易に求めることもできる [9]．
+　グラフの辺連結度(点連結度)は全点対間の局所辺連結度(局所点連結度)の最小値に一致する．局所辺連結度や局所点連結度は，最大フロー・最小カット定理の特別な場合であるメンガーの定理により特徴づけされるので，これらの連結度(および連結度を決めている辺カットや点カットの１つ）はフローアルゴリズムをもちいて多項式時間で計算できる [3]．任意の無向グラフには２点間の局所辺連結度(局所点連結度)が一方の点の次数に等しい２点が存在し，そのような点対を線形時間で見つけることができる [8]．このような点対を繰り返し縮約していくことで辺連結度を容易に求めることもできる [9]．
 　指定点<math>s\, </math>を持つ重みなし有向グラフに対し，<math>s\, </math>を含む点の真部分集合から残りの点の集合へ向かう有向辺の集合を<math>s\, </math>-カットと呼ぶとき，<math>s\, </math>-カットの大きさの最小値は，<math>s\, </math>を根とする有向全域出木(すなわち全域木に根から葉へ向かって辺に向きをつけたもの)の互いに辺素な集合の最大値に等しい(J.Edmondsの定理 [1] )．大きさ最小の<math>s\, </math>-カットを多項式時間で求めることができる．
@@ 28行目: / 28行目: @@
 [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.
+[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.
@@ 38行目: / 38行目: @@
 [7] W. Mader, "Konstruktion aller ''n''-fach kantenzusammenh&auml;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.
+[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.
 [[Category:グラフ･ネットワーク|ぐらふのれんけつど]]

@@ 1行目: / 1行目: @@
 '''【れんけつど (connectivity of graph)】'''
 無向(有向)グラフ<math>G\,</math>の辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなるとき, 辺カットという. <math>G\,</math>の点の部分集合は, それを除去すると残ったグラフが2点以上をもち, かつ連結(強連結)でなくなるとき, 点カットという. 辺カット(点カット)の大きさの最小値を辺連結度(点連結度)という.
-詳しくは[[《グラフの連結度》|基礎編：グラフの連結度]]を参照.
+=== 詳説 ===

← 古い版		2007年8月8日 (水) 11:50時点における版
2行目:		2行目:

	無向(有向)グラフ<math>G\,</math>の辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなるとき, 辺カットという. <math>G\,</math>の点の部分集合は, それを除去すると残ったグラフが2点以上をもち, かつ連結(強連結)でなくなるとき, 点カットという. 辺カット(点カット)の大きさの最小値を辺連結度(点連結度)という.		無向(有向)グラフ<math>G\,</math>の辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなるとき, 辺カットという. <math>G\,</math>の点の部分集合は, それを除去すると残ったグラフが2点以上をもち, かつ連結(強連結)でなくなるとき, 点カットという. 辺カット(点カット)の大きさの最小値を辺連結度(点連結度)という.
		+
		+	詳しくは[[《グラフの連結度》\|基礎編：グラフの連結度]]を参照.

← 古い版		2007年7月11日 (水) 07:59時点における版
1行目:		1行目:
	'''【れんけつど (connectivity of graph)】'''		'''【れんけつど (connectivity of graph)】'''

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

← 古い版	2007年7月20日 (金) 00:56時点における版
(相違点なし)