連結度 (グラフの)

【れんけつど (connectivity of graph)】

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