Graphes
Corrigé
44
Ens. de spécialité
matT_1200_14_06C
D'après Pondichéry • Avril 2012
Exercice 2 • 5 points
Les points de collecte d'un camion d'une société recyclant des « déchets papier », ainsi que les temps de trajet (en minutes) entre ces différents points, sont représentés par le graphe n° 1.
Le dépôt est représenté par le sommet A et les autres sommets représentent les différents points de collecte.

Combien y a-t-il de trajets possibles permettant d'aller du dépôt A au point de collecte H en quatre étapes ? Justifier la réponse. (1 point)

Durée conseillée : 45 min.
Les thèmes en jeu
Matrice associée à un graphe • Graphes pondérés • Chaînes de longueur donnée.
Les conseils du correcteur
> 1. Déterminer s'il est possible de colorier un graphe avec un nombre donné de couleurs
Puisque les quatre sommets A, B, C et D sont deux à deux reliés, il faut au moins quatre couleurs pour colorer les sommets du graphe de manière à ce que deux sommets adjacents n'aient jamais la même couleur.
> 2. Déterminer sur un graphe le nombre de trajets comportant un nombre donné d'étapes pour aller d'un point à un autre
Le nombre de trajets permettant d'aller du point A au point H en quatre étapes est le coefficient situé à l'intersection de la première ligne et de la huitième colonne de la matrice M4.
Ce coefficient est égal à 9.
> 3. Rechercher sur un graphe pondéré un chemin de longueur minimale
Pour déterminer un chemin qui minimise le temps de trajet de A à H, on utilise l'algorithme de Dijkstra :
A | B | C | D | E | F | G | H |
|
---|---|---|---|---|---|---|---|---|
0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A |
0 (A) | 3 (A) | 7 (A) | 11 (A) | ∞ | ∞ | ∞ | ∞ | B |
| 3 (A) | 6 (B) | 10 (B) | 14 (B) | ∞ | ∞ | ∞ | C |
|
|
| 10 (B) | 9 (C) | ∞ | ∞ | ∞ | E |
|
|
| 10(B) |
| 17 (E) | 19 (E) | ∞ | D |
|
|
| 10(B) |
| 17 (E) | 12(D) | ∞ | G |
|
|
|
|
| 16 (G) | 12 (D) | 24 (G) | F |
|
|
|
|
| 16 (G) |
| 23(F) | H |
|
|
|
|
|
|
| 23(F) |
|
Certaines questions ont été modifiées ou remplacées pour adapter le sujet au nouveau programme.