ZoĆ© Christoff edited untitled.tex  about 8 years ago

Commit id: d7859772800a61bafee057d03eb3b983b55a02b5

deletions | additions      

       

We start with some preliminary graph-theoretic remarks.   Let us first recall some vocabulary.   Let $G = \tuple{\N, R}$ be a graph and $R^*$ be the transitive and symmetric closure of $R$. A \emph{path} is a sequence of nodes $$, such that, for all $l\in\{1,\dots,k\}$, $i_lRi_{l+1}$.A $i_lRi_{l+1}$.   A  \emph{cycle} is a path of length $k$ such that $i_1=i_k$; $i_1=i_k$.  A set of nodes $S\subseteq \N$ is said to be: \begin{itemize}  \item[]\emph{connected} if for any $i,j \in \S$: $iR^*j$,   \item[]\emph{strongly connected} if for any $i,j \in \S$: $iRj$,   \item[]\emph{closed} if for any $i\in S$, $j\notin S$, it is not the case that $iRj$,  \item[]a \emph{connected component} if for any $i,j \in \N$: $iR^*j$ if and only if $i,j\in S$,  \item[]\emph{aperiodic} if the greatest common divisor of the lengths of  its cycles is $1$. \end{itemize}