(closed) walk / trek / trail / path
Graph theory terminology is notoriously variable so the following definitions should be used with caution. In books, most authors define their usage at the beginning.
In a graph, multigraph or even pseudograph ,
-
•
a walk of length is formed by a sequence of edges such that any two successive edges in the sequence share a vertex (aka node). The walk is also considered to include all the vertices (nodes) incident to those edges, making it a subgraph.
In the case of a simple graph (i.e. not a multigraph) it is also possible to define the walk uniquely by the vertices it visits: a walk of length is then a sequence of vertices , , … such that an edge exists for all . Again the walk is considered to contain those edges as well as the vertices.
-
•
A trek is a walk that does not backtrack, i.e. no two successive edges are the same.
For simple graphs this also implies for all .
-
•
A trail is a walk where all edges are distinct, and
-
•
a path is one where all vertices are distinct.
The walk, etc. is said to run from to , to run between them, to connect them etc. The term trek was introduced by Cameron [Cam94] who notes the lexicographic mnemonic
The other terms are fairly widespread, cf. [Wil02], but beware: many authors call walks paths, and some then call paths chains. And when edges are called arcs, a trek of length sometimes goes by the name -arc.
Note that for the purpose of defining connectivity any of these types of wanderings can be used; if a walk exists between vertices and then there also exists a path between them. And here we must allow to make “are connected by a path” an equivalence relation on vertices (in order to define connected components as its equivalence classes).
-
•
A closed walk aka circuit of length is a walk where ,
-
•
a closed trek is a trek that’s closed in the same way, and
-
•
a closed trail likewise;
-
•
a closed path aka (elementary) cycle is like a path (except that we only demand that for are distinct) and again closed ( again coincides with ).
Beware: cycles are often called circuits [Cam94]; the distinction between circuits and cycles here follows Wilson [Wil02]. These closed wanderings are often called after their length: -circuits, -cycles.
The case is excluded from these definitions; -cycles are loops so imply a pseudograph; -cycles are double edges implying multigraphs; so is the minimum cycle length in a proper graph.
Note also that in trivalent aka cubic graphs a closed trail is automatically a closed path: it is impossible to visit a vertex (in via edge , out via edge say) and visit it again (in via , out via ) without also revisiting an edge, because there are only three edges at each vertex.
-
•
An open walk, open trek, open trail is one that isn’t closed.
-
•
An open path (sometimes open chain) is just a path as defined above (because a closed path isn’t actually a path). Still, the term is useful when you want to emphasise the contrast with a closed path.
References
- 1
-
Cam94
Peter J. Cameron,
Combinatorics: topics, techniques, algorithms
Camb. Univ. Pr. 1994, ISBN 0 521 45761 0,
http://www.maths.qmul.ac.uk/ pjc/comb/http://www.maths.qmul.ac.uk/ pjc/comb/ (solutions, errata &c.) -
Wil02
Robert A. Wilson,
Graphs, Colourings and the Four-colour Theorem,
Oxford Univ. Pr. 2002, ISBN 0 19 851062 4 (pbk),
http://www.maths.qmul.ac.uk/ raw/graph.htmlhttp://www.maths.qmul.ac.uk/ raw/graph.html (errata &c.)
Title | (closed) walk / trek / trail / path |
Canonical name | closedWalkTrekTrailPath |
Date of creation | 2013-03-22 15:09:50 |
Last modified on | 2013-03-22 15:09:50 |
Owner | marijke (8873) |
Last modified by | marijke (8873) |
Numerical id | 9 |
Author | marijke (8873) |
Entry type | Definition |
Classification | msc 05C38 |
Related topic | Path2 |
Related topic | ConnectedGraph |
Related topic | KConnectedGraph |
Related topic | Diameter3 |
Defines | walk |
Defines | trek |
Defines | trail |
Defines | path |
Defines | chain |
Defines | circuit |
Defines | cycle |
Defines | closed walk |
Defines | closed trek |
Defines | closed trail |
Defines | closed path |
Defines | closed chain |
Defines | open walk |
Defines | open trek |
Defines | open trail |
Defines | open path |
Defines | open chain |
Defines | -arc |
Defines | -cycle |
Defines | elementary cycle |
Defines | -circuit |