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. 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 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. 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.
Computational Representation In graph theory, distances between nodes can be represented computationally by using a distance matrix (also called the all-pairs shortest-path matrix). This is the square matrix ( D = ( d i j ) ) {\displaystyle (D=(d_{ij}))} , where each entry ( d i j ) {\displaystyle (d_{ij})} indicates the length of a shortest path between the two vertices ( v i ) {\displaystyle (v_{i})} and ( v j ) {\displaystyle (v_{j})} .
Distance matrices have several applications, which include telecommunications and chemistry. In chemical graph theory, multiple topological indices that characterize molecular structure were able to be derived from the distance matrix. Beyond exact matrix representations, graph distances can also be represented using metric embeddings. This approach maps the vertices of a graph to points in a geometric space (such as Euclidean space) in a way that preserves the graph distances as closely as possible.
Directed Graph Distance In a directed graph, edges have an assigned direction, meaning travel between vertices is not necessarily bidirectional. As a result, the distance from u {\textstyle u} to v {\displaystyle v} may differ from the distance from v {\displaystyle v} to u {\displaystyle u} . This makes directed graph distance a quasi-metric rather than a true metric. Formally, for vertices u {\displaystyle u} and v {\displaystyle v} in a directed graph G {\displaystyle G} , it is not guaranteed that d ( u , v ) = d ( v , u ) {\displaystyle d(u,v)=d(v,u)} , and d ( u , v ) {\displaystyle d(u,v)} may be undefined if no directed path from u {\displaystyle u} to v {\displaystyle v} exists.
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. The eccentricity ϵ(v) of a vertex v is the greatest distance between v and any other vertex; in symbols,
ϵ ( v ) = max u ∈ V d ( v , u ) . {\displaystyle \epsilon (v)=\max _{u\in V}d(v,u).}
It can be thought of as how far a node is from the node most distant from it in the graph. The radius r of a graph is the minimum eccentricity of any vertex or, in symbols,
r = min v ∈ V ϵ ( v ) = min v ∈ V max u ∈ V d ( v , u ) . {\displaystyle r=\min _{v\in V}\epsilon (v)=\min _{v\in V}\max _{u\in V}d(v,u).}
The diameter d of a graph is the maximum eccentricity of any vertex in the graph. That is, d is the greatest distance between any pair of vertices or, alternatively,
d = max v ∈ V ϵ ( v ) = max v ∈ V max u ∈ V d ( v , u ) . {\displaystyle d=\max _{v\in V}\epsilon (v)=\max _{v\in V}\max _{u\in V}d(v,u).}
… excerpt ends here. Continue reading the full article.
