거리 (그래프 이론)

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

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

같이 보기

• 거리 행렬
• 저항 거리
• 매개 중심성
• 중심성
• 근접성
• 거리 그래프