点連結度

提供: ORWiki
2007年7月12日 (木) 22:39時点における122.17.2.240 (トーク)による版 (新しいページ: '【てんれんけつど (vertex connectivity)】 無向(有向)グラフ$G$の点の部分集合は, それを除去するとグラフが2点以上をもち, かつ連結(強...')
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

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

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