Matrices et graphes • Plus court chemin
Corrigé
36
Ens. de Spécialité
matT_1306_01_04C
Afrique • Juin 2013
Exercice 2 • 5 points
Dans le graphe ci-dessous, les sommets représentent différentes zones de résidence ou d'activités d'une municipalité. Une arête reliant deux de ces sommets indique l'existence d'une voie d'accès principale entre deux lieux correspondants.
associée au graphe (les sommets seront mis dans l'ordre alphabétique). (0,5 point)
.
Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant 
et 
, puis donner leur liste. (1 point)
Ce même candidat se trouve à la mairie (
) quand on lui rappelle qu'il a un rendez-vous avec le responsable de l'hôpital situé en zone G.
Durée conseillée : 45 min.
Les thèmes en jeu
Graphe pondéré • Matrice associée à un graphe • Chaîne de longueur donnée • Chaîne eulérienne.
Les conseils du correcteur
donnent le nombre de chemins de longueur 3 entre deux sommets donnés.
> 1. Déterminer le degré des sommets d'un graphe
| Sommet | A | B | C | D | E | F | G |
| Degré | 2 | 4 | 5 | 5 | 4 | 4 | 2 |
Notez bien
Sur la diagonale de M, tous les termes sont égaux à 0 car le graphe ne comporte aucune boucle.
> 2. a) Déterminer la matrice associée à un graphe
b) Déterminer le nombre de chemins de longueur donnée entre deux sommets d'un graphe
Le nombre de chemins de longueur 3, c'est-à-dire formés de 3 arêtes, reliant A (premier sommet) à F (sixième sommet dans l'ordre alphabétique) est le coefficient de 
situé sur la première ligne et la sixième colonne, égal au coefficient situé sur la sixième ligne et la première colonne.
Ce nombre est égal à 5, donc
Ces chemins sont :
Info
Un tel chemin est par exemple :
CBACEBDCFEDFGD
(le graphe comporte 13 arêtes).
Il n'existe pas de parcours partant et arrivant au même sommet et passant une fois et une seule par chacune des voies.
> 3. Déterminer si un graphe possède une chaîne eulérienne
Un parcours empruntant une fois et une seule chacune des voies est une chaîne eulérienne du graphe.
On a vu à la question
Il est donc possible de parcourir
> 4. a) Rechercher sur un graphe pondéré un chemin de durée minimale
On utilise l'algorithme de Dijkstra pour déterminer le chemin le plus rapide de A à G. Cet algorithme peut se traduire par le tableau suivant :
| A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
|
| 8 (A) | 4 (A) | ∞ | ∞ | ∞ | ∞ |
|
| 8 (A) |
| 20 (C) | 16 (C) | 24 (C) | ∞ |
|
|
|
| 12 (B) | 16 (C) | 24 (C) | ∞ |
|
|
|
|
| 16 (C) | 24 (C) | 32 (D) |
|
|
|
|
|
| 20 (E) | 32 (D) |
|
|
|
|
|
|
| 28 (F) |
Le chemin le plus rapide de A à G est donc :
b) Déterminer la durée d'un trajet sur un graphe
Notez bien
Ce trajet est formé de quatre arêtes. Il existe des trajets de A à G formés de trois arêtes (par exemple A – B – D – G), mais leur durée est supérieure à 28 minutes.
Pour trouver la durée de ce parcours, on additionne les durées des différents trajets.