Exercice 2: Théorie des graphes
Une entreprise de distribution de produits laitiers et qui approvisionne un ensemble de villes
A, B, C, DE, F, G, H, I, J désire acheminer des marchandises
dans ces villes en partant de A à
J.
Les distances (en km) séparant les villes et les coûts de transport (en FCFA) au km pour
acheminer les marchandises d'une ville à l'autre sont fournies par le tableau ci-
dessous.
7ABCDEFGH IJ
ABCDEFGH
95/14 61/12 220/18.
119/20
151/8
55/18
105/18
250/12
50/18 70/10 279/18
35/10
70/20
145/8
113/10
40/18
-
Légende
Distance
Coût
1)
a) Etablir le dictionnaire des suivants et des précédents.
b) Déterminer le niveau de chaque sommet.
c) Tracer le graphe par niveau correspondant à ce problème.
d) Déterminer le chemin le plus court reliant A à J.
2) On suppose qu'il y a un pont à péage de 1000F au point D et un autre à 500f au point H.
a) Quel est le coût total de transport correspondants à ce chemin le plus court?
b) Quel est l'itinéraire qui minimise le coût the transport de A à J? Quel est ce coût?