查看“︁距离 (图论)”︁的源代码

在[[图论]]中，一张[[无向图]]里，两[[顶点 (图论)|顶点]]之间的'''距离'''是指他们之间'''最短路径'''（{{lang-en| shortest path}}）{{notetag|两点间的最短路径也被称为'''图的测地线'''（{{lang-en|graph geodesic}}）。}}的长度，两[[顶点 (图论)|顶点]]之间的'''距离'''也被称为'''测地距离'''（{{Lang-en|geodesic distance}}）<ref>{{Cite journal|title=Geodesic distance in planar graphs|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|last=Bouttier|first=Jérémie|last2=Di Francesco,P.|date=July 2003|journal=Nuclear Physics B|accessdate=2008-04-23|issue=3|doi=10.1016/S0550-3213(03)00355-9|volume=663|pages=535–567|quote=By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces|last3=Guitter, E.|archive-date=2008-10-04|archive-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|dead-url=no}}</ref>。需要注意的是两个[[顶点 (图论)|顶点]]之间可能有多条最短路径<ref>{{Cite mathworld|urlname=GraphGeodesic|title=Graph Geodesic|accessdate=2008-04-23|quote=The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v|archive-date=2008-04-23|archive-url=https://web.archive.org/web/20080423071114/http://mathworld.wolfram.com/GraphGeodesic.html|dead-url=no}}</ref>，如果两个顶点之间不存在路径（即他们属于不同的[[连通图|连通分量]]），那么按照传统它们距离被定义为无穷大。

在[[有向图]]中，如果从[[顶点 (图论)|顶点]] <math>u</math> 到顶点 <math>v</math> 存在'''有向路径'''（{{Lang-en|directed path}}），那么距离 <math>d(u,v)</math> 被定义为从顶点 <math>u</math> 到顶点 <math>v</math> 之间'''最短有向路径'''的长度<ref>{{cite book| author= F. Harary | title= Graph Theory| url= https://archive.org/details/graphtheory0000hara | publisher= Addison-Wesley| date= 1969| page= [https://archive.org/details/graphtheory0000hara/page/199 199]}}</ref>。不同于无向图，在有向图中 <math>d(u,v)</math> 不一定和 <math>d(v,u)</math> 相等{{notetag|见例1。}}，甚至有可能出现从顶点 <math>u</math> 到顶点 <math>v</math> 存在有向路径，而从顶点 <math>v</math> 到顶点 <math>u</math> 却不存在有向路径的情况。

== 相关概念 ==
一个[[顶点 (图论)|顶点]] <math>v</math> 的'''偏心率''' <math>\epsilon(v)</math> 被定义为 <math>v</math> 和其它顶点的距离的最大值，也即是这个点和离其最远点的距离<ref name='topics'/>。

一张图的'''半径''' <math>r</math> 被定义为最小的偏心率：<math>r = \min_{v \in V} \epsilon(v)</math><ref name='topics'>{{cite book|author= Chartrand G., Johns G., Oellermann O.R.| editor=Bodendiek R., Henn R. | title=Topics in Combinatorics and Graph Theory | chapter=On Peripheral Vertices in Graphs| publisher=Physica-Verlag HD | date=1990| }}</ref>

一张图的'''直径''' <math>d</math> 被定义为最大的偏心率：<math>d = \max_{v \in V}\epsilon(v)</math>，也即最远的两点间的距离。若要求得一张图的直径，首先要求得任意两点之间的最短路径，在这些所有的最短路径中，取其长度最长者，即是这张图的直径<ref name='topics'/>。

一张半径为 <math>r</math> 的图的'''中心点'''是所有的偏心率为 <math>r</math> 的[[顶点 (图论)|顶点]]。若 <math>v</math> 是一个中心点，那么可用数学符号表示为 <math>\epsilon(v) = r</math>。一张图可以有不止一个中心点<ref name='topics'/>。

'''边缘点'''和中心点的定义类似。一张直径为 <math>d</math> 的图的'''边缘点'''是所有的偏心率为 <math>d</math> 的顶点。若 <math>v</math> 是一个边缘点，那么 <math>\epsilon(v) = d</math>。一张图可以有多个边缘点<ref name='topics'/>。

== 例子 ==
[[File:Directed_graph,_cyclic.svg|thumb|150px|right|图1]]
[[File:6n-graf_v_nodes.svg|thumb|150px|right|图2]]
[[File:Incidence_matrix_unoriented.svg|thumb|150px|right|图3]]

=== 有向图 ===
在图1中，[[顶点 (图论)|顶点]] <math>B</math> 到顶点 <math>C</math> 的距离 <math> d(B,C)=1 </math>，而顶点 <math>C</math> 到顶点 <math>B</math> 的距离 <math>d(C,B)=3</math>。

=== 直径和半径 ===
{| class="wikitable"
|-
| [[顶点 (图论)|顶点]] || <math> V_1</math> || <math> V_2</math> || <math> V_3</math> || <math> V_4</math> || <math> V_5</math> || <math> V_6</math>
|-
| 偏心率 || 3 || 3 || 2 || 2 || 2 || 3
|}
在图2中，例如，距离[[顶点 (图论)|顶点]] <math> V_1</math> 的最远点是顶点 <math> V_6 </math>，那么 <math> \epsilon(V_1) = 3</math>。每一个顶点的偏心率如上表所示，所以图1的半径为2，而直径为3。

=== 加权图 ===
导言中定义的顶点间的'''距离'''也可以被扩展至'''[[加权图]]'''{{notetag|加权图的含义是每一条边可以有各自的长度。}}（{{Lang-en|weighted graph}}）。如在图3中，顶点3到顶点5的距离为 <math>d(3,5)=7</math>。

== 参见 ==

* [[连通图]]
* [[最短路问题]]
* [[图论术语]]

== 注释 ==
{{notefoot}}

== 参考资料 ==
{{reflist}}

== 参考文献 ==
* {{Cite book|title=Graph Theory|url=https://archive.org/details/gmbhhandbuchfuer00libg|last=Diestel|first=Reinhard|publisher=Springer|year=2000|isbn=9780585498935|location=|pages=[https://archive.org/details/gmbhhandbuchfuer00libg/page/n18 8]| language=en}}

[[Category:图论]]