# walk

• Feb 15th 2011, 05:13 AM
alexandrabel90
walk
may i know what is the difference between a path and a walk, they seem to be the same thing to me.

i classified a walk as abcdef where each alphabet represents a vertex but my tutor said that that is a path...
• Feb 15th 2011, 07:49 AM
Sudharaka
Quote:

Originally Posted by alexandrabel90
may i know what is the difference between a path and a walk, they seem to be the same thing to me.

i classified a walk as abcdef where each alphabet represents a vertex but my tutor said that that is a path...

Hi alexandrabel90,

A walk is a finite sequence of vertices and edges beginning and ending with a vertex. Here both vertices and edges could repeat.

A path is a walk with distinct vertices and edges with the starting vertex and end vertex. Also the starting and end vertex in a path must be distinct.

So by the definitions we can see that every path is a walk.

For a more detailed discription refer Glossary of graph theory - Wikipedia, the free encyclopedia
• Feb 15th 2011, 08:12 AM
Plato
Quote:

Originally Posted by alexandrabel90
may i know what is the difference between a path and a walk, they seem to be the same thing to me.
i classified a walk as abcdef where each alphabet represents a vertex but my tutor said that that is a path...

There is no universal agreement on these terms.
One text book on graph theory has a hierarchy of terms: walk, a trail, and a path.
A walk is a collection of successive adjacent edges.
A trail is a walk in which all edges are distinct.
A path is a trail in which all vertices are distinct.