© gonewiththewind, 123RF

Kaum eine Informatikvorlesung über Graphentheorie kommt am Thema “Königsberger Brückenproblem” vorbei. Mike Schilli rückt dem Brückengeflecht mit Graphen, Axiomen und Algorithmen zu Leibe.

Die gestellte Aufgabe, die sieben Pregel-Brücken des heutzutage Kaliningrad genannten Ortes auf einem Stadtrundgang zu überqueren, ohne eine auszulassen oder zweimal abzuschreiten [2], ist einfach bestechend anschaulich.

Der kauzige Schweizer Mathematiker Leonhard Euler hat zwar schon anno 1736 bewiesen, dass dies unmöglich ist, doch als mathematische Kopfübung taugt die Aufgabe auch heute noch, denn das Brückengeflecht lässt sich in einen Graph (Abbildung 1) umwandeln und mit graphentheoretischen Axiomen und Algorithmen traktieren.

Abbildung 1: Abstraktion des Wanderwegs über die Königsberger Brücken hin zum Graphen. (Quelle: CC BY-SA 3.0, Bogdan Giusca)

Leonhard Euler erkannte, dass die Anzahl der Kanten, die zu einem Knoten führen (der so genannte Grad des Knotens), direkt bestimmt, ob sich das Problem des wiederholungsfreien Rundgangs lösen lässt oder nicht.

Gerade oder ungerade

Verfügt jeder Knoten nämlich über eine gerade Anzahl von Kanten, kann ein Tourist alle der Reihe nach abwandern, ohne jemals hängen zu bleiben. Ähnliches gilt, falls genau zwei der Knoten im Graphen eine ungerade Anzahl von Zugängen aufweisen und die restlichen Knoten eine gerade Anzahl – in diesem Fall fängt der Wanderer beim ersten der ungeraden Knoten an zu laufen und beendet den Stadtrundgang am zweiten ungeraden. In allen anderen Fällen, zum Beispiel auch beim vorliegenden Königsberger Brückenproblem, bei dem sogar alle vier Knoten ungerade Grade aufweisen, ist also mathematisch kein wiederholungsfreier Rundweg möglich.

Brute Force

Spaßeshalber könnte man das Problem nun auch durch ein Python-Skript anpacken, das durch den Graphen marschiert und erst dann anhält, falls es an einem Knoten nicht mehr weitergeht, weil alle dort anliegenden Segmente schon vorher bereist wurden. Ergibt die Prüfung, dass die Reise alle Segmente des Graphen umfasst hat, gilt das Ergebnis als richtige Lösung. Im Fall von Königsberg ist dies zwar nicht möglich, doch wenn ich noch eine weitere Verbindung in den Graphen einbaue, findet sich ein Weg.

Damit das Skript alle möglichen Pfadkombinationen durchprobiert, arbeitet sich ein rekursiver Depth-First-Algorithmus durch die verschiedenen Brückenkombinationen. Auf der Reise führt er in einem Dictionary Buch darüber, welche Brücken er schon passiert hat, und schlägt keine Route ein, die über eine bereits passierte Brücke führt.

Abbildung 2: Von »a« bis »g« benannte Brücken zwischen den als Knoten dargestellten Landverbindungen.

Bleibt er an einem Knoten stecken, setzt er zurück und probiert weitere Kombinationen vorher eingeschlagener Richtungen bei Weggabelungen durch. In einem Objektattribut speichert er den längsten gefundenen Pfad. Stimmt später dessen Länge mit der Anzahl aller definierten Brücken überein, ist das Problem gelöst.

Graph eintrichtern

Zuerst stellt sich das Problem, dem Skript in Listing 1 den Graphen in Abbildung 2 einzutrichtern. Es wählt hierzu die Datenstruktur ab Zeile 4, in der Dictionary-Einträge unter der Knotennummer (etwa »1«) als Schlüssel liegen. Die zugehörigen Werte bestehen aus Listen, deren Elemente jeweils die Zielknotennummer (etwa »2«) sowie eine Liste mit Pfadmöglichkeiten enthalten (etwa »[“a”, “b”]«, weil von Knoten 1 nach Knoten 2 die Brücken »a« und »b« führen).

01 #!/usr/bin/env python3
02 from bridgewalk import BridgeWalk
03
04 g = { "1" : [["2", ["a", "b"]],
05              ["3", ["d", "e"]],
06              ["4", ["c"]]
07             ],
08       "2" : [["1", ["a", "b"]],
09              ["4", ["f"]]
10             ],
11       "3" : [["1", ["d", "e"]],
12              ["4", ["g"]],
13             ],
14       "4" : [["2", ["f"]],
15              ["3", ["g"]],
16              ["1", ["c"]]
17             ]
18 }
19
20 trail = BridgeWalk(g)
21 trail.explore()
22
23 print(trail.maxpath)
24
25 if len(trail.bridges) == \
26    len(trail.maxpath):
27     print("Solved!")
28 else:
29     print("Impossible!")

Diese Definition des Puzzles übergibt Zeile 20 dem Konstruktor der Klasse »BridgeWalk« (weiter unten in Listing 2 definiert), und die darauf auf dem entstandenen Objekt ausgeführte Methode »explore()« hangelt sich durch den Graphen, um den längsten Pfad ohne Überlappung zu finden.

01 #!/usr/bin/env python3
02 class BridgeWalk(object):
03   def __init__(self, graph):
04     self.graph   = graph
05     self.bridges = {}
06     self.maxpath = []
07
08     for node in self.graph:
09       for fork in self.graph[node]:
10         for bridge in fork[1]:
11           self.bridges[bridge] = 1
12
13   def explore(self):
14     # try different start nodes
15     for node in self.graph:
16       self.scan(node)
17
18   def scan(self, node, path=[], seen={}):
19     # try different connected nodes
20     for fork in self.graph[node]:
21       # try all bridges leading there
22       for bridge in fork[1]:
23         self.bridge_ok(bridge, fork[0],
24           path.copy(), seen.copy())
25
26   def bridge_ok(self, bridge,
27                 node, path, seen):
28     if not bridge in seen:
29       seen[bridge]=1
30       path.append(bridge)
31
32       if len(self.maxpath) < len(path):
33         self.maxpath = path.copy()
34
35       # recurse
36       self.scan(node, path, seen)

Das Objektattribut »maxpath« enthält abschließend eine Liste mit Brücken in der Reihenfolge ihrer Überquerung. Die »print()«-Anweisung in Zeile 23 wandelt sie automatisch in einen String um und gibt ihn aus. Das Attribut »bridges« führt ein Dictionary mit den Schlüsseln für alle im Graphen definierten Brücken.

Stimmt deren mit »len()« ermittelte Anzahl mit der Zahl der Brücken auf dem längsten Wanderweg in »maxpath« überein, meldet das Skript in Zeile 27 die erfolgreiche Lösung des Puzzles.

Wanderalgorithmus

Den Algorithmus zur Analyse des Graphen zeigt die Klasse »BridgeWalk« in Listing 2. Der Konstruktor »__init__« ab Zeile 3 definiert drei Instanzvariablen: »graph« zum Speichern der Graphenstruktur aus Listing 1, ein Dictionary »bridges«, das die For-Schleife ab Zeile 8 mit Schlüsseln aus allen im Graphen definierten Brücken füllt, und »maxpath«, einer Liste mit dem längsten gefundenen Pfad über die sieben Brücken. Listing 1 ruft die Methode »explore()« ab Zeile 13 ohne Parameter auf, sodass sie Listing 2 nur mit dem in Python-Klassen üblichen Platzhalter »self« definiert, mit dem sie dann später objektspezifische Aufrufe tätigen kann.

Die For-Schleife ab Zeile 15 hangelt sich durch alle Knotendefinitionen im Graphen und ruft für jede gefundene die weiter unten definierte Methode »scan()« mit der Knotennummer auf. Da diese später auch rekursiv aufgerufen wird und zwei weitere Parameter – den aktuellen Pfad »path« als Liste sowie ein Dictionary mit den begangenen Brücken (»seen«) – mitbekommt, setzt die Funktionsdefinition in Zeile 18 diese auf die leere Liste beziehungsweise ein leeres Dictionary, falls sie fehlen wie beim ersten Aufruf.

Die beiden For-Schleifen in Zeile 20 und 22 probieren alle Möglichkeiten aus, um vom aktuellen Knoten zum nächsten zu kommen, und decken alle direkt verbundenen Knoten sowie unter Umständen parallel gebaute Brücken ab. Um zu sehen, ob eine Brücke begehbar, also noch unbetreten ist, prüft die Methode »bridge_ok«, ob sie im Dictionary »seen« bereits vorliegt, und falls sie sie dort nicht findet, setzt sie in Zeile 29 einen Merker, in dem sie den zugehörigen Schlüssel auf den Wert 1 setzt.

Außerdem hängt sie den Brückennamen an den schon durchlaufenen Pfad in »path« an. Ist der Pfad länger als der bislang längste in »maxpath«, legt Zeile 33 dort eine Kopie ab, damit das Programm die Daten später abholen kann.

Abkapseln

Betritt der Algorithmus eine neue Brücke, geht der Weg von dort weiter, und zwar durch Rekursion, indem Zeile 36 wieder die Methode »scan()« aus Zeile 18 aufruft, jetzt mit dem neuen Zielknoten aus der Weggabelung. Die Parameter »path« und »seen« aus Zeile 24 dienen den Funktionen mit Informationen, werden aber auch von diesen modifiziert. Also aufpassen: Weitere Durchläufe der For-Schleifen (Zeilen 20 und 22) benötigen die unmodifizierten Datenstrukturen, da sie separate Pfade durchlaufen.

Die Lösung des Dilemmas liegt im Kapseln der Prüfung in »bridge_ok()« zusammen mit den ».copy()«-Aufrufen in Zeile 24, die die zwei Parameter nicht wie in Python üblich als Referenz, sondern als separate Kopie übergeben. Als Ergebnis druckt Listing 1 die Meldung

['a', 'b', 'f', 'g', 'd', 'e']
Impossible!

aus, denn es konnte nur sechs Brücken verbinden, Leonhard Euler hatte natürlich recht.

Abbildung 3: Der Pfad »h« reduziert die Zahl der ungeraden Knoten auf zwei und ermöglicht eine Lösung.

Würde Kaliningrad eine weitere Brücke »h« bauen, die in Abbildung 3 die Knoten 3 und 4 parallel zur Brücke »g« verbindet, könnte die Stadt den wiederholungsfreien Rundgang bieten, wie eine Kombination aus Listing 1 und Listing 3 zeigt:

1 "3" : [["1", ["d", "e"]],
2        ["4", ["g","h"]],
3       ],
4 "4" : [["2", ["f"]],
5        ["3", ["g","h"]],
6        ["1", ["c"]]
7       ]

$ ./solved.py
['a', 'b', 'd', 'e', 'c', 'g', 'h', 'f']
Solved!

Abbildung 3 zeigt, dass so an nur zwei der insgesamt vier Knoten eine ungerade Zahl von Brücken hängen und somit die Eulersche Forderung erfüllt ist. Die korrespondierende Änderung der Datenstruktur zeigt Listing 3, das zwischen Knoten 3 und 4 eine Brücke »h« einbaut, die, wie die Ausgabe oben zeigt, mit dem gleichen Algorithmus das Problem löst.