Odtnhj

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 a directed graph the distance d(u,v)displaystyle d(u,v) between two vertices udisplaystyle u and vdisplaystyle v is defined as the length of a shortest directed path from udisplaystyle u to vdisplaystyle 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)displaystyle d(u,v) does not necessarily coincide with d(v,u)displaystyle d(v,u), 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)displaystyle epsilon (v) of a vertex vdisplaystyle v is the greatest distance between vdisplaystyle v and any other vertex. It can be thought of as how far a node is from the node most distant from it in the graph.

The radius rdisplaystyle r of a graph is the minimum eccentricity of any vertex or, in symbols, r=minv∈Vϵ(v)displaystyle r=min _vin Vepsilon (v).

The diameter ddisplaystyle d of a graph is the maximum eccentricity of any vertex in the graph. That is, ddisplaystyle d is the greatest distance between any pair of vertices or, alternatively, d=maxv∈Vϵ(v)displaystyle d=max _vin Vepsilon (v). 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 rdisplaystyle r is one whose eccentricity is rdisplaystyle r—that is, a vertex that achieves the radius or, equivalently, a vertex vdisplaystyle v such that ϵ(v)=rdisplaystyle epsilon (v)=r.

A peripheral vertex in a graph of diameter ddisplaystyle d is one that is distance ddisplaystyle d from some other vertex—that is, a vertex that achieves the diameter. Formally, vdisplaystyle v is peripheral if ϵ(v)=ddisplaystyle epsilon (v)=d.

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

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:

1. Choose a vertex udisplaystyle u.


2. Among all the vertices that are as far from udisplaystyle u as possible, let vdisplaystyle v be one with minimal degree.


3. If ϵ(v)>ϵ(u)displaystyle epsilon (v)>epsilon (u) then set u=vdisplaystyle u=v and repeat with step 2, else udisplaystyle u is a pseudo-peripheral vertex.

See also

• Distance matrix


• Resistance distance


• Betweenness centrality


• Centrality


• Closeness


• 
  Degree diameter problem for graphs and digraphs
  


• Metric graph

Notes