Der folgende ungerichtete Graph besteht aus sieben Knoten und zwölf Kanten mit einem Gesamtgewicht von 243.


Der selbe Graph kann mit folgender Matrix dargestellt werden.

    ABCDEFG
A-161221---
B16--1720--
C12--28-31-
D211728-181923
E-20-18--11
F--3119--27
G---231127-

Jedoch ist es möglich, den Graphen zu minimieren, indem man einige Kanten entfernt und dabei sicherstellt, dass alle Knoten im Graphen verbunden bleiben. Der Graph, der maximale Einsparung erzielt, ist unten angezeigt. Er hat ein Gewicht von 93, was eine Einsparung von 243 − 93 = 150 im Vergleich zum ursprünglichen Graphen zeigt.


Benutzen Sie network.txt (Rechtsklick und 'Ziel speichern unter...'), eine 6K Textdatei, die einen Graphen mit vierzig Knoten gegeben in Matrix-Form enthält, und finden Sie die maximale Einsparung, die durch Entfernen überflüssiger Kanten erreicht werden kann, wobei sichergestellt werden muss, dass der Graph verbunden bleibt.

Diese Aufgabe auf projecteuler.net