(closed) walk / trek / trail / pathClosedPath2005-03-29 03:20:262005-04-04 17:02:29Definitionwalktrektrailpathchaincircuitcycleclosed walkclosed trekclosed trailclosed pathclosed chainopen walkopen trekopen trailopen pathopen chain${s}$-arc${s}$-cycleelementary cycle${s}$-circuit\usepackage{amssymb}
% makra.sty 1989-2005 by Marijke van Gans %
% ^ ^
\catcode`\@=11 % o o
% ->*<-
% ~
%%%% CHARS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% code char frees for
%let\Para\S % \Para ç \S \scriptstyle
%let\Pilcrow\P % \Pilcrow ö \P
\mathchardef\lt="313C % \lt < < bra
\mathchardef\gt="313E % \gt > > ket
%let\bs\backslash % \bs \
%let\us\_ % \us _ \_ display
%%%% DIACRITICS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%let\udot\d % under-dot (text mode), frees \d
%let\odot\. % over-dot (text mode), frees \.
%let\hacek\v % hacek (text mode), frees \v
%let\makron\= % makron (text mode), frees \=
%let\tilda\~ % tilde (text mode), frees \~
%let\uml\" % umlaut (text mode), frees \"
%def\ij/{i{\kern-.07em}j}
%def\trema#1{\discretionary{-}{#1}{\uml #1}}
%%%% amssymb %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\let\le\leqslant
\let\ge\geqslant
%let\prece\preceqslant
%let\succe\succeqslant
%%%% USEFUL MISC %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%def\C++{C$^{_{++}}$}
%let\writelog\wlog
%def\wl@g/{{\sc wlog}}
%def\wlog{\@ifnextchar/{\wl@g}{\writelog}}
%def\org#1{\lower1.2pt\hbox{#1}}
% chem struct formulae: \bs, --- / \org{C} etc.
%%%% USEFUL INTERNAL LaTeX STUFF %%%%%%%%%%%%%%%%%%%%%%%%
%let\Ifnextchar=\@ifnextchar
%let\Ifstar=\@ifstar
%def\currsize{\@currsize}
%%%% KERNING, SPACING, BREAKING %%%%%%%%%%%%%%%%%%%%%%%%%
%def\qqquad{\hskip3em\relax}
%def\qqqquad{\hskip4em\relax}
%def\qqqqquad{\hskip5em\relax}
%def\qqqqqquad{\hskip6em\relax}
%def\qqqqqqquad{\hskip7em\relax}
%def\qqqqqqqquad{\hskip8em\relax}
%%%% LAYOUT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% COUNTERS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% EQUATIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% LEMMATA %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% DISPLAY %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% MATH LAYOUT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\let\D\displaystyle
\let\T\textstyle
\let\S\scriptstyle
\let\SS\scriptscriptstyle
% array:
%def\<#1:{\begin{array}{#1}}
%def\>{\end{array}}
% array using [ ] with rounded corners:
%def\[#1:{\left\lgroup\begin{array}{#1}}
%def\]{\end{array}\right\rgroup}
% array using ( ):
%def\(#1:{\left(\begin{array}{#1}}
%def\){\end{array}\right)}
% \def\hh{\noalign{\vskip\doublerulesep}}
%%%% MATH SYMBOLS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%def\d{\mathord{\rm d}} % d as in dx
%def\e{{\rm e}} % e as in e^x
%def\Ell{\hbox{\it\char`\$}}
\def\sfmath#1{{\mathchoice%
{{\sf #1}}{{\sf #1}}{{\S\sf #1}}{{\SS\sf #1}}}}
\def\Stalkset#1{\sfmath{I\kern-.12em#1}}
%def\Bset{\Stalkset B}
\def\Nset{\Stalkset N}
%def\Pset{\Stalkset P}
\def\Rset{\Stalkset R}
%def\Hset{\Stalkset H}
%def\Fset{\Stalkset F}
%def\Kset{\Stalkset K}
%def\kset{\Stalkset k}
\def\In@set{\raise.14ex\hbox{\i}\kern-.237em\raise.43ex\hbox{\i}}
\def\Roundset#1{\sfmath{\kern.14em\In@set\kern-.4em#1}}
\def\Qset{\Roundset Q}
\def\Cset{\Roundset C}
%def\Oset{\Roundset O}
%def\Gset{\Roundset G}
\def\Zset{\sfmath{Z\kern-.44emZ}}
%frac overwrites LaTeX's one (use TeX \over instead)
%def\fraq#1#2{{}^{#1}\!/\!{}_{\,#2}}
\def\frac#1#2{\mathord{\mathchoice%
{\T{#1\over#2}}
{\T{#1\over#2}}
{\S{#1\over#2}}
{\SS{#1\over#2}}}}
%def\half{\frac12}
\mathcode`\<="4268 % < now is \langle, \lt is <
\mathcode`\>="5269 % > now is \rangle, \gt is >
%def\biggg#1{{\hbox{$\left#1\vbox %to20.5\p@{}\right.\n@space$}}}
%def\Biggg#1{{\hbox{$\left#1\vbox %to23.5\p@{}\right.\n@space$}}}
\let\epsi=\varepsilon
\def\omikron{o}
\def\Alpha{{\rm A}}
\def\Beta{{\rm B}}
\def\Epsilon{{\rm E}}
\def\Zeta{{\rm Z}}
\def\Eta{{\rm H}}
\def\Iota{{\rm I}}
\def\Kappa{{\rm K}}
\def\Mu{{\rm M}}
\def\Nu{{\rm N}}
\def\Omikron{{\rm O}}
\def\Rho{{\rm P}}
\def\Tau{{\rm T}}
\def\Ypsilon{{\rm Y}} % differs from \Upsilon
\def\Chi{{\rm X}}
%def\dg{^{\circ}} % degrees
%def\1{^{-1}} % inverse
%def\*#1{{\bf #1}} % boldface e.g. vector
%def\vi{\mathord{\hbox{\bf\i}}} % boldface vector \i
%def\vj{\mathord{\,\hbox{\bf\j}}} % boldface vector \j
%def\union{\mathbin\cup}
%def\isect{\mathbin\cap}
%let\so\Longrightarrow
%let\oso\Longleftrightarrow
%let\os\Longleftarrow
% := and :<=>
%def\isdef{\mathrel{\smash{\stackrel{\SS\rm def}{=}}}}
%def\iffdef{\mathrel{\smash{stackrel{\SS\rm def}{\oso}}}}
%def\isdef{\mathrel{\mathop{=}\limits^{\smash{\hbox{\tiny def}}}}}
%def\iffdef{\mathrel{\mathop{\oso}\limits^{\smash{\hbox{\tiny def}}}}}
%def\tr{\mathop{\rm tr}} % tr[ace]
%def\ter#1{\mathop{^#1\rm ter}} % k-ter[minant]
%let\.=\cdot
%let\x=\times % ÃÂÃÂÃÂÃÂ (direct product)
%def\qed{ ${\S\circ}\!{}^\circ\!{\S\circ}$}
%def\qed{\vrule height 6pt width 6pt depth 0pt}
\def\edots{\mathinner{\mkern1mu
\raise7pt\vbox{\kern7pt\hbox{.}}\mkern1mu % . shorter
\raise4pt\hbox{.}\mkern1mu % .
\raise1pt\hbox{.}\mkern1mu}} % .
\def\fdots{\mathinner{\mkern1mu
\raise7pt\vbox{\kern7pt\hbox{.}} % . ~45ÃÂð
\raise4pt\hbox{.} % .
\raise1pt\hbox{.}\mkern1mu}} % .
\def\mod#1{\allowbreak \mkern 10mu({\rm mod}\,\,#1)}
% redefines TeX's one using less space
%def\int{\intop\displaylimits}
%def\oint{\ointop\displaylimits}
%def\intoi{\int_0^1}
%def\intall{\int_{-\infty}^\infty}
%def\su#1{\mathop{\sum\raise0.7pt\hbox{$\S\!\!\!\!\!#1\,$}}}
%let\frakR\Re
%let\frakI\Im
%def\Re{\mathop{\rm Re}\nolimits}
%def\Im{\mathop{\rm Im}\nolimits}
%def\conj#1{\overline{#1\vphantom1}}
%def\cj#1{\overline{#1\vphantom+}}
%def\forAll{\mathop\forall\limits}
%def\Exists{\mathop\exists\limits}
%%%% PICTURES %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%def\cent{\makebox(0,0)}
%def\node{\circle*4}
%def\nOde{\circle4}
%%%% REFERENCES %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\opcit{[{\it op.\,cit.}]}
\def\bitem#1{\bibitem[#1]{#1}}
\def\name#1{{\sc #1}}
\def\book#1{{\sl #1\/}}
\def\paper#1{``#1''}
\def\mag#1{{\it #1\/}}
\def\vol#1{{\bf #1}}
\def\isbn#1{\hbox{\small\tt ISBN\,\,#1}}
\def\seq#1{{\small\tt #1}}
%def\url<{\verb>}
\def\@cite#1#2{[{#1\if@tempswa\ #2\fi}]}
%%%% VERBATIM CODE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\"{\verb"}
%%%% WORDS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \hyphenation{pre-sent pre-sents pre-sent-ed pre-sent-ing
% re-pre-sent re-pre-sents re-pre-sent-ed re-pre-sent-ing
% re-fer-ence re-fer-ences re-fer-enced re-fer-encing
% ge-o-met-ry re-la-ti-vi-ty Gauss-ian Gauss-ians
% Des-ar-gues-ian}
%def\oord/{o{\trema o}rdin\-ate}
% usage: C\oord/s, c\oord/.
% output: co\"ord... except when linebreak at co-ord...
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% ^ ^
\catcode`\@=12 % ` '
% ->*<-
% ~\PMlinkescapeword{arcs}
\PMlinkescapeword{cycle}
\PMlinkescapeword{closed}
\PMlinkescapeword{length}
\PMlinkescapeword{node}
\PMlinkescapeword{nodes}
\PMlinkescapeword{open}
\PMlinkescapeword{order}
\PMlinkescapeword{sequence}
\PMlinkescapeword{term}
\PMlinkescapeword{terms}
\PMlinkescapeword{types}
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 $G$,
%
\begin{itemize}
\item a {\bf walk} of length $s$ is formed by a sequence of $s$ 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
{\bf walk} of length $s$ is then a sequence of vertices $\nu_0$,
$\nu_1$, \dots\ $\nu_s$ such that an edge $\nu_i\nu_{i+1}$ exists
for all $0\le i\lt s$. Again the walk is considered to contain those
edges as well as the vertices.
\item A {\bf trek} is a walk that does not backtrack, i.e.\
no two successive edges are the same.
For simple graphs this also implies
$\nu_i \ne \nu_{i+2}$ for all $0\le i\le s-2$.
\item A {\bf trail} is a walk where all edges are distinct, and
\item a {\bf path} is one where all vertices are distinct.
\end{itemize}
%
The walk, etc.\ is said to {\bf run from $\nu_0$ to $\nu_s$}, to {\bf run between} them, to {\bf connect} them etc. The term {\em trek\/} was introduced by Cameron~\cite{Cam94} who notes the lexicographic mnemonic
$$
\hbox{\em paths\/} \;\subset\;
\hbox{\em trails\/} \;\subset\;
\hbox{\em treks\/} \;\subset\;
\hbox{\em walks\/}
$$
The other terms are fairly widespread, cf.~\cite{Wil02}, but {\bf beware:} many authors call walks {\bf paths}, and some then call paths {\bf chains}. And when edges are called {\bf arcs}, a trek of length $s$ sometimes goes by the name
{\bf $s$-arc}.
Note that for the purpose of defining connectivity any of these types of wanderings can be used; if a walk exists between vertices $\mu$ and $\nu$ then there also exists a path between them. And here we must allow $s=0$ to make ``are connected by a path'' an equivalence relation on vertices (in order to define
connected components as its equivalence classes).
%
\begin{itemize}
\item A {\bf closed walk} aka {\bf circuit} of length $s\ne0$ is a walk where
$\nu_0 = \nu_s$,
\item a {\bf closed trek} is a trek that's closed in the same way, and
\item a {\bf closed trail} likewise;
\item a {\bf closed path} aka ({\bf elementary}) {\bf cycle} is like a path
(except that we only demand that $\nu_i$ for $0\le i\lt s$ are distinct)
and again closed ($\nu_s$ again coincides with $\nu_0$).
\end{itemize}
%
{\bf Beware:} cycles are often called circuits~\cite{Cam94}; the distinction between circuits and cycles here follows Wilson~\cite{Wil02}. These closed wanderings are often called after their length: {\bf $s$-circuits}, {\bf $s$-cycles}.
The case $s=0$ is excluded from these definitions; $1$-cycles are loops so imply a pseudograph; $2$-cycles are double edges implying multigraphs; so $3$ 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 $a$, out via edge $b$ say) and visit it again (in via $c$, out via $d$) without also revisiting an edge, because there are only three edges at each vertex.
%
\begin{itemize}
\item An {\bf open walk}, {\bf open trek}, {\bf open trail} is one that isn't
closed.
\item An {\bf open path} (sometimes {\bf 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.
\end{itemize}
\begin{thebibliography}{MST73}
\bitem{Cam94} \name{Peter~J.~Cameron},
\book{Combinatorics: topics, techniques, algorithms}\\
Camb.~Univ.~Pr.~1994, \isbn{0\,521\,45761\,0},\\
{\tt\PMlinkexternal{http://www.maths.qmul.ac.uk/~pjc/comb/}{http://www.maths.qmul.ac.uk/~pjc/comb/}}
(solutions, errata \&c.)
\bitem{Wil02} \name{Robert~A.~Wilson},
\book{Graphs, Colourings and the Four-colour Theorem},\\
Oxford~Univ.~Pr.~2002, \isbn{0\,19\,851062\,4} (pbk),\\
{\tt\PMlinkexternal{http://www.maths.qmul.ac.uk/~raw/graph.html}{http://www.maths.qmul.ac.uk/~raw/graph.html}}
(errata \&c.)
\end{thebibliography}