「連結度 (グラフの)」の版間の差分
ナビゲーションに移動
検索に移動
細 ("連結度 (グラフの)" を保護しました。 [edit=sysop:move=sysop]) |
|||
| 2行目: | 2行目: | ||
無向(有向)グラフ<math>G\,</math>の辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなるとき, 辺カットという. <math>G\,</math>の点の部分集合は, それを除去すると残ったグラフが2点以上をもち, かつ連結(強連結)でなくなるとき, 点カットという. 辺カット(点カット)の大きさの最小値を辺連結度(点連結度)という. | 無向(有向)グラフ<math>G\,</math>の辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなるとき, 辺カットという. <math>G\,</math>の点の部分集合は, それを除去すると残ったグラフが2点以上をもち, かつ連結(強連結)でなくなるとき, 点カットという. 辺カット(点カット)の大きさの最小値を辺連結度(点連結度)という. | ||
| + | |||
| + | 詳しくは[[《グラフの連結度》|基礎編：グラフの連結度]]を参照. | ||
2007年8月8日 (水) 20:50時点における版
【れんけつど (connectivity of graph)】
無向(有向)グラフの辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなるとき, 辺カットという. の点の部分集合は, それを除去すると残ったグラフが2点以上をもち, かつ連結(強連結)でなくなるとき, 点カットという. 辺カット(点カット)の大きさの最小値を辺連結度(点連結度)という.
詳しくは基礎編：グラフの連結度を参照.