거리 (그래프 이론)

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

유향 그래프의 경우에 호로 이루어진 두 점 와 간의 거리 는 에서 까지 가는 경로가 적어도 하나가 있을 때, 가장 짧은 거리로 정의한다.F. Harary, Graph Theory, Addison-Wesley, 1969, p.199. 무향 그래프의 경우와는 달리 는 와 같을 필요가 없고, 하나는 정의되고 다른 하나는 정의되지 않을 수도 있다.

 같이 보기 
 거리 행렬
 저항 거리
 매개 중심성
 중심성
 근접성
 거리 그래프

 각주 

분류:그래프 이론
분류:계량기하학