GR-CThéorie des graphes

Matrice d'adjacence, chemins de longueur n et plus court chemin (Dijkstra)

Idée directrice

Deux lectures complémentaires du graphe Eco-Gestion : (1) la matrice associée (d'adjacence) dont les puissances comptent les chaînes de longueur $n$ ; (2) l'algorithme de Dijkstra pour le plus court chemin dans un graphe valué. Attesté 2018–2022 (Dijkstra en contrôle 2022).

Signature de reconnaissance — l'énoncé se trahit ainsi

« matrice M associée à ce graphe »

« chaînes de longueur n reliant … »

« algorithme de Dijkstra » / « plus court chemin »

Sujet principal

Exercice — matrice d'adjacence et plus court chemin

4 questionsCorrigé masqué

Partie A. Soit le graphe non orienté $G$ de sommets $A,B,C,D$ (dans cet ordre) et d'arêtes $AB,BC,CD,DA,AC$ .

Écrire la matrice associée $M$ (matrice d'adjacence) du graphe $G$ .
Calculer $(M^2)_{A,C}$ . Combien de chaînes de longueur $2$ relient $A$ à $C$ ? Citer les exemples.

Partie B. Un livreur part de l'entrepôt $S$ vers le client $T$ sur le graphe valué dont les arêtes et durées (minutes) sont : $S\xrightarrow{4}P$ , $S\xrightarrow{6}Q$ , $P\xrightarrow{3}Q$ , $P\xrightarrow{5}T$ , $Q\xrightarrow{2}T$ .

Appliquer l'algorithme de Dijkstra depuis $S$ et dresser le tableau des distances provisoires jusqu'à clôture de $T$ .
En déduire le plus court chemin de $S$ à $T$ et sa durée.

Voir la correction commentéeAprès avoir posé votre démarche

A.1. On pose la matrice associée (ordre $A,B,C,D$ ) : $M=\begin{pmatrix}0&1&1&1\\1&0&1&0\\1&1&0&1\\1&0&1&0\end{pmatrix}$ .

A.2. On pose $M^2=M\times M=\begin{pmatrix}3&1&2&1\\1&2&1&2\\2&1&3&1\\1&2&1&2\end{pmatrix}$ . On a : le coefficient $(M^2)_{A,C}$ vaut $2$ . Il y a donc deux chaînes de longueur $2$ reliant $A$ à $C$ : $A-B-C$ et $A-D-C$ .

B.1. On applique Dijkstra depuis $S$ :

• Initialisation : $d(S)=0$ , $d(P)=d(Q)=d(T)=+\infty$ .

• On ouvre $S$ : $d(P)=4$ , $d(Q)=6$ .

• On ouvre $P$ ( $4$ ) : $d(T)=\min(+\infty,4+5)=9$ ; $d(Q)$ reste $6$ car $4+3=7>6$ .

• On ouvre $Q$ ( $6$ ) : $d(T)=\min(9,6+2)=8$ .

• On ouvre $T$ ( $8$ ) : algorithme terminé pour $T$ .

B.2. On obtient $d(T)=8$ minutes. Le plus court chemin est $S-Q-T$ . L'algorithme de Dijkstra a mis à jour $T$ lors du passage par $Q$ .

Exercices d'entraînement — une nuance à la fois

Entraînement 01 / 02

Drill GR-C.1 — Lire M^3 pour compter des chaînes

2 questionsCorrigé masqué

Soit un graphe orienté dont la matrice associée $M$ (ordre $A,B,C$ ) est $M=\begin{pmatrix}0&1&1\\0&0&1\\1&0&0\end{pmatrix}$ .

Calculer $M^2$ .
Combien de chaînes orientées de longueur $2$ vont de $A$ vers $C$ ?

Voir la correction commentéeAprès avoir posé votre démarche

1. On pose $M^2=M\times M$ . On a : $M^2=\begin{pmatrix}1&0&1\\1&0&0\\0&1&1\end{pmatrix}$ .

2. On a : le coefficient ligne $A$ , colonne $C$ de $M^2$ vaut $1$ . Il y a donc une chaîne orientée de longueur $2$ de $A$ vers $C$ : $A\to B\to C$ .

Entraînement 02 / 02

Drill GR-C.2 — Plus court chemin sur un petit graphe valué

2 questionsCorrigé masqué

Sur le graphe valué de sommets $A,B,C$ : arêtes $A\xrightarrow{2}B$ , $A\xrightarrow{5}C$ , $B\xrightarrow{2}C$ .

Appliquer Dijkstra depuis $A$ pour obtenir $d(C)$ .
Quel est le plus court chemin de $A$ à $C$ ?

Voir la correction commentéeAprès avoir posé votre démarche

1. On pose $d(A)=0$ et $d(B)=d(C)=+\infty$ . On ouvre $A$ : $d(B)=2$ , $d(C)=5$ . On ouvre ensuite $B$ (distance $2$ ) : $d(C)=\min(5,2+2)=4$ . On obtient $d(C)=4$ minutes.

2. Le plus court chemin de $A$ à $C$ est $A-B-C$ (durée $4$ ). L'arête directe $A\xrightarrow{5}C$ est strictement plus longue. L'algorithme de Dijkstra a mis à jour $d(C)$ lors de l'ouverture du sommet $B$ .

Méthode / Automatismes

Ordonner les sommets avant d'écrire la matrice associée.
Le coefficient $(M^n)_{ij}$ compte les chaînes de longueur $n$ de $i$ vers $j$ .
Dijkstra : toujours ouvrir le sommet de distance provisoire minimale non encore fixé.

Pièges classiques

Compter les sommets au lieu des arêtes dans une chaîne de longueur $n$ . Réinitialiser Dijkstra à chaque étape. Oublier qu'un graphe non orienté a une matrice symétrique.