Graphes, « plus court chemin »
matT_1509_04_10C
Ens. de spécialité
34
Antilles, Guyane • Septembre 2015
Exercice 2 • 5 points
Graphe et itinéraires de pistes cyclables
Un cycliste désire visiter plusieurs villages notés A, B, C, D, E, F et G reliés entre eux par un réseau de pistes cyclables.
Le graphe suivant schématise son plan les arêtes représentent les pistes cyclables et les distances sont en kilomètre.
partie a
Pour faire son parcours, le cycliste décide qu'il procédera selon l'algorithme ci-dessous :
| ligne 1 | Marquer sur le plan tous les villages comme non « visités » | |
| ligne 2 | Choisir un village de départ | |
| ligne 3 | Visiter le village et le marquer « visité » | |
| ligne 4 | Rouler vers le village le plus proche | |
| ligne 5 | Tant que le village où il arrive n'est pas un village déjà visité | |
| ligne 6 ligne 7 | visiter le village et le marquer « visité » rouler vers le village le plus proche sans revenir en arrière | |
| ligne 8 | Fin Tant que | |
| ligne 9 | Afficher la liste des villages visités | |
▶ 1. Quelle propriété du graphe permet à la ligne 4 d'être toujours exécutable ? (0,5 point)
▶ 2. En partant du village noté G, quelle sera la liste des villages visités ? (0,5 point)
▶ 3. Existe-t-il un village de départ qui permette, en suivant cet algorithme, de visiter tous les villages ? (1 point)
▶ 4. Le cycliste abandonne l'idée de suivre l'algorithme. Il souhaite maintenant, partant d'un village, y revenir après avoir emprunté toutes les pistes cyclables une et une seule fois. Cela sera-t-il possible ? (1 point)
partie b
▶ 1. Écrire la matrice de transition de ce graphe (dans l'ordre A, B, C, … , G). (1 point)
▶ 2. On donne la matrice :
Interpréter le terme en gras, ligne A, colonne F (valant 1) dans le contexte de l'exercice. (1 point)
Les clés du sujet
Durée conseillée : 45 minutes
Les thèmes en jeu
Boucle avec arrêt conditionnel « Tant que » • Matrice • Graphe pondéré • Chaîne de longueur donnée • Chaîne eulérienne • Plus court chemin.
Les conseils du correcteur
Partie A
▶ 1. Justifiez et utilisez la connexité du graphe.
▶ 4. Utilisez le théorème d'Euler.
Partie B
▶ 2. Les coefficients de M4 donnent le nombre de chaînes de longueur 4 entre deux sommets.
Corrigé
partie a
▶ 1. Reconnaître et utiliser une propriété d'un graphe
Le graphe est connexe, donc à partir d'un village donné, il est toujours possible d'atteindre au moins un autre village.
Donc la ligne 4 du graphe est donc toujours exécutable.
▶ 2. Déterminer sur un graphe un trajet déterminé par un algorithme
En partant du village noté G et en suivant l'algorithme, le trajet du cycliste peut être décrit de la manière suivante :
de G, il va en B, qui est le village le plus proche
de B, il va en A car il ne peut pas revenir en G
de A, il va en F car il ne peut pas revenir en B
de F, il ne peut aller qu'en G car il ne peut pas revenir en arrière
dans l'exécution de l'algorithme, on sort alors de la boucle « Tant que » car le cycliste arrive dans un village déjà visité.
En suivant l'algorithme proposé et en partant du village noté G, la liste des villages successivement visités sera donc :
▶ 3. Déterminer un trajet passant par tous les sommets d'un graphe
On examine successivement tous les « points de départ » possibles d'un trajet déterminé en suivant l'algorithme.
Partant de A, le « circuit » serait :
A – B – G – E – D – G
partant de B : B – G – E – D – G
partant de C : C – D – E – G – B – A – F – G
partant de D : D – E – G – B – A – F – G
partant de E : E – D – G – B – A – F – G
partant de F : F – G – B – A – F
le cas du trajet partant de G a été étudié à la question précédente.
Il est possible, en suivant l'algorithme, de visiter tous les villages : il suffit de partir de C.
▶ 4. Déterminer si un graphe possède un cycle eulérien
Déterminer s'il existe un trajet partant d'un village et y revenant après avoir emprunté toutes les pistes cyclables une et une seule fois revient à déterminer si le graphe possède un cycle eulérien.
D'après le théorème d'Euler, un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair.
On a vu précédemment que la chaîne C – D – E – G – B – A – F contient tous les sommets du graphe, donc ce graphe est connexe. On peut résumer dans un tableau le degré de ses sommets :
| Sommet | A | B | C | D | E | F | G |
| Degré | 2 | 4 | 2 | 4 | 2 | 2 | 4 |
Tous les sommets sont de degré pair d'après le théorème d'Euler, le graphe admet un cycle eulérien.
Il existe donc un trajet partant d'un village et y revenant après avoir emprunté toutes les pistes cyclables une et une seule fois.
partie B
▶ 1. Écrire la matrice de transition d'un graphe
La matrice de transition du graphe donné est :
▶ 2. Interpréter un coefficient d'une puissance de la matrice de transition d'un graphe
Le terme (valant 1) situé ligne A, colonne F de la matrice est le nombre de chaînes de longueur 4 (c'est-à-dire formées de 4 arêtes) entre A et F.
Il existe donc une seule chaîne de longueur 4 entre le village A et le village F :
A – B – D – G – F.