É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