Distance (graph theory)

Encyclopedia : D : DI : DIS : Distance (graph theory)

In the mathematical subfield of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path connecting them. This is also known as the geodesic distance.

There are a number of other measurements defined in terms of distance:

The eccentricity [\epsilon] of a vertex [v] is the greatest distance between [v] and any other vertex.

The radius of a graph is the minimum eccentricity of any vertex.

The diameter of a graph is the maximum eccentricity of any vertex in the graph. That is, it is the greatest distance between any two vertices. A peripheral vertex in a graph of diameter [d] is one that is distance [d] from some other vertex—that is, a vertex that achieves the diameter.

A pseudo-peripheral vertex [v] has the property that for any vertex [u], if [v] is as far away from [u] as possible, then [u] is as far away from [v] as possible. Formally, if the distance from [u] to [v] equals the eccentricity of [u], then it equals the eccentricity of [v].

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, let [v] be one with minimal degree.
If [\epsilon(v) > \epsilon(u)] then set u=v and repeat with step 2, else v is a pseudo-peripheral vertex.

Distance (graph theory)

Algorithm for finding pseudo-peripheral vertices

See also