Centres étrangers 1 – juin 2003
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 :
Donner la matrice M associée au graphe G.
On donne la matrice M6 :
On s’intéresse aux chemins partant de l’entrepôt A et se terminant en A.
Combien existe-t-il de chemins de longueur 6 reliant A à A ?
Citer ces chemins.
Parmi ceux qui passent par tous les sommets du graphe, lequel minimise le temps de parcours ?
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