Edge Distance Function

An Edge Distance Function is a graph node distance function [math]\displaystyle{ f(v_x,v_y) }[/math] that is based on the count of graph edges along the shortest path between the two graph nodes.

• AKA: Geodesic Distance.
• Context:
  • If there is no path between the two Nodes then the distance is infinite.
  • It, along with the Node Set, forms a Metric Space iff the Graph is a Connected Graph.
• See: Length Function, Graph Node Eccentricity, Graph Radius, Graph Diameter.

---

---

References

2012

• (Wikipedia, 2012) ⇒ http://en.wikipedia.org/wiki/Graph_metric
  • 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 because it is the length of the graph geodesic between those two vertices. 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.

    The vertex set (of an undirected graph) and the distance function form a metric space, if and only if the graph is connected.

    A metric defined over a set of points in terms of distances in a graph defined over the set is called a graph metric.

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

    • The eccentricity [math]\displaystyle{ \epsilon }[/math] of a vertex [math]\displaystyle{ v }[/math] is the greatest geodesic distance between [math]\displaystyle{ v }[/math] and any other vertex. It can be thought of as how far a node is from the node most distant from it in the graph.
    • 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 pair of vertices. 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 [math]\displaystyle{ r }[/math] is one whose eccentricity is [math]\displaystyle{ r }[/math]—that is, a vertex that achieves the radius.
    • A peripheral vertex in a graph of diameter [math]\displaystyle{ d }[/math] is one that is distance [math]\displaystyle{ d }[/math] from some other vertex—that is, a vertex that achieves the diameter.
    • A pseudo-peripheral vertex [math]\displaystyle{ v }[/math] has the property that for any vertex [math]\displaystyle{ u }[/math], if [math]\displaystyle{ v }[/math] is as far away from [math]\displaystyle{ u }[/math] as possible, then [math]\displaystyle{ u }[/math] is as far away from [math]\displaystyle{ v }[/math] as possible. Formally, a vertex u is pseudo-peripheral,

if for each vertex v with [math]\displaystyle{ d(u,v) = \epsilon(u) }[/math] holds [math]\displaystyle{ \epsilon(u)=\epsilon(v) }[/math].

---