From: Jean-François Couchot Date: Mon, 16 Feb 2015 15:14:11 +0000 (+0100) Subject: td X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/commitdiff_plain/f18e5003b9da99d6565d366a1a9d56f8d893e5d9?ds=inline;hp=46923e2a8ce7f8ad2258360cba2127f7f1b79155 td --- diff --git a/images/iter_f0c.dot b/images/iter_f0c.dot index be8e695..74be438 100644 --- a/images/iter_f0c.dot +++ b/images/iter_f0c.dot @@ -7,30 +7,37 @@ digraph { 101 [shape="none", label="101", pos="11.7320508076,9!"]; 110 [shape="none", label="110", pos="12,8!"]; 111 [shape="none", label="111", pos="13.7320508076,9!"]; - // 000:nw -> 000:so [color="blue"] - 000 -> 010; - 000 -> 001; - //010:ne -> 010:se [color="blue"] - 010 -> 110; - 010 -> 011; - 001 -> 000; - //001 -> 001 [color="blue"] - 001 -> 101; - //101 -> 101 [color="blue"] - 101 -> 100; - 101 -> 111; - //110 -> 110 [color="blue"] - 110 -> 100; - 110 -> 111; - 011 -> 010; - 011 -> 001; - //011 -> 011 [color="blue"] - 100 -> 000; - //100 -> 100 [color="blue"] - 100 -> 110 - //111 -> 111 [color="blue"] - 111 -> 011; - 111 -> 101 + 000:nw -> 000:w [label="1"] + 000 -> 010 [label="2"] + 000 -> 001 [label="3"] + + 010 -> 010 [label="2"] + 010 -> 110 [label="1"] + 010 -> 011 [label="3"] + + 001 -> 000 [label="3"] + 001:nw -> 001:w [label="2"] + 001 -> 101 [label="1"] + + 101:nw -> 101:w [label="1"] + 101 -> 100 [label="3"] + 101 -> 111 [label="2"] + + 110 -> 110 [label="1"] + 110 -> 100 [label="2"] + 110 -> 111 [label="3"] + + 011 -> 010 [label="3"] + 011 -> 001 [label="2"] + 011 -> 011 [label="1"] + + 100 -> 000 [label="1"] + 100:nw -> 100:w [label="3"] + 100 -> 110 [label="2"] + + 111 -> 111 [label="3"] + 111 -> 011 [label="1"] + 111 -> 101 [label="2"] /* 000 -> 100 [style="dashed"] 100 -> 101 [style="dashed"] diff --git a/preliminaries.tex b/preliminaries.tex index f90fdae..8f7774a 100644 --- a/preliminaries.tex +++ b/preliminaries.tex @@ -34,54 +34,46 @@ the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(i,x)$. Let us consider for instance $n=3$. Let $f^*: \Bool^3 \rightarrow \Bool^3$ be defined by - $f^*(x_1,x_2,x_3) = (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2}, -\overline{x_1}\overline{x_3} + x_1x_2)$ - - +\overline{x_1}\overline{x_3} + x_1x_2)$. The iteration graph $\Gamma(f^*)$ of this function is given in Figure~\ref{fig:iteration:f*}. \vspace{-1em} \begin{figure}[ht] \begin{center} -\includegraphics[scale=0.5]{images/iter_f0c.eps} +\includegraphics[scale=0.5]{images/iter_f0c} \end{center} \vspace{-0.5em} \caption{Iteration Graph $\Gamma(f^*)$ of the function $f^*$}\label{fig:iteration:f*} \end{figure} \end{xpl} -\vspace{-0.5em} -It is easy to associate a Markov Matrix $M$ to such a graph $G(f)$ -as follows: - -$M_{ij} = \frac{1}{n}$ if there is an edge from $i$ to $j$ in $\Gamma(f)$ and $i \neq j$; $M_{ii} = 1 - \sum\limits_{j=1, j\neq i}^n M_{ij}$; and $M_{ij} = 0$ otherwise. - -\begin{xpl} -The Markov matrix associated to the function $f^*$ is - -\[ -M=\dfrac{1}{3} \left( -\begin{array}{llllllll} -1&1&1&0&0&0&0&0 \\ -1&1&0&0&0&1&0&0 \\ -0&0&1&1&0&0&1&0 \\ -0&1&1&1&0&0&0&0 \\ -1&0&0&0&1&0&1&0 \\ -0&0&0&0&1&1&0&1 \\ -0&0&0&0&1&0&1&1 \\ -0&0&0&1&0&1&0&1 -\end{array} -\right) -\] - - - - - -\end{xpl} +% \vspace{-0.5em} +% It is easy to associate a Markov Matrix $M$ to such a graph $G(f)$ +% as follows: + +% $M_{ij} = \frac{1}{n}$ if there is an edge from $i$ to $j$ in $\Gamma(f)$ and $i \neq j$; $M_{ii} = 1 - \sum\limits_{j=1, j\neq i}^n M_{ij}$; and $M_{ij} = 0$ otherwise. + +% \begin{xpl} +% The Markov matrix associated to the function $f^*$ is + +% \[ +% M=\dfrac{1}{3} \left( +% \begin{array}{llllllll} +% 1&1&1&0&0&0&0&0 \\ +% 1&1&0&0&0&1&0&0 \\ +% 0&0&1&1&0&0&1&0 \\ +% 0&1&1&1&0&0&0&0 \\ +% 1&0&0&0&1&0&1&0 \\ +% 0&0&0&0&1&1&0&1 \\ +% 0&0&0&0&1&0&1&1 \\ +% 0&0&0&1&0&1&0&1 +% \end{array} +% \right) +% \] +%\end{xpl} It is usual to check whether rows of such kind of matrices