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

Commit id: 3147879186957e8a07ef0bce0a1f9bfa893fda8c

deletions | additions      

       

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 set of nodes $S\subseteq \N$ is \emph{connected} if for any $i,j \in \S$: $iR^*j$, \emph{strongly connected} if for any $i,j \in \S$: $iRj$, and \emph{closed} if for any $i\in S$, $j\notin S$, $i\sout{R}j$. $i\centernot{R}j$.  A \emph{connected component} of $G$ is a set $C\subseteq \N$ such that, for any $i,j \in \N$: $iR^*j$ if and only if $i,j\in C$.   A set of nodes is said to be ``strongly connected" if there is a directed path from any node to any other node in the set, ``closed" if there is no link from nodes in the set to nodes outside the set, and aperiodic if the greatest common divisor of all directed cycles is $1$  A path is a sequence of nodes $$, such that, for all $l\in\{1,\dots,k\}$, $i_lRi_{l+1}$, and a cycle is a path of length $k$ such that $i_1=i_k$.