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

Commit id: 773e3dff491aaba39169b710907c6296143f0da7

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$.   \begin{itemize}  \item[]A \emph{path} is a sequence of nodes $$, such that, for all $l\in\{1,\dots,k\}$, $i_lRi_{l+1}$. $i_lRi_{l+1}$;  \item[]A \emph{cycle} is a path of length $k$ such that $i_1=i_k$. $i_1=i_k$;  \item[]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$ $iRj$,  \item[]a \emph{connected component} if for any $i,j \in \N$: $iR^*j$ if and only if $i,j\in C$. C$,  \item[]\emph{aperiodic} if the greatest common divisor of its cycles is $1$.  \end{itemize}  \end{itemize}  We note Note  that a graph which is the graphs we are interested in (finite,  serial and functional contains exactly one cycle in functional) come with a special shape:  each of its finite their  connected components, components contains exactly one cycle,  and this cycle has to be forms  the ``tail" of the component: \begin{fact} \label{fact:connected}  Let $G$ be an influence graph and $C$ be a connected component of $G$.   Then $C$ contains exactly one cycle, and cycle.   %and  this cycle is a closed set. \end{fact}  \begin{proof}  Assume that $C$ does not contain any cycle. Then Then, since $\N$ is finite and  no path repeats any node, any path  in $C$ can contain twice is finite. Let $i$ be  the same node. last element of the longuest path in $C$. Then $i$ does not have any successor, which contradicts seriality.  Assume that $C$ containsa cycle which is not closed. Then  more than one cycle. Let $i,j\in C$ be such that $i$ is a member of a cycle, and $j$ a member of a different cycle. By connectedness, there is a path from $i$ to $j$, so there exists a node in one of the cycles which has a successor outside of the this  cycle, but that which  contradicts functionality.Therefore, $C$ contains exactly one cycle. If the cycle were not closed,   Now assume that $C$ contains no cycle.  \end{proof}  \subsection{Backdrop: extra graph theoretical remark (WE DON'T NEED THIS ONE)}