Our website is made possible by displaying online advertisements to our visitors.
Please consider supporting us by disabling your ad blocker.
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.
- ^ 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
- ^ 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
- ^ F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.
Previous Page Next Page
