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

2007年7月13日 (金) 01:06時点における版

【てんれんけつど (vertex connectivity)】

無向(有向)グラフ $G\,$ の点の部分集合は, それを除去するとグラフが2点以上をもち, かつ連結(強連結)でなくなるとき, 点カットという. 点連結度 $\kappa (G)\,$ は点カットの大きさの最小値. すべての点対間の局所点連結度の最小値とグラフの点連結度は一致する.

2007年7月12日 (木) 22:39時点における版 (ソースを閲覧) 122.17.2.240 (トーク) (新しいページ: '【てんれんけつど (vertex connectivity)】無向(有向)グラフ$G$の点の部分集合は, それを除去するとグラフが2点以上をもち, かつ連結(強...')		2007年7月13日 (金) 01:06時点における版 (ソースを閲覧) 211.9.162.254 (トーク) 新しい編集 →
1行目:		1行目:
	【てんれんけつど (vertex connectivity)】		【てんれんけつど (vertex connectivity)】

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