Lösungen

1
Chr.Nelius: Graphentheorie (WS 2015/16)
14. Aufgabenblatt
Lösungen
53. Aufgabe: a) Da G Dreiecke enthält, ist G nicht bipartit. Folglich χ(G) ≥ 3 .
G ist ein schlichter planarer Graph. Nach dem Vierfarben–Satz (14.14) ist G 4–eckenfärbbar,
also χ(G) ≤ 4 .
b) Es gibt eine 4–Eckenfärbung von G (s. Bild), aber keine 3–Eckenfärbung (durch Ausprobieren festgestellt!). Wegen χ(G) ≤ 4 nach a) folgt dann χ(G) = 4 .
c) Es gibt eine 3–Flächenfärbung von G (s. Bild) . G ist eine Landkarte (3–zusammenhängend
und planar) und kein Euler–Graph, da es ungerade Ecken in G gibt. Nach (16.5) ist damit G
nicht 2–flächenfärbbar.
d) Es gilt n = 9 , Γ(G) = (4, 4, 4, 4, 4, 5, 5, 5, 5) ,
X
degG (v) = 40 =⇒ m = 20,
v∈E(G)
2 = n − m + f = 9 − 20 + f = −11 + f
=⇒
f = 13 .
Flächengradfolge von G ist F = (3, . . . , 3, 4) .
|
{z
12×
}
Mit (15.7) folgt dann n⋆ = f = 13 , m⋆ = m = 20 , f ⋆ = n = 9 .
Mit (15.9) f) und g) ergibt sich Γ(G⋆ ) = F und Flächengradfolge von G⋆ = Γ(G) .
e) Da G nach b) 4–eckenfärbbar ist, ist G⋆ nach (16.6) 4–flächenfärbbar. Wäre G⋆ 3–
flächenfärbbar, müsste G nach(16.6) 3–eckenfärbbar sein, was aber nicht der Fall ist, da
χ(G) = 4 gilt.
Wendet man (16.6) auf den dualen Graphen G⋆ an, so gilt:
G⋆ k–eckenfärbbar ⇐⇒ G⋆⋆ = G k–flächenfärbbar.
Da G 3–flächenfärbbar ist, ist also G⋆ 3–eckenfärbbar, d.h. χ(G⋆ ) ≤ 3. Wäre G⋆ 2–
eckenfärbbar, müsste G 2–flächenfärbbar sein, was nicht der Fall ist. Also χ(G⋆ ) = 3.
2
Chr.Nelius: Graphentheorie (WS 2015/16) , 14. Aufgabenblatt
f)
r
r
G⋆
r
r
r
r
r
r
r
r
r
r
G
r
g) Es gibt eine 4–Eckenfärbung von G . Da G zusammenhängend und planar ist, liegt jede
Ecke u von G in genau einer Fläche Fu⋆ von G⋆ . Da G keine Schlingen besitzt, gibt es nach
(1⋆ ) aus (14.13) in G⋆ keine Brücken (dies ist Voraussetzung für eine zulässige Flächenfärbung).
Färbe die Fläche Fu⋆ mit der Farbe von u . Dies liefert eine zulässige Flächenfärbung von G⋆ :
Sind nämlich Fu⋆ und Fv⋆ zwei Flächen von G mit einer gemeinsamen Randkante, so sind die
Ecken u und v von G adjazent (nach Konstruktion von G⋆ ) und daher unterschiedlich gefärbt.
Damit haben dann auch die beiden Flächen verschiedene Farben. G⋆ ist also 4–flächenfärbbar.
r
G⋆
r
r
r
r
r
r
r
r
r
G
=⇒
G 4–flächenfärbbar
⋆
r
r
G 4–eckenfärbbar
r
In dem Bild auf der linken Seite ist
der Graph G mit schwarzen Kanten
und farbigen Ecken eingezeichnet, der
Graph G⋆ mit roten Kanten und roten
quadratischen Ecken. Eine Fläche von
G⋆ ist mit der Farbe gefärbt, die
die in ihr liegende Ecke von G hat
(der Deutlichkeit halber sind unterschiedliche Farbtönungen gewählt worden) .
3
Chr.Nelius: Graphentheorie (WS 2015/16) , 14. Aufgabenblatt
Die zweite Frage lässt sich ganz entsprechend beantworten:
Der Graph G hat keine Brücken, folglich besitzt G⋆ keine Schlingen (dies ist Voraussetzung
für eine zulässige Eckenfärbung) . In jeder Fläche F von G liegt nach Konstruktion des dualen
Graphen genau eine Ecke uF von G⋆ . Färbe eine Ecke uF von G⋆ mit der Farbe der Fläche
F , in der diese Ecke liegt. Sind dann zwei Ecken uF1 und uF2 von G⋆ adjazent, so geht die
Kante, die diese beiden Ecken verbindet, durch eine gemeinsame Randkante von F1 und F2 ,
so dass dies beiden Flächen unterschiedlich gefärbt sind. Folglich haben auch uF1 und uF2
verschiedene Farben. Also ist G⋆ 4–eckenfärbbar.
rs
G⋆
G 3–flächenfärbbar =⇒
G⋆ 3–eckenfärbbar
rs
rs
rs
rs
rs
In dem Bild auf der linken Seite ist
der Graph G mit schwarzen Kanten
und Ecken, sowie mit farbigen Flächen
eingezeichnet, der Graph G⋆ mit roten
Kanten und quadratischen Ecken. Eine
Ecke von G⋆ wird mit der Farbe der
Fläche gefärbt, in der sie liegt. Es resultiert eine 3–Eckenfärbung von G⋆ .
rs
rs
rs
rs
rs
rs
G
rs
h) Zeichne den bidualen Graphen G⋆⋆ und vegleiche sein Bild mit dem von G .
r
r
G⋆
r
G⋆
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
G⋆⋆ ist wieder der ursprüngliche Graph G .
G⋆⋆
r
Chr.Nelius: Graphentheorie (WS 2015/16) , 14. Aufgabenblatt
4
54. Aufgabe: a) Nein G enthält Dreiecke.
b) Nein G enthält mehr als 2 ungerade Ecken und enthält deshalb weder eine Euler–Rundtour
noch eine Euler–Tour.
c) Nein Die beiden Ecken links unten und rechts oben haben den Grad 2. Deshalb gehören
die dazu inzidenten Kanten zu jedem Hamilton-Kreis. Da diese 4 Kanten aber schon einen
Kreis bilden, kann es keinen Hamilton–Kreis in G geben. (s. Konstruktionsregeln (8.18)).
d) Ja
e) Ja
f) Nein Wegen d) oder e) ist G nach dem Satz von Kuratowski nicht planar.
g) G enthält W6 als Untergraphen, so dass 4 = χ(W6 ) ≤ χ(G) gilt.
Nach dem Satz von Brooks, dessen Voraussetzungen hier alle erfüllt sind, gilt
χ(G) ≤ ∆(G) = 7 .
h)
Es gibt also eine 4–Eckenfärbung von G, so dass mit g) folgt χ(G) = 4 .
i) Eine (zulässige) Flächenfärbung ist nur für ebene Zeichnungen planarer Graphen möglich.
Chr.Nelius: Graphentheorie (WS 2015/16) , 14. Aufgabenblatt
55. Aufgabe:
5
Für die folgenden Aufgabenteile ist jeweils ein Beweis zu erbringen:
a) Ein Graph G mit n Ecken, der schlicht und n–chromatisch ist, ist der vollständige Graph
Kn .
Annahme: G ist nicht der vollständige Graph Kn . Dann gibt es zwei verschiedene Ecken u
und v , die nicht adjazent sind. Färbe die übrigen n −2 Ecken mit n −2 verschiedenen Farben,
und die beiden Ecken u und v, die ja nicht adjazent sind, mit einer (n−1)–ten Farbe. Dadurch
entsteht eine zulässige Eckenfärbung aus n − 1 Farben, d.h. G ist (n − 1)–eckenfärbbar, im
Widerspruch dazu, dass G die chromatische Zahl n hat.
b) Ein schlichter bipartiter Graph G mit Minimalgrad 4 ist nicht planar.
Da G bipartit ist, enthält G keine ungeraden Kreise, also insbesondere keine Dreiecke. Wäre
G planar, müsste G nach (11.11b) eine Ecke vom Grade ≤ 3 enhalten im Widerspruch zu der
Voraussetzung δ(G) = 4 .
c) Ist G ein planarer Graph, so ist die Anzahl der Flächen, die einen ungeraden Grad haben,
eine gerade Zahl.
Die Summe aller Flächengrade ist nach (10.8) gleich der doppelten Kantenzahl. Die Behauptung
wird dann ganz analog zum Beweis von (1.11) gezeigt.
d) K5 ist nicht planar (Gib einen Beweis, der (11.9) nicht benutzt. Führe einen indirekten
Beweis und benutze die EPF.)
Annahme: K5 ist planar. Dann gilt nach der EPF 2 = n − m + f = 5 − 10 + f , d.h.
f = 7 . Da K5 schlicht ist, gilt deg(F ) ≥ 3 für jede Fläche F von K5 . Mit (10.8) folgt
2m = 20 =
X
F
deg(F ) ≥ 7 · 3 = 21 ,
|
{z
≥3
}
d.h. 20 ≥ 21 . Das ist aber ein Widerspruch, so dass die Annahme falsch war.
e) Ein Euler–Graph besitzt keine Brücke.
In einem Euler–Graphen G gibt es einen geschlossenen Kantenzug, der jede Kante (genau einmal) enthält und der durch jede Ecke (mindestens einmal) verläuft, da G zusammenhängend
ist. Zwischen je zwei verschiedenen Ecken u und v gibt es also zwei Kantenzüge. Löscht man
nun eine beliebige Kante α von G , so bleibt immer noch ein Kantenzug (und damit ein Weg)
zwischen u und v , d.h. G − α bleibt zusammenhängend. Folglich ist α keine Brücke.
6
Chr.Nelius: Graphentheorie (WS 2015/16) , 14. Aufgabenblatt
56. Aufgabe: a) Beweise: Ein zusammenhängender planarer Graph G ist genau dann 2–
flächenfärbbar, wenn der duale Graph G⋆ bipartit ist.
Es sind zwei Beweisrichtungen erforderlich!
” =⇒ ”
Ist G 2–flächenfärbbar, so ist G⋆ 2–eckenfärbar. Dies folgt, wenn man (16.6)
auf den dualen Graphen G⋆ anwendet: G⋆ ist genau dann 2–eckenfärbbar, wenn G⋆⋆ = G
2–flächenfärbbar ist. Insbesondere gibt es in G⋆ keine Schlingen, so dass G⋆ nach (6.4) bipartit
ist.
” ⇐= ” Ist G⋆ bipartit, so ist G⋆ nach (6.4) 2–eckenfärbar. Nach (16.6) ist dann G⋆⋆ = G
2–flächenfärbbar ist.
b) Es sei G eine Landkarte mit 13 Flächen, die eine Euler–Rundtour enthält. Begründe, dass
G⋆ kein Hamilton–Graph ist.
Nach (16.5) ist G 2–flächenfärbbar, so dass G⋆ nach Aufgabenteil a) bipartit ist. Da G 13
Flächen besitzt, hat G⋆ 13 Ecken. Wäre G⋆ ein Hamilton–Graph, müsste es in G⋆ einen Kreis
der Länge 13 (ungerade!) geben, was aber in einem bipartiten Graphen nicht möglich ist.
c) Finde eine Landkarte H , die 13 Flächen und eine Euler–Rundtour besitzt. Zeichne H ⋆
mit geradlinigen Kanten und zeichne eine 2–Eckenfärbung von H ⋆ .
H
H⋆
H ist ein 3–zusammenhängender planarer
Graph, also eine Landkarte. H hat 8 Ecken
vom Grade 4 und eine Ecke vom Grade 8,
hat also 20 Kanten. Die Flächenzahl ist nach
der EPF m − n + 2 = 13 . Da jede Ecke
gerade und der Graph zusammenhängend ist,
ist H ein Euler–Graph. Nach (16.5) ist daher
H 2–flächenfärbbar. Eine 2–Flächenfärbung
von H lässt sich leicht zeichnen.
Da H eine Landkarte ist, ist H ⋆ schlicht
und lässt sich daher auch mit geradlinigen
Kanten zeichnen. H ist 2–flächenfärbbar.
Folglich ist H ⋆ 2–eckenfärbbar und bipartit.
Eine 2–Eckenfärbung lässt sich leicht finden.

Download Report