Exercices corrigés : Graphes et matrices (Terminale)

1. Les deux matrices sont carrées d'ordre $2$, donc $AB$ et $BA$ existent et sont carrées d'ordre $2$. $$AB=\begin{pmatrix} 1\times 0+2\times 2 & 1\times 1+2\times 4 \\ 3\times 0+(-1)\times 2 & 3\times 1+(-1)\times 4 \end{pmatrix}=\begin{pmatrix} 4 & 9 \\ -2 & -1 \end{pmatrix}$$ $$BA=\begin{pmatrix} 0\times 1+1\times 3 & 0\times 2+1\times(-1) \\ 2\times 1+4\times 3 & 2\times 2+4\times(-1) \end{pmatrix}=\begin{pmatrix} 3 & -1 \\ 14 & 0 \end{pmatrix}$$ On constate que $AB\neq BA$ : le produit matriciel n'est pas commutatif.

2. $$A^2=\begin{pmatrix} 1\times 1+2\times 3 & 1\times 2+2\times(-1) \\ 3\times 1+(-1)\times 3 & 3\times 2+(-1)\times(-1) \end{pmatrix}=\begin{pmatrix} 7 & 0 \\ 0 & 7 \end{pmatrix}=7I_2.$$ Donc $k=7$.

3. D'après la question 2 : $$A\times\left(\frac{1}{7}A\right)=\frac{1}{7}A^2=\frac{1}{7}\times 7I_2=I_2.$$ Pour des matrices carrées de même ordre, cette seule égalité suffit : $A$ est inversible et $$A^{-1}=\frac{1}{7}A=\begin{pmatrix} \frac{1}{7} & \frac{2}{7} \\ \frac{3}{7} & -\frac{1}{7} \end{pmatrix}.$$

4. $\det(A)=1\times(-1)-2\times 3=-7\neq 0$, donc $A$ est inversible et $$A^{-1}=\frac{1}{-7}\begin{pmatrix} -1 & -2 \\ -3 & 1 \end{pmatrix}=\frac{1}{7}\begin{pmatrix} 1 & 2 \\ 3 & -1 \end{pmatrix}=\frac{1}{7}A.$$ Les deux méthodes donnent le même résultat.

1. $\det(M)=3\times 4-2\times 5=12-10=2\neq 0$, donc $M$ est inversible et $$M^{-1}=\frac{1}{2}\begin{pmatrix} 4 & -2 \\ -5 & 3 \end{pmatrix}=\begin{pmatrix} 2 & -1 \\ -\frac{5}{2} & \frac{3}{2} \end{pmatrix}.$$ Vérification : $MM^{-1}=\begin{pmatrix} 6-5 & -3+3 \\ 10-10 & -5+6 \end{pmatrix}=I_2$.

2. Le système s'écrit $MX=B$ avec $X=\begin{pmatrix} x \\ y \end{pmatrix}$ et $B=\begin{pmatrix} 1 \\ 3 \end{pmatrix}$. Comme $M$ est inversible, il admet une unique solution : $$X=M^{-1}B=\begin{pmatrix} 2\times 1-1\times 3 \\ -\frac{5}{2}\times 1+\frac{3}{2}\times 3 \end{pmatrix}=\begin{pmatrix} -1 \\ 2 \end{pmatrix}.$$ Vérification : $3\times(-1)+2\times 2=1$ et $5\times(-1)+4\times 2=3$. La solution est $(x;y)=(-1;2)$.

3. $\det(A_m)=m(m+1)-2\times 3=m^2+m-6$. Or $(m+3)(m-2)=m^2-2m+3m-6=m^2+m-6$. Donc $$\det(A_m)=0\iff m=-3\ \text{ou}\ m=2.$$ Par exemple, $A_2=\begin{pmatrix} 2 & 2 \\ 3 & 3 \end{pmatrix}$ a ses colonnes égales. Conclusion : $A_m$ est inversible si et seulement si $m\neq -3$ et $m\neq 2$.

1. $G$ a $5$ sommets : il est d'ordre $5$.

La somme des degrés vaut $2+3+3+3+1=12=2\times 6$, et $G$ a bien $6$ arêtes.

2. La chaîne $A-B-C-D-E$ passe par tous les sommets ; deux sommets quelconques sont donc reliés par une portion de cette chaîne : $G$ est connexe. $G$ n'est pas complet : par exemple $A$ et $E$ ne sont pas adjacents. Un graphe complet d'ordre $5$ possède $\frac{5\times 4}{2}=10$ arêtes ; il faudrait en ajouter $10-6=4$ (ce sont $\{A,D\}$, $\{A,E\}$, $\{B,E\}$, $\{C,E\}$).

3. $$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}$$ Elle est symétrique, de diagonale nulle, et la somme de chaque ligne est le degré du sommet.

4. Coefficient $(1,4)$ de $M^2$ : ligne $1$ de $M$, $(0,1,1,0,0)$, et colonne $4$ de $M$, $(0,1,1,0,1)$ : $$0\times 0+1\times 1+1\times 1+0\times 0+0\times 1=2.$$ Il existe $2$ chaînes de longueur $2$ de $A$ à $D$ : $A-B-D$ et $A-C-D$.

Coefficient $(5,5)$ de $M^2$ : ligne $5$, $(0,0,0,1,0)$, et colonne $5$, $(0,0,0,1,0)$ : la somme vaut $1$. Il existe une seule chaîne fermée de longueur $2$ partant de $E$ : $E-D-E$. On retrouve le degré de $E$.

1. $$A^2=\begin{pmatrix} 4 & 4 \\ 0 & 4 \end{pmatrix},\qquad A^3=A^2A=\begin{pmatrix} 8 & 4+8 \\ 0 & 8 \end{pmatrix}=\begin{pmatrix} 8 & 12 \\ 0 & 8 \end{pmatrix}.$$

2. On a $1=1\times 2^0$, $4=2\times 2^1$, $12=3\times 2^2$. On conjecture, pour $n\geqslant 1$ : $$A^n=\begin{pmatrix} 2^n & n2^{n-1} \\ 0 & 2^n \end{pmatrix}.$$ Initialisation : pour $n=1$, la formule donne $\begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}=A$.

Hérédité : supposons la formule vraie au rang $n\geqslant 1$. Alors $$A^{n+1}=A^nA=\begin{pmatrix} 2^n & n2^{n-1} \\ 0 & 2^n \end{pmatrix}\begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}=\begin{pmatrix} 2^{n+1} & 2^n+n2^n \\ 0 & 2^{n+1} \end{pmatrix}=\begin{pmatrix} 2^{n+1} & (n+1)2^n \\ 0 & 2^{n+1} \end{pmatrix}.$$ C'est la formule au rang $n+1$.

Conclusion : la formule est vraie pour tout $n\geqslant 1$. Pour $n=0$, elle donne $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}=I_2=A^0$ : elle est vraie aussi.

3. Avec $U_n=\begin{pmatrix} u_n \\ v_n \end{pmatrix}$, le système s'écrit $U_{n+1}=AU_n$, donc $U_n=A^nU_0$ pour tout $n$. Comme $U_0=\begin{pmatrix} 0 \\ 1 \end{pmatrix}$, $U_n$ est la deuxième colonne de $A^n$ : $$u_n=n2^{n-1},\qquad v_n=2^n.$$ Contrôle : $u_1=2\times 0+1=1$ et $u_2=2\times 1+2=4$ ; la formule donne $1\times 2^0=1$ et $2\times 2^1=4$.

1. Les données se traduisent par $$\begin{cases} x+2y=5 \\ y+z=4 \\ x+z=3 \end{cases}$$ c'est-à-dire $AX=B$ avec $X=\begin{pmatrix} x \\ y \\ z \end{pmatrix}$ et $B=\begin{pmatrix} 5 \\ 4 \\ 3 \end{pmatrix}$.

2. On combine chaque ligne de $A$ avec chaque colonne de $N$ :

• ligne $1$, $(1,2,0)$ : $1+2+0=3$ ; $-2+2+0=0$ ; $2-2+0=0$ ;
• ligne $2$, $(0,1,1)$ : $0+1-1=0$ ; $0+1+2=3$ ; $0-1+1=0$ ;
• ligne $3$, $(1,0,1)$ : $1+0-1=0$ ; $-2+0+2=0$ ; $2+0+1=3$.

Donc $AN=3I_3$, soit $A\times\dfrac{1}{3}N=I_3$. Pour des matrices carrées, cela suffit : $A$ est inversible et $$A^{-1}=\frac{1}{3}N=\frac{1}{3}\begin{pmatrix} 1 & -2 & 2 \\ 1 & 1 & -1 \\ -1 & 2 & 1 \end{pmatrix}.$$

3. Comme $A$ est inversible, le système a une unique solution : $$X=A^{-1}B=\frac{1}{3}\begin{pmatrix} 5-8+6 \\ 5+4-3 \\ -5+8+3 \end{pmatrix}=\frac{1}{3}\begin{pmatrix} 3 \\ 6 \\ 6 \end{pmatrix}=\begin{pmatrix} 1 \\ 2 \\ 2 \end{pmatrix}.$$ Vérification : $1+2\times 2=5$, $2+2=4$, $1+2=3$. Un stylo coûte $1$ euro, un cahier $2$ euros, un classeur $2$ euros.

1. $$A=\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$$

2. Coefficient diagonal de $A^2$ : par exemple $(1,1)$ vaut $0+1+1=2$. Coefficient hors diagonale : par exemple $(1,2)$ vaut $0\times 1+1\times 0+1\times 1=1$. Par symétrie des rôles : $$A^2=\begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{pmatrix}=\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}+\begin{pmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{pmatrix}=A+2I_3.$$

3. De $A^2=A+2I_3$ on tire $A^2-A=2I_3$, soit $A(A-I_3)=2I_3$, donc $A\times\dfrac{1}{2}(A-I_3)=I_3$. Ainsi $A$ est inversible et $$A^{-1}=\frac{1}{2}(A-I_3)=\frac{1}{2}\begin{pmatrix} -1 & 1 & 1 \\ 1 & -1 & 1 \\ 1 & 1 & -1 \end{pmatrix}.$$

4. $A^3=AA^2=A(A+2I_3)=A^2+2A=A+2I_3+2A=3A+2I_3$, donc $$A^3=\begin{pmatrix} 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \end{pmatrix}.$$

5. Le coefficient $(1,2)$ de $A^3$ vaut $3$ : il y a $3$ chaînes de longueur $3$ de $1$ à $2$ : $$1-2-1-2,\qquad 1-2-3-2,\qquad 1-3-1-2.$$ Le coefficient $(1,1)$ de $A^3$ vaut $2$ : il y a $2$ chaînes fermées de longueur $3$ partant de $1$, qui parcourent le triangle dans un sens ou dans l'autre : $1-2-3-1$ et $1-3-2-1$.

1. $$P=\begin{pmatrix} 0{,}9 & 0{,}1 \\ 0{,}3 & 0{,}7 \end{pmatrix}$$

2. $Q+R=\dfrac{1}{4}\begin{pmatrix} 4 & 0 \\ 0 & 4 \end{pmatrix}=I_2$ et $Q+0{,}6R=\dfrac{1}{4}\begin{pmatrix} 3{,}6 & 0{,}4 \\ 1{,}2 & 2{,}8 \end{pmatrix}=\begin{pmatrix} 0{,}9 & 0{,}1 \\ 0{,}3 & 0{,}7 \end{pmatrix}=P$. $$Q^2=\frac{1}{16}\begin{pmatrix} 9+3 & 3+1 \\ 9+3 & 3+1 \end{pmatrix}=\frac{1}{4}\begin{pmatrix} 3 & 1 \\ 3 & 1 \end{pmatrix}=Q,\qquad R^2=\frac{1}{16}\begin{pmatrix} 1+3 & -1-3 \\ -3-9 & 3+9 \end{pmatrix}=R,$$ $$QR=\frac{1}{16}\begin{pmatrix} 3-3 & -3+3 \\ 3-3 & -3+3 \end{pmatrix}=0,\qquad RQ=\frac{1}{16}\begin{pmatrix} 3-3 & 1-1 \\ -9+9 & -3+3 \end{pmatrix}=0.$$

3. Initialisation : $Q+0{,}6^0R=Q+R=I_2=P^0$. Hérédité : supposons $P^n=Q+0{,}6^nR$. Alors $$P^{n+1}=P^nP=(Q+0{,}6^nR)(Q+0{,}6R)=Q^2+0{,}6\,QR+0{,}6^n\,RQ+0{,}6^{n+1}R^2=Q+0{,}6^{n+1}R.$$ Conclusion : pour tout $n\in\mathbb{N}$, $P^n=Q+0{,}6^nR$.

4. Comme $-1<0{,}6<1$, $0{,}6^n\to 0$, donc chaque coefficient de $P^n$ tend vers le coefficient correspondant de $Q$ : $P^n\to Q$. Soit $\pi_0=\begin{pmatrix} \alpha & 1-\alpha \end{pmatrix}$. Alors $\pi_n=\pi_0P^n=\pi_0Q+0{,}6^n\,\pi_0R$, et $\pi_0Q=\begin{pmatrix} \frac{3}{4}(\alpha+1-\alpha) & \frac{1}{4}(\alpha+1-\alpha) \end{pmatrix}=\begin{pmatrix} \frac{3}{4} & \frac{1}{4} \end{pmatrix}$. Donc $(\pi_n)$ converge vers $\pi=\begin{pmatrix} \frac{3}{4} & \frac{1}{4} \end{pmatrix}$. Vérification : $\pi P=\begin{pmatrix} 0{,}675+0{,}075 & 0{,}075+0{,}175 \end{pmatrix}=\begin{pmatrix} 0{,}75 & 0{,}25 \end{pmatrix}=\pi$. À long terme, la machine fonctionne trois jours sur quatre.

5. $q_n$ est la probabilité d'être dans l'état $1$ au jour $n$ sachant qu'on part de l'état $2$ : c'est le coefficient $(2,1)$ de $P^n$, soit $$q_n=\frac{3}{4}-\frac{3}{4}\times 0{,}6^n=\frac{3}{4}\left(1-0{,}6^n\right).$$ Contrôle : $q_1=0{,}75\times 0{,}4=0{,}3$. $$q_n\geqslant 0{,}7\iff 1-0{,}6^n\geqslant\frac{14}{15}\iff 0{,}6^n\leqslant\frac{1}{15}\iff n\ln(0{,}6)\leqslant -\ln(15)\iff n\geqslant\frac{\ln(15)}{-\ln(0{,}6)},$$ le sens change car $\ln(0{,}6)<0$. Or $\dfrac{\ln(15)}{-\ln(0{,}6)}\approx 5{,}30$. Le plus petit entier est $n=6$. Contrôle : $q_5\approx 0{,}692$ et $q_6\approx 0{,}715$.

Partie A

1. Degrés : $A$ : $2$, $B$ : $3$, $C$ : $3$, $D$ : $2$. La somme vaut $10$, donc $G$ a $5$ arêtes, ce qui correspond aux $5$ portes. $G$ n'est pas complet : $A$ et $D$ ne sont pas adjacents. Il est connexe : la chaîne $A-B-C-D$ passe par tous les sommets.

2. $$M=\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix},\qquad M^2=\begin{pmatrix} 2 & 1 & 1 & 2 \\ 1 & 3 & 2 & 1 \\ 1 & 2 & 3 & 1 \\ 2 & 1 & 1 & 2 \end{pmatrix}.$$ Par exemple, le coefficient $(1,4)$ vaut $0\times 0+1\times 1+1\times 1+0\times 0=2$ (chaînes $A-B-D$ et $A-C-D$) et le coefficient $(2,3)$ vaut $1\times 1+0\times 1+1\times 0+1\times 1=2$ (chaînes $B-A-C$ et $B-D-C$). La diagonale donne les degrés.

3. Le coefficient $(1,4)$ de $M^3$ vaut $2$ : il existe $2$ chaînes de longueur $3$ de $A$ à $D$, à savoir $A-B-C-D$ et $A-C-B-D$. Le coefficient $(2,2)$ vaut $4$ : il existe $4$ chaînes fermées de longueur $3$ partant de $B$ : $B-A-C-B$, $B-C-A-B$, $B-C-D-B$, $B-D-C-B$ (les deux triangles $ABC$ et $BCD$, parcourus dans les deux sens).

Partie B

1. Depuis $A$, les portes mènent en $B$ et en $C$ ; depuis $D$ aussi : depuis l'état $1$, on passe dans l'état $2$ avec probabilité $1$. Depuis $B$, les trois portes mènent en $A$, $C$, $D$ : on va dans l'état $1$ (pièces $A$ ou $D$) avec probabilité $\frac{2}{3}$ et on reste dans l'état $2$ (pièce $C$) avec probabilité $\frac{1}{3}$ ; depuis $C$, les voisins $A$, $B$, $D$ donnent les mêmes probabilités. D'où $$P=\begin{pmatrix} 0 & 1 \\ \frac{2}{3} & \frac{1}{3} \end{pmatrix}.$$

2. Avec $\pi_n=\begin{pmatrix} p_n & 1-p_n \end{pmatrix}$ et $\pi_{n+1}=\pi_nP$, le premier coefficient donne $$p_{n+1}=0\times p_n+\frac{2}{3}(1-p_n)=-\frac{2}{3}p_n+\frac{2}{3}.$$

3. Le réel $\ell$ tel que $\ell=-\frac{2}{3}\ell+\frac{2}{3}$ vérifie $\frac{5}{3}\ell=\frac{2}{3}$, soit $\ell=\frac{2}{5}$. Par soustraction, $p_{n+1}-\frac{2}{5}=-\frac{2}{3}\left(p_n-\frac{2}{5}\right)$ : la suite $\left(p_n-\frac{2}{5}\right)$ est géométrique de raison $-\frac{2}{3}$ et de premier terme $p_0-\frac{2}{5}=1-\frac{2}{5}=\frac{3}{5}$, car le robot part de $A$. Donc $$p_n=\frac{2}{5}+\frac{3}{5}\left(-\frac{2}{3}\right)^n.$$ $p_3=\frac{2}{5}+\frac{3}{5}\times\left(-\frac{8}{27}\right)=\frac{18}{45}-\frac{8}{45}=\frac{2}{9}$. Contrôle avec la récurrence : $p_1=0$, $p_2=\frac{2}{3}$, $p_3=-\frac{4}{9}+\frac{6}{9}=\frac{2}{9}$.

4. Comme $-1<-\frac{2}{3}<1$, $\left(-\frac{2}{3}\right)^n\to 0$, donc $p_n\to\frac{2}{5}$ et $1-p_n\to\frac{3}{5}$. $\pi P=\begin{pmatrix} \frac{2}{5}\times 0+\frac{3}{5}\times\frac{2}{3} & \frac{2}{5}\times 1+\frac{3}{5}\times\frac{1}{3} \end{pmatrix}=\begin{pmatrix} \frac{2}{5} & \frac{3}{5} \end{pmatrix}=\pi$ : $\pi$ est invariante.

5. La somme des degrés de $A$ et $D$ vaut $4$ et la somme de tous les degrés $10$ : le quotient vaut $\frac{4}{10}=\frac{2}{5}$. À long terme, le robot se trouve dans une pièce $A$ ou $D$ avec une probabilité proportionnelle au nombre de portes de ces pièces.