§13: Der Satz von Kuratowski

Chr.Nelius: Graphentheorie (WS 2015/16)
44
§13 : Der Satz von Kuratowski
In diesem Paragraphen soll ein Planaritätskriterium angegeben werden.
Aus einem gegebenen Graphen G kann man einen neuen Graphen H bilden, indem man in gewisse
Kanten von G neue Ecken einfügt, die dann alle in dem Graphen H den Grad 2 haben. Man nennt
dann H eine Unterteilung von G . Bei diesem Prozess ändert sich nichts an der Eigenschaft von G ,
planar zu sein oder nicht.
G
H
In diesem Beispiel sind die beiden Graphen G und H planar.
K3,3
H
Hier sind beide Graphen nicht planar.
(13.1) DEF: G und H seien Graphen. H heißt Unterteilung von G , wenn H aus G durch
Einfügen neuer Ecken vom Grade 2 in Kanten von G entsteht.
(13.2) BEM: a) Bei einer Unterteilung soll es auch möglich sein, überhaupt keine Ecke vom
Grade 2 einzufügen, d.h. wir können G als eine Unterteilung von sich selbst auffassen.
b) G ist i.a. kein Untergraph einer Unterteilung H von G , es sei denn, es gilt G = H .
(13.3) SATZ: G sei ein Graph. Dann gilt:
a) Ist G planar, so ist auch jede Unterteilung von G planar.
b) Ist G nicht planar, so ist auch jede Unterteilung von G nicht planar.
45
Chr. Nelius: Graphentheorie (WS 2015/16)
(13.4) SATZ: Kuratowski (1930)
Für einen Graphen G sind folgende Aussagen äquivalent:
a) G ist planar
b) G enthält keine Unterteilung von K5 oder K3,3 als Untergraphen.
Kazimierz Kuratowski , 1896–1980, polnischer Mathematiker.
Bew: a) =⇒ b)
Annahme: G enthält eine Unterteilung H von K5 oder K3,3 als Untergraphen. Da K5 und K3,3
beide nicht planar sind, ist dann auch H nach (13.3b) nicht planar. Damit enthält G den nichtplanaren Untergraphen H , und ist daher nach (10.3b) selbst nicht planar.
b) =⇒ a)
Der Beweis ist zu lang und kompliziert, als dass er hier geführt werden könnte.
(13.5) ANWENDUNG: Der Petersen–Graph ist nicht planar.
Es werden die beiden rot eingezeichneten Kanten gelöscht. In dem Untergraphen P ′ entstehen
dadurch 4 Ecken (rot gezeichnet) vom Grade 2 .
P :
P′ :
Entfernt man nun diese Ecken vom Grade 2 , so entsteht der Graph P ′′ , der eine Darstellung des
Graphen K3,3 ist (s. Aufg. 44a) :
P ′′ :
K3,3 :
Folglich ist P ′ eine Unterteilung von K3,3 . Damit enthält P einen Untergraphen, der eine Unterteilung von K3,3 ist, und ist daher nach dem Satz (13.4) von Kuratowski nicht planar.
46
Chr. Nelius: Graphentheorie (WS 2015/16)
(13.6) BEM: a) Ein nichtplanarer Graph muss nicht notwendig K5 oder K3,3
selbst als einen Untergraphen enthalten, sondern nur eine Unterteilung eines dieser
beiden Graphen.
!
b) Enthält ein Graph G eine Unterteilung von K5 als Untergraphen, so muss G mindestens 5 Ecken
vom Grade ≥ 4 besitzen.
c) Enthält ein Graph G eine Unterteilung von K3,3 als Untergraphen, so muss G mindestens 6
Ecken vom Grade ≥ 3 besitzen.
d) (13.4) beschreibt die Planarität eines Graphen mit rein graphentheoretischen Eigenschaften (Untergraph, Unterteilung, K5 , K3,3 ) , während die ursprüngliche Definition geometrischer Natur ist
(Zeichnung in der Ebene, Überschneidungen der Kanten).
e) Für die praktische Anwendung ist dieser Satz weniger geeignet, da er einen zu großen Aufwand erfordert. Es gibt heute brauchbare algorithmische Verfahren, die Planarität eines Graphen festzustellen,
die nicht auf diesem Satz beruhen.

Download Report