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