📂그래프이론

그래프에서의 거리, 네이버후드, 지름, 둘레

정의

그래프 $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\}$$

설명

그래프에서 버텍스 사이의 거리는 지오데식 거리^{geodesic distance}라 불리기도 한다. 이러한 명명은 유클리드 거리와 달리 실제로 한 버텍스에서 다른 버텍스로 도달할 때까지 걸리는 횟수를 나타내므로 타당하다고 볼 수 있겠다. 예로써 다음의 그래프에서 $d(v,w)$ 는 모든 경우의 수를 고려해보아도 $2$ 보다 작아질 순 없고, $d(v,w) = 2$ 다.

지름의 정의는 언뜻 어색해보일 수 있다. 비유로써 원 $x^2 + y^2 = r^2$ 을 생각해보자. 원 위에서 임의의 두 점을 고른다고 했을 때, 두 점의 거리가 가장 멀어지는 경우는 두 점이 원의 중심에 대해 대칭으로 위치할 때다. 당연하지만 그 거리는 $2r$, 이는 우리가 원에서 말하는 지름이다. 예로써 위의 그래프는 지름이 $2$ 다.

안둘레는 개념적으로 말해 그래프에서 가장 작은 사이클의 크기를 말한다. 굳이 쓰지는 않았지만 그래프에 사이클이 존재하지 않을 경우 무한대로 둔다. 또한 자명하게도 어떤 그래프든 안둘레의 최소값은 $3$ 보다 낮아질 수 없다. 예를 들어 다음의 그림을 보면 여러 사이클이 존재하지만 가장 작은 사이클의 길이는 $3$ 이므로 안둘레는 $3$ 이 된다.