그래프 이론에서 거리(距離, distance)는 두 정점(vertex) 사이의 최단 경로(shortest path)의 길이를 나타내는 개념이다. 이는 두 정점이 그래프 내에서 얼마나 "가까이" 연결되어 있는지를 측정하는 척도로 사용된다.
정의
-
무가중치 무방향 그래프 (Unweighted Undirected Graph) 가중치가 없는 무방향 그래프에서 두 정점 $u$와 $v$ 사이의 거리 $d(u, v)$는 $u$에서 $v$로 가는 최단 경로를 구성하는 간선(edge)의 개수를 의미한다. 이러한 최단 경로는 지름길(geodesic)이라고도 불린다.
-
가중 그래프 (Weighted Graph) 각 간선에 양의 가중치(weight)가 할당된 가중 그래프에서 두 정점 $u$와 $v$ 사이의 거리 $d(u, v)$는 $u$에서 $v$로 가는 모든 경로 중에서 간선 가중치의 합이 가장 작은 경로의 가중치 합을 의미한다. 이 경우, 최단 경로를 찾기 위해 다익스트라(Dijkstra) 알고리즘이나 벨만-포드(Bellman-Ford) 알고리즘과 같은 알고리즘이 사용된다.
-
방향 그래프 (Directed Graph) 방향 그래프에서는 $u$에서 $v$로 가는 경로와 $v$에서 $u$로 가는 경로가 다를 수 있으므로, 거리 또한 방향성을 가진다. 즉, $d(u, v)$는 $u$에서 $v$로 가는 최단 경로의 길이를 의미하며, 일반적으로 $d(v, u)$와는 다를 수 있다.
속성
일반적으로 그래프 이론에서의 거리는 다음과 같은 속성을 만족한다 (특히 무방향 그래프에서):
- 비음성(Non-negativity): $d(u, v) \ge 0$.
- 동일성(Identity of indiscernibles): $d(u, v) = 0$ 이면 $u = v$ 이다.
- 대칭성(Symmetry): 무방향 그래프에서 $d(u, v) = d(v, u)$ 이다. (방향 그래프에서는 일반적으로 성립하지 않음)
- 삼각 부등식(Triangle inequality): $d(u, w) \le d(u, v) + d(v, w)$.
이러한 속성들 때문에 그래프의 거리는 특정 조건 하에서 수학적 거리 공간(metric space)의 공리를 만족하기도 한다.
특수한 경우
- 자기 자신과의 거리: 어떤 정점 $u$에서 자기 자신 $u$까지의 거리는 항상 0이다 ($d(u, u) = 0$).
- 연결되지 않은 정점: 두 정점 $u$와 $v$ 사이에 경로가 존재하지 않는 경우(즉, 같은 연결 요소(connected component)에 속하지 않는 경우), 이들 사이의 거리는 종종 무한대($\infty$)로 정의된다.
관련 개념
그래프의 거리를 기반으로 다양한 개념들이 정의된다.
-
이심률(Eccentricity): 한 정점 $v$의 이심률 $e(v)$는 해당 정점에서 그래프 내의 다른 모든 정점들까지의 거리 중에서 가장 먼 거리, 즉 $e(v) = \max_{u \in V} d(v, u)$ 로 정의된다. 이는 해당 정점이 다른 정점들로부터 얼마나 멀리 떨어져 있는지를 나타낸다.
-
반지름(Radius): 그래프의 반지름 $rad(G)$는 모든 정점의 이심률 중에서 가장 작은 값이다. $rad(G) = \min_{v \in V} e(v)$. 이는 그래프 내에서 "가장 중심적인" 정점이 가질 수 있는 이심률의 최솟값이다.
-
지름(Diameter): 그래프의 지름 $diam(G)$은 모든 정점의 이심률 중에서 가장 큰 값이다. 즉, 그래프 내의 어떤 두 정점 사이의 최단 거리 중 가장 큰 값이다. $diam(G) = \max_{v \in V} e(v) = \max_{u,v \in V} d(u,v)$. 이는 그래프 내에서 가장 멀리 떨어져 있는 두 정점 사이의 거리를 나타낸다.
-
중심(Center): 이심률이 그래프의 반지름과 같은 정점들을 그래프의 중심이라고 한다. 이들은 그래프에서 가장 "중앙"에 위치하는 정점들로 볼 수 있다.
-
주변(Periphery): 이심률이 그래프의 지름과 같은 정점들을 그래프의 주변이라고 한다. 이들은 그래프에서 가장 "가장자리"에 위치하는 정점들로 볼 수 있다.