For faster navigation, this Iframe is preloading the Wikiwand page for Distance (graph theory).

Distance (graph theory)

In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path (also called a graph geodesic) connecting them. This is also known as the geodesic distance or shortest-path distance.[1] Notice that there may be more than one shortest path between two vertices.[2] If there is no path connecting the two vertices, i.e., if they belong to different connected components, then conventionally the distance is defined as infinite.

In the case of a directed graph the 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 a quasi-metric, and it might be the case that one is defined while the other is not.

Related concepts

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

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

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

The radius r of a graph is the minimum eccentricity of any vertex or, in symbols,

The diameter 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,

To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph.

A central vertex in 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.

A peripheral vertex in 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.

A pseudo-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).

A level structure of the graph, given a starting vertex, is a partition of the graph's vertices into subsets by their distances from the starting vertex.

A geodetic graph is one for which every pair of vertices has a unique shortest path connecting them. For example, all trees are geodetic.[4]

The weighted shortest-path distance generalises the geodesic distance to weighted graphs. In this case it is assumed that the weight of an edge represents its length or, for complex networks the cost of the interaction, and the weighted shortest-path distance dW(u, v) is the minimum sum of weights across all the paths connecting u and v. See the shortest path problem for more details and algorithms.

Algorithm for finding pseudo-peripheral vertices

Often peripheral sparse matrix algorithms 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:

  1. Choose a vertex .
  2. Among all the vertices that are as far from as possible, let be one with minimal degree.
  3. If then set and repeat with step 2, else is a pseudo-peripheral vertex.

See also

Notes

  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. Archived from the original on 2008-04-23. Retrieved 2008-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
{{bottomLinkPreText}} {{bottomLinkText}}
Distance (graph theory)
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Get ready for Wikiwand 2.0 🎉! the new version arrives on September 1st! Don't want to wait?