Distance (graph theory)

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.[1] Notice that there may be more than one shortest path between two vertices.[2] 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 d(u,v) between two vertices u and v is defined as the length of a shortest directed path from u to v consisting of arcs, provided at least one such path exists.[3] Notice that, in contrast with the case of undirected graphs, d(u,v) does not necessarily coincide with d(v,u)—so it is just a quasi-metric, and it might be the case that one is defined while the other is not.

  1. ^ Bouttier, Jérémie; Di Francesco, P.; Guitter, E. (July 2003). "Geodesic distance in planar graphs". Nuclear Physics B. 663 (3): 535–567. arXiv:cond-mat/0303272. Bibcode:2003NuPhB.663..535B. doi:10.1016/S0550-3213(03)00355-9. S2CID 119594729. By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces
  2. ^ Weisstein, Eric W. "Graph Geodesic". MathWorld--A Wolfram Web Resource. Wolfram Research. Archived from the original on 2008-04-23. Retrieved 2008-04-23. The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v
  3. ^ F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.