📂グラフ理論

グラフ内の距離、近傍、直径、周囲

定義

グラフ $G$ で、始点が$v \in V(G)$ で終点が$w \in V(G)$ のパスの集まりを$P(v,w)$ とし、$v \in V(G)$ を含むサイクルの集まりを$C(v)$ としよう。そして、ウォーク $x$ の長さを$l(x)$と示そう。

1. 二つの頂点$v,w \in V(G)$ 間の距離$d$ は、$v$ が始点で$w$ が終点のパスの長さの中で最も小さい値で定義される。つまり、 $$d(v,w) := \min_{v,w \in V(G)} \left\{ l(x) : x \in P(v,w) \right\}$$
2. 頂点$v \in V(G)$ に対し、$v$ との距離が正確に$i$ の頂点の集まり$N^{i} (v) \subset V(G)$ を**$i$-ネイバーフッド**と言う。
3. グラフ$G$ の直径$\text{diam}$ は、すべての頂点間の距離の中で最大の値として定義される。つまり、 $$\text{diam} (G) := \sup_{v,w \in V(G)} \left\{ d(v,w) : v \ne w \right\}$$
4. グラフ$G$ の周長$\text{girth}$ は、すべてのサイクルの長さの中で最小の値として定義される。つまり、 $$\text{girth}(G) := \min_{v \in V(G)} \left\{ l(x) : x \in C(v) \right\}$$

説明

グラフ内の頂点間の距離は、ジオデシック距離とも呼ばれる。ユークリッド距離と異なり、一つの頂点から別の頂点に到達するまでの実際の歩数を表しているため、この名前は妥当と言えるだろう。例えば、以下のグラフでは、$d(v,w)$ はどんな場合でも$2$ より小さくなることは無く、$d(v,w) = 2$ になる。

直径の定義は初めは奇妙に感じられるかもしれない。比喩として、円 $x^2 + y^2 = r^2$を考えてみよう。円上に任意の二点を選んだ場合、二点間の距離が最も遠くなるのは、二点が円の中心に対して対称的に位置するときだ。もちろん、その距離は$2r$で、これが我々が円の直径と呼ぶものだ。例えば、上記のグラフの直径は$2$である。

周長は概念的に、グラフにおける最小のサイクルのサイズを言う。明示的には述べていないが、グラフにサイクルが存在しない場合は、その周長を無限大とする。また、任意のグラフにおいて周長の最小値が$3$ より低くなることはないと自明である。例えば、下の図を見れば、いくつかのサイクルが存在するものの、最小のサイクルの長さは$3$ であるため、周長は$3$ になる。