Un groupe de skieurs décide de pratiquer le ski sur un circuit modélisé par le graphe (5) ci-contre:

8

g

Chaque sommet représente une station du cir- cuit.

10

Chaque arête représente une piste entre deux stations.

16

5

Sur chaque arête, on a noté la durée du par- cours estimée en minutes entre deux stations

18

B

12

(e)

1a Recopier et compléter le tableau suivant

Sommet

UN

B

D

C

ET

F

g

14

2

Degré

3

b Justifier que le graphe (5) admet au moins une chaine culérienne.

c. Déterminer un encadrement du nombre chromatique y de (4), puis sa valeur.

2 a En utilisant l'algorithme de Dijkstra déterminer la plus courte chaine allant du sommet A au sommet D

b Les skieurs ont programmé de se regrouper au sommet D à 17 heures pour prendre le même bus. Sachant que l'un d'entre eux est au sommet A à 16 heure 36 minutes, pourrait-il rejoindre le groupe à l'heure? Si oui identifier le parcours qu'il doit emprunter.