Ykhjuy

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 u{displaystyle u} and v{displaystyle v} is defined as the length of a shortest directed path from u{displaystyle u} to v{displaystyle 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 v{displaystyle v} is the greatest distance between v{displaystyle 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 r{displaystyle r} of a graph is the minimum eccentricity of any vertex or, in symbols, r=minv∈Vϵ(v){displaystyle r=min _{vin V}epsilon (v)}.

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

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

A pseudo-peripheral vertex v{displaystyle v} has the property that for any vertex u{displaystyle u}, if v{displaystyle v} is as far away from u{displaystyle u} as possible, then u{displaystyle u} is as far away from v{displaystyle 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 u{displaystyle u}.


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


3. If ϵ(v)>ϵ(u){displaystyle epsilon (v)>epsilon (u)} then set u=v{displaystyle u=v} and repeat with step 2, else u{displaystyle 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