Matrice d'adjacence et chemins : exercices de Terminale

On range les sommets dans l'ordre A, B, C, D : la matrice est $4 \times 4$. La ligne A contient un 1 pour chaque sommet voisin de A, c'est-à-dire B et C : $(0\ 1\ 1\ 0)$.

Ligne B : voisins A et C, donc $(1\ 0\ 1\ 0)$. Ligne C : voisins A, B et D, donc $(1\ 1\ 0\ 1)$. Ligne D : seul voisin C, donc $(0\ 0\ 1\ 0)$.

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

Le graphe n'est pas orienté : une arête relie A à B comme B à A, donc $a_{ij} = a_{ji}$ et la matrice est symétrique. La diagonale est nulle car il n'y a aucune boucle ⁴.

Somme des coefficients : $2 + 2 + 3 + 1 = 8$ (somme des lignes). Chaque arête apparaît deux fois, une fois au-dessus de la diagonale et une fois en dessous : $8 = 2 \times 4$ arêtes.

La diagonale est nulle : aucune boucle. Tous les coefficients valent 0 ou 1 : aucune arête multiple. La matrice est symétrique ($a_{12} = a_{21} = 1$, $a_{14} = a_{41} = 1$, $a_{23} = a_{32} = 1$, $a_{24} = a_{42} = 1$, les autres valent 0), donc le graphe n'est pas orienté ⁴.

La ligne 2 est $(1\ 0\ 1\ 1)$ : le sommet 2 est relié à 1, 3 et 4. Son degré est 3.

Somme de tous les coefficients : $2 + 3 + 1 + 2 = 8$. Chaque arête est comptée deux fois, donc le graphe a $8 \div 2 = 4$ arêtes.

On peut les nommer : 1-2, 1-4, 2-3 et 2-4.

Ligne 1 : un seul arc part de 1, vers 2, donc $(0\ 1\ 0)$. Ligne 2 : un arc vers 3, donc $(0\ 0\ 1)$. Ligne 3 : des arcs vers 1 et vers 2, donc $(1\ 1\ 0)$.

$B = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$

On a $b_{12} = 1$ mais $b_{21} = 0$ : la matrice n'est pas symétrique. C'est normal : un graphe non orienté donne une matrice symétrique ⁴, donc une matrice non symétrique signale un graphe orienté.

Les arcs qui partent de 3 correspondent aux 1 de la ligne 3 : $1 + 1 + 0 = 2$ arcs.

Ligne A de $M^2$ : A est relié à B et C, on additionne les lignes B et C de $M$ : $(1\ 0\ 1\ 0) + (1\ 1\ 0\ 1) = (2\ 1\ 1\ 1)$.

Ligne B : B est relié à A et C, donc $(0\ 1\ 1\ 0) + (1\ 1\ 0\ 1) = (1\ 2\ 1\ 1)$. Ligne C : C est relié à A, B et D, donc $(0\ 1\ 1\ 0) + (1\ 0\ 1\ 0) + (0\ 0\ 1\ 0) = (1\ 1\ 3\ 0)$. Ligne D : D n'est relié qu'à C, donc c'est la ligne C de $M$ : $(1\ 1\ 0\ 1)$.

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

Le coefficient $(i,i)$ de $M^2$ compte les parcours de longueur 2 qui partent de $i$ et y reviennent ⁴ : il faut aller vers un voisin puis revenir, donc il y en a autant que de voisins. Les valeurs 2, 2, 3, 1 sont bien les degrés de A, B, C, D.

Le coefficient en ligne A, colonne D vaut 1 : un seul parcours de longueur 2 relie A à D, à savoir A, C, D.

$T = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}, \quad T^2 = \begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{pmatrix}.$

Ligne A de $T^3 = T^2 \times T$ : $2 \times (0\ 1\ 1) + 1 \times (1\ 0\ 1) + 1 \times (1\ 1\ 0) = (2\ 3\ 3)$. Par symétrie du triangle :

$T^3 = \begin{pmatrix} 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \end{pmatrix}.$

Le coefficient en ligne A, colonne B vaut 3 : il y a 3 parcours de longueur 3 de A à B ⁴.

Énumération. Si x = B, alors y doit être voisin de B et on doit finir en B : y = A ou y = C, d'où A, B, A, B et A, B, C, B. Si x = C, alors y doit être voisin de C et de B : seul y = A convient, d'où A, C, A, B. Total : 3 parcours, ce qui confirme le calcul.

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

Ligne 1 de $C^2$ : on additionne les lignes 2 et 3 de $C$ : $(0\ 0\ 1) + (1\ 0\ 0) = (1\ 0\ 1)$. Ligne 2 : c'est la ligne 3 de $C$, soit $(1\ 0\ 0)$. Ligne 3 : c'est la ligne 1 de $C$, soit $(0\ 1\ 1)$.

$C^2 = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{pmatrix}$

Ligne 1 de $C^4 = C^2 \times C^2$ : on additionne les lignes 1 et 3 de $C^2$ : $(1\ 0\ 1) + (0\ 1\ 1) = (1\ 1\ 2)$.

Le coefficient en ligne 1, colonne 3 vaut 2 : il y a 2 parcours de longueur 4 du sommet 1 au sommet 3 ⁴.

Vérification : $1 \to 2 \to 3 \to 1 \to 3$ et $1 \to 3 \to 1 \to 2 \to 3$. Chaque arc existe bien dans le graphe, et il n'y a pas d'autre combinaison possible.

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

Ligne 2 de $D$ : $(0\ 0\ 1\ 0)$. Le coefficient en colonne 1 vaut 0 : aucun arc direct de 2 vers 1.

Ligne 2 de $D^2$ : c'est la ligne 3 de $D$, soit $(0\ 0\ 0\ 1)$. Colonne 1 : 0, donc pas de parcours de longueur 2.

Ligne 2 de $D^3$ : on multiplie $(0\ 0\ 0\ 1)$ par $D$, ce qui donne la ligne 4 de $D$, soit $(1\ 0\ 0\ 0)$. Colonne 1 : 1 ⁴.

Le plus petit entier $k$ pour lequel le coefficient $(2,1)$ de $D^k$ est non nul est donc 3, et il y a exactement un parcours de cette longueur : $2 \to 3 \to 4 \to 1$.

Par définition, le coefficient diagonal compte les boucles du sommet ⁴. Seul $g_{22}$ vaut 1 :

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

Ligne 1 de $G^2$ : c'est la ligne 2 de $G$, soit $(1\ 1\ 1)$. Ligne 2 : somme des trois lignes de $G$, soit $(0\ 1\ 0) + (1\ 1\ 1) + (0\ 1\ 0) = (1\ 3\ 1)$. Ligne 3 : $(1\ 1\ 1)$.

$G^2 = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 3 & 1 \\ 1 & 1 & 1 \end{pmatrix}$

Ligne 1 de $G^3 = G^2 \times G$ : $(1\ 1\ 1) \times G = (0\ 1\ 0) + (1\ 1\ 1) + (0\ 1\ 0) = (1\ 3\ 1)$. Ligne 2 : $(1\ 3\ 1) \times G = (0\ 1\ 0) + 3 \times (1\ 1\ 1) + (0\ 1\ 0) = (3\ 5\ 3)$. Par symétrie, la ligne 3 est $(1\ 3\ 1)$.

$G^3 = \begin{pmatrix} 1 & 3 & 1 \\ 3 & 5 & 3 \\ 1 & 3 & 1 \end{pmatrix}$

Ligne 1 de $G^4 = G^3 \times G$ : $1 \times (0\ 1\ 0) + 3 \times (1\ 1\ 1) + 1 \times (0\ 1\ 0) = (3\ 5\ 3)$. Le coefficient en colonne 3 vaut 3 : il y a 3 parcours de longueur 4 de 1 à 3 ⁴.

Énumération : le seul voisin de 1 est 2 et le seul voisin de 3 est 2, donc le parcours commence par $1, 2$ et finit par $2, 3$. Il reste deux pas au milieu, pour passer de 2 à 2 en 2 pas : $2 \to 1 \to 2$, $2 \to 2 \to 2$ (par la boucle deux fois) ou $2 \to 3 \to 2$. D'où $1, 2, 1, 2, 3$ ; $1, 2, 2, 2, 3$ ; $1, 2, 3, 2, 3$.