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

a) 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.

b) 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.

c) $M=\begin{pmatrix}0&1&1&0&0\\1&0&1&1&0\\1&1&0&1&0\\0&1&1&0&1\\0&0&0&1&0\end{pmatrix}$

d) 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.

e) 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.

a) $M^{2}=\begin{pmatrix}2&1&1&2&0\\1&3&2&1&1\\1&2&3&1&1\\2&1&1&3&0\\0&1&1&0&1\end{pmatrix}$

b) 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.

c) 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.

d) 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$.

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$.

a) $M=\begin{pmatrix}0{,}8&0{,}2\\0{,}4&0{,}6\end{pmatrix}$

b) $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.

c) $\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)$.

d) $\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.

e) 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}$.

a) $\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$.

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é.

c) 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)$.

d) $\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$.

e) 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}$.

a) 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$.

b) 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$.

c) 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}$

d) 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.

e) $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{,}004$ près : la convergence est très rapide.

a) 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$.

b) $\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)$.

c) $\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$.

d) 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$.

e) 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.

a) $\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}$

b) 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.

c) 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)$.

d) 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.

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.

a) 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.

b) $\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$.

c) 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.

d) $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.

e) Avec $a=0{,}2$ et $b=0{,}4$ on retrouve $M=\begin{pmatrix}0{,}8&0{,}2\\0{,}4&0{,}6\end{pmatrix}$ La limite vaut $\dfrac{0{,}4}{0{,}6}=\dfrac{2}{3}$, ce qui est bien la distribution invariante de l'exercice 4. La raison vaut $1-0{,}2-0{,}4=0{,}4$, ce qui explique le $0{,}4^{\,n}$ de la formule admise à l'exercice 5.

a) Faux. La convergence exige une hypothèse supplémentaire, en pratique qu'une puissance de $M$ ait tous ses coefficients strictement positifs. Contre-exemple : $M=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ est bien une matrice de transition, mais $M^{2}$ est la matrice identité, donc $M^{n}$ vaut $M$ si $n$ est impair et l'identité si $n$ est pair. La suite oscille et ne converge pas. La chaîne correspondante change d'état à coup sûr à chaque étape : elle est périodique.

b) Faux. Les puissances comptent les chaînes, et une chaîne a parfaitement le droit de repasser par un sommet déjà visité. Contre-exemple avec le graphe de l'exercice 1 : le coefficient d'indice $(A\ ;\ B)$ de $M^{3}$ vaut 5, alors que les chemins sans répétition de $A$ à $B$ de longueur 3 n'existent pas en si grand nombre. Parmi les 5 chaînes comptées figurent $A-B-A-B$ et $A-C-A-B$, qui repassent par un sommet déjà visité. Compter les chemins sans répétition est un problème beaucoup plus difficile, qu'aucune puissance de matrice ne résout.

c) Faux. L'unicité demande, elle aussi, une hypothèse : que le graphe de la chaîne soit connexe, autrement dit qu'on puisse aller de n'importe quel état à n'importe quel autre. Contre-exemple : $M=\begin{pmatrix}1&0\\0&1\end{pmatrix}$, où chaque état est absorbant. Toute distribution $(p\ ;\ 1-p)$ vérifie $\pi M=\pi$ : il y en a une infinité. Concrètement, la chaîne ne bouge jamais, donc elle reste sur place quelle que soit la répartition de départ.

d) Faux. L'égalité $\pi M=\pi$ ne suffit pas : il faut encore que $\pi$ soit une distribution de probabilité, c'est-à-dire à coordonnées positives et de somme 1. Contre-exemple avec la matrice de l'exercice 3 : $\pi=(2\ ;\ 1)$ vérifie bien $\pi M=(2\times 0{,}8+1\times 0{,}4\ ;\ 2\times 0{,}2+1\times 0{,}6)=(2\ ;\ 1)$, mais sa somme vaut 3. C'est exactement pour cette raison qu'on ajoute systématiquement l'équation $a+b=1$ au système, comme à l'exercice 4.

a) Chaque ligne somme à 1 : $0{,}6+0{,}3+0{,}1=1$, $0{,}5+0{,}4+0{,}1=1$ et $0{,}25+0{,}15+0{,}6=1$, et tous les coefficients sont positifs. Comme $\pi_{0}=(1\ ;\ 0\ ;\ 0)$, $\pi_{1}$ est la première ligne : $(0{,}6\ ;\ 0{,}3\ ;\ 0{,}1)$. Puis $\pi_{2}=(0{,}36+0{,}15+0{,}025\ ;\ 0{,}18+0{,}12+0{,}015\ ;\ 0{,}06+0{,}03+0{,}06)=(0{,}535\ ;\ 0{,}315\ ;\ 0{,}15)$ et $\pi_{3}=(0{,}516\ ;\ 0{,}309\ ;\ 0{,}175)$.

b) $\pi M$ a pour première coordonnée $0{,}5\times 0{,}6+0{,}3\times 0{,}5+0{,}2\times 0{,}25=0{,}3+0{,}15+0{,}05=0{,}5$, pour deuxième $0{,}5\times 0{,}3+0{,}3\times 0{,}4+0{,}2\times 0{,}15=0{,}15+0{,}12+0{,}03=0{,}3$ et pour troisième $0{,}5\times 0{,}1+0{,}3\times 0{,}1+0{,}2\times 0{,}6=0{,}05+0{,}03+0{,}12=0{,}2$. Donc $\pi M=\pi$, et $0{,}5+0{,}3+0{,}2=1$ : c'est bien la distribution invariante.

c) $\pi_{1}-\pi=(0{,}1\ ;\ 0\ ;\ -0{,}1)$ donc $e_{1}=0{,}1$. $\pi_{2}-\pi=(0{,}035\ ;\ 0{,}015\ ;\ -0{,}05)$ donc $e_{2}=0{,}05$. $\pi_{3}-\pi=(0{,}016\ ;\ 0{,}009\ ;\ -0{,}025)$ donc $e_{3}=0{,}025$. L'écart est divisé par 2 à chaque semaine : on conjecture $e_{n}=0{,}1\times 0{,}5^{\,n-1}$.

d) Il faut $0{,}1\times 0{,}5^{\,n-1}<0{,}001$, soit $0{,}5^{\,n-1}<0{,}01$. En passant au logarithme népérien, qui est strictement croissant : $(n-1)\ln(0{,}5)<\ln(0{,}01)$. Comme $\ln(0{,}5)$ est négatif, l'inégalité change de sens en divisant : $n-1>\dfrac{\ln(0{,}01)}{\ln(0{,}5)}=\dfrac{\ln(100)}{\ln(2)}\approx 6{,}64$. Donc $n-1\geq 7$, soit $n=8$. À partir de la huitième semaine, la distribution est à moins de un millième de l'état stable.

e) Pour le métro, $\dfrac{1}{0{,}5}=2$ semaines. Pour le vélo, $\dfrac{1}{0{,}3}=\dfrac{10}{3}\approx 3{,}3$ semaines. Pour la voiture, $\dfrac{1}{0{,}2}=5$ semaines. Plus un état est probable à long terme, plus on y revient souvent, et le temps moyen de retour est exactement l'inverse de sa probabilité stationnaire. L'étudiant prend donc le métro en moyenne une semaine sur deux, et la voiture une semaine sur cinq.