Graphes Algorithme de Dijkstra - Bac ES Métropole 2009
Exercice 2
5 points-Pour les candidats ayant suivi l'enseignement de spécialité
Le graphe ci-dessous représente le plan d'une ville.
Le sommet A désigne l'emplacement des services techniques.
Les sommets B, C, D, E, F et G désignent les emplacements de jardins publics. Une arête représente l'avenue reliant deux emplacements et est pondérée par le nombre de feux tricolores situés sur le trajet.
Les parties I et II sont indépendantes.
Partie I
On s'intéresse au graphe non pondéré.
Répondre sans justification aux quatre questions suivantes :
Ce graphe est-il connexe ?
Ce graphe est-il complet ?
Ce graphe admet-il une chaîne eulérienne ?
Ce graphe admet-il un cycle eulérien ?
Déterminer, en justifiant, le nombre chromatique de ce graphe.
Partie II
On s'intéresse au graphe pondéré.
Proposer un trajet comportant un minimum de feux tricolores reliant A à G.
La réponse sera justifiée par un algorithme.
Corrigé
Partie 1
Le graphe est connexe car pour toute paire de sommets, il existe une chaîne reliant ces sommets.
Le graphe n'est pas complet car les points A et D (par exemple) ne sont pas relié par une arête.
D'après le théorème d'Euler, le graphe admet une chaîne eulérienne. En effet, il n'existe que deux sommets de degré impair(C et D)
D'après le théorème d'Euler, le graphe n'admet pas de cycle eulérien. Il faudrait pour cela qu'il n'existe aucun sommet de degré impair
BCDE forme un sous-graphe complet. Le nombre chromatique du graphe est donc supérieur ou égal à 4.
On peut colorier le graphe avec 4 couleurs de la façon suivante (par exemple) :
rouge: A, D
bleu: B, F
vert: C, G
jaune: ELe nombre chromatique du graphe est donc 4.
Partie 2
On utilise l'algorithme de Dijkstra :
| A | B | C | D | E | F | G |
| 0 | 2 (A) | 1 (A) | ||||
| 2 (A) | 5 (C) | 4 (C) | 6 (C) | |||
| 3 (B) | 4 (C) | 6 (C) | ||||
| 4 (C) | 6 (C) | 8 (D) | ||||
| 5 (E) | 8 (D) | |||||
| 7 (F) |