Annales gratuites Bac ES : Plan de ville

(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é.
1. Répondre sans justification aux quatre questions suivantes :
a. Ce graphe est-il connexe ?
b. Ce graphe est-il complet ?
c. Ce graphe admet-il une chaîne eulérienne ?
d. Ce graphe admet-il un cycle eulérien ?

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

I - L'ANALYSE DU SUJET

Utilisation des graphes pour déterminer un trajet.

II - LES NOTIONS DU PROGRAMME

● Graphe complet, connexe,
● chaîne eulérienne,
● nombre chromatique.

III - LES OUTILS : SAVOIRS ET SAVOIR-FAIRE

Savoir utiliser l'algorithme.

IV - LES RESULTATS

I.
1.
a. Oui.
b. Non.
c. Non.
d. Oui.

2. δ = 4

II. ACEFG comporte 7 feux.

V - LES RESULTATS COMMENTES ET DETAILLES

Partie I :

1.
a. Tout couple de sommets est relié par une chaîne donc le graphe est connexe.
b. Il n'y a pas d'arête entre les sommets A et E donc le graphe n'est pas complet.
c.

Le graphe est connexe et deux de ses sommets ont des degrés impairs donc il contient une chaîne eulérienne.
d. Non, car deux de ses sommets ont des degrés impairs.

2. Soit δ le nombre chromatique, on a:
δ ≥ 4 car CDEF est un sous graphe complet de degré 4.
δ ≤ 6 car le degré maximum est 5.
On peut trouver une coloration à 4 couleurs:
GG
DA
E
FB
donc δ = 4

Partie II :

On utilise l'algorithme de Dijkstra :

Le trajet comporter au minimum 7 feux :  ACEFG