連結度
提供: Mathpedia
連結性
空でないグラフ $G = (V,E)$ が連結であるとは、$G$ の任意の頂点 $v$, $v'$ についても $v$ と $v'$ を結ぶ道が存在することをいう。
注意 1 (空グラフは非連結)
ここでは空グラフは連結であるとはしない。このnlabの記事などを参照されたい。
連結度
グラフ $G$ について、$k$-連結であるとは、任意の濃度 $k$ 未満の集合 $X \subset |G|$ に対して部分グラフ $G - X$ が連結となることをいう。ただし、$G - X$ とは頂点集合を $|G| \setminus X$ とし、辺集合を $E(G) \cap [|G| \setminus X]^2$ とするグラフのことをいう。
$G$ が $k$-連結となるような最大の整数 $k$ を $G$ の連結度という。
information
情報源
- R. Diestel. "Graph Theory". Springer (2000).
