talk/hamiltonien1.tex

   1 \begin{block}{}
   2 \begin{itemize}
   3 \item CLPFD: approche de type \og générer, tester\fg{}.
   4 \item $f^*(x_1,x_2,x_3) =
   5 (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
   6 \overline{x_1}\overline{x_3} + x_1x_2)$: très faible $b$.
   7 \item $f^*$: $3$-cube ss le \emph{cycle hamiltonien}
   8 $000,100,101,001,011,111,110,010,000$.
   9
  10 \end{itemize}
  11 \vspace{-1em}
  12 \begin{minipage}{0.49\textwidth}
  13 %\includegraphics[scale=0.5]{iter_f0c}
  14   \includegraphics<1>[scale=0.4]{../images/iter_f0c}
  15   \includegraphics<2>[scale=0.4]{./iter_f0d2}
  16 \end{minipage}
  17 \begin{minipage}{0.49\textwidth}
  18 \vspace{-1em}
  19
  20 \[
  21 M=\dfrac{1}{3} \left(
  22 \begin{array}{llllllll}
  23 1&1&1&0&0&0&0&0 \\
  24 1&1&0&0&0&1&0&0 \\
  25 0&0&1&1&0&0&1&0 \\
  26 0&1&1&1&0&0&0&0 \\
  27 1&0&0&0&1&0&1&0 \\
  28 0&0&0&0&1&1&0&1 \\
  29 0&0&0&0&1&0&1&1 \\
  30 0&0&0&1&0&1&0&1
  31 \end{array}
  32 \right)
  33 \]
  34 \end{minipage}
  35 \end{block}
  36
  37
  38 \begin{theorem}[ $\mathsf{N}$-cube privé d'un cycle hamiltonien ~\cite{chgw+14:oip}]
  39   Dans un $\mathsf{N}$-cube,  dans lequel un  cycle hamiltonien a été enlevé:
  40   \begin{itemize}
  41   \item La matrice de Markov engendrée est  doublement stochastique.
  42   \item Le  graphe $\textsc{giu}$ correspondant est fortement connexe.
  43   \end{itemize}
  44 \end{theorem}
  45
  46