Planare Graphen - Fachbereich Mathematik und Informatik

Westfälische Wilhelms-Universität Münster
Fachbereich: Mathematik und Informatik
Planare Graphen
Kreuzungslemma und Charakterisierung planarer Graphen nach
Kuratowski
Andrea Vollmer
Seminar: Graphentheorie
Dr. Thomas Timmermann
Sommersemester 2015
Vortrag vom 22. Juni 2015
Inhaltsverzeichnis
1 Einleitung
1
2 Die Kreuzungszahl und eine erste Abschätzung
2
3 Das Kreuzungslemma
5
4 Charakterisierung planarer Graphen nach Kuratowski
7
4.1
Liste nicht planarer Graphen . . . . . . . . . . . . . . . . . . . . . . . . .
7
4.2
Das Kuratowski-Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
4.3
Anwendung des Kuratowski-Theorems . . . . . . . . . . . . . . . . . . . . 10
i
1 Einleitung
Während die Anfänge der Graphentheorie (z.B. das Königsberger Brückenproblem) bereits im 18. Jahrhundert liegen, werden die meisten ihrer Fortschritte erst im letzten
Jahrhundert verzeichnet. So auch die Erkenntnisse und Sätze zu planaren Graphen, mit
denen ich mich in meinem Vortrag beschäftigt habe.
In dieser Ausarbeitung soll es daher zunächst um die Kreuzungszahl von Graphen und
möglichen Abschätzungen gehen, um anschließend das lang vermutete Kreuzungslemma
zu beweisen. Hierbei werde ich dem Buch der Beweise von Martin Eigner und Günter
M. Ziegler folgen.
In einem zweiten großen Abschnitt wird es um die Charakterisierung planarer Graphen nach Kuratowski gehen, wobei hier vor allem Vorarbeit für das doch erstaunliche
Kuratowski-Theorem geleistet werden soll, was seinerzeit einen Durchbruch der Graphentheorie darstellte. Dieser Teil folgt A Textbuch of Graph theory von Balakrishnan und
Ranganathan sowie Combinatorics and Graph theory von Harris, Hirst und Mossinghoff.
1
2 Die Kreuzungszahl und eine erste
Abschätzung
Zu Beginn müssen ein paar grundlegende Definitionen wiederholt sowie auf eine Proposition verwiesen werden, die bereits in einem früheren Vortrag bewiesen wurde und die
im späteren Verlauf bei der Abschätzung der Kreuzungszahl benötigt wird.
Definition 2.1. Ein Graph heißt planar, wenn er in die Ebene R2 gezeichnet werden
kann, ohne dass sich Kanten kreuzen.
Definition 2.2. Ein Graph heißt eben, wenn schon eine Zeichnung des Graphen im R2
ohne kreuzende Kanten vorliegt.
Aus der Eulerschen Polyederformel kann folgende Beziehung geschlussfolgert werden:
Proposition 2.3. Sei G = (V,E) ein Graph mit n Knoten und m Kanten. Ein ebener
Graph hat dann höchstens 3n-6 Kanten.
Nun gehen wir zum eigentlichen Teil dieses Kapitels über und beginnen mit der Definition der Kreuzungszahl.
Definition 2.4. Die Kreuzungszahl kr(G) eines Graphen G ist die kleinste Anzahl von
Kreuzungen, die für eine Zeichnung von G möglich ist.
Bemerkung 2.5. Mit der Definition der Kreuzungszahl folgt schon, dass kr(G) = 0 für
einen ebenen Graphen G gilt.
Im folgenden betrachten wir so genannte minimale Zeichnungen, d.h Zeichnungen, in
denen es so wenig kreuzende Kanten, wie möglich gibt. Solch eine minimale Zeichnung
erfüllt offenbar folgende Bedingungen:
1. Keine Kante kann sich selber kreuzen.
2. Kanten mit gemeinsamen Endknoten können sich nicht kreuzen.
2
2 Die Kreuzungszahl und eine erste Abschätzung
3. Zwei Kanten können sich nicht mehrmals kreuzen.
Diese Bedingungen lassen sich anhand der folgenden, kleinen Skizzen beweisen. Hierbei
findet man immer eine Repräsentation desselben Graphen mit weniger Kreuzungen:
Abbildung 2.1: Bedingungen für minimale Zeichnungen
Wir wollen nun eine erste Abschätzung der Kreuzungszahl finden und nehmen an, dass
alle Zeichnungen die drei Bedingungen erfüllen.
Sei nun also eine minimale Zeichnung eines Graphen G mit kr(G) Kreuzungen, n Ecken
und m Kanten gegeben. Um eine untere Schranke für die Kreuzungszahl kr(G) festzulegen, betrachten wir den Graphen H, der aus G entsteht, indem man zusätzlich zu den
Knoten und Kanten von G die Kreuzungspunkte von G als neue Knoten in H und die
Kantenstücke zwischen den Kreuzungspunkten von G als neue Kanten in H nimmt. Dann
ist H eben und einfach, da es keine kreuzende Kanten mehr gibt und die drei Bedingungen für minimale Zeichnungen erfüllt sind.
Somit besitzt H nH = nG + kr(G) Knoten und mH = mG + 2kr(G) Kanten, weil jeder
neuer Knoten von Grad 4 ist. Nun lässt sich Proposition 2.3 auf H übertragen:
mH ≤ 3nH − 6
⇔ mG + 2kr(G) ≤ 3(nG + kr(G)) − 6
⇔ kr(G) ≥ mG − 3nG + 6
Also haben wir unsere erste Abschätzung gefunden: kr(G) ≥ m − 3n + 6
Aufgabe 2.6. Zeichnet den vollständigen Graphen K6 auf und erstellt eine minimale
Zeichnung. Wie groß ist kr(K6 )?
3
2 Die Kreuzungszahl und eine erste Abschätzung
Lösung: n = 6, m =15 ⇒ kr(G) ≥ m − 3n + 6 = 15 − 3 · 6 + 6 = 3
Unsere Abschätzung sagt uns also, dass es keine Einbettung des K6 mit weniger als
drei Kreuzungen gibt.
Abbildung 2.2: Einbettung des K6 mit minimaler Anzahl an Kreuzungen
4
3 Das Kreuzungslemma
Diese erste Abschätzung der Kreuzungszahl ist sinnvoll, wenn die Kantenzahl m nur linear
mit der Knotenzahl n wächst. Für den Fall, dass die Kantenzahl echt schneller wächst
als die Knotenanzahl, kann man aber eine bessere untere Schranke für die Kreuzungszahl
finden, was uns zum Kreuzungslemma führt.
Lemma 3.1 (Das Kreuzungslemma). Sei G ein einfacher Graph mit n Ecken und m
Kanten und es gelte m ≥ 4n. Dann ist
kr(G) ≥
1 m3
64 n2
Das Kreuzungslemma wurde bereits 1973 von Erdõs und Guy vermutet, wobei sie
anstatt
1
64
nur eine Konstante c > 0 wählten. Auch als Leighton, Ajtai, Chvátal, Newborn
und Szemerédi 1982 unabhängig voneinander die ersten Beweise mit dem Faktor
1
100
aufstellten, wurden diese erst anerkannt als Lásló Székely 1997 das Kreuzungslemma
auf mehrere geometrische Extremalprobleme anwendete. Der folgende Beweis beruht auf
einen Email-Austausch von Bernard Gazelle, Mich Sharir und Emo Welzl und ist eine
Anwendung der probabilistischen Methode nach Erdõs und Rényi.
Beweis. Wir betrachten eine minimale Einbettung eines Graphen G und eine Wahrscheinlichkeit p ∈ [0, 1]. Wir erzeugen einen Untergraphen von G, in dem wir die einzelnen Ecken unabhängig voneinander mit der Wahrscheinlichkeit p auswählen. So erhalten
wir den induzierten Untergraphen Gp .
Seien np , mp und Xp Zufallsvariablen, wobei np die Anzahl der Ecken in Gp , mp die
Anzahl der Kanten in Gp und Xp die Anzahl der Kreuzungen in Gp zählt.
Wir haben bereits gesehen, dass kr(G) − m + 3n ≥ 6 für jeden Graphen G gilt. Daraus
folgt insbesondere kr(G) − m + 3n ≥ 0. Betrachten wir nun den Erwartungswert:
E(Xp − mp + 3np ) ≥ 0
5
3 Das Kreuzungslemma
⇔ E(Xp ) − E(mp ) + 3E(np ) ≥ 0 (wegen der Linearität)
Da eine Ecke mit Wahrscheinlichkeit p in Gp liegt, folgt E(np ) = pn. Eine Kante liegt
nur in Gp , wenn beide Ecken in Gp liegen und somit gilt E(mp ) = p2 m. Und es folgt
E(Xp ) = p4 kr(G), da eine Kreuzung wiederum nur in Gp liegt, wenn alle ihre vier unterschiedlichen beteiligten Ecken in Gp liegen. Somit erhalten wir:
p4 kr(G) − p2 m + 3pn ≥ 0
m
p2
−
3n
p3
⇔ kr(G) ≥
m
p2
+
⇔ kr(G) −
Setze p :=
4n
m.
≥0
3n
p3
Nach Voraussetzung gilt m ≥ 4n und somit ist p höchstens
Man erhält:
kr(G) ≥
m
)2
( 4n
m
⇔ kr(G) ≥
m3
42 n2
⇔ kr(G) ≥
6
−
3n
)3
( 4n
m
−
3m3
43 n2
1 m3
64 m2
4n
4n
= 1.
4 Charakterisierung planarer Graphen
nach Kuratowski
4.1 Liste nicht planarer Graphen
Nun wollen wir eine Liste nicht planarer Graphen aufstellen, um Kriterien für Planarität
von Graphen zu erkennen und Vorbereitung für das Kuratowski-Theorem zu leisten.
Aus dem Vortrag zur Eulerschen Polyederformel wissen wir bereits, dass der vollständige
Graph K5 und der bipartite Graph K3,3 nicht planar sind. Da dies aber nur für den K5
bewiesen wurde, werde ich den Beweis für den K3,3 noch einmal vorstellen.
(a) K5
(b) K3,3
Abbildung 4.1: Die ersten nicht planaren Graphen auf unserer Liste
Beweis. Wir nehmen an, der K3,3 sei planar.
Wir wissen, dass die Anzahl der Ecken n = 6 und die Anzahl der Kanten m = 9 = e ist.
Die Eulersche Polyederformel besagt, dass n - e + f = 2 gilt und so folgt für die Anzahl
der Flächen von K3,3 f = 5.
Nun betrachten wir das durchschnittliche Verhältnis der Seiten pro Fläche: f =
18
5
2e
f
=
< 4.
Da der K3,3 ein einfacher bipartiter Graph ist, hat jeder seiner Kreise mindestens die
Länge 4, d.h. jede Fläche ist mindestens von vier Kanten begrenzt. Somit haben wir
einen Widerspruch zur durchschnittlichen Seitenanzahl pro Fläche. Also ist der K3,3
nicht planar.
7
4 Charakterisierung planarer Graphen nach Kuratowski
Um die Liste nicht planarer Graphen zu erweitern, fügen wir alle Graphen hinzu, die
den K5 oder K3,3 als Untergraphen enthalten. Denn wir wissen, dass ein Graph, der einen
nicht planaren Untergraphen enthält, nicht planar ist. Doch wie sieht das mit Graphen
wie in Abb. 4.2 aus?
Abbildung 4.2: Beliebiger nicht planarer Graph
Es ist leicht zusehen, dass dieser Graph nicht planar ist, obwohl er weder den K5 noch
den K3,3 als Untergraphen enthält.
Um dies dennoch mit dem noch folgenden Kuratowski-Theorem zu begründen, ist noch
ein bisschen Vorarbeit nötig.
Definition 4.1. Sei G = (V, E). Eine Unterteilung einer Kante e = {u, v} ∈ E ist das
Ersetzen dieser Kante durch zwei neue Kanten a und b, die die beiden Knoten u und v
der entfernten Kante e mit einem neuen Knoten w ∈
/ V verbinden.
H heißt Unterteilungsgraph von G, wenn H durch eine endliche Reihe von Unterteilungen
von G entsteht.
(a) Graph G
(b) Graph H
Abbildung 4.3: H ist Unterteilungsgraph von G
Notation 4.2. Entsteht ein Untergraph des Graphen G durch Entfernen einer Kante
e = {u, v} ∈ G, so schreiben wir G - e. Entsteht dieser Untergraph durch Kontraktion
einer Kante e = {u, v} ∈ G, d.h. durch das Verschmelzen (auch als Zusammenziehen
8
4 Charakterisierung planarer Graphen nach Kuratowski
bezeichnet) ihrer Endpunkte u und v, so schreiben wir G · e. Insbesondere schreiben wir
G · H, wenn dieser Untergraph durch Kontraktion eines Untergraphen H von G entsteht.
4.2 Das Kuratowski-Theorem
Theorem 4.3 (Kuratowski-Theorem). Ein Graph G=(V,E) ist genau dann planar, wenn
er keine Unterteilung von K5 oder K3,3 enthält.
Beweis. ⇒ Wir nehmen an, dass der Graph G eine Unterteilung H von K5 oder K3,3 als
Untergraphen enthält.
Da bereits gezeigt wurde, dass K5 und K3,3 nicht planar sind, folgt schon, dass die Unterteilung H nicht planar ist. G enthält also einen nicht planaren Untergraphen und ist
somit schon nicht planar.
Also gilt: Ist G planar, so enthält er keine Unterteilung von K5 oder K3,3 .
⇐ Diese Richtung ist deutlich schwieriger, sodass wir diesen Teil des Theorems ohne
Beweis stehen lassen und stattdessen einen weiteren Satz (4.5) mit Erläuterungen nennen
werden, der in der Rückrichtung benutzt werden könnte und eine Beweisidee erkennen
lässt.
Definition 4.4. Wenn G · H = K, so nennen wir K eine Kontraktion von G oder sagen,
dass G zu K zusammenziehbar ist.
Wir nennen G zu K subzusammenziehbar, wenn G einen Untergraphen H enthält, der
zu K zusammenziehbar ist. Dabei nennen wir K eine Subkontraktion von G.
(a) G
(b) K
Abbildung 4.4: K ist Kontraktion von G
Satz 4.5. Ein Graph ist genau dann planar, wenn er nicht zu K5 oder K3,3 subzusammenziehbar ist.
9
4 Charakterisierung planarer Graphen nach Kuratowski
Die Idee des Satzes soll kurz erläutert werden. Durch Entfernen von Knoten und anschließener Kantenkontraktion kann man jeden nicht planaren Graphen G zu einem einfacheren nicht planaren Graphen verkleinern. Dabei entfernt man solange Knoten und
die zugehörigen Kanten, bis der nächste Schritt den Graphen planar machen würde. Auf
diese Weise erhält man einen Untergraphen, der den K5 oder K3,3 darstellt. Somit ist G
subzusammenziehbar zum K5 oder K3,3 .
Um dies anschaulich nochmal darzustellen, wollen wir anhand des Satzes 4.5 und den
gerade genannten Schritten zeigen, dass der Petersen-Graph nicht planar ist.
4.3 Anwendung des Kuratowski-Theorems
Abbildung 4.5: Der Petersen-Graph P
Zunächst vereinfachen wir den Petersen-Graph P, indem wir einen beliebigen Knoten
und seine zugehörigen Kanten entfernen. Wir nennen unseren neuen Graph nun P0 . Das
Entfernen eines weiteren Knotens würde P0 planar machen.
Abbildung 4.6: Der vereinfachte Petersen-Graph P0
Nun führen wir mehrere Kantenkontraktionen in P0 durch. Hierbei ziehen wir jeweils
10
4 Charakterisierung planarer Graphen nach Kuratowski
die drei Knoten, die von Grad 2 sind, auf einen ihrer zwei Nachbarn und erhalten den
Graph in Abbildung 4.7.
Abbildung 4.7: P0 nach Kontraktionsschritt
Betrachtet man nun Anzahl und Grad der verbliebenen Knoten, fällt auf, dass alle sechs
Knoten von Grad 3 sind. Dies lässt schon auf den K3,3 schließen und ist nach Verschieben
der Knoten auch schnell zu sehen. Somit haben wir gezeigt, dass der Petersen-Graph P
subzusammenziehbar ist zum K3,3 , da unser vereinfachter Graph P0 ein Untergraph von
P ist und zusammenziehbar zum K3,3 ist. Hiermit folgt, dass der Petersen-Graph nicht
planar ist.
11
Literaturverzeichnis
[BdB] Aigner, Martin; Ziegler, Günter M. Das Buch der Beweise, Springer: Berlin, Heidelberg, 2015.
[BaRa] Blakrishnan, R.; Ranganathan, K. A textbook of Graph theory, Springer: New
York, 2000.
[HaHiMo] Harris, John M.; Hirst, Jeffry L.; Mossinghoff, Michael J. Combinatorics and
Graph theory, Springer: New York, 2008.
12

Download Report