Xavier Badin de Montjoye

On présente ici un résultat important de la théorie des graphes pourtant méconnus des étudiants. Le but de cet exercice est de démontrer le théorème de Kirchhoff, aussi appelé matrix tree theorem. Ce théorème donne une formule pour compter le nombre d’arbres couvrants d’un graphe.

Cet exercice nécessite une bon maîtrise mathématique de la notion de matrice et de déterminant.

Exercice

Soit $G = (S,A)$ un graphe non orienté, avec $n = |S|$ et $m=|A|$ . On associe chaque sommet de $S$ à un élément de l’ensemble $\{1,\,\ldots,\,n\}$ et on pose $A = \{a_1,\, \ldots,\, a_m\}$ . Enfin, on note $\tau(G)$ le nombre d’arbres couvrants de $G$ .

Soit $M$ matrice de $\mathcal{M}_{n}(\mathbb{R})$ et $i,j \leq n$ . On note $M_{i,j}$ la valeur de $M$ à la coordonnée $i,j$ . On définit $M[i]$ comme la matrice $M$ où on a supprimé la $i$ -ème ligne de $M$ et $M[i,j]$ comme la matrice $M$ où on a supprimé la $i$ -ème ligne et $j$ -ème colonne de $M$ .

On considère maintenant $L \in \mathcal{M}_{n}(\mathbb{R})$ la matrice Laplacienne de $G$ . Pour rappel, elle est définie ainsi. Pour $i,j \leq n$ :

$L_{i,j} = \begin{cases} \text{ degré de } i & \text{ si } i = j \\ -1 & \text{ si } (i,j) \in A \\ 0 & \text{ sinon } \end{cases}$

On pose $B$ la matrice de $\mathcal{M}_{n,m}(\mathbb{R})$ définie pour $x \leq m$ , et $(i,j) = a_x$ avec $i \lt j$ , par $B_{i,x} = 1$ , $B_{j,x} = -1$ , et toutes les autres coordonnées sont égales à $0$ .

$1.$ Prouver que $L = BB^{T}$ .

$2.$ Prouver que pour tout $i$ , $L[i,i] = B[i]B[i]^{T}$ .

Soit $U$ un ensemble d’arêtes de $A$ . On définit $B_U$ comme la matrice $B$ dont on ne garde la colonne $i$ que si $a_i \in U$ .

$3.$ Montrer que tout ensemble de $n-1$ arêtes de $G$ forme un arbre couvrant si et seulement si il ne possède pas de cycles.

$4.$ Soit $U \subset A$ de taille $n-1$ tel que $U$ ne forme pas un arbre couvrant. Pour tout $i \leq n$ , calculer $\det(B_U[i])$ .

$5.$ Soit $U \subset A$ de taille $n-1$ tel que $U$ forme un arbre couvrant. Montrer que pour tout $i$ , $\det\left(B_U[i]\right) = \pm 1$ .

Donnons la formule de Binet-Cauchy. Soit $C$ et $D$ des matrices de $\mathcal{M}_{n,m}(\mathbb{R})$ et $\mathcal{M}_{m,n}(\mathbb{R})$ . Pour tout ensemble $U \subset \{1,\,\ldots,\,m\}$ de $n$ éléments, on note $C_U$ la sous-matrice de $C$ dont on n’a gardé que les colonnes de $U$ et $D_U$ la sous-matrice de $D$ dont on n’a gardé que les lignes de $U$ . On a alors l’égalité suivante :

$\det(CD) = \sum\limits_{U \subset \{1,\,\ldots,\,m\} \atop |U| = n} \det(C_U)\det(D_U)$

$6.$ En déduire que pour tout $i \leq n$ on a $\det(L[i,i]) = \tau(G)$ .

Correction

$1.$ Pour tout $i$ , on note $A_i$ l’ensemble des arêtes de $G$ contenant $i$ . Soit $M = BB^{T}$ . On a :

$\begin{align*} M_{i,i} & = \sum\limits_{x \in A} B_{i,x}B^{T}_{x,i} \\ & = \sum\limits_{x \in A_i} B_{i,x}B^{T}_{x,i} \\ & = \sum\limits_{x \in A} 1 \\ M_{i,i} & = |A_i| \end{align*}$

Ainsi, $M_{i,i}$ est bien égal au degré de $i$ et donc à $L_{i,i}.

Pour $i \neq j$ , s’il n’existe pas d’arête $(i,j)$ on a pour toute arête $a \in A$ , soit $B_{i,x} = 0$ , soit $B_{j,x} = 0$ . De ce fait, $M_{i,j} = 0 = L_{i,j}$ .

Enfin, si $(i,j) \in A$ , on a $B_{i,(i,j)}B_{j,(i,j)} = -1$ et pour tout $a$ de $A$ différent de $(i,j)$ , $B_{i,a}B_{j,a} = 0$ . Donc $M_{i,j} = -1 = L_{i,j}$ .

En conclusion on a donc bien prouvé l’égalité suivante :

$\boxed{L = BB^{T}}$

$2.$ Si on considère que les lignes sont indicées par les sommets, on peut écrire : pour tout $j,k$ différents de $i$ on a $L[i,i]_{j,k} = L_{j,k}$ . De plus $\displaystyle L_{j,k} = \sum\limits_{x \in A} B_{j,x}B^{T}_{x,k}$ . Or pour tout $x$ , $B_{j,x} = B[i]_{j,x}$ . On a donc bien :

$\boxed{L[i,i] = B[i]B[i]^{T}}$

$3.$ Tout d’abord, on rappelle qu’un arbre est un graphe connexe sans cycle. Il ne reste donc qu’à prouver qu’un sous ensemble d’arêtes sans cycle de taille $n-1$ est connexe.

Commençons par préciser que tout arbre couvrant de $G$ a exactement $n-1$ arêtes. Pour s’en convaincre, il suffit d’enraciner l’arbre dans un de ses sommets. Chaque autre sommet possède alors exactement un parent et chaque arête définit une relation parent-enfant. Donc, il y a autant d’arêtes que de parents. De ce fait, il y a exactement $n-1$ arêtes.

Ainsi, si un sous-ensemble sans cycle de $n-1$ arêtes n’est pas connexe, on peut le prolonger en un arbre couvrant de taille strictement supérieure à $n-1$ , ce qui n’est pas possible.

De ce fait, tout ensemble de $n-1$ arêtes de $G$ forme un arbre couvrant si et seulement si il ne possède pas de cycles.

$4.$ Si $U$ ne forme pas d’arbre couvrant, par la question précédente, on en déduit que $U$ possède un cycle. Soit $C$ les arêtes traversées dans le cycle de taille minimale de $U$ . On s’intéresse à la matrice $B_C[i]$ . Pour toute arête $x=(i,j) \in C$ avec $i \lt j$ , on pose $\lambda_x$ qui vaut $1$ si notre cycle va de $i$ à $j$ et $-1$ si on parcourt l’arête dans l’autre sens. On note que pour tout $i$ on a :

$\boxed{\sum\limits_{x \in C}\lambda_xB_{i,x} = 0}$

En effet, si $i$ est un sommet apparaissant dans notre cycle, il apparaît dans exactement deux arêtes, pour assurer que $C$ soit bien un cycle minimal. Soit $x$ l’arête qui emmène à $i$ et $y$ celle qui en part. On a alors $B_{i,x} = -1$ et $B_{i,y} = 1$ . Donc $B_{i,x} + B_{i,y} = 0$ . De plus, si $i$ n’apparaît pas dans notre cycle, alors pour tout $x \in C$ , $B_{i,x} = 0$ .

Ainsi, les colonnes de $B_C$ sont linéairement dépendantes, donc les colonnes de $B_C[i]$ et de $B_U[i]$ aussi. De ce fait, $\displaystyle \boxed{\det(B_U[i]) = 0}$ .

$5.$ Pour prouver ce résultat, on procède par récurrence sur $n \geq 2$ , le nombre de sommets dans $G$ . On pose donc $\mathcal{P}(n) =$ « Pour tout graphe $G$ à $n$ sommets et pour tout sous-ensemble $U$ d’arêtes de $G$ formant un arbre couvrant, on a pour tout sommet $i$ , $\det(B_U[i]) = \pm 1$ ».

Pour le cas $n = 2$ , on note que $B_U$ est une matrice à une colonne et deux lignes ayant pour termes $\pm 1$ . De ce fait, $B_U[i]$ est une matrice de dimension $1$ de valeur $\pm 1$ .

On suppose donc que $\mathcal{P}(n)$ est vrai pour $n \geq 2$ . Montrons que $\mathcal{P}(n+1)$ est vrai. Soit $G$ un graphe à $n+1$ sommets et $U$ un ensemble de $n$ arêtes de $G$ formant un arbre couvrant. Soit $i$ un sommet de $G$ . On considère $B_U[i]$ . Soit $a \in S$ une arête de $U$ touchant $i$ . Cette arête existe par définition d’arbre couvrant. Dans la colonne de $B_U[i]$ associé à $a$ , on a donc un seul élément, ligne $j$ , non nul et qui vaut $\pm 1$ . On développe alors suivant cette colonne. On a alors :

$\boxed{\det(B_U[i]) = \pm \det(B_U[i][j,a])}$

Maintenant, on considère le graphe $G’=(S’,A’)$ dans lequel on a contracté l’arête $a$ . C’est à dire, on supprime le sommet $j$ et pour toute arête $(j,k)$ , on ajoute l’arête $(i,k)$ . On note que le sous graphe $(S’,U’)$ qui correspond à la contraction de l’arête $a$ dans le graphe $(S,U)$ , est également un arbre couvrant. De ce fait, on peut appliquer notre hypothèse de récurrence sur $G’$ pour obtenir $\det(B_U[i][j,a]) = \pm 1$ . On a donc montré :

$\boxed{\det(B_U[i]) = \pm 1}$

$6.$ Soit $i$ un sommet de $G$ . On a prouvé que $L[i,i] = B[i]B[i]^{T}$ .

Appliquons la formule de Binet-Cauchy sur $\det(B[i]B[i]^{T})$ . On note, $T$ l’ensemble des sous-ensembles de taille $n-1$ de $A$ formant un arbre couvrant, et $\bar{T}$ ceux de taille $n-1$ qui contiennent un cycle. On obtient alors :

$\begin{align*} \det(L[i,i]) & = \det(B[i]B[i]^{T}) \\ & = \sum\limits_{\substack{U \subset \{1,\,\ldots,\,m\} \\ |U| = n-1}} \det(B_U[i])\det(B_U[i]^{T}) \\ & = \sum\limits_{\substack{U \subset \{1,\,\ldots,\,m\} \\ |U| = n-1}} \det(B_U[i])^{2} \\ & = \sum\limits_{U \in T} \det(B_U[i])^{2} + \sum\limits_{U \in \bar{T}} \det(B_U[i])^{2} \\ \det(L[i,i]) & = \sum\limits_{U \in T} 1 + \sum\limits_{U \in \bar{T}} 0 \end{align*}$

Cela nous permet donc de conclure :

$\boxed{\det(L[i,i]) = \tau(G)}$

Exercice

Le but du codage de Gray est de représenter les entiers de telle sorte qu’un seul bit soit modifié à chaque incrémentation. Pour $n$ un entier strictement positif, on définit la fonction $\Gamma_n$ de $\{\;0,\;\ldots,\;2^{n}-1\;\}$ dans $\{\;0,\;1\;\}^{n}$ , qui à un entier associe son codage de Gray sur $n$ bits. On définit de même la fonction $B_n$ de $\{\;0,\;\ldots,\;2^{n}-1\;\}$ dans $\{\;0,\;1\;\}^{n}$ qui à un entier associe son écriture binaire sur $n$ bits.

On définit récursivement $\Gamma_n$ : $\Gamma_1(0) = 0$ , $\Gamma_1(1) = 1$ et $\forall n \geq 2,\;\forall k \lt 2^{n}$ :

$\Gamma_n(k) = \begin{cases} 0\Gamma_{n-1}(k) \text{ si $k \lt 2^{n-1}$ } \\ 1\Gamma_{n-1}(2^{n}-k-1) \text{ sinon }\end{cases}$

$1.$ a) Donner la table des valeurs de $\Gamma_3$ .

b) Prouver que pour tout entier $n$ et pour tout entier $k \lt 2^{n} – 1$ , les représentations $\Gamma_n(k)$ et $\Gamma_n(k+1)$ ne diffèrent que d’un seul bit.

On note cependant que cette définition ne nous permet pas de passer rapidement d’un entier en binaire à sa représentation en codage de Gray.

Soit $n \geq 1$ et $k \lt 2^{n}$ . On considère la fonction $\Phi_n$ de $\{\;0,\;\ldots,\;2^{n}-1\;\}$ dans $\{\;0,\;1\;\}^{n}$ définie par :

$\Phi_n(k) = B_n(k) \oplus B_n\left(\left\lfloor \frac{k}{2}\right\rfloor\right)$

où l’opérateur $\oplus$ correspond au XOR bit à bit.

$2.$ Prouver que la fonction $\Phi_n$ est bijective.

$3.$ Soit $0 \leq r \lt 2^{n}$ . Prouver la relation :

$B_{n+1}(2^n+r) \oplus B_{n+1}(2^n-r-1) = \underbrace{11\ldots1}_{n+1 \text{ fois}}$

$4.$ Déduire que pour tout $n$ et tout $k \lt 2^{n}$ , on a $\Gamma_n(k) = \Phi_n(k)$ .

$5.$ Donner une méthode directe pour passer de $\Gamma_n(k)$ à $B_n(k)$ et de $B_n(k)$ à $\Gamma_n(k)$ .

Maintenant que nous pouvons aisément représenter les entiers par un codage de Gray, il nous reste à savoir comment incrémenter les entiers sans repasser par le codage binaire. Pour ce faire on présente la méthode suivante : soit $k \lt 2^{n}-1$ . On connaît $\Gamma_n(k)$ et on cherche $\Gamma_n(k+1)$ . Si le nombre de $1$ dans $\Gamma_n(k)$ est pair, alors on inverse le bit le plus à droite. Sinon, on inverse le bit à gauche du bit à $1$ le plus à droite.

$6.$ Prouver la correction de cette méthode.

Correction

$1.$ a) Calculons $\Gamma_3$ .

$\begin{matrix}\Gamma_1(0) = 0 \\ \Gamma_1(1) = 1\end{matrix} \Rightarrow \begin{matrix}\Gamma_2(0) = 00 \\ \Gamma_2(1) = 01 \\ \Gamma_2(2) = 11 \\ \Gamma_2(3) = 10 \end{matrix} \Rightarrow \begin{matrix}\Gamma_3(0) = 000 \\ \Gamma_3(1) = 001 \\ \Gamma_3(2) = 011 \\ \Gamma_3(3) = 010 \\ \Gamma_3(4) = 110 \\ \Gamma_3(5) = 111 \\ \Gamma_3(6) = 101 \\ \Gamma_3(7) = 100\end{matrix}$

b) Prouvons par récurrence sur $n\geq1$ que pour tout $k \lt 2^{n}-1$ , $\Gamma_n(k)$ et $\Gamma_n(k+1)$ ne diffèrent que d’un seul bit.

La table des valeurs de $\Gamma_1$ ci-dessus nous permet de vérifier le cas $1$ . On suppose maintenant la propriété vraie au rang $n$ , montrons qu’elle le reste au rang $n+1$ .

Soit $k \lt 2^{n+1}-1$ .

Si $k \lt 2^{n}-1$ : on a par hypothèse de récurrence que $\Gamma_n(k)$ et $\Gamma_n(k+1)$ ne diffèrent que d’un seul bit. Or :

$\Gamma_{n+1}(k) = 0\Gamma_{n}(k) \text{ et } \Gamma_{n+1}(k+1) = 0\Gamma_{n}(k+1)$

Ainsi $\Gamma_{n+1}(k)$ et $\Gamma_{n+1}(k)$ ne diffèrent que d’un seul bit.

Si $2^{n}-1 \lt k \lt 2^{n+1}-1$ : on a $\Gamma_{n+1}(k) = 1\Gamma_{n}(2^{n+1}-k)$ et $\Gamma_{n+1}(k+1) = 1\Gamma_{n}(2^{n+1}-k-1)$ . Or, par hypothèse de récurrence, $\Gamma_{n}(2^{n+1}-k)$ et $\Gamma_{n}(2^{n+1}-k-1)$ ne diffèrent que d’un seul bit, et donc $\Gamma_{n+1}(k)$ et $\Gamma_{n+1}(k+1)$ aussi.

Enfin, si $k = 2^{n+1}-1$ : on a $\Gamma_{n+1}(k) = 0\Gamma_{n}(k)$ et $\Gamma_{n+1}(k+1) = 1\Gamma_{n}(k)$ . Ces deux mots ne diffèrent que sur le premier bit, donc $\Gamma_{n+1}(k)$ et $\Gamma_{n+1}(k+1)$ ne diffèrent que d’un unique bit.

Cela prouve la propriété au rang $n+1$ et achève la récurrence.

$2.$ On note $B_n(k) = b_1 b_2 \ldots b_n$ . On a alors $\displaystyle B_n\left(\left\lfloor \frac{k}{2}\right\rfloor\right) = 0 b_1 b_2 \ldots b_{n-1}$ . De ce fait, en écrivant $\Phi_n(k) = a_1 a_2 \ldots a_n$ on a les relations suivantes :v

$\begin{align*} a_1 & = b_1 \\ a_2 & = b_1 \oplus b_2 \\ a_3 & = b_2 \oplus b_3 \\ \cdots & = \cdots \\ a_n & = b_{n-1} \oplus b_n \end{align*}$

On considère la fonction $F_n$ de $\{0,\;1\}^{n}$ dans $\{0,\;2^{n}\}$ définie par $F_n(a_1 a_2 \ldots a_n) = u$ où $u$ a pour représentation binaire $u_1 u_2 \ldots u_n$ avec

$\begin{align*} u_1 & = a_1 \\ u_2 & = a_1 \oplus a_2 \\ u_3 & = a_1 \oplus a_2 \oplus a_3 \\ \vdots & = \vdots \\ u_n & = a_1 \oplus a_2 \oplus \ldots \oplus a_n \end{align*}$

On note que $\displaystyle F_n\left(\Phi_n(k)\right) = k$ . De ce fait $\boxed{\Phi_n \text{ est bijective. }}$

$3.$ Cette relation signifie simplement que tous les bits de la représentation en binaire de $2^{n}+r$ et $2^{n}-r-1$ sont distincts. Pour le prouver, on procède par récurrence forte sur $(n,r)$ . Soit $n \in \mathbb{N}$ et $r \lt 2^{n}$ . On note $\mathcal{H}(n,r) =$ « Tous les bits de la représentation en binaire sur $n+1$ bits de $2^{n}+r$ et $2^{n}-r-1$ sont distincts ».

On vérifie à la main pour $n=0$ et $n=1$ .

Pour tout $n$ , on a :

$B_n(2^n) = 1\underbrace{00\ldots0}_{n \text{ fois }} \text{ et } B_n(2^n-1) = 0\underbrace{11\ldots1}_{n \text{ fois }}$

Ce qui prouve $\mathcal{H}(n,0)$ .

Soit $n \geq 1$ et $2^{n}-1 > r \geq 0$ . On suppose $\mathcal{H}(m,k)$ vrai pour tout $m \lt n$ , $k \lt 2^{m}$ et $\mathcal{H}(n, l)$ vrai pour $0 \leq l \leq r$ . Prouvons $\mathcal{H}(n,r+1)$ .

On note $B_{n+1}(2^{n}+r) = b_1 b_2 \ldots b_{n+1}$ . Par hypothèse de récurrence on a :

$B_{n+1}(2^{n}-r-1) = \overline{b_1} \overline{b_2} \ldots \overline{b_{n+1}}$

où $\bar{b_i}$ est le bit inverse de $b_i$ .

Si $b_{n+1} = 0$ : on a alors $B_{n+1}(2^{n}+r+1) = b_1 b_2 \ldots b_{n}1$ et $B_{n+1}(2^{n}-r-2) = \overline{b_1} \overline{b_2} \ldots \overline{b_{n}}0$ . Donc les représentations binaires de $2^{n}+r+1$ et $2^{n}-r-2$ sur $n+1$ bits sont bien distinctes bit à bit.

Si $b_{n+1}=1$ : on a $r$ impair.

Soit $\displaystyle k = \frac{r+1}{2}$ . On a alors $2(2^{n-1} + k ) = 2^{n} + r + 1$ . On rappel que pour représenter le double d’un entier en binaire, il suffit d’ajouter un $0$ à la fin, ce qui nous donne donc :

$B_{n+1}\left(2^{n}+r+1\right) = B_{n}\left(\frac{2^{n}+r-1}{2}+1\right)0$

De même $\displaystyle B_{n+1}(2^{n}-r-2) = B_{n}\left(2^{n-1}-k-1\right)1$ .

Or, par hypothèse de récurrence, $B_{n}\left(2^{n-1}-k-1\right) = \overline{B_{n}\left(2^{n-1}+k\right)}$ .

Il en résulte que $\displaystyle \boxed{B_{n+1}\left(2^{n}+r+1\right) = \overline{B_{n+1}\left(2^{n}-r-2\right)}}$ . Cela prouve donc ${\mathcal{H}(n,r+1)}$ et achève notre récurrence.

$4.$ Pour ce faire, il nous suffit de montrer que $\Gamma_1 = \Phi_1$ , ce qui est immédiat ; puis que la récurrence suivante est satisfaite pour $n\geq2$ :

$\Phi_{n}(k) = \begin{cases} 0\Phi_{n-1}(k) \text{ si $k \lt 2^{n-1}$ } \\ 1\Phi_{n-1}(2^{n}-k-1) \text{ sinon }\end{cases}$

Si $k \lt 2^{n-1}$ on a bien $\Phi_{n}(k) = 0\Phi_{n-1}(k)$ .

Si $k \geq 2^{n-1}$ on pose $r = k-2^{n-1}$ . On a alors $k = 2^{n-1}+r$ et $2^{n}-k-1 = 2^{n-1}-r-1$ . On écrit $B_{n}(k) = b_1 b_2 \ldots b_n$ . La question précédente nous donne $B_{n}(2^{n-1}-r-1) = \overline{b_1} \overline{b_2} \ldots \overline{b_n}$ . On note de plus que $b_1 = 1$ . Ainsi :

$\Phi_n(k) = 1(b_1 \oplus b_2)\ldots(b_{n-1}\oplus b_n) = 1u$

Avec $u$ un mot binaire sur $n-1$ bits.

Et de plus :

$\begin{align*} \Phi_n(2^{n-1}-r-1) & = 0(\overline{b_1} \oplus \overline{b_2})\ldots(\overline{b_{n-1}}\oplus \overline{b_n}) \\ & = 0(b_1 \oplus b_2)\ldots(b_{n-1}\oplus b_n) \\ \Phi_n(2^{n-1}-r-1) & = 0u \end{align*}$

Donc $\displaystyle \boxed{\Phi_{n-1}\left(2^{n-1}-r-1\right) = u}$ et $\Phi$ satisfait notre relation de récurrence.

On a donc bien prouvé que pour tout $n$ et pour tout $k \lt 2^{n}$ :

$\boxed{\Gamma_n(k) = \Phi_n(k)}$

$5.$ Pour passer de $\Gamma_n(k)$ à $B_n(k)$ on utilise la représentation binaire de la fonction $F$ définie plus haut. Autrement dit, pour un mot $a_1 a_2 \ldots a_n$ codage de Gray d’un nombre, la représentation en binaire sur $n$ bits de ce nombre est $b_1 b_2 \ldots b_n$ avec :

$\begin{align*} b_1 & = a_1 \\ b_2 & = a_1 \oplus a_2 \\ b_3 & = a_1 \oplus a_2 \oplus a_3 \\ \cdots & = \cdots \\ b_n & = a_1 \oplus a_2 \oplus \ldots \oplus a_n \end{align*}$

Pour passer d’un codage binaire $b_1 b_2 \ldots b_n$ à un codage de Gray $a_1 a_2 \ldots a_n$ on pose :

$\begin{align*} a_1 & = b_1 \\ a_2 & = b_1 \oplus b_2 \\ a_3 & = b_2 \oplus b_3 \\ \cdots & = \cdots \\ a_n & = b_{n-1} \oplus b_n \end{align*}$

On note que ces deux opérations peuvent être chacune réalisées avec $n-1$ portes XOR.

$6.$ On pose $|u|_1$ le nombre de $1$ dans le mot $u$ .

Encore une fois, on va procéder par récurrence sur $n$ , la taille de notre représentation. Montrons que pour les représentations de taille $n$ notre méthode effectue bien l’incrémentation sur les entiers représentés avec le codage de Gray.

Le cas $n=1$ se vérifie aisément.

On suppose la propriété vraie au rang $n$ , prouvons qu’elle le reste au rang $n+1$ . Soit $k$ un entier positif inférieur strictement à $2^{n+1}-1$ . Si $k$ est inférieur strictement à $2^{n}-1$ notre méthode fonctionne par hypothèse de récurrence, et on peut calculer le codage de Gray de $k+1$ . Sinon, si $k = 2^{n}-1$ , on a $\Gamma_{n}(k) = 10\ldots0$ . Et par notre définition, $\Gamma_{n+1}(k) = 010\ldots0$ et $\Gamma_{n+1}(k+1) = 110\ldots0$ . Or $\Gamma_{n+1}(k)$ possède un nombre impair de $1$ . Notre méthode fonctionne donc bien.

Enfin, si $k \geq 2^n$ on considère $2^{n+1}-k-1$ qui est inférieur à $2^n$ .

Comme on modifie un bit à chaque incrémentation, on change également la parité du nombre de $1$ dans notre codage. Il en résulte que $|\Gamma_{n+1}(k)|_1$ est de même parité que $k$ . Il en résulte que $|\Gamma_{n+1}(k)|_1$ est de même parité que $|\Gamma_{n+1}(2^{n+1}-k-2)|_1$ .

Si $k$ est pair, $2^{n+1}-k-2$ est également pair et on a montré précédemment que pour passer de $\Gamma_{n+1}(2^{n+1}-k-2)$ à $\Gamma_{n+1}(2^{n+1}-k-1)$ il suffisait de changer le bit le plus à droite. Donc, pour passer de $\Gamma_{n+1}(k+1)$ à $\Gamma_{n+1}(k)$ , il faut changer le bit le plus à droite. Autrement dit, on doit bien changer le dernier bit pour passer de $\Gamma_{n+1}(k)$ à $\Gamma_{n+1}(k+1)$ .

Le cas impair se résout de même.

On a donc prouver le cas $n+1$ , ce qui achève la récurrence.

On a donc bien une méthode simple pour implémenter l’incrémentation avec le codage de Gray.

Théorème de Kirchhoff

Exercice

Correction

Codage de Gray

Exercice

Correction