Minimales Netzwerk

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

Das gleiche Netzwerk kann mit folgender Matrix dargestellt werden.

Jedoch ist es möglich, das Netzwerk zu optimieren, indem man einige Kanten entfernt und dabei sicherstellt, dass alle Punkte im Graphen verbunden bleiben. Das Netzwerk, das die größte Einsparung erreicht, ist unten gezeigt. Es hat ein Gewicht von 93, was eine Einsparung von 243 − 93 = 150 im Vergleich zum ursprünglichen Netzwerk darstellt.

Benutzen Sie network.txt (Rechtsklick und 'Link/Ziel speichern unter...'), eine 6K Textdatei, die ein Netzwerk 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 das Netzwerk verbunden bleibt.