Paths and Connectivity Summary

Graph Theory · Axiom Academy

SUMMARY Paths and Connectivity Let's review the key concepts of traversing graphs and measuring connectivity. Walk: Any sequence of adjacent vertices (edges and vertices can repeat) Trail: A walk with no repeated edges (vertices may repeat) Path: A walk with no repeated vertices (most restrictive) Cycle: A closed path where the first and last vertices are the same Connected Graph: A path exists between every pair of vertices Component: A maximal connected subgraph of a graph Cut Vertex: A vertex whose removal increases the number of components Bridge: An edge whose removal increases the number of components Example Recap: Finding Shortest Paths Step 1 - Initialize: Start from the source vertex and mark its distance as 0; all other vertices have distance ∞ Step 2 - Explore Neighbors: For each unvisited neighbor, calculate the distance through the current vertex Step 3 - Update Distances: If the new distance is shorter than the current recorded distance, update it Step 4 - Repeat: Continue with the next closest unvisited vertex until all reachable vertices are processed Eccentricity e(v): Maximum distance from vertex v to any other vertex Radius r(G): Minimum eccentricity among all vertices (closest to center) Diameter d(G): Maximum eccentricity among all vertices (longest shortest path) Center: The set of vertices with eccentricity equal to the radius Periphery: The set of vertices with eccentricity equal to the diameter

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