Graphen und NetzwerkePlanare Graphen

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.

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.

Eulersche Polyederformel

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

Wenn du diese Zahlen vergleichst, wirst du feststellen, dass die Anzahl der Kanten immer eins wenigergrößerdieselbe 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...

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.

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.