Tout blanc tout noir

La figure 3 représente un graphe : cinq sommets numérotés de 1 à 5 et des arêtes entre eux (les arêtes ne sont pas orientées et il n'y a pas de boucle sur un même sommet).

Figure 3: Graphe à 5 sommets et 6 arêtes.

Imaginez que sur chaque sommet se trouve une ampoule, et un interrupteur qui commande non seulement l'ampoule du même sommet, mais aussi celles des sommets voisins. Par exemple appuyer sur l'interrupteur du sommet 2 bascule l'état des ampoules 1, 2, 3 et 5, de «éteinte»  à «allumée», ou bien le contraire. La première observation, est que l'ordre dans lequel les interrupteurs sont actionnés, n'a pas d'influence sur le résultat. Si tout est éteint et que vous actionnez l'interrupteur 1, les ampoules 1, 2 et 5 s'allument. Si ensuite vous actionnez 2, les ampoules 1, 2 et 5 s'éteignent, et 3 s'allume. Le résultat est le même si l'interrupteur 2 est actionné avant le 1. On peut donc parler de l'effet d'un ensemble d'interrupteurs, sans considération de l'ordre dans lequel ils sont actionnés.

Si toutes les ampoules sont éteintes, quel ensemble d'interrupteurs faut-il actionner pour les allumer toutes ? Ou de manière plus condensée, comment passer de «tout noir»  à «tout blanc». De manière assez surprenante, ce problème a toujours au moins une solution quel que soit le graphe, et on peut le résoudre à l'aide de la méthode du pivot de Gauss¹.

Attention, les calculs ne seront pas ceux dont vous avez l'habitude : nous abandonnons les réels pour un ensemble de nombres beaucoup plus petit. Pour jouer le rôle des réels, tout ensemble de nombres doit contenir au moins les éléments neutres pour l'addition et la multiplication : 0 et 1. Le plus petit ensemble possible, celui des entiers modulo 2, ne contient que 0 et 1. On le note $\mathbb{Z}/2\mathbb{Z}$. Voici les tables d'addition et de multiplication.

$$\begin{array}{c\vert cc} +&0&1\\ \hline 0&0&1\\ 1&1&0 \end... ...ray}{c\vert cc} \times&0&1\\ \hline 0&0&0\\ 1&0&1 \end{array}$$

Sur l'ensemble des $n$-uplets de 0 ou de 1, les opérations de $\mathbb{Z}/2\mathbb{Z}$ agissent composante par composante. Par exemple pour $n=4$ :

$$(0,1,0,1)+(1,0,0,1)=(1,1,0,0)\;.$$

Cet ensemble, noté $(\mathbb{Z}/2\mathbb{Z})^n$, est un espace vectoriel sur $\mathbb{Z}/2\mathbb{Z}$, tout comme $\mathbb{R}^n$ est un espace vectoriel sur $\mathbb{R}$. La méthode de résolution des systèmes linéaires dans $\mathbb{R}^n$, reste valable dans $\mathbb{Z}/2\mathbb{Z}$, en n'oubliant pas que $1+1=0$. Etant donné le problème «tout blanc - tout noir»  sur un graphe à $n$ sommets, nous allons lui associer un système linéaire de $n$ équations à $n$ inconnues.

$$(S)\qquad \left\{\begin{array}{ccccccc} a_{1,1} x_1+&\cdots&+a_{... ..._{m,1} x_1+&\cdots&+a_{m,j} x_j+&\cdots&+a_{m,n} x_n&=&1 \end{array}\right.$$

Il faut comprendre un $n$-uplet $(x_1,\ldots,x_n)$ de 0 et de 1 comme une description de l'ensemble des interrupteurs qui seront actionnés : $x_j$ vaut 1 si l'interrupteur $j$ est actionné, 0 sinon. Les coefficients $a_{i,j}$ décrivent l'effet des interrupteurs sur les ampoules : $a_{i,j}$ vaut 1 si l'interrupteur $j$ actionne l'ampoule $i$, 0 sinon. Le premier membre de la ligne $i$ décrit l'effet de la combinaison d'interrupteurs $(x_1,\ldots,x_n)$ sur l'ampoule $i$ : $a_{i,1} x_1+\cdots+a_{i,n} x_n$ vaut 1 si l'ampoule $i$ est finalement allumée, 0 si elle est éteinte. Tous les termes du second membre sont égaux à 1, car on souhaite que toutes les ampoules soient allumées à la fin.

Voici le système correspondant à la figure 3.

$$\left\{ \begin{array}{rrrrrcr} x_1&+x_2&&&+x_5&=&1\ x_1&+x_2&+x_... ...3&+x_4&&=&1\ &&x_3&+x_4&+x_5&=&1\ x_1&+x_2&&+x_4&+x_5&=&1 \end{array} \right.$$ (7)

Vous pouvez vérifier que $x=(1,1,0,0,1)$ est solution (dans $\mathbb{Z}/2\mathbb{Z}$) : actionner les interrupteurs 1, 2 et 5 allume bien toutes les ampoules dans la figure 3.

Si le graphe est trop compliqué pour deviner la solution, comment la calculer ? Par la méthode du pivot de Gauss bien sûr ! Ce qui a été exposé pour les matrices à coefficients réels, vaut pour $\mathbb{Z}/2\mathbb{Z}$. Si on applique la méthode du pivot de Gauss au système (7), on vérifie qu'il est de rang 5, donc $(1,1,0,0,1)$ est l'unique solution. Dans ce cas particulier, le système a une solution unique pour tout second membre. Donc quelle que soit la configuration d'ampoules allumées et éteintes que l'on souhaite atteindre, il y a un ensemble d'interrupteurs et un seul que l'on doit actionner pour atteindre la configuration souhaitée.

Ce n'est pas toujours le cas. Le graphe complet à $n$ sommets est tel que deux sommets quelconques sont toujours reliés par une arête. Sur un graphe complet, basculer un interrupteur quelconque allume ou éteint toutes les ampoules à la fois. Si on commence au début par toutes les ampoules éteintes, la seule autre configuration que l'on puisse atteindre est celle où tout est allumé. Dans ce cas, tous les coefficients $a_{i,j}$ du système sont égaux à 1, son rang est 1, et le système n'a de solution que si tous les coefficients du second membre sont égaux.

Le miracle est que si tous les coefficients du second membre sont égaux à 1, le système a toujours au moins une solution : quel que soit le graphe, il y a toujours un ensemble d'interrupteurs à actionner pour allumer toutes les ampoules.

Théorème 5   Pour tout graphe à $n$ sommets, le système $(S)$ a au moins une solution.

Démonstration : Appliquons la méthode du pivot de Gauss au système $(S)$. On le transforme en prenant des combinaisons linéaires des lignes, jusqu'à le mettre sous forme échelonnée. Si le rang du système est $n$, il n'y aura pas d'équation de compatibilité : le système se résout, et on trouve une solution unique. Mais si le rang est inférieur à $n$, la méthode du pivot de Gauss fait apparaître une combinaison linéaire des équations dont le premier membre est nul. Or nous sommes dans $(\mathbb{Z}/2\mathbb{Z})^n$ : les coefficients d'une combinaison linéaire ne peuvent être que 0 ou 1. Donc une combinaison linéaire est forcément une somme. Que se passe-t-il quand une somme de lignes, disons $L_{i_1}+\cdots+L_{i_k}$ a un premier membre nul ? Cela implique en particulier que chacun des sommets $i_1,\ldots,i_k$ a un nombre impair de voisins parmi les autres sommets du même ensemble $i_1,\ldots,i_k$. Si on restreint le graphe à ces sommets, on obtient un sous-graphe, tel que le nombre de voisins de chaque sommet est impair. Or dans un graphe ayant un nombre impair de sommets, il y a toujours un sommet dont le nombre de voisins est pair (ce n'est pas facile à démontrer : réflechissez !). Si tous les sommets parmi $i_1,\ldots,i_k$ ont un nombre impair de voisins, alors $k$ est pair. Donc si $L_{i_1}+\cdots+L_{i_k}$ a un premier membre nul, alors nécessairement $k$ est un entier pair. Pour appliquer la méthode du pivot de Gauss, on doit effectuer les mêmes transformations à la fois sur le premier membre et sur le second. Or le second ne contient que des 1. La somme dans $\mathbb{Z}/2\mathbb{Z}$ d'un nombre pair de 1 donne 0. Ceci entraîne que si la forme échelonnée contient une équation dont le premier membre est nul, alors le second membre de cette même équation est nul également. Donc le système a une solution.$\square$

Le théorème 2 entraîne que l'ensemble des solutions est en bijection avec un sous-espace vectoriel de $(\mathbb{Z}/2\mathbb{Z})^n$. Un sous-espace vectoriel de dimension $k$ dans $(\mathbb{Z}/2\mathbb{Z})^n$ a $2^k$ éléments. Le nombre de solutions est donc nécessairement une puissance de 2. Pour le graphe de la figure 4, vous pouvez calculer les solutions par la méthode du pivot de Gauss, et vérifier qu'il y en a 2.

Figure 4: Graphe à 6 sommets et 9 arêtes.