Distance (graph theory)
.svg){kind=link}
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 or shortest-path distance.<ref>Template:Cite journal</ref> Notice that there may be more than one shortest path between two vertices.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> 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 Template:Math between two vertices Template:Mvar and Template:Mvar is defined as the length of a shortest directed path from Template:Mvar to Template:Mvar consisting of arcs, provided at least one such path exists.<ref>F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.</ref> Notice that, in contrast with the case of undirected graphs, Template:Math does not necessarily coincide with Template:Math—so it is just a quasi-metric, and it might be the case that one is defined while the other is not.
Related conceptsEdit
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 Template:Math of a vertex Template:Mvar is the greatest distance between Template:Mvar and any other vertex; in symbols,
- <math>\epsilon(v) = \max_{u \in V}d(v,u).</math>
It can be thought of as how far a node is from the node most distant from it in the graph.
The radius Template:Mvar of a graph is the minimum eccentricity of any vertex or, in symbols,
- <math>r = \min_{v \in V} \epsilon(v) = \min_{v \in V}\max_{u \in V}d(v,u).</math>
Template:AnchorThe diameter Template:Mvar of a graph is the maximum eccentricity of any vertex in the graph. That is, Template:Mvar is the greatest distance between any pair of vertices or, alternatively,
- <math>d = \max_{v \in V}\epsilon(v) = \max_{v \in V}\max_{u \in V}d(v,u).</math>
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 Template:Mvar is one whose eccentricity is Template:Mvar—that is, a vertex whose distance from its furthest vertex is equal to the radius, equivalently, a vertex Template:Mvar such that Template:Math.
A peripheral vertex in a graph of diameter Template:Mvar is one whose eccentricity is Template:Mvar—that is, a vertex whose distance from its furthest vertex is equal to the diameter. Formally, Template:Mvar is peripheral if Template:Math.
A pseudo-peripheral vertex Template:Mvar has the property that, for any vertex Template:Mvar, if Template:Mvar is as far away from Template:Mvar as possible, then Template:Mvar is as far away from Template:Mvar as possible. Formally, a vertex Template:Mvar is pseudo-peripheral if, for each vertex Template:Mvar with Template:Math, it holds that Template:Math.
A level structure of the graph, given a starting vertex, is a partition of the graph's vertices into subsets by their distances from the starting vertex.
A geodetic graph is one for which every pair of vertices has a unique shortest path connecting them. For example, all trees are geodetic.<ref>Øystein Ore, Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society, p. 104</ref>
The weighted shortest-path distance generalises the geodesic distance to weighted graphs. In this case it is assumed that the weight of an edge represents its length or, for complex networks the cost of the interaction, and the weighted shortest-path distance Template:Math is the minimum sum of weights across all the paths connecting Template:Mvar and Template:Mvar. See the shortest path problem for more details and algorithms.
Algorithm for finding pseudo-peripheral verticesEdit
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 <math>u</math>.
- Among all the vertices that are as far from <math>u</math> as possible, let <math>v</math> be one with minimal degree.
- If <math>\epsilon(v) > \epsilon(u)</math> then set <math>u=v</math> and repeat with step 2, else <math>u</math> is a pseudo-peripheral vertex.
See alsoEdit
- Distance matrix
- Resistance distance
- Betweenness centrality
- Centrality
- Closeness
- Degree diameter problem for graphs and digraphs
- Diameter (graph theory)
- Triameter (graph theory)
- Metric graph