Distance and Diameter

Graph Theory · Axiom Academy

Understanding fundamental distance metrics in graphs The distance between two vertices u and v, denoted d(u,v), is the length of the shortest path between them. If no path exists, the distance is defined as infinity. The eccentricity of a vertex v, denoted e(v), is the greatest distance from v to any other vertex in the graph. It measures how "far out" the most distant vertex is from v. In this animation, we'll calculate the eccentricity of each vertex by finding the maximum distance from that vertex to all others. Two important global metrics of a graph are derived from vertex eccentricities: The diameter represents the longest shortest path in the graph - the maximum distance between any pair of vertices. The center of a graph consists of all vertices with eccentricity equal to the radius. These are the vertices that minimize the maximum distance to any other vertex. Central vertices are important in network design, as they minimize the worst-case distance to any other location. The peripheral vertices (or periphery) of a graph are vertices with eccentricity equal to the diameter. These vertices are "furthest from the center."

This is the written version of the interactive lesson above. See the full Graph Theory course.