# 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**.^{[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 adirected graphthe distancebetween two verticesandis defined as the length of a shortest directed path fromtoconsisting of arcs, provided at least one such path exists.`

^{[3]}Notice that, in contrast with the case of undirected graphs,does not necessarily coincide with, 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**of a vertexis the greatest distance betweenand any other vertex; in symbols that is. It can be thought of as how far a node is from the node most distant from it in the graph.`The`

**radius**of a graph is the minimum eccentricity of any vertex or, in symbols,.`The`

**diameter**of a graph is the maximum eccentricity of any vertex in the graph. That is,is the greatest distance between any pair of vertices or, alternatively,. 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.`A`

**central vertex**in a graph of radiusis one whose eccentricity is—that is, a vertex that achieves the radius or, equivalently, a vertexsuch that.`A`

**peripheral vertex**in a graph of diameteris one that is distancefrom some other vertex—that is, a vertex that achieves the diameter. Formally,is peripheral if.`A`

**pseudo-peripheral vertex**has the property that for any vertex, ifis as far away fromas possible, thenis as far away fromas possible. Formally, a vertex*u*is pseudo-peripheral, if for each vertex*v*withholds.The partition of a graph's vertices into subsets by their distances from a given starting vertex is called the level structure of the graph.

A graph such that for every pair of vertices there is a unique shortest path connecting them is called a **geodetic graph**. For example, all trees are geodetic.^{[4]}

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:

Choose a vertex .

Among all the vertices that are as far from as possible, let be one with minimal degree.

If then set and repeat with step 2, else is a pseudo-peripheral vertex.

See also

Distance matrix

Resistance distance

Betweenness centrality

Centrality

Closeness

Degree diameter problem for graphs and digraphs

Metric graph

## References

*Nuclear Physics B*.

**663**(3): 535–567. arXiv:cond-mat/0303272. doi:10.1016/S0550-3213(03)00355-9. Archived from the original on 2008-10-04. Retrieved 2008-04-23. By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces

*MathWorld--A Wolfram Web Resource*. Wolfram Research. 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