半径(グラフ)

基本的な用語についてはグラフについても参照されたい。

定義

連結グラフ $G = (V,E)$ について、頂点 $v$ と $v'$ との距離とは、$v$ と $v'$ とをつなぐ道のなかで最短のものの長さのことをいい、$d(v,v')$ と記す。ここで、道 $v_0e_0v_1\ldots e_{n-1}v_n$ の長さを $n$ と定める。

頂点 $v$ について、$v$-半径とは $\mathrm{max}_{v' \in G} d(v, v')$ のことをいい、$\mathrm{rad}(G,v)$ と記す。

$G$ の半径とは、$\mathrm{min}_{v \in G} \mathrm{rad}(G,v)$ のことをいい、$\mathrm{rad}(G)$ と記す。