Editing Distance (graph theory) (section)

==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.