this is for holding javascript data
ZoƩ Christoff edited untitled.tex
about 8 years ago
Commit id: d3630bc1e658fc35dfb7eacfb4a2cb36d1153ca8
deletions | additions
diff --git a/untitled.tex b/untitled.tex
index bdac737..6840edf 100644
--- a/untitled.tex
+++ b/untitled.tex
...
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 A \emph{path} is a sequence of nodes $$, such that, for all $l\in\{1,\dots,k\}$,
$i_lRi_{l+1}$;
\item[]A $i_lRi_{l+1}$.A \emph{cycle} is a path of length $k$ such that $i_1=i_k$;
\item[]A 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$,
\item[]a \emph{connected component} if for any $i,j \in \N$: $iR^*j$ if and only if $i,j\in
C$, S$,
\item[]\emph{aperiodic} if the greatest common divisor of its cycles is $1$.
\end{itemize}
\end{itemize}
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$.