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

Commit id: 16154b8e6ce3bb5495b7a9a0cc5a1d31268b6fa6

deletions | additions      

       

We start with some preliminary graph-theoretic remarks.   Let us first recall some vocabulary. Let $G = \tuple{\N, R}$ and $R*$ the transitive and symmetric closure of $R$.  A connected component $C$ ofa  graph $G = \tuple{\N, R}$ $G$  is a set of nodes $C\subseteq \N$ such that: that,  for any $i,j\in C$, $iRj$ or $jRi$. \N$: $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 observe that our influence graphs are of make the following observation:  a special kind with respect to cycles: each connected component graph which is serial and functional  contains exactly one cycle. cycle in each of its connected components.  \begin{fact} \label{fact:connected}  Let $G$ be an influence graph and $C$ be a finite connected component of $G$. Then $C$ contains exactly one cycle.  \end{fact}