Kaum eine Informatikvorlesung über Graphentheorie kommt am Thema "Königsberger Brückenproblem" [1] vorbei. Die gestellte Aufgabe, die sieben Pregel-Brücken des heutzutage Kaliningrad genannten Ortes auf einem Stadtrundgang zu überqueren, ohne eine auszulassen oder zweimal abzuschreiten, 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. |
Euler fand zunächst heraus, dass sich die Landmassen Königsbergs als Knoten in einem Graphen abbilden lassen, verbunden durch sieben Linien, von Graphentheoretikern "Kanten" genannt, und die die verbindenden Brücken darstellen ("a" bis "g" in Abbildung 2). Die Aufgabe der Stadtführung von Königsberg ist es also, alle im Graphen eingezeichneten Linien (Kanten) abzuwandern, ohne irgendein Segment mehr als einmal zu passieren. Euler erkannte schließlich, dass sich Anzahl der Kanten, die zu einem Knoten führen (der sogenannte "Grad" des Knotens), direkt bestimmt, ob sich das Problem des wiederholungsfreien Stadtrundgangs lösen lässt oder nicht.
Verfügt jeder Knoten nämlich über eine gerade Anzahl von Kanten, kann ein Tourist alle der Reihe nach abwandern, ohne jemals hängenzubleiben. Ähnliches gilt, falls genau zwei der Knoten im Graphen eine ungerade Anzahl von Zugängen aufweisen, und die restlichen Knoten eine gerade -- 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, wie auch beim vorliegenden Königsberger Brückenproblem, bei dem sogar alle vier Knoten ungerade Grade aufweisen, ist rein mathematisch kein perfektes wiederholungsfreies Abschreiten möglich.
 |
| Abbildung 2: Von "a" bis "g" benannte Brücken zwischen den als Knoten dargestellten Landverbindungen. |
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 weiter geht, weil alle dort anliegenden Segmente schon vorher bereist wurden. Ergibt die anschließende 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, dort wenn wir später noch eine weitere Verbindung in den Graphen einbauen, wird sich ein Weg finden.
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. Bleibt er an einem Knoten stecken, setzt er zurück und probiert weitere Kombinationen vorher eingeschlagener Richtungen bei Wegegabelungen 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.
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!")
Als erstes 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 (z.B. "1") als Schlüssel liegen. Die zugehörigen Werte bestehen aus Listen, deren Elemente jeweils die Zielknotennummer (z.B. "2") sowie eine Liste mit Pfadmöglichkeiten enthalten (z.B. "["a", "b"]", weil von Knoten 1 nach Knoten 2 die Brücken "a" und "b" führen). 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.
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 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.
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, eine Liste mit dem längsten gefundenen Pfad über die sieben Brücken.
Die Methode explore() ab Zeile 13 wird von Listing 1 ohne Parameter aufgerufen, sodass sie Listing 2 nur mit dem in Python-Klassen üblichen Platzhalter self definiert, mit dem sie 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 soweit begangenen Brücken (seen), mitbekommt, setzt die Funktionsdefinition in Zeile 18 diese auf die leere Liste bzw. ein leeres Dictionary, falls sie -- wie beim ersten Aufruf -- fehlen.
Die beiden For-Schleifen in Zeile 20 und 22 probieren dann alle Möglichkeiten aus, um vom aktuellen Knoten zum nächsten zu kommen, und decken dabei alle direkt verbundenen Knoten sowie unter Umständen parallel gebaute Brücken ab. Um zu sehen, ob eine ausgewählte Brücke begehbar ist, also noch nie vorher bewandert wurde, prüft die Methode bridge_ok, ob sie schon im Dictionary seen vorliegt, und falls sie sie dort nicht findet, pflanzt sie dort in Zeile 29 einen Merker ein, in dem sie den zugehörigen Schlüssel auf den Wert 1 setzt. Weiter hängt sie den Namen der Brücke an den soweit durchlaufenen Pfad in path an. Falls der Pfad länger als der bislang längste in maxpath ist, legt Zeile 33 dort eine Kopie ab, damit das Hauptprogramm die Daten von dort später abholen kann.
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)
Betritt der Algorithmus eine neue Brücke, geht die Wanderung von dort wieder weiter, und zwar durch Rekursion, indem Zeile 36 wieder die Methode scan() aus Zeile 18 aufruft, diesmal mit dem neuen Zielknoten aus der Wegegabelung. Die mitgeschleiften Parameter path und seen aus Zeile 24 dienen den aufgerufenen Funktionen mit Informationen, werden allerdings auch von diesen modifiziert, und der Programmierer muss aufpassen wie ein Haftelmacher: Denn weitere Durchläufe der For-Schleifen in den Zeilen 20 und 22 benötigen die unmodifizierten Datenstrukturen, da sie separate Pfade durchlaufen. Die Lösung des Dilemmas lässt sich durch Kapseln der Prüfung in bridge_ok erreichen, 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
$ ./koenigsberg.py
['a', 'b', 'f', 'g', 'd', 'e']
Impossible!aus, denn es konnte nur sechs der sieben Brücken auf einem Rundgang verbinden, Leonard Euler hatte natürlich recht.
 |
| Abbildung 3: Ein zusätzlicher Pfad "h" reduziert die Anzahl der ungeraden Knoten auf zwei und ermöglicht eine Lösung. |
01 g = { "1" : [["2", ["a", "b"]],
02 ["3", ["d", "e"]],
03 ["4", ["c"]]
04 ],
05 "2" : [["1", ["a", "b"]],
06 ["4", ["f"]]
07 ],
08 "3" : [["1", ["d", "e"]],
09 ["4", ["g","h"]],
10 ],
11 "4" : [["2", ["f"]],
12 ["3", ["g","h"]],
13 ["1", ["c"]]
14 ]
15 }
Würden sich die Kaliningrader allerdings aufraffen und einfach eine weitere Brücke "h" konstruieren, die, wie in Abbildung 3, die Knoten 3 und vier parallel zur Brücke "g" verbinden würde, könnte die Stadtverwaltung endlich den ersehnten wiederholungsfreien Rundgang anbieten:
$ ./solved.py
['a', 'b', 'd', 'e', 'c', 'g', 'h', 'f']
Solved!Abbildung 3 zeigt auch, dass so an nur 2 der insgesamt 4 Knoten eine ungerade Zahl von Brücken hängen, und somit die Eulersche Forderung erfüllt ist. Die korrespondierene Änderung der Datenstruktur zeigt Listing 3, das in Listing 3 zwischen den Knoten 3 und 4 eine Brücke namens "h" einbaut, die, wie die Ausgabe oben zeigt, mit dem gleichen Algorithmus das Problem tatsächlich löst. Das sollten sich die Stadtväter doch bitte mal überlegen.
Listings zu diesem Artikel: http://www.linux-magazin.de/static/listings/magazin/2018/09/snapshot/
"Königsberger Brückenproblem", Wikipedia, https://de.wikipedia.org/wiki/K%C3%B6nigsberger_Br%C3%BCckenproblem
 |
Michael Schilliarbeitet als Software-Engineer in der San Francisco Bay Area in Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen verschiedener Programmiersprachen. Unter mschilli@perlmeister.com beantwortet er gerne Ihre Fragen. |
Hey! The above document had some coding errors, which are explained below:
Unknown directive: =desc