Ressources · Terminale · Maths expertes (option Tle)

Fiche de révision : matrice d’adjacence et chemins

Matrice d’adjacence d’un graphe orienté ou non ; degrés et nombre d’arêtes lus sur la matrice ; nombre de chemins de longueur k donné par Mᵏ, avec sa démonstration ; chemins fermés, triangles et coefficients nuls ; distance, diamètre et connexité.

Télécharger la fiche PDF

benprofparticulier.frMaths expertes (option Tle) · Terminale

Matrice d’adjacence et chemins

Fiche méthode

(Maths expertes Terminale · Graphes et matrices)

La démarche face à une matrice d’adjacence

1. J’écris l’ordre des sommets à côté de la matrice, et je retiens : ligne = départ, colonne = arrivée.

2. Je contrôle la matrice : symétrique si le graphe n’est pas orienté, diagonale nulle sans boucle, somme des lignes égale aux degrés.

3. Je choisis la bonne puissance : $M^{k}$ pour des chemins de longueur $k$ , les puissances successives pour une distance, $M + M^{2} + \dots + M^{n - 1}$ pour la connexité.

4. Je conclus en citant le théorème : « d’après le cours, le coefficient ligne $i$ , colonne $j$ de $M^{k}$ est le nombre de chemins de longueur $k$ de $i$ à $j$ ».

Le réflexe — un nombre lu dans une matrice ne rapporte rien sans la phrase qui l’interprète : quel coefficient, de quelle puissance, et ce qu’il compte.

Cas 1 · Écrire la matrice d’adjacence

Réflexe — ordre des sommets écrit ; ligne i = arcs qui partent de i ; symétrique seulement si le graphe n’est pas orienté.

Exemple. Question type : « Écrire la matrice d’adjacence du graphe. » Exemple : graphe orienté de sommets $1$ , $2$ , $3$ , $4$ et d’arcs $1 \to 3$ , $2 \to 1$ , $3 \to 2$ , $3 \to 4$ .

$M$ $= (\begin{matrix} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{matrix})$ (ordre $1$ , $2$ , $3$ , $4$ ).

$M$ n’est pas symétrique : $m_{13} = 1$ mais $m_{31} = 0$ . La ligne $4$ est nulle : aucun arc ne part de $4$ .

Attention — m₁₃ se lit « de 1 vers 3 » : intervertir ligne et colonne change la réponse dans un graphe orienté.

Cas 2 · Degrés et nombre d’arêtes

Réflexe — degré = somme de la ligne ; nombre d’arêtes = somme totale ÷ 2 si le graphe n’est pas orienté.

Exemple. Question type : « Déterminer le degré de chaque sommet et le nombre d’arêtes. » Exemple : graphe non orienté de sommets A, B, C, D, E et de matrice $(\begin{matrix} 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \end{matrix})$ .

Sommes des lignes : $d (A) = 3$ , $d (B) = 2$ , $d (C) = 4$ , $d (D) = 3$ , $d (E) = 2$ .

Somme de tous les coefficients : $3 + 2 + 4 + 3 + 2 = 14$ , donc le graphe a $14 \div 2 = 7$ arêtes.

Attention — graphe orienté : ligne = degré sortant, colonne = degré entrant, somme totale = nombre d’arcs sans diviser par 2.

1 / 2

benprofparticulier.frMaths expertes (option Tle) · Terminale

Cas 3 · Compter des chemins de longueur k

Réflexe — coefficient (i ; j) de Mᵏ ; un seul coefficient : ligne i de Mᵏ⁻¹ × colonne j de M.

Exemple. Question type : « Combien y a-t-il de chemins de longueur 3 de B à D ? Les citer. » Exemple : graphe d’arêtes A–B, B–C, C–D, D–A, A–C (ordre A, B, C, D), avec $M^{2}$ $= (\begin{matrix} 3 & 1 & 2 & 1 \\ 1 & 2 & 1 & 2 \\ 2 & 1 & 3 & 1 \\ 1 & 2 & 1 & 2 \end{matrix})$ .

$(M^{3})_{24}$ = ligne $2$ de $M^{2}$ × colonne $4$ de $M$ : $1 \times 1 + 2 \times 0 + 1 \times 1 + 2 \times 0$ $= 2$ .

D’après le cours, il y a $2$ chemins de longueur $3$ de B à D : B–A–C–D et B–C–A–D.

Attention — M² se calcule ligne par colonne, ce n’est pas la matrice des carrés des coefficients.

Cas 4 · Chemins fermés et triangles

Réflexe — diagonale de Mᵏ = chemins fermés ; triangles = trace de M³ ÷ 6 ; circuits de longueur 3 (orienté) = trace ÷ 3.

Exemple. Question type : « Combien le graphe a-t-il de triangles ? » Exemple : graphe d’arêtes A–B, B–C, C–A, C–D, D–E, E–C, dont la diagonale de $M^{3}$ vaut $(2, 2, 4, 2, 2)$ .

Trace de $M^{3}$ : $2 + 2 + 4 + 2 + 2 = 12$ . Chaque triangle est compté $6$ fois (trois départs, deux sens) : $12 \div 6 = 2$ triangles, A–B–C et C–D–E.

$(M^{3})_{33} = 4 = 2 \times 2$ : C appartient aux deux triangles.

Attention — (M⁴)ᵢᵢ compte aussi les allers-retours : ce n’est pas un nombre de cycles.

Cas 5 · Distance et connexité

Réflexe — distance = première puissance de M dont le coefficient (i ; j) n’est pas nul ; connexité : M + … + Mⁿ⁻¹ sans zéro hors diagonale.

Exemple. Question type : « Déterminer d(2 ; 1). » Exemple : graphe orienté d’arcs $1 \to 2$ , $2 \to 3$ , $3 \to 4$ , $4 \to 1$ , $1 \to 3$ .

Ligne $2$ : $(0 0 1 0)$ dans $M$ , $(0 0 0 1)$ dans $M^{2}$ , $(1 0 0 0)$ dans $M^{3}$ . Le coefficient $(2; 1)$ vaut $0$ , $0$ puis $1$ .

Donc $d (2; 1) = 3$ , par $2 \to 3 \to 4 \to 1$ . Le raccourci $1 \to 3$ ne sert pas : il part de $1$ .

Attention — (M³)ᵢⱼ > 0 ne suffit pas pour une distance de 3 : il faut que M et M² donnent 0.

Les pièges

Ligne = départ, colonne = arrivée ; l’ordre des sommets est toujours écrit.
Somme totale = 2m seulement si le graphe n’est pas orienté.
Mᵏ compte tous les chemins, même ceux qui repassent par un sommet.
Trace de M³ : diviser par 6 pour les triangles, par 3 pour les circuits orientés.
Distance : vérifier les puissances inférieures dans l’ordre.
Connexité d’un graphe d’ordre n : aller jusqu’à Mⁿ⁻¹.

Ce document est la propriété intellectuelle de Ben, professeur particulier (benprofparticulier.fr), protégée par le Code de la propriété intellectuelle (art. L. 111-1 et L. 122-4). Il est mis à disposition pour un usage personnel de révision. Toute reproduction, diffusion, mise en ligne ou revente, totale ou partielle, sans autorisation écrite est interdite et constitue une contrefaçon (art. L. 335-2).

2 / 2

À propos de cette page

Cette fiche méthode donne la démarche face à une matrice d’adjacence, puis un exemple rédigé par cas : écrire la matrice d’un graphe orienté, lire degrés et nombre d’arêtes, calculer un coefficient de M³ par un produit ligne × colonne, compter les triangles avec la diagonale de M³, trouver une distance.

Bloqué sur ce chapitre ?

Moi c'est Ben, j'ai créé ce site pour aider le plus d'élèves possible, partout en France. Je peux aussi reprendre avec toi ce qui coince en cours particulier : en visio, ou à domicile si tu es à Marseille.

Réserver un 1^er cours → Voir les tarifs

Soutien scolaire à Marseille · Cours particuliers au collège · Aide aux devoirs