Den Baum auf Kante schneiden

Gesucht war in der jüngsten Mathe-Aufgabe von Rainer Roos die kostengünstigste Lösung. Dabei mussten die Mathe-Freunde Kante zeigen, um einen Graphen in einen Baum zu verwandeln. Zauberei? Nein, alles Mathematik.

Sie erinnern sich der letzten Aufgabe? Ein Wahlversprechen der Ministerpräsidentin, schnelles Internet für alle, auch für die kleinsten Gemeinden, möglichst kostengünstig? Das mathematische Problem wurde an einem Beispiel beschrieben: Nehmen wir einmal an, es gehe um die Anbindung von fünf Gemeinden A, B, C, D, E. Eine davon hat schon einen superschnellen Internetzugang, egal welche.

In Bild 1 sind die möglichen Verbindungen eingezeichnet. Dies ist ein einfacher Graph. Die Gemeinden sind die Knoten, die Verbindungen die Kanten des Graphen. Die blauen Zahlen repräsentieren die Verbindungskosten in geeigneten Geldeinheiten (GE). Gesucht ist ein Verbindungssystem, das alle Gemeinden erfasst und möglichst wenig kostet. Ein solches System heißt ein minimaler spannender Baum. In Bild 2 sehen Sie einen solchen minimal spannenden Baum.

Die Gesamtkosten betragen acht GE, billiger geht es nicht. In diesem einfachen Fall sieht man sofort, dass dies eine Lösung ist. Und man sieht auch sofort: Keine Lösung kann eine geschlossene Kantenfolge wie zum Beispiel BCEB enthalten. Denn man könnte eine Kante wegnehmen, und es bliebe noch immer alles verbunden. Dies ist immer so.

Die konkrete Aufgabe war viel komplizierter. Sie sehen den Ausgangsgraphen in Bild 3, ein so genannter komplizierter Graph. Gesucht war ein minimaler spannender Baum für diesen Graphen. Bloßes Probieren ist aufwendig, nur mit viel Glück findet man eine Lösung. Besser ist systematisches Vorgehen.

Zur Lösung solcher Aufgaben wurden verschiedene Systematiken, Algorithmen , entwickelt. Die bekannteste wurde gleich drei Mal erfunden: 1930 von dem Tschechen Jarnik, 1957 von dem Amerikaner Prim und 1959 von dem Niederländer Dijkstra. Heute wird die Methode meistens nach Prim benannt.

Die Idee ist ganz einfach, wir beschreiben sie an unserer Aufgabe: Wähle als Startgraph einen beliebigen Knoten*. Irgendwo muss man ja anfangen, und jeder Knoten muss in der Lösung vorkommen. Dann werden Schritt für Schritt Kanten hinzugefügt. Und zwar in jedem Schritt eine kostengünstigste Kante, welche den Baum mit Knoten außerhalb des Baumes verbindet. Dies macht man, bis alle Knoten erfasst sind.

Konkret: Wir fangen mit A an. Dann kann man nach dieser Methode nacheinander die Kanten AC, CD, CF, ….hinzufügen. Auf diese Art ist die Lösung in Bild 4 entstanden. Die Gesamtkosten betragen 42 Geldeinheiten, welch ein Zufall. (42 ist die Lieblingszahl von Rainer Roos, Anmerkung der Redaktion).

Es gibt weitere Lösungen der Aufgabe. Dieser Algorithmus von Prim ist "greedy", gierig. In jedem Schritt schnappt er sich eine beste Kante und hofft, dass auch das Gesamtergebnis optimal ist. Hier klappt dies, man kann es beweisen. Bei vielen mathematischen Problemen und im Leben ist es anders. Das dicke Ende kommt zuletzt. Hat Milton Friedman dies übersehen?

*Bei der Beschreibung von Algorithmen ist es üblich, sich zu duzen. Im Saarland sicher kein Problem.

Zum Thema:

 Die kürzeste Verbindung im Blick. Foto: Peter Kneffel/dpa
Die kürzeste Verbindung im Blick. Foto: Peter Kneffel/dpa Foto: Peter Kneffel/dpa

Auf einen Blick Aus allen Einsendungen hat die Glücksfee zehn Gewinner gezogen. Diese erhalten per Brief einen Gutschein über zehn Euro für das Hallenbad in Tholey, von der Gemeinde und zur Verfügung gestellt. 42 Mathefans haben bei der jüngsten Aufgabe mitgemacht. Die Gewinner: J. Dörr aus Püttlingen, Rudi Dupré aus Primstal, Franz Schneider aus Siersburg, Marion Al-Qadi aus Wadgassen, Lina Alt aus Nonnweiler, Vivian Geßner aus Neunkirchen, Ingrid Lindemann aus Kirkel, Sarah Butterbach aus Hermeskeil, Walter Bub aus Überherrn, Frank Reimsbach aus Saarlouis. Herzlichen Glückwunsch. red