距離(グラフ)

同義語：グラフの距離グラフ距離graph distance

概要

定義

本記事では、特に断らない限り無向のグラフ $G=(V,E)$ を扱う（ループや平行辺があってもよい）。$G$ の頂点 $u,v$ を結ぶ道とは、$u$ から始まり $v$ で終わる歩道であって頂点をすべて相異なるものをいい、その長さとは含まれる辺の本数をいう。長さ $0$ の道は 1 個の頂点だけからなる。

グラフの距離

$G=(V,E)$ をグラフとし、$u,v\in V$ とする。$u$ と $v$ を結ぶ道が存在するとき、そのような道の長さの最小値を $u$ と $v$ の距離（distance）といい、$d_G(u,v)$ と書く。$u$ と $v$ を結ぶ道が存在しないときは
$$d_G(u,v):=\infty$$
と定める。$G$ が文脈から明らかなときは $d(u,v)$ と書く。長さが $d_G(u,v)$ に等しい $u$ と $v$ を結ぶ道を $u$ と $v$ の最短路（shortest path）または測地道（geodesic）という。

$u$ と $v$ を結ぶ道が存在するとき、その長さ全体は $\mathbb{N}$ の空でない部分集合なので最小値を持ち、距離は矛盾なく定まる。$G$ が無限グラフでもこの点は変わらない。1 個の頂点 $u$ だけからなる道は $u$ と $u$ を結ぶ長さ $0$ の道なので、常に $d_G(u,u)=0$ である。$\infty$ については、任意の $n\in\mathbb{N}$ に対し $n<\infty$、$n+\infty=\infty+n=\infty+\infty=\infty$ と約束する。

偏心度・半径・直径・中心

$G=(V,E)$ を空でない有限な連結グラフとする。頂点 $v\in V$ の偏心度（eccentricity）を
$$e_G(v):=\max_{u\in V}d_G(v,u)$$
と定める。偏心度は離心度、あるいは $G$ の $v$-半径（$\operatorname{rad}(G,v)$ とも書く）ともよばれる。$G$ の半径（radius）と直径（diameter）を
$$\operatorname{rad}(G):=\min_{v\in V}e_G(v),\qquad \operatorname{diam}(G):=\max_{v\in V}e_G(v)=\max_{u,v\in V}d_G(u,v)$$
と定める。偏心度が半径に等しい頂点を中心頂点（central vertex）といい、中心頂点全体の集合を $G$ の中心（center）という。偏心度が直径に等しい頂点を周辺頂点（peripheral vertex）という。

$G$ が有限連結でない場合、最大値・最小値が存在しないことがあるので、$\max$、$\min$ を $\sup$、$\inf$ に置き換え、値として $\infty$ も許して同じ量を定義する。非連結なグラフでは異なる連結成分(グラフ)の頂点の間の距離が $\infty$ になるので、偏心度・半径・直径はすべて $\infty$ となり、通常は各連結成分ごとに考える。

球と距離層

頂点 $v\in V$ と $r\in\mathbb{N}$ に対し、
$$B_r(v):=\{u\in V\mid d_G(u,v)\le r\},\qquad S_r(v):=\{u\in V\mid d_G(u,v)=r\}$$
をそれぞれ $v$ を中心とする半径 $r$ の球（ball）、および $v$ からの距離層（distance layer）という。$S_0(v)=\{v\}$、$S_1(v)$ は $v$ 以外の隣接頂点全体（$v$ の近傍）であり、$B_r(v)=S_0(v)\cup S_1(v)\cup\cdots\cup S_r(v)$ である。

直感

グラフの距離とは、二つの頂点の間を辺づたいに移動するのに必要な最少の「一歩」の数である。座標や辺の幾何学的な長さは使わず、頂点どうしの接続関係だけから近さを定める点が特徴であり、友人関係の隔たり、通信網の最少中継数、状態遷移の最少手数はいずれもグラフの距離として表せる。距離を導入すると、「結ばれているか否か」という連結性の二値的な情報が $0,1,2,\dots$ という段階的な情報に細分される。ある頂点から同じ距離にある頂点を層に分ければ幅優先探索が得られ、全頂点への距離を集約すれば偏心度・半径・直径が得られる。連結グラフの頂点集合はグラフの距離によって距離空間になり、グラフの距離は組合せ的な接続関係を距離幾何へ翻訳する最初の橋である。

例と反例

完全グラフの距離

$n\ge2$ の完全グラフ $K_n$ では、相異なる 2 頂点は必ず隣接するので $d(u,v)=1$（$u\neq v$）である。したがってすべての頂点の偏心度は $1$ で、$\operatorname{rad}(K_n)=\operatorname{diam}(K_n)=1$ であり、中心は $V$ 全体である。$K_1$ では偏心度・半径・直径はすべて $0$ である。

道グラフの距離

頂点を $0,1,\dots,n-1$ とし、$|i-j|=1$ のとき、かつそのときに限り $i$ と $j$ を辺で結んだグラフを道グラフ $P_n$ という。$P_n$ では $d(i,j)=|i-j|$ である。実際、$i< j$ として $i,i+1,\dots,j$ は長さ $j-i$ の道であり、一方、$i$ から $j$ への任意の道は一歩ごとに頂点の番号を高々 $1$ しか変えないので長さは $j-i$ 以上である。頂点 $i$ の偏心度は $\max\{i,\ n-1-i\}$ だから
$$\operatorname{diam}(P_n)=n-1,\qquad \operatorname{rad}(P_n)=\left\lceil\frac{n-1}{2}\right\rceil$$
であり、中心は $n$ が奇数なら中央の 1 頂点 $\{(n-1)/2\}$、偶数なら中央の 2 頂点 $\{n/2-1,\ n/2\}$ である。

閉路グラフの距離

頂点を $0,1,\dots,n-1$（$n\ge3$）とし、$i$ と $i+1$（添字は $n$ を法として考える）を辺で結んだ閉路グラフ $C_n$ では
$$d(i,j)=\min\{|i-j|,\ n-|i-j|\}$$
である。実際、$i$ から $j$ へは閉路に沿って二つの向きに進む道があり、長さはそれぞれ $|i-j|$ と $n-|i-j|$ である。閉路グラフの道は、途中で進む向きを変えると直前の頂点に戻って頂点が重複するので、二つの向きのいずれかに沿って進むしかなく、これより短い道はない。すべての頂点の偏心度は $\lfloor n/2\rfloor$ であり、半径と直径もともに $\lfloor n/2\rfloor$、中心は $V$ 全体である。

星グラフの距離

中心の頂点 $c$ と $n\ge2$ 個の葉 $\ell_1,\dots,\ell_n$ からなり、辺が $c\ell_1,\dots,c\ell_n$ である星グラフ（完全二部グラフ $K_{1,n}$）では、$d(c,\ell_i)=1$、$d(\ell_i,\ell_j)=2$（$i\neq j$）である。よって $e(c)=1$、$e(\ell_i)=2$ で、$\operatorname{rad}(K_{1,n})=1$、$\operatorname{diam}(K_{1,n})=2$、中心は $\{c\}$ である。これは prop-graph-distance-radius-diameter の不等式 $\operatorname{diam}(G)\le2\operatorname{rad}(G)$ で等号が成り立つ例である。

非連結グラフの距離

$G$ が二つの連結成分(グラフ) $C_1,C_2$ を持ち、$u\in V(C_1)$、$v\in V(C_2)$ なら、$u$ と $v$ を結ぶ道は存在しないので $d_G(u,v)=\infty$ である。同じ成分に属する 2 頂点の間の距離は有限であり、各成分の頂点集合はグラフの距離によって距離空間になる（prop-graph-distance-metric）。

反例：描画上の距離

グラフを平面に描いたとき、紙面上で近くに描かれた 2 頂点のグラフの距離が小さいとは限らず、遠くに描かれた 2 頂点も 1 本の辺で結ばれていれば距離は $1$ である。たとえば長さ 4 の道 $P_5$ を、両端の頂点 $0$ と $4$ が紙面上で隣り合うように折り曲げて描いても $d(0,4)=4$ である。満たす性質：2 頂点は描画上で近い（または遠い）。満たさない性質：グラフの距離が小さい（または大きい）。破る含意：「描画上の距離が小さい ⇒ グラフの距離が小さい」は成り立たない。グラフの距離は図の座標ではなく、辺による接続だけから決まる。

反例：有向グラフの距離の非対称性

有向グラフでは、$u$ から $v$ への有向道の長さの最小値を距離 $d(u,v)$ と定めるが、これは対称とは限らない。頂点 $u,v$ と 1 本の有向辺 $(u,v)$ だけからなる有向グラフでは $d(u,v)=1$ であるが、$v$ から $u$ への有向道はないので $d(v,u)=\infty$ である。満たす性質：非負性、$d(u,v)=0\Leftrightarrow u=v$、三角不等式。満たさない性質：対称性 $d(u,v)=d(v,u)$。破る含意：「有向グラフの距離 ⇒ 距離空間の公理をすべて満たす」は成り立たない。無向グラフの距離が対称であることは prop-graph-distance-metric で示す。

性質

歩道からの道の取り出し

$G$ の頂点 $u$ と $v$ を結ぶ長さ $\ell$ の歩道が存在すれば、$u$ と $v$ を結ぶ長さ $\ell$ 以下の道が存在する。特に $d_G(u,v)\le\ell$ である。

$\ell$ に関する帰納法で示す。歩道 $u=v_0,e_1,v_1,\dots,e_\ell,v_\ell=v$ をとる。頂点 $v_0,\dots,v_\ell$ がすべて相異なればこれは道であり、長さは $\ell$ である。そうでなければ $v_i=v_j$ となる $i< j$ があり、$v_0,e_1,\dots,e_i,v_i=v_j,e_{j+1},\dots,e_\ell,v_\ell$ は $u$ と $v$ を結ぶ長さ $\ell-(j-i)<\ell$ の歩道である。帰納法の仮定により、$u$ と $v$ を結ぶ長さ $\ell-(j-i)\le\ell$ 以下の道が存在する。$\square$

距離空間の公理

$G=(V,E)$ をグラフとする。任意の $u,v,w\in V$ について次が成り立つ。

$d_G(u,v)\in\mathbb{N}\cup\{\infty\}$、特に $d_G(u,v)\ge0$ である。
$d_G(u,v)=0$ であることと $u=v$ であることは同値である。
$d_G(u,v)=d_G(v,u)$ である。
（三角不等式）$d_G(u,w)\le d_G(u,v)+d_G(v,w)$ である。
したがって $G$ が連結グラフなら $d_G$ は $V$ 上の距離関数であり、$(V,d_G)$ は距離空間である。一般のグラフでは $d_G$ は値 $\infty$ を許す距離関数（拡張距離）であり、各連結成分の頂点集合への制限は距離関数である。

距離は道の長さ（自然数）の最小値または $\infty$ である。
$u=v$ なら 1 個の頂点 $u$ からなる道により $d_G(u,u)=0$ である。逆に $d_G(u,v)=0$ なら $u$ と $v$ を結ぶ長さ $0$ の道があり、それは 1 個の頂点からなるので $u=v$ である。
無向グラフでは、$u$ と $v$ を結ぶ道 $v_0,e_1,v_1,\dots,e_\ell,v_\ell$ を逆順にした $v_\ell,e_\ell,\dots,e_1,v_0$ は $v$ と $u$ を結ぶ同じ長さの道である。よって $u$ と $v$ を結ぶ道の長さの集合と $v$ と $u$ を結ぶ道の長さの集合は一致し（どちらも空である場合を含む）、$d_G(u,v)=d_G(v,u)$ である。
$d_G(u,v)$ または $d_G(v,w)$ が $\infty$ なら右辺は $\infty$ で不等式は成り立つ。両方とも有限なら、$u$ と $v$ を結ぶ最短路と $v$ と $w$ を結ぶ最短路を $v$ でつなぐと、$u$ と $w$ を結ぶ長さ $d_G(u,v)+d_G(v,w)$ の歩道が得られる。lem-graph-distance-walk-to-path により $d_G(u,w)\le d_G(u,v)+d_G(v,w)$ である。
$G$ が連結なら任意の 2 頂点を結ぶ道があるので距離はすべて有限であり、(1)〜(4) は距離空間の公理そのものである。$\square$

有限距離と連結成分

グラフ $G=(V,E)$ の頂点の関係「$d_G(u,v)<\infty$」は $V$ 上の同値関係であり、その同値類は $G$ の連結成分(グラフ)の頂点集合と一致する。すなわち、$u,v$ が同じ連結成分に属することと $d_G(u,v)<\infty$ とは同値である。

$d_G(u,v)<\infty$ であることは、定義により $u$ と $v$ を結ぶ道が存在することと同値である。反射性は $d_G(u,u)=0$、対称性は prop-graph-distance-metric (3)、推移性は三角不等式 (4)（有限な二つの値の和は有限）から従う。連結成分とは、この同値関係「結ぶ道が存在する」の同値類が誘導する部分グラフ（極大な連結部分グラフ）であるから、同値類は連結成分の頂点集合である。$\square$

隣接関係の復元

グラフ $G$ の相異なる頂点 $u,v$ について、$u$ と $v$ が隣接することと $d_G(u,v)=1$ とは同値である。したがって、ループのないグラフは頂点集合と距離関数 $d_G$ から（平行辺の重複度を除いて）復元できる。

$u$ と $v$ を結ぶ辺 $e$ があれば $u,e,v$ は長さ $1$ の道なので $d_G(u,v)\le1$ であり、$u\neq v$ より $d_G(u,v)\neq0$ なので $d_G(u,v)=1$ である。逆に $d_G(u,v)=1$ なら $u$ と $v$ を結ぶ長さ $1$ の道、すなわち $u$ と $v$ を結ぶ辺が存在する。$\square$

半径と直径の不等式

空でない有限連結グラフ $G$ について
$$\operatorname{rad}(G)\le\operatorname{diam}(G)\le2\operatorname{rad}(G)$$
が成り立つ。

半径は偏心度の最小値、直径は偏心度の最大値なので、第 1 の不等式は明らかである。第 2 の不等式のため、中心頂点 $c$（$e_G(c)=\operatorname{rad}(G)$ となる頂点）を一つとる。任意の $u,v\in V$ に対し、三角不等式（prop-graph-distance-metric）と偏心度の定義により
$$d_G(u,v)\le d_G(u,c)+d_G(c,v)\le e_G(c)+e_G(c)=2\operatorname{rad}(G)$$
である。すべての $u,v$ について最大値をとれば $\operatorname{diam}(G)\le2\operatorname{rad}(G)$ を得る。$\square$

両方の不等式はそれぞれ最良である。$\operatorname{rad}=\operatorname{diam}$ となる例が完全グラフ・閉路グラフ（ex-graph-distance-complete、ex-graph-distance-cycle）、$\operatorname{diam}=2\operatorname{rad}$ となる例が星グラフ（ex-graph-distance-star）である。

部分グラフと距離

$H$ がグラフ $G$ の部分グラフなら、任意の $u,v\in V(H)$ について $d_G(u,v)\le d_H(u,v)$ である。特に、同じ頂点集合上のグラフで $E(G)\subset E(G')$ なら $d_{G'}(u,v)\le d_G(u,v)$ である。すなわち、辺を加えると距離は増えず、辺を取り除くと距離は減らない。

$H$ の頂点と辺は $G$ の頂点と辺なので、$H$ における $u$ と $v$ を結ぶ道は $G$ における $u$ と $v$ を結ぶ道である。よって $G$ における道の長さの最小値は $H$ におけるそれ以下である（$H$ に道がなければ $d_H(u,v)=\infty$ で不等式は自明）。後半は $G$ を $G'$ の全域部分グラフとみればよい。$\square$

辺を取り除いて連結成分が分かれれば、有限だった距離が $\infty$ に変わることもある。

補足

有限グラフの距離は幅優先探索によって計算できる。始点 $s$ から探索を行うと、頂点は距離層 $S_0(s),S_1(s),S_2(s),\dots$ の順に発見され、距離 $r$ の頂点から未発見の隣接頂点へ距離 $r+1$ が付けられる。長さ $r+1$ の道が実際に構成され、それより短い道があればその頂点は前の層で発見済みであることから、こうして付けた値は距離に一致する。隣接リスト表現を用いれば計算量は頂点数と辺数の和に比例する（BM08 第 6 章、Wes01 §2.3）。
有向グラフでは有向道の長さの最小値を距離と定め、一般に $d(u,v)\neq d(v,u)$ となる（ex-graph-distance-counterexample-directed）。重み付きグラフでは辺の本数の代わりに辺の重みの総和を最小化し、最短路問題として Dijkstra法などのアルゴリズムで扱う。負の重みを持つ辺がある場合には最短路の存在自体に追加の条件が必要であり、本記事の無重みの距離とは区別する。
グラフの距離は、Cayleyグラフの語距離により有限生成群を距離空間として調べる幾何学的群論、Hamming グラフ（Hammingグラフ）の距離が Hamming距離に一致する符号理論、距離正則グラフなどの代数的グラフ理論、平均距離や直径によって通信効率を測るネットワーク科学など、多くの分野で用いられる。本記事の記述はおおむね Die17 §1.3 および BM08 第 3 章に従う。