Path

Definition

A path in a graph is a sequence of edges that connect a sequence of vertices, with no vertex repeated. Paths are fundamental for understanding connectivity and traversal in graphs.

5 Must Know Facts For Your Next Test

1. A simple path does not repeat any vertices except possibly the first and last if it forms a cycle.
2. The length of a path is the number of edges it contains.
3. Paths can be directed or undirected depending on the type of graph.
4. A graph is connected if there is at least one path between every pair of vertices.
5. The shortest path between two vertices is the path with the smallest number of edges.

Review Questions

• What distinguishes a simple path from other types of paths?
• How do you determine the length of a path in a graph?
• What does it mean for a graph to be connected?

Related terms

cycle:

A cycle is a path that starts and ends at the same vertex, with no other repetitions.

connectedGraph: A connected graph has at least one path connecting every pair of vertices.

shortestPath: The shortest path between two vertices is defined as the path with the fewest edges connecting them.