Distance (graph theory)
From Wikipedia, the free encyclopedia
In the mathematical field 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 ε 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.
[edit] 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 ε(v) > ε(u) then set u=v and repeat with step 2, else v is a pseudo-peripheral vertex.
