0%

Problème 107

Énoncé:

Le réseau non orienté suivant est composé de sept sommets et de douze arêtes dont le poids total est de $243$.

Le même réseau peut être représenté par la matrice ci-dessous.

A B C D E F G
A - 16 12 21 - - -
B 16 - - 17 20 - -
C 12 - - 28 - 31 -
D 21 17 28 - 18 19 23
E - 20 - 18 - - 11
F - - 31 19 - - 27
G - - - 23 11 27 -

Il est toutefois possible d'optimiser le réseau en supprimant certaines arêtes tout en veillant à ce que tous les points du réseau restent connectés. Le réseau qui permet de réaliser le maximum d'économies est présenté ci-dessous. Il a un poids de $93$, ce qui représente une économie de $243 - 93 = 150$ par rapport au réseau d'origine.

À l'aide de network.txt (clic droit "Enregistrer le lien sous..."), un fichier texte de 6 Ko contenant un réseau de quarante sommets, et présenté sous forme de matrice, trouvez l'économie maximale qui peut être réalisée en supprimant les arêtes redondantes tout en veillant à ce que le réseau reste connecté.

Lien du problème originel