Directed walk

Definition

A directed walk in a graph is a sequence of vertices and edges where each edge has a direction, moving from one vertex to another. It follows the direction of the edges and can repeat vertices and edges.

5 Must Know Facts For Your Next Test

1. A directed walk can traverse any vertex or edge multiple times.
2. The direction of the edges must be followed strictly in a directed walk.
3. A directed walk may start and end at the same vertex, forming a closed walk.
4. Directed walks are used to explore networks like social media connections or web page links.
5. In formal terms, a directed walk is represented as an alternating sequence of vertices and directed edges.

Review Questions

• What distinguishes a directed walk from an undirected walk?
• Can a directed walk revisit the same vertex or edge? Explain.
• What is required for a sequence to qualify as a directed walk in graph theory?

Related terms

Path: A sequence of vertices connected by edges without repeating any vertices or edges.

Cycle: A path that starts and ends at the same vertex, with no other repetitions of vertices and edges.

Graph: A collection of vertices (nodes) connected by edges which may be either undirected or directed.