「辺連結度」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: '【へんれんけつど (edge connectivity)】 無向(有向)グラフ$G$の辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなるとき,...') |
|||
| 1行目: | 1行目: | ||
【へんれんけつど (edge connectivity)】 | 【へんれんけつど (edge connectivity)】 | ||
| − | 無向(有向)グラフ | + | 無向(有向)グラフ<math>G\,</math>の辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなるとき, 辺カットという. 辺連結度<math>\lambda(G)\,</math>は辺カットの大きさの最小値. グラフの辺に重みがついている場合には, 辺カットの辺の重み和の最小値. |
2007年7月14日 (土) 14:11時点における版
【へんれんけつど (edge connectivity)】
無向(有向)グラフの辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなるとき, 辺カットという. 辺連結度は辺カットの大きさの最小値. グラフの辺に重みがついている場合には, 辺カットの辺の重み和の最小値.
