Exercice corrigé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: E
Le 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) | \infty | \infty | \infty | \infty |
| 2 (A) | 5 (C) | 4 (C) | 6 (C) | \infty | ||
| 3 (B) | 4 (C) | 6 (C) | \infty | |||
| 4 (C) | 6 (C) | 8 (D) | ||||
| 5 (E) | 8 (D) | |||||
| 7 (F) |
Le trajet ACEFG comporte le nombre minimum de 7 feux.