Matrice d’adjacence et chemins

1. a)La ligne d’un sommet contient les arcs qui en partent (ligne = départ, colonne = arrivée) : $$M=\left(\begin{array}{cccc}0& 0& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\\ 1& 0& 1& 0\end{array}\right).$$ (1)
2. b)Les lignes ont pour sommes $1$, $2$, $1$ et $2$ ; la somme totale vaut $1+2+1+2=6$. Le graphe étant orienté, chaque arc est compté une fois : il a $6$ arcs, sans division par $2$. (1)
3. c)Degré sortant de A : somme de la ligne $1$, $0+0+1+0=1$ (l’arc A → C). Degré entrant de A : somme de la colonne $1$, $0+1+0+1=2$ (les arcs B → A et D → A). (1)
4. d)Non : $m_{13}=1$ mais $m_{31}=0$. L’arc A → C existe sans l’arc C → A : les liaisons ont un sens, et l’on ne peut pas lire ce graphe comme un graphe non orienté. La matrice d’un graphe non orienté, elle, est toujours symétrique. (1)

Repère — Dans un graphe orienté, la ligne donne ce qui part, la colonne ce qui arrive, et la somme totale le nombre d’arcs.

1. a)$$M=\left(\begin{array}{ccccc}0& 1& 1& 1& 0\\ 1& 0& 1& 0& 0\\ 1& 1& 0& 1& 0\\ 1& 0& 1& 0& 1\\ 0& 0& 0& 1& 0\end{array}\right);$$ la matrice est symétrique, de diagonale nulle, comme celle de tout graphe non orienté sans boucle. (1)
2. b)$$M^2=\left(\begin{array}{ccccc}3& 1& 2& 1& 1\\ 1& 2& 1& 2& 0\\ 2& 1& 3& 1& 1\\ 1& 2& 1& 3& 0\\ 1& 0& 1& 0& 1\end{array}\right).$$ Par exemple, la ligne $2$ de $M^2$ (celle de Q) est la somme des lignes de P et de R, les deux voisins de Q. (1)
3. c)Le coefficient ligne $2$, colonne $5$ de $M^2$ vaut $0$ : d’après le théorème, aucune chaîne de longueur $2$ ne relie Q à T. En effet, le seul voisin de T est S, et S n’est pas voisin de Q. (1)
4. d)$(M^3{)}_{25}$ = ligne $2$ de $M^2$ × colonne $5$ de $M$ : $(12120)$ et $(00010)$ donnent $2\times 1=2$. Le coefficient $(2;5)$ vaut $0$ dans $M$ et dans $M^2$, et $2$ dans $M^3$ : $d(Q;T)=3$. Les deux chaînes de longueur $3$ sont Q–P–S–T et Q–R–S–T. (1)

Repère — Un seul coefficient de M³ : la ligne de M² multipliée par la colonne de M, sans calculer toute la matrice.

1. a)$$M=\left(\begin{array}{cccccc}0& 1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0\\ 1& 1& 0& 1& 0& 0\\ 0& 0& 1& 0& 1& 1\\ 0& 0& 0& 1& 0& 1\\ 0& 0& 0& 1& 1& 0\end{array}\right).$$ (1)
2. b)Première ligne de $M^2$ : $1$ a pour voisins $2$ et $3$, donc c’est $L_2+L_3=(211100)$, de dernier coefficient nul. Première ligne de $M^3$ : $2L_1+L_2+L_3+L_4$ $=(234111)$, de dernier coefficient $1$. Le coefficient $(1;6)$ vaut $0$ dans $M$ et $M^2$, et $1$ dans $M^3$ : $d(1;6)=3$, par la chaîne 1–3–4–6. (1)
3. c)Les sommets $1$ et $2$ sont à distance $3$ de $5$ et de $6$ ; les sommets $5$ et $6$ sont à distance $3$ de $1$ et de $2$ : leur plus grande distance vaut $3$. Le sommet $3$ est voisin de $1$, $2$, $4$ et à distance $2$ de $5$ et $6$ ; de même, $4$ est à distance au plus $2$ de tous : leur plus grande distance vaut $2$. Le diamètre est le maximum, $3$ (atteint par exemple pour $d(1;6)$ et $d(2;5)$). (1)
4. d)Avec l’arête 1–6, on a bien $d(1;6)=1$, mais $d(2;5)$ reste égal à $3$ : les voisins de $2$ sont $1$ et $3$, et aucun des deux n’est voisin de $5$ (les voisins de $5$ sont $4$ et $6$). Aucune chaîne de longueur $2$ ne relie $2$ à $5$, tandis que 2–1–6–5 a pour longueur $3$. Le diamètre reste $3$ : raccourcir une distance ne diminue pas forcément la plus grande. (1)

Repère — La distance se lit sur la première puissance de M dont le coefficient n’est pas nul ; le diamètre est la plus grande de toutes les distances.

1. a)Dans un graphe non orienté simple, $(M^2{)}_{ii}$ compte les allers-retours $i$–$r$–$i$, un par voisin : c’est le degré de $i$. La diagonale de $M^2$ est donc $(2,3,4,4,3,2)$. Sa somme, $18$, vaut $2m$ : le graphe a $9$ arêtes. (1)
2. b)La somme des coefficients diagonaux de $M^3$ vaut $2+4+6+6+4+2=24$. Chaque triangle est compté $6$ fois (trois sommets de départ, deux sens) : il y a $24÷6=4$ triangles, A–B–C, B–C–D, C–D–E et D–E–F. (1)
3. c)$(M^3{)}_{33}$ compte les chemins fermés de longueur $3$ partant de C : chaque triangle contenant C en donne deux (un par sens). Donc C appartient à $6÷2=3$ triangles : A–B–C, B–C–D et C–D–E. (1)
4. d)On a $$M=\left(\begin{array}{cccccc}0& 1& 1& 0& 0& 0\\ 1& 0& 1& 1& 0& 0\\ 1& 1& 0& 1& 1& 0\\ 0& 1& 1& 0& 1& 1\\ 0& 0& 1& 1& 0& 1\\ 0& 0& 0& 1& 1& 0\end{array}\right).$$ La ligne $1$ de $M^2$ est $L_2+L_3=(211210)$, et celle de $M^3$ vaut $(256333)$. Le coefficient $(1;6)$ vaut $0$ dans $M$ et $M^2$, et $3$ dans $M^3$ : $d(A;F)=3$, et il y a $3$ chaînes de longueur $3$ de A à F : A–B–D–F, A–C–D–F et A–C–E–F. (1)

Repère — Diagonale de M² : les degrés ; diagonale de M³ : deux fois le nombre de triangles de chaque sommet.

1. a)$$M=\left(\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 0\end{array}\right).$$ Par définition du produit, $(M^2{)}_{ij}$ $={\sum }_{r=1}^4{m}_{ir}{m}_{rj}$. Le terme $m_{ir}{m}_{rj}$ vaut $1$ exactement lorsque $i$–$r$ et $r$–$j$ sont des arêtes, c’est-à-dire lorsque $i$–$r$–$j$ est une chaîne de longueur $2$, et $0$ sinon. La somme compte donc les chaînes de longueur $2$ de $i$ à $j$. (1)
2. b)$$M^2=\left(\begin{array}{cccc}1& 0& 1& 0\\ 0& 2& 0& 1\\ 1& 0& 2& 0\\ 0& 1& 0& 1\end{array}\right),M^3=\left(\begin{array}{cccc}0& 2& 0& 1\\ 2& 0& 3& 0\\ 0& 3& 0& 2\\ 1& 0& 2& 0\end{array}\right).$$ Le coefficient $(1;4)$ vaut $0$ dans $M$ et dans $M^2$, puis $1$ dans $M^3$ : $d(1;4)=3$, par la chaîne 1–2–3–4. (1)
3. c)On range les sommets en deux groupes, $\{1,3\}$ et $\{2,4\}$ : chaque arête relie un sommet d’un groupe à un sommet de l’autre. Une chaîne de longueur paire change de groupe un nombre pair de fois, donc revient dans le groupe de départ ; or $1$ et $4$ ne sont pas dans le même groupe. Aucune chaîne de longueur paire ne les relie, ce que confirme $(M^2{)}_{14}=0$. (1)
4. d)$(M^7{)}_{14}$ est la première ligne de $M^5$ multipliée par la quatrième colonne de $M^2$, $(0101)$ : $0\times 0+5\times 1+0\times 0+3\times 1$ $=8$. D’après le théorème, il existe $8$ chaînes de longueur $7$ de $1$ à $4$. (1)

Repère — Avec $M^{p+q}=M^p\times M^q$, un coefficient d’une grande puissance se calcule par un seul produit ligne × colonne.