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.

ÉPREUVE DE MATHÉMATIQUES corrigé Série STG - Profmath55 Annales officielles. SUJETS ? CORRIGÉS. BAC+2 admission en 1re année d'?ESC. BAC+3/4 The Economist Global Executive, December 4th, 2003. Text 2: Faire des exercices simples et les annales du concours en temps limité. ? Bien lire 
Corrige complet du bac ES Mathématiques Spécialité - Sujet de bac Nous avons cette année ajouté des corrigés : ils sont réalisés bénévolement par les collègues sous leur responsabilité. Bureau des enseignements post-?baccalauréat DLC5. Arrêté portant Les sujets comportent : deux exercices de.
Mathématiques Annales 2003 - ARPEME 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
CORRECTION SUJET NATIONAL ? BAC S - 2003 B) CORRECTION 0 ? x ?2002 et ax ? b [2003]. Exercices de spécialité. 75. Page 76. A. P. M. E. P.. Baccalauréat S.
Baccalauréat S 2003 L'intégrale de septembre 2002 à juin 2003 2) Analyser l'erreur commise dans l'exercice 2 et donner une correction. Exprimer les mesures des angles ABO, BAC, ACB, CBD et ODC en fonction de .
Corrigé du baccalauréat Métropole S septembre 2003 - Apmep Baccalauréat S Antilles?Guyane septembre 2003. EXERCICE 1. 5 points. Une association organise des promenades en montagne. Douze guides emmènent.
Corrigé du baccalauréat S Centres étrangers juin 2003 - Apmep CORRECTION SUJET NATIONAL ? BAC S - 2003. Enseignement obligatoire , juin 2003. B) CORRECTION de l' EXERCICE 2 : Partie Obligatoire (candidats 
Sujet et Corrigé Baccalauréat S Liban 2003 LIBAN BACCALAUREAT S 2003 Retour vers l'accueil. Exercice 1 : Commun à tous les candidats. Une urne contient 4 boules noires et 2 boules blanches.
Programmation avancée en Java - Travaux dirigés – Corrigés Programmation avancée en Java - Travaux dirigés ? Corrigés. ? Par Dr. Samia Description : Formation Java Pratique - Exercices. * Copyright : * Société : DR.
QCM de Java corrigé - Irif QCM de Java corrigé. 1. Java est un langage. (a). Compilé. (b). Interprété. (c). Compilé et interprété. (d). Ni compilé ni interprété. Le compilateur compile le code 
TD n 5 - Correction - Normalesup.org Exercice 1 (Valeurs et références, surcharge). Qu'affiche le programme suivant ? 1 class A{. 2 private int val=0;. 3. 4 public static void incremente( int a){. 5 a++;.
Corrigé du TD de Java n°2 Dans cette partie, il faut réfléchir aux entêtes de certaines fonctions (quelles seront les paramètres de la fonction) et à leur valeur de retour. C'est un exercice?