Glossar

Wähle eines der Schlüsselwörter auf der linken Seite…

Graphen und NetzwerkePlanare Graphen

Lesezeit: ~25 min

Hier ist ein weiteres Rätsel, das mit der Graphentheorie zu tun hat.

In einem kleinen Dorf gibt es drei Häuser und drei Versorgungswerke, die Wasser, Strom und Gas produzieren. Wir müssen die einzelnen Leitungen an jedes der Versorgungswerke anschließen, aber aufgrund der Anordnung des Dorfes dürfen sich die verschiedenen Rohre und Kabel nicht kreuzen.

Versuche, jedes der Häuser mit jedem der untenstehenden Versorgungswerke zu verbinden, ohne dass sich eine deiner Leitungen kreuzt:

Genau wie bei den Königsberger Brücken vorher, stellt man schnell fest, dass auch dieses Problem nicht lösbar ist. Es scheint, dass einige Graphen ohne überlappende Kanten gezeichnet werden können - diese nennt man planare Graphen , andere jedoch nicht.

K3 ist planar.

K4 .

K5 .

Der vollständige Graph K5 ist der kleinste Graph, der nicht planar ist. Jeder andere Graph, der K5 in irgendeiner Weise als Teilgraph enthält, ist auch nicht planar. Dazu gehören K6, K7, und alle größeren vollständigen Graphen.

Der Graph im Rätsel der drei Versorgungswerke ist der bipartite graph K3,3. Es stellt sich heraus, dass jeder nicht-planare Graph entweder einen K5 oder einen K3,3 (bzw. eine Unterteilung dieser beiden Graphen) als Teilgraph enthalten muss. Das ist bekannt als Kuratowskis Theorem.

Planarität

Dies ist ein planarer Graph, aber die Knoten ${n} sind durcheinander geraten. Ordne die Knoten neu an, so dass keine der Kanten überlappen.

Eulersche Polyederformel

Alle planaren Graphen unterteilen die Ebene, auf der sie gezeichnet werden, in mehrere Bereiche, genannt Flächen.

Ecken (Knoten)
Flächen
Kanten
11 Ecken + Flächen

Ecken (Knoten)
Flächen
Kanten
15 Ecken + Flächen

Ecken (Knoten)
Flächen
Kanten
25 Ecken + Flächen

Wenn du diese Zahlen vergleichst, wirst du feststellen, dass die Anzahl der Kanten immer ist als die Anzahl der Flächen plus die Anzahl der Knoten, die wir hier als Ecken E bezeichnen wollen. Mit anderen Worten: F + E = K + 1. Dieses Ergebnis wollen wir Euler-Formel nennen, nach demselben Mathematiker, der auch das Problem der Königsberger Brücken gelöst hat.

Leider gibt es unendlich viele Graphen, und wir können nicht jeden einzelnen überprüfen, um zu sehen, ob die Euler-Formel funktioniert. Stattdessen können wir versuchen, einen einfachen Beweis zu finden, der für jeden Graphen funktioniert...

FEK
010

0 + 1  =  0 + 1

Der einfachste Graph besteht aus einer einzigen Ecke (Knoten). Wir können leicht überprüfen, dass die Euler-Formel funktioniert.
Wir wollen eine neue Ecke zu unserem Graphen hinzufügen. Außerdem müssen wir noch eine Kante hinzufügen, und die Euler-Formel funktioniert immer noch.
Wenn wir eine dritte Ecke zum Graphen hinzufügen wollen, haben wir zwei Möglichkeiten. Wir könnten ein kleines Dreieck erstellen: dies fügt eine Ecke, eine Fläche und zwei Kanten hinzu, so dass die Euler-Formel immer noch funktioniert.
Stattdessen könnten wir die Linie einfach um eins verlängern: das fügt eine Ecke und eine Kante hinzu, und die Euler-Formel funktioniert.
Machen wir weiter: Wenn wir jetzt ein Viereck erstellen, fügen wir eine Ecke, zwei Kanten und eine Fläche hinzu. Die Euler-Formel funktioniert immer noch.

Jeder (endliche) Graph kann konstruiert werden, indem man mit einem Knoten beginnt und nach und nach weitere Knoten hinzufügt. Wir haben gezeigt, dass, egal auf welche Weise wir neue Knoten hinzufügen, die Euler-Formel gültig ist. Daher ist sie für alle Graphen gültig.

Der Prozess, den wir verwendet haben, wird mathematische Induktion genannt. Das ist eine sehr nützliche Technik, um Ergebnisse in unendlich vielen Fällen zu beweisen, indem man einfach mit dem einfachsten Fall beginnt und zeigt, dass das Ergebnis, wenn man komplexere Fälle entwickelt, bei jedem Schritt gültig bleibt.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Viele planare Graphen sehen den Netzen von Polyedern, dreidimensionalen Körpern mit polygonalen Flächen, sehr ähnlich. Wenn wir uns vorstellen, dass Polyeder aus Gummibändern bestehen, könnten wir sie so lange dehnen, bis sie zu flachen, planaren Graphen werden:

Das bedeutet, dass wir die Euler-Formel nicht nur für planare Graphen, sondern auch für alle Polyeder verwenden können - mit einem kleinen Unterschied. Wenn man die Polyeder in Graphen umwandelt, verschwindet eine der Flächen: die oberste Fläche der Polyeder wird zur "Umrandung" des jeweiligen Graphen.

Mit anderen Worten, wenn du die Anzahl der Kanten, Flächen und Ecken eines beliebigen Polyeders zählst, wirst du feststellen, dass F + E = K + ist, bekannt als Eulersche Polyederformel.

Ikosaeder
20 Flächen
12 Ecken
30 Kanten

Rhombicosidodekaeder
62 Flächen
60 Ecken
120 Kanten

Abgestumpftes Icosahedron
32 Flächen (12 schwarz, 20 weiß)
60 Ecken
90 Kanten