Centres étrangers I ? Série ES ? Juin 2003 - Exercice Un livreur d ...

PanaMaths [ 1 - 5 ] Novembre 2005
Centres étrangers I - Série ES - Juin 2003 - Exercice
Un livreur d'une société de vente à domicile doit, dans son après-midi,
charger son camion à l'entrepôt noté A, livrer cinq clients que nous
noterons B, C, D, E et F puis retourner à l'entrepôt.
Le réseau routier, tenant compte des sens de circulation, et les temps
de parcours (en minutes) sont indiqués sur le graphe G suivant :

1. Donner la matrice M associée au graphe G.
2. On donne la matrice 6
M :

6
866346
19 11 12 9 6 16
36 28 23 22 18 34
M
37 24 25 17 15 31
15 12 9 10 8 15
28 22 19 15 15 26

On s'intéresse aux chemins partant de l'entrepôt A et se terminant en
A.
a. Combien existe-t-il de chemins de longueur 6 reliant A à A ?
b. Citer ces chemins. E
A D
F
B
C 4
4
9
6
3
2
2
2 6
6 3
3
9
PanaMaths [ 2 - 5 ] Novembre 2005
c. Parmi ceux qui passent par tous les sommets du graphe, lequel
minimise le temps de parcours ?
d. Quelle conséquence peut tirer le livreur du dernier résultat ?
Au départ de sa tournée, le livreur a choisi de suivre l'itinéraire le
plus rapide. Malheureusement le client C n'est pas présent au
passage du livreur et celui-ci décide de terminer sa livraison par ce
client. Indiquer quel est le chemin le plus rapide pour revenir à
l'entrepôt A à partir de C. La réponse devra être justifiée.

PanaMaths [ 3 - 5 ] Novembre 2005
Analyse

Cet exercice sur les graphe propose, pour le graphe connexe considéré, deux problèmes de
cheminement : recherche de cycle de longueur 6 de A à A (question 2.a. et 2.b.), cycle de
longueur 6 de A à A de longueur minimale (question 2.c. et 2.d.) et détermination d'un plus
court chemin (3
ème
question).


Résolution

Question 1.

En tenant soigneusement compte des orientations des arêtes et en considérant les sommets du
graphe dans l'ordre alphabétique, on obtient :

000010
100001
010101M=101001
000100
111000


Question 2.a.

Le nombre de chemins de longueur 6 reliant A à A est directement donné par l'élément de
6
M situé à l'intersection de la première ligne et de la première colonne.

Il y a 8 chemins de longueur 6 reliant A à A.


Question 2.b.

La seule arête issue de A conduit au sommet E.
La seule arête issue de E conduit au sommet D.

Déterminer tous les chemins de longueur 6 reliant A à A revient donc à déterminer tous les
chemins de longueur 4 reliant D à A. On obtient :

D-A-E-D-A D-F-B-F-A
D-C-B-F-A D-F-C-B-A
D-C-F-B-A D-F-C-D-A
D-C-D-F-A D-F-C-F-A

PanaMaths [ 4 - 5 ] Novembre 2005


Les 8 chemins de longueur 6 reliant A à A sont donc :

A-E-D-A-E-D-A A-E-D-F-B-F-A
A-E-D-C-B-F-A A-E-D-F-C-B-A
A-E-D-C-F-B-A A-E-D-F-C-D-A
A-E-D-C-D-F-A A-E-D-F-C-F-A



Question 2.c.

Parmi les chemins précédents, trois passent par tous les sommets du graphe :
A-E-D-C-B-F-A, A-E-D-C-F-B-A et A-E-D-F-C-B-A.

Les longueurs de ces chemins sont :

Chemin A-E-D-C-B-F-A :
44293628
Chemin A-E-D-C-F-B-A :
44263221
Chemin A-E-D-F-C-B-A :
44369228

Le plus court des trois chemins est donc le chemin A-E-D-C-F-B-A.
Le temps de parcours correspondant est de 21 minutes.


Question 2.d.

On déduit de la question précédente :

Le chemin A-E-D-C-F-B-A est le chemin de durée minimale
(21 minutes) permettant au
livreur d'effectuer sa tournée complète (départ de A, livraison des clients B, C, D, E, F
et, enfin, retour en A).


Question 3.d.

Le problème ici consiste à trouver le parcours de durée minimale reliant C à A.
Nous allons utiliser l'algorithme de Dijkstra.

Dans le tableau suivant, les plus courtes distances du sommet de départ (C) aux différents
sommets sont indiquées en gras (par exemple, la plus courte distance du sommet C au sommet
F vaut 5 et on arrive en F par le sommet D).

PanaMaths [ 5 - 5 ] Novembre 2005

C B D E F A
0
9 (C) 2 (C) 6 (C)
9 (C) 2 (C) 6 (C)
9 (C) 5 (D) 11 (D)
9 (C) 5 (D) 11 (D)
8 (F) 11 (F)
8 (F) 11 (F)
10 (B)
10 (B)


D'après le tableau obtenu ci-dessus, on peut affirmer que le parcours le plus court de C à A
correspond à une durée totale de 10 minutes.

Pour ce qui est des sommets :
On arrive en A à partir de B ;
On arrive en B à partir de F ;
On arrive en F à partir de D ;
On arrive en D à partir de C.

La chaîne la plus courte est la chaîne : C-D-F-BA.

L'agent de sécurité devra emprunter le chemin C-D-F-B-A pour que la durée de son
parcours de C à A soit la plus faible. Cette durée est de 11 minutes.