辺連結度

提供: ORWiki

2007年7月13日 (金) 11:24時点における122.17.2.240 (トーク)による版 (新しいページ: '【へんれんけつど (edge connectivity)】無向(有向)グラフ$G$の辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなるとき,...')

(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)

ナビゲーションに移動検索に移動

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

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

「https://orsj-ml.org/orwiki/wiki/index.php?title=辺連結度&oldid=4060」から取得