Geodesic Distance Between Two Graph-Nodes Measure

From GM-RKB
(Redirected from Distance (graph theory))
Jump to navigation Jump to search

A Geodesic Distance Between Two Graph-Nodes Measure is a length measure [math]\displaystyle{ f(v_x,v_y) }[/math] which is a graph-based distance measure that is based on the count of graph edges along the shortest path between the two graph nodes.



References

2020

  • (Wikipedia, 2020) ⇒ https://en.wikipedia.org/wiki/Distance_(graph_theory) Retrieved:2020-6-30.
    • 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. Notice that there may be more than one shortest path between 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. In the case of a directed graph the distance [math]\displaystyle{ d(u,v) }[/math] between two vertices [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] is defined as the length of a shortest directed path from [math]\displaystyle{ u }[/math] to [math]\displaystyle{ v }[/math] consisting of arcs, provided at least one such path exists. [1] Notice that, in contrast with the case of undirected graphs, [math]\displaystyle{ d(u,v) }[/math] does not necessarily coincide with [math]\displaystyle{ d(v,u) }[/math] , and it might be the case that one is defined while the other is not.
  1. F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.