annexesccg.tex

   1 Soit $\alpha\in\Bool$.
   2 On nomme $f^{\alpha}$ la fonction de $\Bool^{n-1}$
   3 dans lui-même définie pour
   4 chaque $x\in\Bool^{n-1}$ par
   5 \[
   6 f^{\alpha}(x)=(f_1(x,\alpha),\dots,f_{n-1}(x,\alpha)).
   7 \]
   8 On nomme $\Gamma(f)^\alpha$ le sous-graphe
   9 de $\Gamma(f)$ engendré par le sous-ensemble
  10 $\Bool^{n-1} \times \{\alpha\}$ de $\Bool^n$.
  11
  12
  13
  14
  15 Énonçons et prouvons tout d'abord les lemmes techniques suivants:
  16
  17 \begin{lemma}\label{lemma:subgraph}
  18 $G(f^\alpha)$ est un sous-graphe de $G(f)$: chaque arc de $G(f^\alpha)$ est
  19 un arc de $G(f)$. De plus si $G(f)$ n'a pas d'arc de $n$ vers un autre
  20 sommet $i\neq n$, alors on déduit
  21 $G(f^\alpha)$ de $G(f)$ en supprimant le sommet $n$ ainsi que tous les
  22 arcs dont $n$ est soit l'extrémité, soit l'origine (et dans ce dernier
  23 cas, les arcs sont des boucles sur $n$).
  24 \end{lemma}
  25
  26 \begin{Proof}
  27 Supposons que $G(f^{\alpha})$ possède un arc de  $j$ vers $i$ de signe
  28 $s$. Par définition, il existe un sommet $x\in\Bool^{n-1}$ tel que
  29 $f^{\alpha}_{ij}(x)=s$, et puisque
  30 $f^{\alpha}_{ij}(x)=f_{ij}(x,\alpha)$, on en déduit que $G(f)$ possède un arc
  31 de $j$ à $i$ de signe $s$. Ceci prouve la première assertion.
  32 Pour démontrer la seconde, il suffit de  prouver que si
  33 $G(f)$ a un arc de $j$ vers $i$ de signe $s$, avec $i,j\neq n$, alors
  34 $G(f^\alpha)$ contient aussi cet arc. Ainsi, supposons que $G(f)$ a un
  35 arc de $j$ vers $i$ de signe $s$, avec $i,j\neq n$.
  36 Alors, il existe
  37 $x\in\Bool^{n-1}$ et $\beta\in\Bool$ tels que
  38 $f_{ij}(x,\beta)=s$. Si $f_{ij}(x,\beta)\neq f_{ij}(x,\alpha)$, alors
  39 $f_i$ dépend du  $n^{\textrm{ème}}$ composant, ce qui est en contradiction
  40 avec les hypothèses.
  41 Ainsi $f_{ij}(x,\alpha)$ est égal à $s$.
  42 On a donc aussi
  43 $f^{\alpha}_{ij}(x)=s$. Ainsi $G(f^\alpha)$ possède un arc
  44 arc de $j$ vers $i$ de signe $s$.
  45 \end{Proof}
  46
  47 \begin{lemma}\label{lemma:iso}
  48 Les graphes $\Gamma(f^\alpha)$ et $\Gamma(f)^\alpha$ sont isomorphes.
  49 \end{lemma}
  50
  51 \begin{Proof}
  52 Soit $h$ la bijection de $\Bool^{n-1}$ vers
  53 $\Bool^{n-1}\times \{\alpha\}$ définie par $h(x)=(x,\alpha)$ pour chaque
  54 $x\in\Bool^{n-1}$.
  55 On voit facilement que $h$ permet de définir un isomorphisme
  56 entre $\Gamma(f^\alpha)$ et $\Gamma(f)^\alpha$:
  57 $\Gamma(f^\alpha)$ possède un arc de $x$ vers $y$ si et seulement si
  58 $\Gamma(f)^\alpha$ a un  arc de $h(x)$ vers $h(y)$.
  59 \end{Proof}
  60
  61
  62 \begin{Proof}
  63 du Théorème~\ref{th:Adrien}.
  64 La preuve se fait par induction sur $n$.
  65 Soit $f$ une fonction de $\Bool^n$ dans lui-même et qui vérifie les hypothèses
  66 du théorème.
  67 Si $n=1$ la démonstration est élémentaire:
  68 en raison du troisième point du théorème, $G(f)$ a une boucle négative;
  69 ainsi $f(x)=\overline{x}$ et $\Gamma(f)$ est un cycle de longueur 2.
  70 On suppose donc que $n>1$ et que le théorème est valide pour toutes les
  71 fonctions de $\Bool^{n-1}$ dans lui-même.
  72 En raison du premier point du théorème, $G(f)$
  73 contient au moins un sommet $i$ tel qu'il n'existe pas dans $G(f)$
  74 d'arc de $i$ vers un autre sommet $j\neq i$.
  75 Sans perte de généralité, on peut considérer que
  76 ce sommet est  $n$.
  77 Alors, d'après le lemme~\ref{lemma:subgraph},
  78 $f^0$ et $f^1$ vérifient les conditions de l'hypothèse.
  79 Alors, par hypothèse d'induction $\Gamma(f^0)$ et
  80 $\Gamma(f^1)$ sont fortement connexes.
  81 Ainsi, d'après le lemme~\ref{lemma:iso},
  82 $\Gamma(f)^0$ et $\Gamma(f)^1$ sont fortement
  83 connexes.
  84 Pour prouver que $\Gamma(f)$ est fortement connexe, il suffit
  85 de prouver que $\Gamma(f)$ contient un arc $x\to y$ avec
  86 $x_n=0<y_n$ et un arc $x\to y$ avec $x_n=1>y_n$.
  87 En d'autres mots, il suffit de prouver que:
  88 \begin{equation}\tag{$*$}
  89 \forall \alpha\in\Bool,~\exists x\in\Bool^n,\qquad  x_n=\alpha\neq f_n(x).
  90 \end{equation}
  91
  92 On suppose tout d'abord que $n$ a une boucle
  93 négative.
  94 Alors, d'après la définition de
  95 $G(f)$, il existe $x\in\Bool^n$ tel que $f_{nn}(x)<0$.
  96 Ainsi si $x_n=0$, on a  $f_n(x)>f_n(\overline{x}^n)$, et donc
  97 $x_n=0\neq f_n(x)$ et
  98 $\overline{x}^n_n=1\neq f_n(\overline{x}^n)$;
  99 et si  $x_n=1$, on a
 100 $f_n(x)<f_n(\overline{x}^n)$, donc $x_n=1\neq f_n(x)$ et $\overline{x}^n_n=0\neq
 101 f_n(\overline{x}^n)$.
 102 Dans les deux cas, la condition ($*$) est établie.
 103
 104 Supposons maintenant que  $n$ n'a pas de boucle négative.
 105 D'après la seconde hypothèse,
 106 $n$ n'a pas de boucle, \emph{i.e.}, la valeur de $f_n(x)$
 107 ne dépend pas de la valeur de $x_n$.
 108 D'après la troisième hypothèse,
 109 il existe $i\in \llbracket 1;n \rrbracket$ tel que $G(f)$ a un arc de
 110 $i$ vers $n$.
 111 Ainsi, il existe $x \in \Bool^n$ tel que $f_{ni}(x) \neq 0$ et donc
 112 %$n$ n'est donc pas de degré zéro dans $G(f)$, \emph{i.e.}
 113 $f_n$ n'est pas constante.
 114 Ainsi, il existe $x,y\in \Bool^n$ tel que
 115 $f_n(x)=1$ et $f_n(y)=0$.
 116 Soit  $x'=(x_1,\dots,x_{n-1},0)$ et
 117 $y'=(y_1,\dots,y_{n-1},1)$.
 118 Puisque la valeur de $f_n(x)$
 119 (resp. de $f_n(y)$) ne dépend pas de la  valeur de  $x_n$ (resp. de  $y_n$),
 120 on a $f_n(x')=f_n(x)=1\neq x'_n$ (resp. $f_n(y')=f_n(y)=0\neq
 121 y'_n$).
 122 Ainsi la  condition ($*$) est établie, et le théorème est prouvé.
 123 \end{Proof}
 124
 125
 126