거리 (그래프 이론)

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

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

같이 보기[편집]

각주[편집]

↑ Bouttier, Jérémie; Di Francesco,P.; Guitter, E. (July 2003). “Geodesic distance in planar graphs”. 《Nuclear Physics B》 663 (3): 535–567. doi:10.1016/S0550-3213(03)00355-9. 2008년 10월 4일에 원본 문서에서 보존된 문서. 2008년 4월 23일에 확인함. By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces
↑ Weisstein, Eric W. “Graph Geodesic”. 《MathWorld--A Wolfram Web Resource》. Wolfram Research. 2008년 4월 23일에 확인함. The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v
↑ F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.

[1] Bouttier, Jérémie; Di Francesco,P.; Guitter, E. (July 2003). “Geodesic distance in planar graphs”. 《Nuclear Physics B》 663 (3): 535–567. doi:10.1016/S0550-3213(03)00355-9. 2008년 10월 4일에 원본 문서에서 보존된 문서. 2008년 4월 23일에 확인함. By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces

[2] Weisstein, Eric W. “Graph Geodesic”. 《MathWorld--A Wolfram Web Resource》. Wolfram Research. 2008년 4월 23일에 확인함. The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v

[3] F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.

[1]

[2]

[3]