거리 (그래프 이론)

틀:위키데이터 속성 추적 그래프 이론의 수학적 영역에서, 그래프의 두 꼭짓점간의 거리는 두 점을 잇는 최단 경로(그래프 지오데식(틀:Llang)이라고도 불린다)에 있는 모서리의 개수이다. 이 거리는 지오데식 거리(틀:Llang)라고도 부른다.^[1] 두 꼭짓점 사이에는 최단 경로가 하나 이상 있을 수 있다는 점을 주목하라.^[2] 두 꼭짓점 사이에 경로가 없을 때, 즉, 두 꼭짓점이 서로 다른 연결 요소에 있다면, 전통적으로 거리는 무한으로 정의한다.

유향 그래프의 경우에 호로 이루어진 두 점 $u$ 와 $v$ 간의 거리 $d (u, v)$ 는 $u$ 에서 $v$ 까지 가는 경로가 적어도 하나가 있을 때, 가장 짧은 거리로 정의한다.^[3] 무향 그래프의 경우와는 달리 $d (u, v)$ 는 $d (v, u)$ 와 같을 필요가 없고, 하나는 정의되고 다른 하나는 정의되지 않을 수도 있다.