「辺連結度」の版間の差分

2007年7月17日 (火) 13:43時点における版

【へんれんけつど (edge connectivity)】

無向(有向)グラフ $G\,$ の辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなるとき, 辺カットという. 辺連結度 $\lambda (G)\,$ は辺カットの大きさの最小値. グラフの辺に重みがついている場合には, 辺カットの辺の重み和の最小値.

2007年7月14日 (土) 14:11時点における版 (ソースを閲覧) 222.225.128.87 (トーク) ← 古い編集		2007年7月17日 (火) 13:43時点における版 (ソースを閲覧) 122.17.2.240 (トーク) 新しい編集 →
1行目:		1行目:
−	【へんれんけつど (edge connectivity)】	+	'''【へんれんけつど (edge connectivity)】'''

	無向(有向)グラフ<math>G\,</math>の辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなるとき, 辺カットという. 辺連結度<math>\lambda(G)\,</math>は辺カットの大きさの最小値. グラフの辺に重みがついている場合には, 辺カットの辺の重み和の最小値.		無向(有向)グラフ<math>G\,</math>の辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなるとき, 辺カットという. 辺連結度<math>\lambda(G)\,</math>は辺カットの大きさの最小値. グラフの辺に重みがついている場合には, 辺カットの辺の重み和の最小値.