Das britische Königshaus und die Suche in Netzwerken

Auch wenn der Titel es anders vermuten lässt, so wird es sich in diesem Artikel zuerst und die Suche in Netzwerken drehen und dann um das britische Königshaus - genauer um die Thronfolge im britischen Königshaus. Elizabeth II. wird schließlich auch nicht jünger.

Als Netzwerk (oder Graph) bezeichnet man eine Ansammlung von Punkten (den sog. Knoten) und Verbindungen zwischen den Knoten (den sog. Kanten). In Abbildung 1 kann man ein solches Netzwerk sehen.  Die Knoten sind hierbei die durchnummerierten Kreise und die Kanten die Verbindungslinien.

Abbildung 1. Ein Netzwerk mit 14 Knoten und 14 Kanten.

Es gibt nun diverse Eigenschaften, die ein solches Netzwerk haben kann. Das Netzwerk in Abbildung 1 ist zum Beispiel unzusammenhängend - man kann nicht von jedem Knoten zu jedem Knoten gelangen. Außerdem ist das Netzwerk zyklisch - es gibt Kreise im Netzwerk.

Netzwerke werden vor allem in der Kombinatorik studiert. Dort sollen sie Netzwerke in der echten Welt modellieren, wie zum Beispiel ein Straßennetz oder ein Computer-Netzwerk. Gegeben ein Netzwerk kann man sich nun diverse Fragen stellen - einige Beispiele:

1. Kürzester Weg: Wie kommt man am schnellsten von Knoten 1 zu Knoten 9?
2. Chinesischer Postbote: Wie läuft man am schnellsten alle Kanten ab?
3. Eulertour: Kann man alle Kanten am Stück ablaufen, ohne eine Kante zweimal zu nehmen? (Siehe auch: Königsberger Brückenproblem oder das Haus vom Nikolaus)
4. Zusammenhang: Ist das Netzwerk zusammenhängend?
5. Hamiltonkreis: Gibt es einen Weg, der genau einmal durch jeden Knoten läuft und dort herauskommt, wo er anfing.
6. uvm.

Das Zusammenhangsproblem (4.) ist ein relativ einfach zu erklärendes und zu lösendes Problem. Wie angedeutet heißt ein Netzwerk zusammenhängend, wenn man über Kanten laufend von jedem Knoten zu jedem Knoten gelangen kann. Anderenfalls heißt das Netzwerk unzusammenhängend. In Abbildung 1 lässt sich leicht erkennen, dass das Netzwerk unzusammenhängend ist. Dies ist in der Regel nicht der Fall. Insbesondere nicht, wenn das Netzwerk groß ist, oder nicht hingezeichnet ist. Es gibt mehrere Methoden ein solches Netzwerk zu spezifizieren. Zum Beispiel beschreibt man die Menge der Knoten

V = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}

und die Menge der Kanten

E = {{1, 2}, {2, 3}, {2, 6}, {3, 4}, {3, 5}, {4, 6}, {6, 7}, {6, 8}, {7, 10}, {8, 9}, {9, 10}, {11, 12}, {12, 13}, {13, 14}}.

Hier ließe sich nun nicht einfach erkennen, ob das Netzwerk zusammenhängend ist, oder nicht.

Relativ einfache Methoden, mit denen man (Un-)Zusammenhang entdecken kann, sind Breitensuche und Tiefensuche. Die Algorithmen funktionieren beide nach einem sehr ähnlichen Prinzip: 

1. Breitensuche (Breadth-first-search; BFS): Alle Knoten sind weiß und man hat eine leere Warteschlange. Man wählt einen beliebigen Knoten als Startknoten aus und färbt ihn schwarz. Dann läuft man alle Knoten ab, die zum Startknoten verbunden sind, und färbt sie schwarz und steckt sie in eine Warteschlange. Gibt es keinen Knoten mehr, der zum Startknoten verbunden und weiß ist, nimmt man nun Knoten nach Knoten aus der Warteschlange und verfährt genauso, wie mit dem Startknoten zuvor. Der Algorithmus ist beendet, wenn man von keinem Knoten keinen weißen Knoten erreichen kann.
2. Tiefensuche (Depth-first-search; DFS): Alle Knoten sind weiß und man hat einen leeren Stapel. Man wählt einen beliebigen Knoten als Startknoten aus und färbt ihn schwarz und legt ihn auf den Stapel. Dann läuft zum ersten Knoten ab, der mit dem Startknoten verbunden ist, färbt ihn schwarz und legt ihn auf den Stapel. Dann verfährt man mit dem Knoten, der oben auf dem Stapel liegt, so wie mit dem Startknoten. Liegt ein Knoten oben auf dem Stapel, hat aber keine ungefärbten Nachbarknoten, löscht man ihn vom Stapel. Der Algorithmus ist beendet, wenn man von keinem Knoten keinen weißen Knoten erreichen kann.

Die Algorithmen basieren auf demselben Ansatz, verfahren aber unterschiedlich. Bei der Breitensuche geht man zuerst in die Breite, dann in die Tiefe, bei der Tiefensuche geht man erst in die Tiefe, denn in die Breite. Ich habe zwei Animationen (Videos 1 und 2) gebastelt, bei denen man den Unterschied ganz gut sehen kann. Die Algorithmen sehen grundsätzlich keine Reihenfolge vor, in der zwei gleichwertige Kanten, die demselben Knoten zugeordnet sind, abgelaufen werden. In den Animationen habe ich die Konvention befolgt, immer zuerst zu dem Knoten mit der kleineren Nummer zu gehen. Darauf komme ich später zurück.

Video 1. Breitensuche.

Video 2. Tiefensuche

Bei beiden Algorithmen erkennt man übrigens, ob die Netzwerke zusammenhängend sind, oder nicht, wenn man beim Durchlaufen die Knoten zählt, die man schwarz färbt. Stimmt die Anzahl mit der Gesamtanzahl der Knoten überein, so ist das Netzwerk zusammenhängend.

Nun zum britischen Königshaus. Ein anderes Beispiel für ein Netzwerk ist ein Stammbaum, zum Beispiel der Stammbaum der Familie Windsor. Den Stammbaum mit Elizabeths, Charles und Williams Nachfahren habe ich mal in Abbildung 2 aufgemalt.

Abbildung 2. Ein sehr stark gekürzter Stammbaum der Familie Windsor.

Die Regelung der Thronfolge im britischen Königshaus war für mich immer sehr verwirrend. Bis 2013 sah die Rangliste so aus:

1. Charles
2. William
3. Harry
4. Andrew

Nun hat William aber drei Kinder, damit wurde ab Platz 2 alle nach hinten verdrängt:

1. Charles
2. William
3. George
4. Charlotte
5. Louis
6. Harry
7. Andrew

Damit steht nun sogar der Säugling Louis vor Harry. Sollte nun Harry ebenfalls Nachwuchs erwarten, könnte Andrew innerhalb von wenigen Jahren von Platz 4 auf eine zweistellige Position vertrieben werden. Schlimmer noch: Bis zu Williams Geburt in 1982 war er sogar auf Platz 2. Im Geschäft der Thronfolge gilt: Ältere Geschwister sind grundsätzlich schlecht, aber wenn sie erst mal Kinder haben, ist alles aus.

Betrachtet man den Stammbaum der Familie Windsor als Netzwerk, so ist die Thronfolge tatsächlich eine Tiefensuche, die bei dem aktuellen Throninhaber anfängt: Nach einer Person kommen immer erst die Kinder dieser Person, dann die Geschwister dieser Person. 

Genau wie oben erwähnt und in Videos 1-2 dargestellt kann man hier in jedem Schritt nicht irgendeinen weißen Knoten wählen. Hier muss dies nach Geburtsjahr (und irgendeinem sexistischen Scheiß, den es seit 2011 nicht mehr gibt) geschehen. Je früher eine Person geboren ist, desto früher wird man vom Algorithmus gezogen. 

Dies stelle ich in Video 3 da, in welchem ich eine Tiefensuche im Stammbaum der Familie Windsor nachgebaut habe. Das Video hört nach Andrew auf, da noch vor Edward die Kinder von Andrew ein Anrecht auf den Thron hätten. Die wiederum haben es aber nicht ins Video geschafft.

Video 3. Tiefensuche auf dem Stammbaum der Familie Windsor.

Nun habe ich mich gefragt, ob es auch Königreiche gibt, in der die Thronfolge wie eine Breitensuche funktioniert. Das ist in gewisser Weise der Fall in Saudi Arabien - dort geht die Krone in der Regel über an einen Bruder des Königs. Aber dort funktioniert die Thronfolge nicht wie ein deterministischer Algorithmus in einem Netzwerk - Kronprinzen werden gewählt.