Exercice 3

Sujet

Le plan d'un bâtiment comportant douze salles se présente de la façon suivante :

Le réseau informatique existant est quelque peu désordonné et de ce fait, nécessite de relier les ordinateurs en « poste à poste». Il a les caractéristiques suivantes :

Des prises (symbolisées par des lettres) sont installées dans toutes les salles et toutes les prises sont opérationnelles sauf les prises B et H que l'on vient d'installer respectivement dans les salles 2 et 8 , salles que l'on souhaite connecter entre elles.

• Des gaines contenant des câbles relient entre elles certaines salles de classes par les faux-plafonds ou par le sous-sol. Dans l'état actuel des choses, les salles 1 et 3 sont reliées et on note AC (ou bien \(\mathrm{CA})\) la liaison existante. De même, existent et fonctionnent les liaisons \(\mathrm{AD}, \mathrm{AF}, \mathrm{CD}, \mathrm{CF}, \mathrm{DE}, \mathrm{DI}\), EF, EK, GI, GL, IJ, JK, KL.
• Pour l'instant, les salles 2 et 8 ne sont connectées à aucune autre. Afin de les connecter entre elles, on va devoir faire passer de nouveaux câbles dans des gaines existantes. De plus, on ne peut raccorder directement la prise B qu'à la prise A ou bien à la prise C . De même, on ne peut raccorder la prise H qu'à la prise G ou bien à la prise I .

Une entreprise a évalué le coût (main d'œuvre et fourniture) de chaque liaison intermédiaire pour le passage de nouveaux câbles :

Quel chemin choisir pour relier les salles 2 et 8 afin d'effectuer les travaux à moindre coût? Quel serait alors le montant des travaux?