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 questionsFigure fournieCorrigé 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 Idée : $m_{ij}=1$ si $i$ et $j$ sont adjacents, $0$ sinon ; matrice symétrique, diagonale nulle. $M=\begin{pmatrix}0&1&1&1\\1&0&1&0\\1&1&0&1\\1&0&1&0\end{pmatrix}$ .

A.2 Idée : $(M^2)_{ij}=\sum_k m_{ik}m_{kj}$ compte les sommets $k$ voisins à la fois de $i$ et de $j$ . $(M^2)_{A,C}=m_{AB}m_{BC}+m_{AD}m_{DC}=1+1=2$ : deux chaînes de longueur $2$ de $A$ à $C$ , $A-B-C$ et $A-D-C$ (le calcul complet donne $M^2=\begin{pmatrix}3&1&2&1\\1&2&1&2\\2&1&3&1\\1&2&1&2\end{pmatrix}$ ; la diagonale redonne les degrés).

B.1 Idée : Dijkstra ouvre à chaque étape le sommet provisoire le plus proche et met à jour ses voisins. Départ $d(S)=0$ , les autres à $+\infty$ . Ouvrir $S$ : $d(P)=4$ , $d(Q)=6$ . Ouvrir $P$ ( $4$ ) : $d(T)=4+5=9$ ; $d(Q)$ reste $6$ car $4+3=7>6$ . Ouvrir $Q$ ( $6$ ) : $d(T)=\min(9,\,6+2)=8$ . Ouvrir $T$ ( $8$ ) : terminé.

B.2 Idée : remonter les prédécesseurs. $T$ a été atteint via $Q$ , $Q$ via $S$ : le plus court chemin est $S-Q-T$ , de durée $\boxed{8\ \text{min}}$ ; passer par $P$ coûterait $9$ min.

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. Idée : produit ligne par colonne. $M^2=\begin{pmatrix}1&0&1\\1&0&0\\0&1&1\end{pmatrix}$ (par exemple $(M^2)_{A,A}=m_{AC}m_{CA}=1$ : le circuit $A\to C\to A$ ).

2. Idée : lire ligne $A$ , colonne $C$ . $(M^2)_{A,C}=m_{AB}m_{BC}+m_{AC}m_{CC}=1+0=1$ : une seule chaîne orientée de longueur $2$ , $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. Idée : Dijkstra depuis $A$ . $d(A)=0$ ; ouvrir $A$ : $d(B)=2$ , $d(C)=5$ ; ouvrir $B$ : $d(C)=\min(5,\,2+2)=4$ ; ouvrir $C$ : fin. $d(C)=4$ .

2. Idée : le détour est plus court que l'arête directe. Plus court chemin $A-B-C$ (durée $4$ ) ; l'arête directe $A\to C$ vaut $5$ .

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.