this is for holding javascript data
ZoƩ Christoff edited untitled.tex
about 8 years ago
Commit id: b202367ddf05ec87bd3534e120f9ce7bfed9e979
deletions | additions
diff --git a/untitled.tex b/untitled.tex
index e5bb5bf..86d8256 100644
--- a/untitled.tex
+++ b/untitled.tex
...
We start with some preliminary graph-theoretic remarks.
Let us first recall some vocabulary.
Let $G = \tuple{\N, R}$ be a graph and $R^*$ be the transitive and symmetric closure of $R$.
A \begin{itemize}
\item[]A set of nodes $S\subseteq \N$ is
\emph{connected} said to be:
\begin{itemize}
\item[]\emph{connected} if for any $i,j \in \S$: $iR^*j$,
\emph{strongly \item[]\emph{strongly connected} if for any $i,j \in \S$: $iRj$,
and \emph{closed} \item[]\emph{closed} if for any $i\in S$, $j\notin S$,
$i\centernot{R}j$.
A it is not the case that $iRj$
\item[]a \emph{connected component}
of $G$ is a set $C\subseteq \N$ such that, if for any $i,j \in \N$: $iR^*j$ if and only if $i,j\in C$.
A set of nodes is said to be ``strongly connected" if there is a directed path from any node to any other node in the set, ``closed" if there is no link from nodes in the set to nodes outside the set, and aperiodic if the greatest common divisor of all directed cycles is $1$
A \end{itemize}
\item[]A path is a sequence of nodes $$, such that, for all $l\in\{1,\dots,k\}$,
$i_lRi_{l+1}$, and a $i_lRi_{l+1}$
\item[]A cycle is a path of length $k$ such that $i_1=i_k$.
\end{itemize}
We observe that a graph which is serial and functional contains exactly one cycle in each of its finite connected components.
\begin{fact} \label{fact:connected}