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. Notice that there may be more than one shortest path between two vertices. 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.
Contents
In the case of a directed graph the distance
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
The radius
The diameter
A central vertex in a graph of radius
A peripheral vertex in a graph of diameter
A pseudo-peripheral vertex
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.
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
u . - Among all the vertices that are as far from
u as possible, letv be one with minimal degree. - If
ϵ ( v ) > ϵ ( u ) then setu = v and repeat with step 2, elsev is a pseudo-peripheral vertex.