Graphes, « plus court chemin »
matT_1405_02_09C
Ens. de spécialité
33
CORRIGE
Amérique du Nord • Mai 2014
Exercice 4 • 5 points
Lors d’une campagne électorale, un homme politique doit effectuer une tournée dans les villes A, B, C, D, E, F, G et H, en utilisant le réseau autoroutier. Le graphe 
ci-dessous représente les différentes villes de la tournée et les tronçons d’autoroute reliant ces villes (une ville est représentée par un sommet, un tronçon d’autoroute par une arête) :
partie a
est :
la matrice d’adjacence associée au graphe 
(les sommets étant pris dans l’ordre alphabétique).
. (0,5 point)
.
Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant E à H.
Préciser ces chemins. (1 point)
partie b
Des contraintes d’organisation obligent cet homme politique à se rendre dans la ville F après la ville A.
Le graphe 
est complété ci-dessous par les longueurs en kilomètre de chaque tronçon d’autoroute.
Déterminer, en utilisant l’algorithme de Dijkstra, le trajet autoroutier le plus court pour aller de A à F. Préciser la longueur en kilomètre de ce trajet. (1,25 point)
Les thèmes en jeu
Matrice • Graphe pondéré • Chaîne de longueur donnée • Chaîne eulérienne • Plus court chemin.
Les conseils du correcteur
Partie A
est égal au nombre de chemins de longueur 3 entre deux sommets donnés.
partie a
> 1. a) Déterminer si un graphe est complet
Il n’existe pas d’arête entre les sommets A et E (les villes A et E ne sont pas reliées par un tronçon d’autoroute).
b) Déterminer si un graphe est connexe
Deux sommets quelconques sont reliés par une arête ou par une chaîne ; il n’existe pas de sommet « isolé », on peut aller d’une ville à une autre en empruntant un ou plusieurs tronçons d’autoroute.
> 2. a) Déterminer si un graphe possède une chaîne eulérienne
Il est possible d’organiser la tournée en passant au moins une fois par chaque ville, et en empruntant une fois et une seule chaque tronçon d’autoroute si et seulement si le graphe possède une chaîne eulérienne.
D’après le théorème d’Euler, un graphe connexe possède une chaîne eulérienne si et seulement si le nombre de sommets de ce graphe de degré impair (c’est-à-dire extrémités d’un nombre impair d’arêtes) est égal à 0 ou 2. On peut résumer dans un tableau les degrés des différents sommets :
|
Sommet |
A |
B |
C |
D |
E |
F |
G |
H |
|
Degré |
2 |
3 |
4 |
3 |
4 |
2 |
4 |
4 |
Notez bien
Une chaîne eulérienne peut passer plusieurs fois par le même sommet.
Il y a exactement deux sommets de degré impair, B et D, donc le graphe possède une chaîne eulérienne.
b) Citer une chaîne eulérienne d’un graphe
Une chaîne eulérienne a nécessairement comme extrémités B et D, qui sont les deux sommets de degré impair.
Un exemple de trajet qui passe au moins une fois par chaque ville et emprunte une fois et une seule chaque tronçon d’autoroute est :
> 3. a) Déterminer la matrice d’adjacence d’un graphe
Notez bien
Le coefficient situé à l’intersection de la ligne 
et la colonne 
de 
est égal à 0 s’il n’y a pas d’arête d’extrémités les sommets 
et 
, à 1 s’il y en a une.
La matrice d’adjacence du graphe est :
b) Déterminer le nombre de chemins de longueur donnée entre deux sommets
Les sommets (c’est-à-dire les villes de la tournée) sont rangés dans l’ordre alphabétique, donc E est le sommet numéro 5 et H le sommet numéro 8.
Le nombre de chemins de longueur 3 reliant E à H est donc le coefficient de la matrice 
situé à l’intersection de la ligne 5 et de la colonne 8 (ou de la ligne 8 et de la colonne 5), c’est-à-dire 4.
On en déduit qu’
Ces chemins sont :
partie b
Déterminer un plus court chemin sur un graphe et calculer sa longueur
Pour trouver le chemin le plus court du sommet A au sommet F, on utilise l’algorithme de Dijkstra, qui peut se résumer par le tableau ci-dessous :
|
A |
B |
C |
D |
E |
F |
G |
H |
|
0 |
400 (A) |
∞ |
600 (A) |
∞ |
∞ |
∞ |
∞ |
|
|
|
1 000 (B) |
600 (A) |
800 (B) |
∞ |
∞ |
∞ |
|
|
|
1 000 (B) |
|
800 (B) |
∞ |
∞ |
1 500 (D) |
|
|
|
1 000 (B) |
|
|
∞ |
1 400 (E) |
1 500 (D) |
|
|
|
|
|
|
∞ |
1 400 (E) |
1 450 (C) |
|
|
|
|
|
|
1 600 (G) |
|
1 450 (C) |
|
|
|
|
|
|
1 600 (G) |
|
|
Le chemin le plus court du sommet A au sommet F est donc :
Sa longueur est