Definition:Walk

From ProofWiki
Jump to: navigation, search

Definition

A walk on a graph is:


A walk between two vertices $u$ and $v$ is called a $u$-$v$ walk.


To describe a walk on a simple graph it is sufficient to list just the vertices in order, as the edges (being unique between vertices) are unambiguous.


Closed

A closed walk is a walk whose first vertex is the same as the last.

That is, it is a walk which ends where it starts.

Open

An open walk is a walk whose first vertex and last vertex are distinct.

That is, it is a walk which ends on a different vertex from the one where it starts.


Length

The length of a walk 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 iff it has infinitely many edges.


Also known as

Some sources refer to a walk as a path, and use the term simple path to define what we have here as a path.


Also see



Sources