Matrice d’adjacence et chemins

Le graphe orienté $G_1$ a pour sommets $1$, $2$, $3$, $4$ (dans cet ordre) et pour arcs $1\to 2$, $2\to 3$, $3\to 1$, $3\to 4$ et $4\to 2$. On note $M$ sa matrice d’adjacence.

1. Écrire $M$. Coefficient $m_{34}$ :
   On remplit la ligne $i$ avec les arcs qui partent de $i$ : $M$ $=\left(\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\end{array}\right).$ $m_{34}=1$ : l’arc $3\to 4$ existe.
2. Coefficient $m_{43}$ :
   $m_{43}$ compte les arcs qui vont de $4$ vers $3$ : il n’y en a pas (l’arc existant va de $3$ vers $4$), donc $m_{43}=0$.
3. Justifier que $M$ n’est pas symétrique. Nombre de paires de sommets reliées par un arc dans chacun des deux sens :
   Rédaction attendue. Une matrice symétrique vérifierait $m_{ij}=m_{ji}$ pour tous $i$ et $j$. Or $m_{34}=1$ et $m_{43}=0$ : $M$ n’est pas symétrique. Pour chacun des cinq arcs, l’arc de sens contraire est absent ($2\to 1$, $3\to 2$, $1\to 3$, $4\to 3$, $2\to 4$ n’existent pas) : aucune paire de sommets n’est reliée dans les deux sens, et pour chaque coefficient égal à $1$, le coefficient symétrique vaut $0$.

Un graphe non orienté $G_2$ a pour sommets A, B, C, D, E (dans cet ordre) et pour matrice d’adjacence $M$ $=\left(\begin{array}{ccccc}0& 1& 1& 0& 0\\ 1& 0& 1& 1& 0\\ 1& 1& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 0\end{array}\right).$

1. Nombre d’arêtes de $G_2$ :
   La matrice étant symétrique, on lit les coefficients égaux à $1$ au-dessus de la diagonale : A–B, A–C, B–C, B–D, C–E et D–E, soit $6$ arêtes.
2. Le sommet E est relié à C et à
   La ligne $5$ (celle de E) est $(00110)$ : E est relié au $3$e sommet, C, et au $4$e, D.
3. Justifier que $G_2$ n’est pas complet. Nombre d’arêtes qu’il faudrait ajouter pour obtenir $K_5$ :
   Rédaction attendue. Dans la matrice d’un graphe complet, tous les coefficients hors de la diagonale valent $1$. Ici $m_{14}=0$ : A et D ne sont pas reliés, donc $G_2$ n’est pas complet. $K_5$ a ${\displaystyle \frac{5\times 4}{2}}=10$ arêtes ; il en manque $10-6=4$ (A–D, A–E, B–E et C–D).
4. Justifier que $G_2$ est connexe en lisant sur $M$ une chaîne qui passe une fois par chaque sommet. Longueur de cette chaîne :
   Rédaction attendue. Les coefficients $m_{12}$, $m_{24}$, $m_{45}$ et $m_{53}$ valent $1$ : A–B–D–E–C est une chaîne qui passe par les cinq sommets. Deux sommets quelconques sont reliés par une portion de cette chaîne : $G_2$ est connexe. Elle emprunte $4$ arêtes, donc sa longueur est $4$.

Un graphe orienté a pour sommets $1$, $2$, $3$, $4$, $5$, $6$ (dans cet ordre) ; il y a un arc $i\to j$ lorsque $j-i$ vaut $1$ ou $2$. On note $M$ sa matrice d’adjacence.

1. Écrire $M$. Coefficient $m_{24}$ :
   $M$ $=\left(\begin{array}{cccccc}0& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 0& 0\\ 0& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 1\\ 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0& 0\end{array}\right).$ $4-2=2$, donc l’arc $2\to 4$ existe : $m_{24}=1$.
2. Coefficient $m_{42}$ :
   $2-4=-2$, qui ne vaut ni $1$ ni $2$ : l’arc $4\to 2$ n’existe pas, $m_{42}=0$.
3. Justifier que tous les coefficients situés sur la diagonale ou au-dessous sont nuls. Numéro de la ligne de $M$ entièrement nulle :
   Rédaction attendue. Un coefficient $m_{ij}$ situé sur la diagonale ou au-dessous vérifie $j⩽i$, donc $j-i⩽0$ : $j-i$ ne vaut ni $1$ ni $2$, et $m_{ij}=0$. Aucun arc ne part de $6$, car $7$ et $8$ ne sont pas des sommets : la ligne $6$ est nulle.
4. Démontrer que le numéro du sommet augmente strictement le long de tout chemin de ce graphe. En déduire le nombre de circuits du graphe :
   Rédaction attendue. Le long d’un arc $i\to j$, on a $j-i⩾1$ : le numéro du sommet augmente strictement. Le long d’un chemin, il augmente donc strictement à chaque pas, et le sommet d’arrivée a un numéro strictement plus grand que celui du départ. Un chemin de longueur non nulle ne revient jamais à son point de départ : le graphe n’a aucun circuit.

Un graphe non orienté a pour sommets A, B, C, D et pour arêtes A–B, B–C, B–D et C–D. On note $N$ sa matrice d’adjacence quand les sommets sont rangés dans l’ordre D, A, C, B.

1. Coefficient ligne $2$, colonne $4$ de $N$ :
   Dans l’ordre D, A, C, B, la ligne $2$ est celle de A et la colonne $4$ celle de B. L’arête A–B existe : le coefficient vaut $1$. En entier, $N$ $=\left(\begin{array}{cccc}0& 0& 1& 1\\ 0& 0& 0& 1\\ 1& 0& 0& 1\\ 1& 1& 1& 0\end{array}\right).$
2. Coefficient ligne $1$, colonne $2$ de $N$ :
   Ligne de D, colonne de A : D et A ne sont pas reliés, le coefficient vaut $0$.
3. On donne la matrice $Q$ $=\left(\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 1\\ 0& 1& 0& 0\\ 1& 1& 0& 0\end{array}\right)$. Démontrer que $Q$ est la matrice de ce même graphe pour un autre ordre des sommets. Dans cet ordre, le sommet numéro $3$ est
   Rédaction attendue. Changer l’ordre des sommets permute les lignes : la liste des sommes des lignes (les degrés) ne change pas. Les degrés du graphe sont $d(A)=1$, $d(B)=3$, $d(C)=2$, $d(D)=2$ ; les lignes de $Q$ ont pour sommes $2$, $3$, $1$, $2$. La ligne $3$, de somme $1$, ne peut être que celle de A, et la ligne $2$, de somme $3$, celle de B. Essayons l’ordre C, B, A, D : la ligne de C doit contenir des $1$ dans les colonnes de B et de D, soit $(0101)$ ; celle de B, $(1011)$ ; celle de A, $(0100)$ ; celle de D, $(1100)$. On retrouve exactement $Q$ : c’est la matrice du graphe dans l’ordre C, B, A, D, et le sommet numéro $3$ est A. (L’ordre D, B, A, C convient aussi, car C et D jouent le même rôle ; dans les deux cas, le sommet numéro $3$ est A.)

Un graphe non orienté a pour sommets A, B, C, D, E, F (dans cet ordre) et pour matrice d’adjacence $M$ $=\left(\begin{array}{cccccc}0& 1& 1& 0& 0& 1\\ 1& 0& 1& 1& 0& 0\\ 1& 1& 0& 1& 1& 0\\ 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 0& 0& 1\\ 1& 0& 0& 1& 1& 0\end{array}\right).$

1. Degré de C :
   Ligne $3$ : $1+1+0+1+1+0=4$. C a quatre voisins, A, B, D et E.
2. Somme de tous les coefficients de $M$ :
   Les sommes des lignes sont les degrés : $3$, $3$, $4$, $3$, $2$, $3$. Leur somme vaut $3+3+4+3+2+3=18$.
3. Nombre d’arêtes :
   Le graphe n’est pas orienté : la somme totale vaut $2m$, donc $m=18÷2=9$.
4. Seul sommet de degré $2$ :
   La ligne $5$, celle de E, est $(001001)$ : $d(E)=2$, et c’est la seule ligne de somme $2$.

Un graphe orienté a pour sommets $1$, $2$, $3$, $4$, $5$ (dans cet ordre) et pour matrice d’adjacence $M$ $=\left(\begin{array}{ccccc}0& 1& 0& 0& 1\\ 0& 0& 1& 0& 0\\ 1& 0& 0& 1& 0\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 0& 0\end{array}\right).$

1. $d^{+}(4)=$
   Ligne $4$ : $(01001)$, de somme $2$. Deux arcs partent de $4$ : $4\to 2$ et $4\to 5$.
2. $d^{-}(3)=$
   Colonne $3$ : $(01001)$, de somme $2$. Deux arcs arrivent en $3$ : $2\to 3$ et $5\to 3$.
3. Nombre d’arcs :
   Somme de tous les coefficients : les lignes donnent $2+1+2+2+1=8$. Le graphe est orienté : il a $8$ arcs, sans division par $2$.
4. Nombre de sommets dont le degré entrant vaut $1$ :
   Sommes des colonnes : $d^{-}(1)=1$, $d^{-}(2)=2$, $d^{-}(3)=2$, $d^{-}(4)=1$, $d^{-}(5)=2$. Deux sommets, $1$ et $4$, ont un degré entrant égal à $1$. Contrôle : $1+2+2+1+2=8$, le nombre d’arcs.

Graphes complets et parité.

1. Somme de tous les coefficients de la matrice d’adjacence de $K_{11}$ :
   Chacune des $11$ lignes contient $10$ coefficients égaux à $1$ (tous sauf le diagonal) : la somme vaut $11\times 10=110$.
2. Nombre d’arêtes de $K_{11}$ :
   $K_{11}$ n’est pas orienté : $110÷2=55$, ce qui est bien ${\displaystyle \frac{11\times 10}{2}}$.
3. Démontrer que la somme de tous les coefficients de la matrice d’adjacence d’un graphe non orienté sans boucle est paire. Un graphe non orienté d’ordre $7$ dont tous les sommets seraient de degré $3$ aurait une matrice de somme totale
   Rédaction attendue. La diagonale est nulle (pas de boucle). Hors de la diagonale, les coefficients vont par paires : $m_{ij}$ et $m_{ji}$, avec $i<j$, sont égaux car la matrice est symétrique. La somme totale vaut donc $2{\sum }_{i<j}{m}_{ij}$ : elle est paire. Pour le graphe proposé, chaque ligne aurait pour somme $3$, donc la somme totale vaudrait $7\times 3=21$, impaire : un tel graphe n’existe pas.

Un graphe orienté de sommets $1$, $2$, $3$, $4$ a pour matrice d’adjacence $M$ $=\left(\begin{array}{cccc}0& 1& a& 0\\ b& 0& 1& 1\\ 0& c& 0& 1\\ 1& 0& d& 0\end{array}\right),$ où $a$, $b$, $c$, $d$ valent $0$ ou $1$. On sait qu’en chaque sommet, le degré entrant est égal au degré sortant.

1. Démontrer que $a$, $b$, $c$ et $d$ sont déterminés de façon unique. $a=$ ; $b=$ ; $c=$ ; $d=$
   Rédaction attendue. Degrés sortants (sommes des lignes) : $d^{+}(1)=1+a$, $d^{+}(2)=b+2$, $d^{+}(3)=c+1$, $d^{+}(4)=1+d$. Degrés entrants (sommes des colonnes) : $d^{-}(1)=b+1$, $d^{-}(2)=1+c$, $d^{-}(3)=a+1+d$, $d^{-}(4)=2$. Au sommet $4$ : $1+d=2$, donc $d=1$. Au sommet $2$ : $b+2=1+c$, donc $c=b+1$ ; comme $c⩽1$, $b=0$ et $c=1$. Au sommet $1$ : $1+a=b+1$, donc $a=b=0$. Contrôle au sommet $3$ : $c+1=2$ et $a+1+d=2$. La seule solution est $a=0$, $b=0$, $c=1$, $d=1$.
2. Nombre d’arcs du graphe :
   Avec ces valeurs, les sommes des lignes valent $1$, $2$, $2$ et $2$ : le graphe a $1+2+2+2=7$ arcs.

Le graphe non orienté $G_3$ a pour sommets A, B, C, D (dans cet ordre) et pour arêtes A–B, B–C, C–D et D–A. On note $M$ sa matrice d’adjacence.

1. Écrire $M$, puis calculer $M^2$ et $M^3$. Coefficient ligne $1$, colonne $2$ de $M^3$ :
   $M$ $=\left(\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right),M^2$ $=\left(\begin{array}{cccc}2& 0& 2& 0\\ 0& 2& 0& 2\\ 2& 0& 2& 0\\ 0& 2& 0& 2\end{array}\right),M^3$ $=\left(\begin{array}{cccc}0& 4& 0& 4\\ 4& 0& 4& 0\\ 0& 4& 0& 4\\ 4& 0& 4& 0\end{array}\right).$ Le coefficient $(1;2)$ de $M^3$ vaut $4$ : d’après le théorème du cours, il y a $4$ chaînes de longueur $3$ de A à B.
2. Écrire ces chaînes. Combien d’entre elles repassent par un sommet déjà visité ?
   Les quatre chaînes sont A–B–A–B, A–B–C–B, A–D–A–B, A–D–C–B. Seule A–D–C–B ne repasse par aucun sommet : A–B–A–B repasse par A et par B, A–B–C–B par B, A–D–A–B par A. Il y en a donc $3$, et elles sont toutes comptées par le théorème.
3. Nombre de chaînes de longueur $4$ de A à C :
   $(M^4{)}_{13}$ = ligne $1$ de $M^3$ × colonne $3$ de $M$ : $0\times 0+4\times 1+0\times 0+4\times 1$ $=8$. Il y a $8$ chaînes de longueur $4$ de A à C.

Un graphe orienté a pour sommets $1$, $2$, $3$, $4$ (dans cet ordre). On donne sa matrice d’adjacence et son carré : $M$ $=\left(\begin{array}{cccc}0& 1& 0& 1\\ 0& 0& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\end{array}\right),M^2$ $=\left(\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 2& 0& 1\\ 0& 0& 1& 0\end{array}\right).$

1. Nombre de chemins de longueur $2$ de $3$ vers $2$ :
   D’après le théorème, c’est $(M^2{)}_{32}=2$. Ce sont 3 → 1 → 2, 3 → 4 → 2 : les deux successeurs de $3$, à savoir $1$ et $4$, mènent chacun à $2$.
2. Nombre de chemins de longueur $3$ de $3$ vers $2$ :
   $(M^3{)}_{32}$ = ligne $3$ de $M^2$ × colonne $2$ de $M$ : $0\times 1+2\times 0+0\times 0+1\times 1$ $=1$. Le seul chemin est 3 → 1 → 4 → 2.
3. Nombre de circuits de longueur $3$ partant de $2$ et y revenant :
   $(M^3{)}_{22}$ = ligne $2$ de $M^2$ × colonne $2$ de $M$ : $1\times 1+0\times 0+0\times 0+1\times 1$ $=2$. Ce sont 2 → 3 → 1 → 2, 2 → 3 → 4 → 2.

Un graphe non orienté a pour sommets A, B, C, D, E, F (dans cet ordre) et pour arêtes A–B, A–C, A–D, B–C, B–E, C–D, D–E et E–F. On donne $M^2$ $=\left(\begin{array}{cccccc}3& 1& 2& 1& 2& 0\\ 1& 3& 1& 3& 0& 1\\ 2& 1& 3& 1& 2& 0\\ 1& 3& 1& 3& 0& 1\\ 2& 0& 2& 0& 3& 0\\ 0& 1& 0& 1& 0& 1\end{array}\right).$

1. Justifier que le coefficient $(1;6)$ de $M^4$ s’obtient en multipliant la ligne $1$ de $M^2$ par la colonne $6$ de $M^2$, puis le calculer :
   Rédaction attendue. Comme $M^4=M^2\times M^2$, le coefficient ligne $1$, colonne $6$ de $M^4$ est la ligne $1$ de $M^2$ multipliée par la colonne $6$ de $M^2$ : $3\times 0+1\times 1+2\times 0+1\times 1+2\times 0+0\times 1$ $=2$. D’après le théorème, il y a $2$ chaînes de longueur $4$ de A à F.
2. Ces chaînes arrivent en F par E, seul voisin de F. Juste avant E, l’une passe par B, l’autre par
   Ce sont A–C–B–E–F, A–C–D–E–F. On les retrouve sans calcul : avant E, la chaîne vient d’un voisin de E autre que F, donc B ou D ; et elle doit atteindre ce sommet en deux pas depuis A. Le seul voisin commun de A et de B est C, de même pour A et D : on obtient exactement ces deux chaînes.
3. Nombre de chaînes fermées de longueur $4$ partant de F :
   $(M^4{)}_{66}$ = ligne $6$ de $M^2$ × colonne $6$ de $M^2$ : $0\times 0+1\times 1+0\times 0+1\times 1+0\times 0+1\times 1$ $=3$. Ce sont F–E–B–E–F, F–E–D–E–F, F–E–F–E–F.

On note $M$ la matrice d’adjacence du graphe complet $K_5$ et $I$ la matrice identité d’ordre $5$. On admet que, pour tout entier $k⩾1$, il existe deux réels $a_k$ et $b_k$ tels que $M^k=a_{k}M+b_{k}I$, et que cette écriture est unique.

1. Déterminer les coefficients de $M^2$, puis les réels $\alpha$ et $\beta$ tels que $M^2=\alpha M+\beta I$. $\alpha =$ ; $\beta =$
   Rédaction attendue. Le coefficient $(i;j)$ de $M^2$ compte les chaînes de longueur $2$ de $i$ à $j$. Si $i=j$, c’est un aller-retour $i$–$r$–$i$ vers l’un des $4$ voisins de $i$ : $(M^2{)}_{ii}=4$. Si $i\ne j$, la chaîne s’écrit $i$–$r$–$j$ avec $r$ voisin de $i$ et de $j$, c’est-à-dire $r$ distinct de $i$ et de $j$ : $3$ choix, donc $(M^2{)}_{ij}=3$. La matrice $3M+4I$ a aussi des $4$ sur la diagonale et des $3$ ailleurs : $M^2=3M+4I$, donc $\alpha =3$ et $\beta =4$.
2. Exprimer, en justifiant, $a_{k+1}$ et $b_{k+1}$ en fonction de $a_k$ et $b_k$. Valeur de $a_3$ :
   Rédaction attendue. $M^{k+1}$ $=M^k\times M$ $=(a_{k}M+b_{k}I)M$ $=a_k{M}^2+b_{k}M$ $=a_k(3M+4I)+b_{k}M$ $=(3a_k+b_k)M+4a_{k}I$. Par unicité de l’écriture, $a_{k+1}=3a_k+b_k$ et $b_{k+1}=4a_k$. Avec $a_1=1$ et $b_1=0$ (car $M^1=1\times M+0\times I$) : $a_2=3\times 1+0=3$ et $b_2=4$, ce qui redonne $M^2=3M+4I$ ; puis $a_3=3\times 3+4=13$ et $b_3=4\times 3=12$.
3. Nombre de chaînes de longueur $4$ reliant deux sommets distincts : ; nombre de chaînes fermées de longueur $4$ partant d’un sommet donné :
   Avec $a_3=13$ et $b_3=12$ (question précédente) : $a_4=3\times 13+12=51$ et $b_4=4\times 13=52$. Hors de la diagonale, $M^4$ a pour coefficient $a_4=51$ ; sur la diagonale, $a_4\times 0+b_4=52$.
4. Calculer $b_4+4a_4$ : , puis interpréter ce nombre.
   $52+4\times 51=52+204=256=4^4$. Depuis un sommet fixé, une chaîne de longueur $4$ se construit en choisissant à chaque pas l’un des $4$ voisins du sommet courant : il y en a $4^4=256$. On les range selon leur extrémité : $52$ reviennent au départ, et $51$ arrivent sur chacun des $4$ autres sommets.

Un graphe non orienté simple a pour sommets $1$ à $6$. On donne $M^2$ $=\left(\begin{array}{cccccc}2& 1& 1& 1& 2& 0\\ 1& 4& 0& 2& 1& 1\\ 1& 0& 1& 1& 1& 0\\ 1& 2& 1& 3& 1& 1\\ 2& 1& 1& 1& 3& 0\\ 0& 1& 0& 1& 0& 1\end{array}\right)$ et la diagonale de $M^3$ : $(2,4,0,4,2,0)$.

1. Degré du sommet $2$ :
   $(M^2{)}_{22}$ compte les allers-retours $2$–$r$–$2$, un par voisin : $d(2)=4$.
2. Nombre d’arêtes :
   La diagonale de $M^2$ donne les degrés $2$, $4$, $1$, $3$, $3$, $1$, de somme $14=2m$ : le graphe a $7$ arêtes.
3. Nombre de triangles :
   Trace de $M^3$ : $2+4+0+4+2+0=12$. Chaque triangle est compté $6$ fois (trois départs, deux sens) : $12÷6=2$ triangles.
4. Nombre de triangles qui contiennent le sommet $4$ :
   $(M^3{)}_{44}=4$ compte chaque triangle contenant $4$ deux fois (deux sens) : $4÷2=2$. Les deux triangles du graphe contiennent donc le sommet $4$ ; comme $(M^3{)}_{22}=4$ aussi, ils contiennent tous deux le sommet $2$.

Le graphe orienté $G_4$ a pour sommets A, B, C, D (dans cet ordre) et pour arcs A → B, B → C, C → A et A → D.

1. Écrire $M$, calculer $M^2$ et $M^3$. Coefficient $(M^3{)}_{11}$ :
   $M$ $=\left(\begin{array}{cccc}0& 1& 0& 1\\ 0& 0& 1& 0\\ 1& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right),M^2$ $=\left(\begin{array}{cccc}0& 0& 1& 0\\ 1& 0& 0& 0\\ 0& 1& 0& 1\\ 0& 0& 0& 0\end{array}\right),M^3$ $=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 0\\ 0& 0& 0& 0\end{array}\right).$ $(M^3{)}_{11}=1$ : le seul chemin fermé de longueur $3$ partant de A est le circuit A → B → C → A.
2. Démontrer que la quatrième ligne de $M^k$ est nulle pour tout entier $k⩾1$. Nombre de chemins de longueur $5$ partant de D :
   Rédaction attendue. Par récurrence. Pour $k=1$, la ligne $4$ de $M$ est nulle : aucun arc ne part de D. Soit $k⩾1$ tel que la ligne $4$ de $M^k$ est nulle ; la ligne $4$ de $M^{k+1}=M^k\times M$ s’obtient en multipliant cette ligne nulle par chaque colonne de $M$ : elle est nulle. Par récurrence, la ligne $4$ de $M^k$ est nulle pour tout $k⩾1$. D’après le théorème, aucun chemin de longueur $5$ (ni d’aucune longueur) ne part de D.
3. Justifier, à l’aide de $S=M+M^2+M^3$, que $G_4$ n’est pas fortement connexe. Coefficient ligne $4$, colonne $1$ de $S$ :
   Rédaction attendue. $S$ $=\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& 1& 1\\ 1& 1& 1& 1\\ 0& 0& 0& 0\end{array}\right).$ Le graphe est d’ordre $4$ : il serait fortement connexe si et seulement si tous les coefficients hors de la diagonale de $S=M+M^2+M^3$ étaient non nuls. Or la ligne $4$ est nulle, en particulier $S_{41}=0$ : aucun chemin ne va de D vers A. $G_4$ n’est pas fortement connexe.

Le graphe orienté $G_5$ a pour sommets $1$, $2$, $3$, $4$, $5$ (dans cet ordre) et pour arcs $1\to 2$, $2\to 3$, $3\to 4$, $4\to 5$, $5\to 1$ et $1\to 3$. On donne $M^4$ $=\left(\begin{array}{ccccc}1& 0& 0& 0& 1\\ 1& 0& 0& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 0\\ 0& 0& 0& 1& 1\end{array}\right).$

1. Nombre de circuits de longueur $4$ partant de $1$ et y revenant :
   $(M^4{)}_{11}=1$ : c’est 1 → 3 → 4 → 5 → 1, qui emprunte le raccourci $1\to 3$.
2. Somme des coefficients diagonaux de $M^4$ :
   $1+0+1+1+1=4$. Le circuit $1\to 3\to 4\to 5\to 1$ passe par quatre sommets, et il est compté une fois depuis chacun d’eux. $(M^4{)}_{22}=0$ : aucun circuit de longueur $4$ ne passe par $2$.
3. Déterminer, en justifiant à l’aide de $M^3$, le nombre de circuits de longueur $3$ de $G_5$ :
   Rédaction attendue. $M^3$ $=\left(\begin{array}{ccccc}0& 0& 0& 1& 1\\ 0& 0& 0& 0& 1\\ 1& 0& 0& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 0\end{array}\right).$ Sa diagonale est nulle : aucun chemin fermé de longueur $3$, donc aucun circuit de longueur $3$. On le voit aussi sur le graphe : les deux circuits possibles, $1\to 2\to 3\to 4\to 5\to 1$ et $1\to 3\to 4\to 5\to 1$, ont pour longueurs $5$ et $4$.
4. Distance du sommet $2$ au sommet $1$ :
   Le coefficient $(2;1)$ vaut $0$ dans $M$, $M^2$ et $M^3$, et $1$ dans $M^4$ : $d(2;1)=4$, par $2\to 3\to 4\to 5\to 1$. Le raccourci $1\to 3$ part de $1$ : il ne sert pas.

Trois maisons, numérotées $1$, $2$, $3$, doivent être reliées à trois services, numérotés $4$ (eau), $5$ (gaz) et $6$ (électricité). On modélise par un graphe non orienté : une arête relie chaque maison à chaque service, et il n’y a pas d’autre arête. On note $M$ sa matrice d’adjacence.

1. Démontrer que, pour tout entier $k$ impair et tout sommet $i$, $(M^k{)}_{ii}=0$. Nombre de triangles du graphe :
   Rédaction attendue. Chaque arête relie une maison à un service : un chemin passe d’un groupe à l’autre à chaque pas. Après un nombre impair de pas, il est dans l’autre groupe que son départ : il ne peut pas être revenu à son point de départ. Donc aucun chemin fermé de longueur impaire n’existe, et, d’après le théorème, $(M^k{)}_{ii}=0$ pour $k$ impair. En particulier la trace de $M^3$ est nulle : le graphe n’a aucun triangle.
2. Coefficient $(M^2{)}_{12}$ :
   Les chaînes de longueur $2$ de la maison $1$ à la maison $2$ passent par un service : 1–4–2, 1–5–2, 1–6–2. Donc $(M^2{)}_{12}=3$.
3. Démontrer que $M^3=9M$. Nombre de chaînes de longueur $5$ de $1$ à $4$ :
   Rédaction attendue. Soit $i$ et $j$ deux sommets. S’ils sont dans le même groupe, $(M^3{)}_{ij}=0$ (longueur impaire), et $m_{ij}=0$. S’ils sont dans deux groupes différents, une chaîne $i$–$a$–$b$–$j$ de longueur $3$ se construit en choisissant $a$ parmi les $3$ sommets de l’autre groupe que $i$, puis $b$ parmi les $3$ sommets du groupe de $i$ ; l’arête $b$–$j$ existe toujours. Il y a $3\times 3=9$ chaînes, et $m_{ij}=1$. Dans tous les cas, $(M^3{)}_{ij}=9m_{ij}$ : $M^3=9M$. Alors $M^5$ $=M^3\times M^2$ $=9M\times M^2$ $=9M^3$ $=81M$, et $(M^5{)}_{14}=81\times 1=81$.

Le graphe non orienté $G_6$ a pour sommets A, B, C, D, E, F (dans cet ordre) et pour arêtes A–B, B–C, B–E, C–D, D–E et E–F. On note $M$ sa matrice d’adjacence.

1. Calculer la ligne $1$ de $M^2$, puis celle de $M^3$. Coefficient $(M^3{)}_{16}$ :
   La ligne $1$ de $M$ est $(010000)$ : A n’a qu’un voisin, B, donc la ligne $1$ de $M^2$ est la ligne $2$ de $M$, $(101010)$. La ligne $1$ de $M^3$ est la somme des lignes $1$, $3$ et $5$ de $M$ : $(030201)$. Donc $(M^3{)}_{16}=1$.
2. Justifier que $d(A;F)=$
   Rédaction attendue. Le coefficient $(1;6)$ vaut $0$ dans $M$ (A et F ne sont pas voisins), $0$ dans $M^2$ et $1$ dans $M^3$. La plus petite puissance qui donne un coefficient non nul est $3$ : $d(A;F)=3$, par la chaîne A–B–E–F.
3. $d(F;C)=$
   F n’a qu’un voisin, E ; les voisins de E sont B, D et F, et C n’en fait pas partie : aucune chaîne de longueur $1$ ou $2$ ne relie F à C. F–E–D–C a pour longueur $3$, donc $d(F;C)=3$.
4. Diamètre de $G_6$ :
   Plus grande distance de chaque sommet aux autres : A, $3$ (vers D et F) ; B, $2$ ; C, $3$ (vers F) ; D, $3$ (vers A) ; E, $2$ ; F, $3$. Le maximum vaut $3$ : le diamètre est $3$.

Un graphe non orienté a pour sommets A, B, C, D, E, F (dans cet ordre) et pour matrice d’adjacence $M$ $=\left(\begin{array}{cccccc}0& 0& 0& 1& 0& 1\\ 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 0& 1\\ 0& 0& 1& 0& 0& 0\\ 1& 0& 0& 1& 0& 0\end{array}\right).$ On donne $S$ $=M+M^2+M^3+M^4+M^5$ $=\left(\begin{array}{cccccc}20& 0& 0& 21& 0& 21\\ 0& 3& 7& 0& 3& 0\\ 0& 7& 6& 0& 7& 0\\ 21& 0& 0& 20& 0& 21\\ 0& 3& 7& 0& 3& 0\\ 21& 0& 0& 21& 0& 20\end{array}\right).$

1. Coefficient $S_{12}$ :
   Ligne $1$, colonne $2$ : $S_{12}=0$. Aucun chemin de longueur $1$ à $5$ ne relie A à B.
2. Justifier que le graphe n’est pas connexe. Nombre de sommets de la composante connexe qui contient A :
   Rédaction attendue. Le graphe est d’ordre $6$ : il serait connexe si et seulement si tous les coefficients hors de la diagonale de $S=M+\dots +M^5$ étaient non nuls. Or $S_{12}=0$ : il n’est pas connexe. Les coefficients non nuls de la ligne $1$ sont dans les colonnes de A, D et F : la composante de A est $\{A,D,F\}$, à $3$ sommets. L’autre est $\{B,C,E\}$.
3. $d(B;E)=$
   $m_{25}=0$ : B et E ne sont pas voisins. La chaîne B–C–E existe, car $m_{23}=m_{35}=1$ : $d(B;E)=2$.

Un réseau de navettes à sens unique relie cinq terminaux A, B, C, D, E (dans cet ordre) par les liaisons A → B, B → C, C → D, C → A, D → E et E → A. On note $M$ la matrice d’adjacence du graphe orienté associé ; on donne $S$ $=M+M^2+M^3+M^4$ $=\left(\begin{array}{ccccc}1& 2& 1& 1& 1\\ 2& 1& 2& 1& 1\\ 3& 2& 1& 2& 1\\ 1& 1& 1& 0& 1\\ 2& 1& 1& 1& 0\end{array}\right).$

1. Justifier que le graphe est fortement connexe. Coefficient ligne $4$, colonne $3$ de $S$ :
   Rédaction attendue. Le graphe est d’ordre $5$, et tous les coefficients hors de la diagonale de $S=M+M^2+M^3+M^4$ sont non nuls : pour tous terminaux distincts $i$ et $j$, il existe un chemin de $i$ vers $j$. Le graphe est fortement connexe, malgré les sens uniques. $S_{43}=1$ : il y a un seul chemin de longueur au plus $4$ de D vers C.
2. $d(A;E)=$
   Le coefficient $(1;5)$ vaut $0$ dans $M$, $M^2$ et $M^3$, et $1$ dans $M^4$ : $d(A;E)=4$, par A → B → C → D → E. On a $M^4$ $=\left(\begin{array}{ccccc}0& 1& 0& 0& 1\\ 1& 0& 1& 0& 0\\ 1& 1& 0& 1& 0\\ 0& 0& 1& 0& 0\\ 1& 0& 0& 1& 0\end{array}\right)$.
3. $d(D;C)=$
   De D, le seul arc mène à E, puis à A, puis à B, puis à C : $(M{)}_{43}=(M^2{)}_{43}=(M^3{)}_{43}=0$ et $(M^4{)}_{43}=1$. Donc $d(D;C)=4$, par D → E → A → B → C.
4. Diamètre du graphe :
   Aucune distance ne dépasse $4=n-1$, et la valeur $4$ est atteinte (par exemple de A à E) : le diamètre vaut $4$. Un usager peut aller de n’importe quel terminal à n’importe quel autre, mais il lui faut parfois quatre navettes.

On étudie jusqu’où il faut aller dans la somme $M+M^2+\dots$ pour décider de la connexité.

1. Démontrer que, dans un graphe d’ordre $n$, deux sommets distincts reliés par un chemin le sont par un chemin de longueur au plus $n-1$. Pour un graphe d’ordre $6$, la plus grande puissance de $M$ utile dans $S$ est donc la puissance
   Rédaction attendue. Soit un chemin de longueur minimale de $i$ à $j$. S’il passait deux fois par un même sommet $s$, on supprimerait la portion comprise entre ces deux passages : on obtiendrait un chemin de $i$ à $j$ strictement plus court, ce qui est impossible. Il passe donc par des sommets tous distincts, au plus $n$, et compte au plus $n-1$ arcs. Pour $n=6$, il suffit d’aller jusqu’à $M^5$.
2. Le graphe orienté de sommets $1$ à $6$ et d’arcs $1\to 2$, $2\to 3$, $3\to 4$, $4\to 5$, $5\to 6$, $6\to 1$ et $4\to 2$ vérifie : $d(1;6)=$
   Depuis $1$, les arcs imposent $1\to 2\to 3\to 4$, puis $4\to 5\to 6$ (l’arc $4\to 2$ ramène en arrière). Le coefficient $(1;6)$ vaut $0$ dans $M$, $M^2$, $M^3$, $M^4$, et $1$ dans $M^5$ : $d(1;6)=5$.
3. Coefficient $(1;6)$ de $M+M^2+M^3+M^4$ :
   Il vaut $0+0+0+0=0$. S’arrêter à $M^4$ ferait croire, à tort, qu’aucun chemin ne va de $1$ vers $6$ : pour un graphe d’ordre $6$, il faut aller jusqu’à $M^5$.
4. Justifier que ce graphe est fortement connexe. Diamètre :
   Rédaction attendue. $M+M^2+M^3+M^4+M^5$ $=\left(\begin{array}{cccccc}0& 2& 2& 1& 1& 1\\ 1& 1& 2& 2& 1& 1\\ 1& 3& 1& 2& 2& 1\\ 1& 3& 3& 1& 2& 2\\ 1& 1& 1& 1& 0& 1\\ 1& 2& 1& 1& 1& 0\end{array}\right).$ Tous les coefficients hors de la diagonale sont non nuls : le graphe est fortement connexe. Aucune distance ne dépasse $n-1=5$, et $d(1;6)=5$ : le diamètre vaut $5$.