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

Commit id: 34a6a403ed46701d540a64027e97ae2d4f3a0177

deletions | additions      

       

Note that the graphs we are interested in (finite, serial and functional) come with a special shape: each of their connected components contains exactly one cycle, and this cycle 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, since Since  $\N$ is finiteand no  path repeats do not repeat  any node, any path in $C$ is finite. Let $i$ be the last element of the longuest path in $C$. Then $i$ does not have any successor, which contradicts seriality. Assume that So  $C$ contains more than at least  one cycle. Let $i,j\in C$ $S$  be such that $i$ is a member the set of node  of a cycle, cycle in $C$. Assume that $S$ is not closed: for some $i\in S$  and $j$ a member of $j\notin S$, $iRj$. Since $S$ is  a different cycle. By connectedness, cycle,  there is also some $k\in S$, such that $iRk$, which contradicts functionality.  Assume that $C$ contains more than one cycle. Since each cycle forms  a path from $i$ to $j$, so closed set,  there exists a is no path connecting any  node in one of inside  the cycles which has a successor cycle to any node  outside of this the  cycle, which contradicts functionality. connectedness. So $C$ contains a unique cycle which is a closed set.  \end{proof}  \subsection{Backdrop: extra graph theoretical remark (WE DON'T NEED THIS ONE)}