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

Commit id: 46d19f99cc82917fbefa2bdcea103b8e37a4a983

deletions | additions      

       

We start with some preliminary graph-theoretic remarks.   Let us first recall some vocabulary. Let $G = \tuple{\N, R}$ and $R*$ $R^*$  the transitive and symmetric closure of $R$. A connected component $C$ of graph $G$ is a set of nodes $C\subseteq \N$ such that, for any $i,j\in \N$: $iR*j$ $iR^*j$  if and only if $i,j\in C$. 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$.   We make the following observation: a graph which is serial and functional contains exactly one cycle in each of its connected components.