거리 (그래프 이론) 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]의 [[수학]]적 영역에서, [[그래프]]의 두 [[꼭짓점 (그래프 이론)|꼭짓점]]간의 '''거리'''는 두 점을 잇는 [[최단 경로 문제|최단 경로]]('''그래프 지오데식'''({{llang|en|geodesic}})이라고도 불린다)에 있는 모서리의 개수이다. 이 거리는 '''지오데식 거리'''({{llang|en|geodesic distance}})라고도 부른다.<ref>{{저널 인용 |last=Bouttier |first=Jérémie |author2=Di Francesco,P. |author3=Guitter, E. |date=July 2003 |title=Geodesic distance in planar graphs |journal=Nuclear Physics B |volume=663 |issue=3 |pages=535–567 |url=http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TVC-48KW72R-1&_user=3742306&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000061256&_version=1&_urlVersion=0&_userid=3742306&md5=86dd4de63373a7e72d23d16840947661 |accessdate=2008-04-23 |quote=By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces |doi=10.1016/S0550-3213(03)00355-9 |보존url=https://web.archive.org/web/20081004094451/http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TVC-48KW72R-1&_user=3742306&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000061256&_version=1&_urlVersion=0&_userid=3742306&md5=86dd4de63373a7e72d23d16840947661 |보존날짜=2008-10-04 |url-status=dead }}</ref> 두 꼭짓점 사이에는 최단 경로가 하나 이상 있을 수 있다는 점을 주목하라.<ref>
{{웹 인용|url=http://mathworld.wolfram.com/GraphGeodesic.html |title=Graph Geodesic |accessdate= 2008-04-23
|last=Weisstein |first=Eric W. |authorlink=Eric W. Weisstein |work=MathWorld--A Wolfram Web Resource
|publisher= Wolfram Research
|quote=The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v }}
</ref> 두 꼭짓점 사이에 경로가 없을 때, 즉, 두 꼭짓점이 서로 다른 [[연결 요소 (그래프 이론)|연결 요소]]에 있다면, 전통적으로 거리는 무한으로 정의한다.

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

== 같이 보기 ==
* [[거리 행렬]]
* [[저항 거리]]
* [[매개 중심성]]
* [[중심성]]
* [[근접성 (그래프 이론)|근접성]]
* [[거리 그래프]]

== 각주 ==
{{각주}}

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