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é.

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

1.

a.Le graphe est connexe car pour toute paire de sommets, il existe une chaîne reliant ces sommets.

b.Le graphe n'est pas complet car les points A et D (par exemple) ne sont pas relié par une arête.

c.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.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

2.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)
	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)

Le trajet ACEFG comporte le nombre minimum de 7 feux.