Editing Distance (graph theory)

{{Short description|Length of shortest path between two nodes of a graph}}

[[File:Distance (graph).svg|thumb|350px|Distances in various graphs between selected vertices. Some have no defined distance (marked as infinite distance) because they are in different [[component (graph_theory)|connected components]], or if edges in a directed graph can't lead from the first to the second. The latter may occur even if the distance in the other direction between the same two vertices is defined.]]

In the [[mathematics|mathematical]] field of [[graph theory]], the '''distance''' between two [[vertex (graph theory)|vertices]] in a [[Graph (discrete mathematics)|graph]] is the number of edges in a [[shortest path problem|shortest path]] (also called a '''graph geodesic''') connecting them.  This is also known as the '''geodesic distance''' or '''shortest-path distance'''.<ref>{{cite journal 
 |last = Bouttier  
 |first = Jérémie 
 |author2 = Di Francesco, P. 
 |author3 = Guitter, E. 
 |date = July 2003
 |title = Geodesic distance in planar graphs 
 |journal =  Nuclear Physics B
 |volume = 663 
 |issue = 3
 |pages = 535–567
 |quote = By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces
 |doi = 10.1016/S0550-3213(03)00355-9
 |arxiv = cond-mat/0303272 
|bibcode = 2003NuPhB.663..535B 
 |s2cid = 119594729 
 }}</ref> Notice that there may be more than one shortest path between two vertices.<ref>{{cite web |url=http://mathworld.wolfram.com/GraphGeodesic.html |title=Graph Geodesic |access-date=2008-04-23 |last=Weisstein |first=Eric W. |author-link=Eric W. Weisstein |work=MathWorld--A Wolfram Web Resource |publisher=Wolfram Research |quote=The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v |archive-date=2008-04-23 |archive-url=https://web.archive.org/web/20080423071114/http://mathworld.wolfram.com/GraphGeodesic.html |url-status=live }}</ref> If there is no [[Path (graph theory)|path]] connecting the two vertices, i.e., if they belong to different [[component (graph theory)|connected component]]s, then conventionally the distance is defined as infinite.

In the case of a [[directed graph]] the distance {{math|''d''(''u'',''v'')}} between two vertices {{mvar|u}} and {{mvar|v}} is defined as the length of a shortest directed path from {{mvar|u}} to {{mvar|v}} 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, {{math|''d''(''u'',''v'')}} does not necessarily coincide with {{math|''d''(''v'',''u'')}}—so it is just a [[Metric (mathematics)#Quasimetrics|quasi-metric]], 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 (graph theory)|connected]].

The '''eccentricity''' {{math|''ϵ''(''v'')}} of a vertex {{mvar|v}} is the greatest distance between {{mvar|v}} 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''' {{mvar|r}} 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>

{{anchor|diameter}}The '''[[Diameter (graph theory)|diameter]]''' {{mvar|d}} of a graph is the maximum eccentricity of any vertex in the graph.  That is, {{mvar|d}} 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 problem|shortest path]] between each pair of [[vertex (graph theory)|vertices]]. The greatest length of any of these paths is the diameter of the graph.

A '''central vertex''' in a graph of radius {{mvar|r}} is one whose eccentricity is {{mvar|r}}&mdash;that is, a vertex whose distance from its furthest vertex is equal to the radius, equivalently, a vertex {{mvar|v}} such that {{math|1=''ϵ''(''v'') = ''r''}}.

A '''peripheral vertex''' in a graph of diameter {{mvar|d}} is one whose eccentricity is {{mvar|d}}&mdash;that is, a vertex whose distance from its furthest vertex is equal to the diameter. Formally, {{mvar|v}} is peripheral if {{math|1=''ϵ''(''v'') = ''d''}}.

A '''pseudo-peripheral vertex''' {{mvar|v}} has the property that, for any vertex {{mvar|u}}, if {{mvar|u}} is as far away from {{mvar|v}} as possible, then {{mvar|v}} is as far away from {{mvar|u}} as possible.  Formally, a vertex {{mvar|v}} is pseudo-peripheral if, for each vertex {{mvar|u}} with {{math|1=''d''(''u'',''v'') = ''ϵ''(''v'')}}, it holds that {{math|1=''ϵ''(''u'') = ''ϵ''(''v'')}}.

A '''[[level structure]]''' of the graph, given a starting vertex, is a [[partition of a set|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 [[Tree (graph theory)|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 [[Glossary of graph theory#weighted graph|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 {{math|''d''{{sup|''W''}}(''u'', ''v'')}} is the minimum sum of weights across all the [[Glossary of graph theory#path|paths]] connecting {{mvar|u}} and {{mvar|v}}. See the [[shortest path problem]] for more details and algorithms.

==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 <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 (graph theory)|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 also==
{{col div|colwidth=40em}}
* [[Distance matrix]]
* [[Resistance distance]]
* [[Betweenness centrality]]
* [[Centrality]]
* [[Closeness (graph theory)|Closeness]]
* [[Degree diameter problem]] for [[Graph (discrete mathematics)|graph]]s and [[digraph (mathematics)|digraph]]s
* [[Diameter (graph theory)]]
* [[Triameter (graph theory)]]
* [[Metric graph]]
{{colend}}

==Notes==
{{reflist}}

[[Category:Graph theory]]
[[Category:Metric geometry]]
[[Category:Graph distance| ]]