Exercices corrigés : graphes et matrices (maths expertes)

L'ordre est le nombre de sommets, donc 5. Les degrés se lisent sur la figure : $\deg(A)=2$, $\deg(B)=3$, $\deg(C)=3$, $\deg(D)=3$, $\deg(E)=1$. Les arêtes sont $AB$, $AC$, $BC$, $BD$, $CD$ et $DE$, il y en a 6.

La somme des degrés vaut $2+3+3+3+1=12$, et $2\times 6=12$ : l'égalité est vérifiée. En général, chaque arête relie exactement deux sommets, donc elle est comptée une fois dans le degré de chacune de ses deux extrémités : elle contribue 2 à la somme des degrés. En sommant sur toutes les arêtes, la somme des degrés vaut $2m$ où $m$ est le nombre d'arêtes.

Le graphe n'est pas orienté : si $A$ est relié à $B$, alors $B$ est relié à $A$, donc $m_{ij}=m_{ji}$ pour tout couple $(i\ ;\ j)$, ce qui est exactement la symétrie de $M$. La diagonale est nulle parce qu'aucun sommet n'est relié à lui-même : le graphe ne comporte pas de boucle.

Non. Si les cinq sommets étaient tous de degré 1, la somme des degrés vaudrait $5$, qui est impair. Or cette somme vaut $2m$, un nombre pair. C'est impossible. Plus généralement, dans tout graphe le nombre de sommets de degré impair est pair.

C'est le nombre de chaînes de longueur 2 allant de $A$ à $D$, c'est-à-dire le nombre de sommets intermédiaires reliés à la fois à $A$ et à $D$. Ce sont $A-B-D$ et $A-C-D$, d'où le 2.

Une chaîne de longueur 2 d'un sommet vers lui-même consiste à partir vers un voisin puis à revenir : il y en a exactement $\deg(i)$. Donc le coefficient diagonal vaut $\deg(i)$. On lit bien $2$, $3$, $3$, $3$, $1$ sur la diagonale de $M^{2}$, ce qui correspond aux degrés trouvés à l'exercice 1.

Le seul voisin de $E$ est $D$, donc toute chaîne de longueur 3 de $A$ à $E$ se termine par $D-E$ et commence par une chaîne de longueur 2 de $A$ à $D$. D'après b) il y en a 2 : $A-B-D-E$ et $A-C-D-E$.

Un coefficient diagonal de $M^{3}$ compte les chaînes fermées de longueur 3 issues d'un sommet, c'est-à-dire les triangles passant par ce sommet, chacun étant parcouru dans les deux sens : chaque triangle est donc compté $3\times 2=6$ fois dans la somme des coefficients diagonaux. Le nombre de triangles vaut $12/6=2$. Ce sont $ABC$ et $BCD$.

$0{,}8+0{,}2=1$ et $0{,}4+0{,}6=1$. La ligne $i$ contient les probabilités de tous les états atteignables depuis l'état $i$ à l'étape suivante. Ces événements forment un système complet, donc la somme de leurs probabilités vaut 1.

$\pi_{1}=\pi_{0}M=(0\times 0{,}8+1\times 0{,}4\ ;\ 0\times 0{,}2+1\times 0{,}6)=(0{,}4\ ;\ 0{,}6)$. Puis $\pi_{2}=\pi_{1}M=(0{,}4\times 0{,}8+0{,}6\times 0{,}4\ ;\ 0{,}4\times 0{,}2+0{,}6\times 0{,}6)=(0{,}56\ ;\ 0{,}44)$.

$\pi_{3}=\pi_{2}M=(0{,}56\times 0{,}8+0{,}44\times 0{,}4\ ;\ 0{,}56\times 0{,}2+0{,}44\times 0{,}6)=(0{,}624\ ;\ 0{,}376)$. Au bout de trois soirs, la probabilité qu'il révise est d'environ $62\ \%$ : partie d'un élève qui ne révisait pas, elle augmente à chaque étape.

La relation $\pi_{n+1}=\pi_{n}M$ traduit la formule des probabilités totales à chaque étape. Par récurrence : c'est vrai au rang 0 car $M^{0}$ est la matrice identité ; et si $\pi_{n}=\pi_{0}M^{n}$, alors $\pi_{n+1}=\pi_{n}M=\pi_{0}M^{n}M=\pi_{0}M^{n+1}$.

$\pi M=(0{,}8a+0{,}4b\ ;\ 0{,}2a+0{,}6b)$, donc $\pi M=\pi$ équivaut au système $0{,}8a+0{,}4b=a$ et $0{,}2a+0{,}6b=b$.

La première équation s'écrit $0{,}4b=0{,}2a$, soit $a=2b$. La seconde s'écrit $0{,}2a=0{,}4b$, soit exactement la même relation. Le système se réduit donc à une seule équation, et admet une infinité de solutions proportionnelles entre elles : par exemple $(2\ ;\ 1)$ ou $(4\ ;\ 2)$. La condition $a+b=1$ sélectionne parmi elles l'unique solution qui est une distribution de probabilité.

De $a=2b$ et $a+b=1$ on tire $3b=1$, donc $b=\frac{1}{3}$ et $a=\frac{2}{3}$. La distribution invariante est $\pi=\left(\frac{2}{3}\ ;\ \frac{1}{3}\right)$.

$\pi M=\left(\frac{2}{3}\times 0{,}8+\frac{1}{3}\times 0{,}4\ ;\ \frac{2}{3}\times 0{,}2+\frac{1}{3}\times 0{,}6\right)=\left(\frac{1{,}6+0{,}4}{3}\ ;\ \frac{0{,}4+0{,}6}{3}\right)=\left(\frac{2}{3}\ ;\ \frac{1}{3}\right)=\pi$.

On avait $0{,}4$, puis $0{,}56$, puis $0{,}624$, et $\frac{2}{3}\approx 0{,}667$. La première coordonnée semble croître vers $\frac{2}{3}$ : on conjecture que $\pi_{n}$ converge vers la distribution invariante. L'exercice 5 le démontre, et l'exercice 8 montre que la limite ne dépend pas de $\pi_{0}$.

Pour $n=0$ : $0{,}4^{0}=1$, donc les quatre coefficients valent $\frac{2}{3}+\frac{1}{3}=1$, $\frac{1}{3}-\frac{1}{3}=0$, $\frac{2}{3}-\frac{2}{3}=0$ et $\frac{1}{3}+\frac{2}{3}=1$ : on obtient bien la matrice identité. Pour $n=1$ : $\frac{2}{3}+\frac{0{,}4}{3}=\frac{2{,}4}{3}=0{,}8$, $\frac{1}{3}-\frac{0{,}4}{3}=\frac{0{,}6}{3}=0{,}2$, $\frac{2}{3}-\frac{0{,}8}{3}=\frac{1{,}2}{3}=0{,}4$ et $\frac{1}{3}+\frac{0{,}8}{3}=\frac{1{,}8}{3}=0{,}6$. On retrouve $M$.

Initialisation : le cas $n=0$ est fait. Hérédité : supposons la formule vraie au rang $n$ et posons $t=0{,}4^{\,n}$. Le coefficient d'indice $(1\ ;\ 1)$ de $M^{n}M$ vaut $\left(\frac{2}{3}+\frac{t}{3}\right)\times 0{,}8+\left(\frac{1}{3}-\frac{t}{3}\right)\times 0{,}4=\frac{1{,}6+0{,}8t}{3}+\frac{0{,}4-0{,}4t}{3}=\frac{2+0{,}4t}{3}=\frac{2}{3}+\frac{0{,}4t}{3}$, c'est-à-dire $\frac{2}{3}+\frac{1}{3}\times 0{,}4^{\,n+1}$. Les trois autres coefficients se traitent de la même façon, ce qui donne la formule au rang $n+1$.

Comme $0<0{,}4<1$, la suite $\left(0{,}4^{\,n}\right)$ converge vers 0. Donc $M^{n}$ converge vers $\begin{pmatrix}\tfrac{2}{3}&\tfrac{1}{3}\\\tfrac{2}{3}&\tfrac{1}{3}\end{pmatrix}$

On a $\pi_{n}=\pi_{0}M^{n}$. Si $\pi_{0}=(p\ ;\ 1-p)$, la limite de $\pi_{n}$ vaut $\left(p\times\frac{2}{3}+(1-p)\times\frac{2}{3}\ ;\ p\times\frac{1}{3}+(1-p)\times\frac{1}{3}\right)=\left(\frac{2}{3}\ ;\ \frac{1}{3}\right)$, quelle que soit la valeur de $p$. Autrement dit, la chaîne oublie complètement son état de départ : la limite est toujours la distribution invariante de l'exercice 4.

$0{,}4^{5}=0{,}01024$, donc le coefficient d'indice $(1\ ;\ 1)$ vaut $\frac{2+0{,}01024}{3}\approx 0{,}6701$ et celui d'indice $(2\ ;\ 1)$ vaut $\frac{2-2\times 0{,}01024}{3}\approx 0{,}6598$. Les deux lignes sont déjà égales à $\left(\frac{2}{3}\ ;\ \frac{1}{3}\right)$ à moins de $0{,}007$ près : la convergence est très rapide.

Si l'étudiant révise à la bibliothèque une semaine, alors la semaine suivante il y retourne avec la probabilité $0{,}7$, révise à la maison avec la probabilité $0{,}2$ et au café avec la probabilité $0{,}1$. Tous les coefficients sont positifs et chaque ligne somme à 1 : $0{,}7+0{,}2+0{,}1=1$, $0{,}1+0{,}8+0{,}1=1$, $0{,}2+0{,}2+0{,}6=1$.

$\pi_{1}=\pi_{0}M$ est la première ligne de $M$, soit $(0{,}7\ ;\ 0{,}2\ ;\ 0{,}1)$. Puis $\pi_{2}=\pi_{1}M=(0{,}49+0{,}02+0{,}02\ ;\ 0{,}14+0{,}16+0{,}02\ ;\ 0{,}07+0{,}02+0{,}06)=(0{,}53\ ;\ 0{,}32\ ;\ 0{,}15)$.

$\pi M=\pi$ donne les trois équations $0{,}7a+0{,}1b+0{,}2c=a$, $0{,}2a+0{,}8b+0{,}2c=b$ et $0{,}1a+0{,}1b+0{,}6c=c$, auxquelles s'ajoute $a+b+c=1$.

La troisième équation s'écrit $0{,}1a+0{,}1b=0{,}4c$, soit $0{,}1(a+b)=0{,}4c$. Or $a+b=1-c$, d'où $0{,}1(1-c)=0{,}4c$, puis $0{,}1=0{,}5c$ et $c=0{,}2$. La première équation s'écrit $0{,}1b+0{,}2c=0{,}3a$, soit $0{,}1b+0{,}04=0{,}3a$. Avec $b=0{,}8-a$ il vient $0{,}1(0{,}8-a)+0{,}04=0{,}3a$, soit $0{,}12=0{,}4a$ et $a=0{,}3$, puis $b=0{,}5$.

Vérification sur la deuxième équation : $0{,}2\times 0{,}3+0{,}8\times 0{,}5+0{,}2\times 0{,}2=0{,}06+0{,}4+0{,}04=0{,}5=b$. La distribution invariante est $\pi=(0{,}3\ ;\ 0{,}5\ ;\ 0{,}2)$ : à long terme, l'étudiant révise à la maison une semaine sur deux, à la bibliothèque trois semaines sur dix et au café une sur cinq.

$\deg(A)=2$, $\deg(B)=2$, $\deg(C)=3$, $\deg(D)=1$. Depuis un sommet de degré $d$, chaque voisin est atteint avec la probabilité $\frac{1}{d}$, d'où $W=\begin{pmatrix}0&\tfrac{1}{2}&\tfrac{1}{2}&0\\\tfrac{1}{2}&0&\tfrac{1}{2}&0\\\tfrac{1}{3}&\tfrac{1}{3}&0&\tfrac{1}{3}\\0&0&1&0\end{pmatrix}$

Ligne $A$ : $\frac{1}{2}+\frac{1}{2}=1$. Ligne $B$ : idem. Ligne $C$ : $\frac{1}{3}\times 3=1$. Ligne $D$ : $1$. Toutes les lignes somment bien à 1.

On part de $\pi_{0}=(0\ ;\ 0\ ;\ 0\ ;\ 1)$. Alors $\pi_{1}$ est la ligne $D$ de $W$, soit $(0\ ;\ 0\ ;\ 1\ ;\ 0)$ : depuis $D$, le jeton ne peut aller qu'en $C$. Puis $\pi_{2}$ est la ligne $C$, soit $\left(\frac{1}{3}\ ;\ \frac{1}{3}\ ;\ 0\ ;\ \frac{1}{3}\right)$. Enfin $\pi_{3}=\frac{1}{3}(\text{ligne }A)+\frac{1}{3}(\text{ligne }B)+\frac{1}{3}(\text{ligne }D)=\left(\frac{1}{6}\ ;\ \frac{1}{6}\ ;\ \frac{2}{3}\ ;\ 0\right)$.

Calculons la $j$-ième coordonnée de $\pi W$. Par définition du produit, $(\pi W)_{j}=\sum_{i}\pi_{i}\,w_{ij}$. Or $w_{ij}$ est nul si $i$ et $j$ ne sont pas voisins, et vaut $\frac{1}{\deg(i)}$ s'ils le sont. La somme se réduit donc aux voisins de $j$ : $(\pi W)_{j}=\sum_{i\sim j}\frac{\deg(i)}{2m}\times\frac{1}{\deg(i)}=\sum_{i\sim j}\frac{1}{2m}$. Cette somme comporte autant de termes que $j$ a de voisins, c'est-à-dire $\deg(j)$ termes tous égaux à $\frac{1}{2m}$. D'où $(\pi W)_{j}=\frac{\deg(j)}{2m}=\pi_{j}$. Le point clé est que le facteur $\deg(i)$ apporté par le numérateur de $\pi_{i}$ s'annule exactement avec le $\frac{1}{\deg(i)}$ de la probabilité de transition. Enfin $\sum_{i}\pi_{i}=\frac{1}{2m}\sum_{i}\deg(i)=\frac{2m}{2m}=1$ par le lemme des poignées de main : $\pi$ est bien une distribution de probabilité. Aucune propriété particulière du graphe n'a été utilisée.

Ici $m=4$, donc $2m=8$ et $\pi=\left(\frac{2}{8}\ ;\ \frac{2}{8}\ ;\ \frac{3}{8}\ ;\ \frac{1}{8}\right)=(0{,}25\ ;\ 0{,}25\ ;\ 0{,}375\ ;\ 0{,}125)$. On remarque que les distributions de la question c) n'approchent pas $\pi$ de façon régulière : $\pi_{2}$ donne une probabilité nulle à $C$ alors que $\pi_{3}$ lui en donne $\frac{2}{3}$. La convergence vers l'état stable existe bien, mais elle n'est pas monotone : le sommet $D$, qui n'a qu'un seul voisin, force le jeton à faire des allers-retours qui font osciller la distribution avant qu'elle ne se stabilise.

Comme $a$ et $b$ sont dans $]0\ ;\ 1[$, les quatre coefficients $1-a$, $a$, $b$ et $1-b$ sont strictement positifs. De plus $(1-a)+a=1$ et $b+(1-b)=1$ : chaque ligne somme à 1.

$\pi M=\left(\dfrac{b(1-a)+ab}{a+b}\ ;\ \dfrac{ba+a(1-b)}{a+b}\right)=\left(\dfrac{b-ab+ab}{a+b}\ ;\ \dfrac{ab+a-ab}{a+b}\right)=\left(\dfrac{b}{a+b}\ ;\ \dfrac{a}{a+b}\right)=\pi$. Et la somme des coordonnées vaut $\dfrac{b+a}{a+b}=1$ : c'est bien une distribution de probabilité. Elle est définie car $a+b>0$.

La première coordonnée de $\pi_{n}M$ vaut $x_{n}(1-a)+(1-x_{n})b=x_{n}-ax_{n}+b-bx_{n}=(1-a-b)x_{n}+b$. Or cette coordonnée est $x_{n+1}$, d'où la relation.

$y_{n+1}=x_{n+1}-\dfrac{b}{a+b}=(1-a-b)x_{n}+b-\dfrac{b}{a+b}$. En remplaçant $x_{n}=y_{n}+\dfrac{b}{a+b}$ : $y_{n+1}=(1-a-b)y_{n}+(1-a-b)\dfrac{b}{a+b}+b-\dfrac{b}{a+b}$. Le terme constant vaut $\dfrac{b(1-a-b)+b(a+b)-b}{a+b}=\dfrac{b-ab-b^{2}+ab+b^{2}-b}{a+b}=0$. Donc $y_{n+1}=(1-a-b)y_{n}$ : la suite $(y_{n})$ est géométrique de raison $q=1-a-b$. Comme $0<a<1$ et $0<b<1$, on a $0<a+b<2$, donc $-1<1-a-b<1$, c'est-à-dire $|q|<1$ : $y_{n}=q^{n}y_{0}$ tend vers 0. Ainsi $x_{n}$ tend vers $\dfrac{b}{a+b}$, et cette limite ne fait intervenir ni $x_{0}$ ni $n$ : la chaîne oublie son état initial.