Definition:Walk (Graph Theory)/Length
< Definition:Walk (Graph Theory)(Redirected from Definition:Length of Walk)
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 1
In the graph below:
the path $1, 3, 4$ has length $2$.
The vertex $5$ forms a zero length walk.
Arbitrary Example 2
In the rooted tree below:
the path from $1$ to $9$ has length $4$.
Sources
- 1977: Gary Chartrand: Introductory Graph Theory: Chapter $10$: Graphs and Other Mathematics: $10.1$: Graphs and Matrices
- 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): walk
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): walk