Exercice 18

1. Dans un graphe non orienté, chaque arête entre $i$ et $j$ se lit dans les deux sens : elle produit un $1$ en position $(i\,;j)$ et en position $(j\,;i)$. $$\boxed{\begin{array}{c} \text{Une matrice d'adjacence correspond à un graphe non orienté} \\[1mm] \text{si et seulement si elle est symétrique} \end{array}}$$ On vérifie ici que $A$ est symétrique, alors que $B$ ne l'est pas : par exemple le coefficient en ligne $1$, colonne $2$ de $B$ vaut $0$ alors que celui en ligne $2$, colonne $1$ vaut $1$. $$\boxed{G_{1} \text{ est non orienté} \qquad ; \qquad G_{2} \text{ est orienté}}$$ On remarque de plus que la diagonale de $B$ n'est pas nulle : $G_{2}$ possède des boucles, aux sommets $1$, $2$ et $4$.

2. (a) Les arêtes de $G_{1}$ se lisent au-dessus de la diagonale : $1$--$2$, $1$--$3$, $1$--$4$ et $2$--$4$. Pour $G_{2}$, on lit ligne par ligne les arcs $1\to 1$, $1\to 3$, $2\to 1$, $2\to 2$, $3\to 1$, $4\to 1$, $4\to 2$, $4\to 3$ et $4\to 4$.

Remarque : dans $G_{2}$, les arcs $1\to 3$ et $3\to 1$ existent tous les deux, ce qui explique le tracé de deux flèches distinctes entre ces deux sommets.

(b) On élève chaque matrice au cube. $$A^{2}=\begin{pmatrix} 3 & 1 & 0 & 1 \\ 1 & 2 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 2 \end{pmatrix} \qquad A^{3}=\begin{pmatrix} 2 & 4 & 3 & 4 \\ 4 & 2 & 1 & 3 \\ 3 & 1 & 0 & 1 \\ 4 & 3 & 1 & 2 \end{pmatrix}$$ Le coefficient en ligne $2$, colonne $4$ vaut $3$ : $$\boxed{\text{dans } G_{1}, \text{ il existe } 3 \text{ chaînes de longueur } 3 \text{ reliant } 2 \text{ à } 4}$$ Ce sont $2$--$1$--$2$--$4$, puis $2$--$4$--$1$--$4$ et enfin $2$--$4$--$2$--$4$ : dans un graphe non orienté, rien n'interdit d'emprunter deux fois la même arête.

$$B^{2}=\begin{pmatrix} 2 & 0 & 1 & 0 \\ 2 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 4 & 2 & 2 & 1 \end{pmatrix} \qquad B^{3}=\begin{pmatrix} 3 & 0 & 2 & 0 \\ 4 & 1 & 2 & 0 \\ 2 & 0 & 1 & 0 \\ 9 & 3 & 5 & 1 \end{pmatrix}$$ Le coefficient en ligne $2$, colonne $4$ vaut $0$ : $$\boxed{\text{dans } G_{2}, \text{ il n'existe aucun chemin de longueur } 3 \text{ reliant } 2 \text{ à } 4}$$ Ce résultat se lit directement sur $B$ : sa quatrième colonne est $\begin{pmatrix} 0 & 0 & 0 & 1 \end{pmatrix}^{\!\top}$, donc le seul arc arrivant en $4$ part de $4$ lui-même. Le sommet $4$ est inaccessible depuis n'importe quel autre sommet, et ce quelle que soit la longueur du chemin : les colonnes $4$ de $B^{2}$ et $B^{3}$ sont d'ailleurs nulles elles aussi, sauf en dernière ligne.