Distance (graph theory)

In themathematicalfield ofgraph theory,thedistancebetween twoverticesin agraphis the number of edges in ashortest path(also called agraph geodesic) connecting them. This is also known as thegeodesic distanceorshortest-path distance.^[1]Notice that there may be more than one shortest path between two vertices.^[2]If there is nopathconnecting the two vertices, i.e., if they belong to differentconnected components,then conventionally the distance is defined as infinite.

In the case of adirected graphthe distance $d (u, v)$ between two vertices $u$ and $v$ is defined as the length of a shortest directed path from $u$ to $v$ consisting of arcs, provided at least one such path exists.^[3]Notice that, in contrast with the case of undirected graphs, $d (u, v)$ does not necessarily coincide with $d (v, u)$ —so it is just aquasi-metric,and it might be the case that one is defined while the other is not.

Related concepts

Ametric spacedefined over a set of points in terms of distances in a graph defined over the set is called agraph metric. The vertex set (of an undirected graph) and the distance function form a metric space, if and only if the graph isconnected.

Theeccentricity $ϵ (v)$ of a vertex $v$ is the greatest distance between $v$ and any other vertex; in symbols,

\epsilon (v)=\max _{u\in V}d(v,u).

It can be thought of as how far a node is from the node most distant from it in the graph.

Theradius $r$ of a graph is the minimum eccentricity of any vertex or, in symbols,

r=\min _{v\in V}\epsilon (v)=\min _{v\in V}\max _{u\in V}d(v,u).

Thediameter $d$ of a graph is the maximum eccentricity of any vertex in the graph. That is, $d$ is the greatest distance between any pair of vertices or, alternatively,

d=\max _{v\in V}\epsilon (v)=\max _{v\in V}\max _{u\in V}d(v,u).

To find the diameter of a graph, first find theshortest pathbetween each pair ofvertices.The greatest length of any of these paths is the diameter of the graph.

Acentral vertexin a graph of radius $r$ is one whose eccentricity is $r$ —that is, a vertex whose distance from its furthest vertex is equal to the radius, equivalently, a vertex $v$ such that $ϵ (v) = r$ .

Aperipheral vertexin a graph of diameter $d$ is one whose eccentricity is $d$ —that is, a vertex whose distance from its furthest vertex is equal to the diameter. Formally, $v$ is peripheral if $ϵ (v) = d$ .

Apseudo-peripheral vertex $v$ has the property that, for any vertex $u$ ,if $u$ is as far away from $v$ as possible, then $v$ is as far away from $u$ as possible. Formally, a vertex $v$ is pseudo-peripheral if, for each vertex $u$ with $d (u, v) = ϵ (v)$ ,it holds that $ϵ (u) = ϵ (v)$ .

Alevel structureof the graph, given a starting vertex, is apartitionof the graph's vertices into subsets by their distances from the starting vertex.

Ageodetic graphis one for which every pair of vertices has a unique shortest path connecting them. For example, alltreesare geodetic.^[4]

Theweighted shortest-path distancegeneralises the geodesic distance toweighted graphs.In this case it is assumed that the weight of an edge represents its length or, forcomplex networksthecostof the interaction, and the weighted shortest-path distance $d W (u, v)$ is the minimum sum of weights across all thepathsconnecting $u$ and $v$ .See theshortest path problemfor more details and algorithms.

Algorithm for finding pseudo-peripheral vertices

Often peripheralsparse matrixalgorithms need a starting vertex with a high eccentricity. A peripheral vertex would be perfect, but is often hard to calculate. In most circumstances a pseudo-peripheral vertex can be used. A pseudo-peripheral vertex can easily be found with the following algorithm:

Choose a vertex $u$ .
Among all the vertices that are as far from $u$ as possible, let $v$ be one with minimaldegree.
If $\epsilon (v)>\epsilon (u)$ then set $u=v$ and repeat with step 2, else $u$ is a pseudo-peripheral vertex.

Notes

^Bouttier, Jérémie; Di Francesco, P.; Guitter, E. (July 2003). "Geodesic distance in planar graphs".Nuclear Physics B.663(3): 535–567.arXiv:cond-mat/0303272.Bibcode:2003NuPhB.663..535B.doi:10.1016/S0550-3213(03)00355-9.S2CID 119594729.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.Archivedfrom the original on 2008-04-23.Retrieved2008-04-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.
^Øystein Ore,Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society, p. 104

[1] Bouttier, Jérémie; Di Francesco, P.; Guitter, E. (July 2003). "Geodesic distance in planar graphs".Nuclear Physics B.663(3): 535–567.arXiv:cond-mat/0303272.Bibcode:2003NuPhB.663..535B.doi:10.1016/S0550-3213(03)00355-9.S2CID 119594729.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.Archivedfrom the original on 2008-04-23.Retrieved2008-04-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.

[4] Øystein Ore,Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society, p. 104

[1]

[2]

[3]

[4]

Related concepts

Algorithm for finding pseudo-peripheral vertices

See also

Notes