Definition:Walk (Graph Theory)/Length
Jump to navigation
Jump to search
This page is about length of a walk in the context of Graph Theory. For other uses, see Length.
Definition
The length of a walk (or a path, or a trail) is the number of edges it has, counting repeated edges as many times as they appear.
A walk is said to be of infinite length if and only if it has infinitely many edges.
Zero Length Walk
A zero length walk is a walk which consists of one vertex.
Examples
Arbitrary Example
In the graph below:
the path $1, 3, 4$ has length $2$.
The vertex $5$ forms a zero length walk.
Sources
- 1979: John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation ... (previous) ... (next): Chapter $1$: Preliminaries: $1.2$ Graphs and Trees
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 2.3.4.1$: Free Trees
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): Entry: walk
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Entry: walk