直径(グラフ)

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

定義

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

$G$ の直径とは、$\mathrm{max}_{v,v' \in G} d(v,v')$ のことをいい、$\mathrm{diag}(G)$ と記す。