距離(グラフ)
概要
グラフ $G=(V, E)$ の$2$頂点 $v$, $w$ 間の距離とは、$v$ と $w$ を結ぶ道の長さの最小値のことである。
定義
グラフ $G = (V,E)$ の$2$頂点 $v, ~ w\in V$ の距離 (distance) とは、$v$ と $w$ を結ぶ道の長さの最小値をいい、$d(v, w)$ によりあらわす。$v$ と $w$ を結ぶ道が存在しないときは $d(v, w)=\infty$ と定める。
与えられた頂点 $v\in V$ について、$v$ と他の頂点の距離 $d(v, w) ~ (w\in V)$ の最大値を $G$ の $v$-半径といい、
$$\rad (G, v)=\max_{w\in V} d(v, w)$$
によりあらわす。$v$-半径の最小値を $G$ の半径 (radius) といい、
$$\rad (G)=\min_{v\in V} \rad(G, v)=\min_{v\in V}\max_{w\in V} d(v, w)$$
によりあらわす。$v$-半径の最大値、つまりあらゆる$2$頂点 $v, ~ w\in V$ に関する $d(v, w)$ の最大値を $G$ の直径 (diameter) といい、
$$\diam (G)=\max_{v\in V} \rad(G, v)=\max_{v, ~ w\in V} d(v, w)$$
によりあらわす。
例
完全グラフ $K_n$ においては、異なる$2$頂点間の距離はつねに $1$ となるので、半径、直径はともに $1$ となる。
性質
通常の距離空間と同様に、グラフの距離については三角不等式が成り立つ。
$u, v, w\in V$ について、つねに
$$d(u, w)\leq d(u, v)+d(v, w)$$
が成り立つ。
$m=d(u, v)$ とおいて、$u$ と $v$ を結ぶ最短の道をひとつとり、
$$u_0=u, u_1, \ldots, u_m=v$$ とおく。
同様に、$n=d(u, v)$ とおいて、$w$ と $v$ を結ぶ最短の道をひとつとり、$$w_0=w, w_1, \ldots, w_n=v$$ とおく。
$u_i=w_j$ となる $j$ が存在する $i$ で最小のものをとり（$u_m=w_n=v$ だから、このような $i$ は少なくともひとつ存在する）、これを $s$ とおく。
さらに $u_s=w_j$ となる $j$ をひとつとり、これを $t$ とおく。
このとき、$0\leq i\leq s-1$, $0\leq j\leq t-1$ の範囲には $u_i=w_j$ となる $i$, $j$ は存在しないから
$$u=u_0, u_1, \ldots, u_s=w_t, w_{t-1}, \ldots, w_0=w$$
は $u, w$ を結ぶ道となるので、
$$d(u, w)\leq s+t\leq d(u, v)+d(v, w)$$
が成り立つ。
