Planare Graphen und ihre Darstellungen
Wir definieren:
Definition (planar)
Ein Graph G = (E, K) heißt planar, falls es ein Ecken-Kanten-Diagramm von G in der Ebene gibt, in dem sich die Kanten nicht schneiden. Ein solches Diagramm nennen wir auch eine planare Darstellung von G.
Die Definition ist in dieser Form nicht vollständig, da wir „Ecken-Kanten-Diagramm“ nicht formal definiert haben. Dies ist möglich, indem wir Ecken als Punkte der Ebene und Kanten als bestimmte Kurven zwischen den Ecken auffassen. Für die folgende Diskussion ist obige Definition ausreichend.
Beispiele
(1) | Die Darstellung des vollständigen Graphen K4 mit einem Quadrat oder Rechteck als Ecken ist nicht planar. Es gibt aber eine Möglichkeit den K4 überschneidungsfrei zu zeichnen, sodass der K4 planar ist: |
(2) | Der vollständig bipartite Graph K3, 2 ist ebenfalls planar: |
(3) | Der vollständige Graph K5 und der vollständig bipartite Graph K3, 3 sind nicht planar. Wir geben unten einen Beweis hierfür mit Hilfe der Eulerschen Polyederformel. |
(4) | Streichen wir aus dem K5 oder K3, 3 eine beliebige Kante, so sind die entstehenden Graphen planar. Für das Streichen von 45 aus K5 und 36 aus K3, 3 erhalten wir zum Beispiel die planaren Darstellungen: |
(5) | Jeder Teilgraph G′ eines planaren Graphen G ist planar. Denn aus einer planaren Darstellung von G ergibt sich eine planare Darstellung von G′ durch Entfernen von gewissen Ecken und Kanten. |
Dem Leser ist vielleicht aufgefallen, dass wir alle planaren Graphen mit geraden Kanten gezeichnet haben. Überraschenderweise ist dies immer möglich: Ist ein Graph planar, so gibt es eine planare Darstellung, die nur gerade Kanten verwendet (Satz von Wagner und Fáry).
Unterteilungsgraphen und der Satz von Kuratowski
Die Graphen K5 und K3, 3 sind die wichtigsten Beispiele für nicht planare Graphen, da sie sich nach einem Satz von Kuratowski in jedem nicht planaren Graphen wiederfinden lassen. Um dies zu präzisieren, definieren wir:
Definition (Unterteilungsgraph)
Sei G = (E, K) ein Graph. Ein Graph G′ = (E′, K′) heißt eine 1-Schritt Erweiterung von G, falls es ein c ∉ E gibt mit E′ = E ∪ { c } und
K′ = (K − { ab }) ∪ { ac, cb }.
Weiter heißt ein Graph H ein Unterteilungsgraph von G, falls es Graphen G1, …, Gn mit G1 = G und Gn = H gibt derart, dass für alle 1 ≤ i < n gilt:
Gi + 1 ist eine 1-Schritt-Erweiterung von Gi.
Ein Unterteilungsgraph H eines Graphen G entsteht also durch schrittweises Ersetzen einer Kante ab durch zwei Kanten ac, cb mit einer neuen Ecke c. In jedem Erweiterungsschritt kommt eine neue Ecke hinzu und die Anzahl der Kanten erhöht sich um eins.
Ein Unterteilungsgraph des K5
Damit können wir das Ergebnis genau formulieren:
Satz (Satz von Kuratowski)
Sei G = (E, K) ein Graph. Dann sind äquivalent:
(a) | G ist nicht planar. |
(b) | Es gibt einen Teilgraphen H von G, der ein Unterteilungsgraph eines vollständigen Graphen mit 5 Ecken oder eines vollständig bipartiten Graphen des Typs 3-3 ist. |
Wir verweisen den Leser auf die Literatur für einen Beweis. Hier begnügen wir uns mit einem Beispiel zur Illustration dieses Ergebnisses.
Beispiel
Wir betrachten den folgenden Graphen G:
Dass G nicht planar ist, ist keineswegs klar. Folgende Darstellung hat nur eine Überschneidung:
Der Nachweis der Nichtplanarität ist erbracht, indem wir einen vollständig bipartiten Unterteilungsgraphen des Typs 3-3 isolieren. Der rot gezeichnete Graph ist ein Unterteilungsgraph (mit eingefügten Ecken 5, 6, 8) des durch { 1, 4, 9 }, { 2, 3, 10 } vollständig bipartiten Graphen: