Lösungen Aufgaben 26

1
Chr.Nelius: Graphentheorie (WS 2015/16) , 7.Aufgabenblatt
26. Aufgabe:
Beantworte die folgenden Fragen und gib jeweils eine Begründung:
a) Für welche Werte von n ist der vollständige Graph Kn bipartit und für welche nicht?
Nur für n = 2
b) Für welche Werte von n ist der Kreis–Graph Cn bipartit und für welche nicht?
Nur für gerades n
c) Ist der Petersen Graph P bipartit? Nein! Es gibt ungerade Kreise
v2
v3
v8
v1
v9
v10
v13
v7
v12
v4
v11
v6
v5
d) Ist der Graph G aus Aufgabe 13 (4. Üb.) bipartit? Ja! Es gibt eine 2–Eckenfärbung. (4)
27. Aufgabe: a) Wege zwischen a und d :
Es sind nur Wege der Länge 4, 6, 8, 10 möglich! (s. Bemerkung unten)
a−b−h−c−d
(Länge 4)
a−b−k−f −j−e−d
a−b−k−f −j−g−l−c−d
(Länge 6)
(Länge 8)
a−b−h−c−l−g−k−f −j−e−d
(Länge 10)
Auffällig: Alle gefundenen Wege zwischen a und d haben eine gerade Länge.
b) Wege zwischen a und c :
a−b−h−c
(Länge 3)
a−b−k−f −j−g−l−c
a−f −i−e−m−c
(Länge 5)
(Länge 7)
a−b−k−f −i−e−j −g−l−c
(Länge 9)
Auffällig: Alle gefundenen Wege zwischen a und c haben eine ungerade Länge.
c) Nach dem Beweis von (6.8) erhält man folgendermaßen eine Bipartition (U, V ) von G :
U = { u | u ∈ E(G) , es gibt einen Weg gerader Länge zwischen u und i } ∪ { i }
V = { v | v ∈ E(G) , es gibt einen Weg ungerader Länge zwischen v und i }
Wir bestimmen jetzt für jedes w ∈ E(G), w 6= i die Länge eines Weges zwischen w und i :
e−i , f −i
2 Wege der Länge 1
a−f −i , d−e−i , j −f −i , k−f −i , l−e−i , m−e−i
b−k−f −i, c−d−e−i , g−m−e−i
h−c−d−e−i
3 Wege der Länge 3
1 Weg der Länge 4
Folglich: U = { a, d, h, i, j, k, l, m }
,
6 Wege der Länge 2
V = { b, c, e, f, g }
2
Chr.Nelius: Graphentheorie (WS 2015/16) , 7. Aufgabenblatt
d) Färbe die Ecken von U mit einer Farbe (etwa rot) und die Ecken von V mit einer anderen
Farbe (etwa blau). Dies ergibt dann eine 2–Eckenfärbung von G, da adjazente Ecken immer
unterschiedlich gefärbt sind.
h
b
a
l
k
c
m
g
j
f
d
e
i
Bemerkung zu Aufgabe 27a)
Es gibt in G zwischen a und d nur gerade Wege der Länge 4, 6, 8, 10 !!!
Einen Weg der Länge 2 zwischen a und d gibt es offensichtlich nicht.
Da G 13 Ecken enthält, kann ein Weg höchstens die Länge 12 haben. Nach Aufg. 27c) gibt es
eine Bipartition (U, V ) mit |U | = 8 und |V | = 5 , so dass der Graph G bipartit ist. Dabei
gilt a, d ∈ U . Ein Weg zwischen a und d beginnt in a , springt zwischen den Ecken von V
und U hin und her und landet dann bei d . Dafür stehen nur die 5 Ecken von V zur Verfügung,
so dass ein Weg zwischen a und d höchstens die Länge 10 haben kann.
a
d
U
V
Chr.Nelius: Graphentheorie (WS 2015/16) , 7. Aufgabenblatt
3
28. Aufgabe: a) Ein Weg–Graph Pn ist ein Baum–Graph und daher nach (6.9) für n ≥ 2
bipartit. Für n = 1 ist P1 nicht bipartit, da ein bipartiter Graph nach (6.3a) mindestens 2
Ecken besitzt.
b) Am besten beginnt man die Eckenfärbung bei einer Endecke, etwa u.
w
w1
u
v
w2
c) T besitzt Endecken (5.6) . Färbe eine beliebige Endecke u gelb. u besitzt genau eine
Nachbarecke v, die rot gefärbt wird. Ist w eine beliebige Nachbarecke von v, so kann diese
nicht adjazent zu u ist, da es sonst einen Kreis u − v − w − u geben würde, den es aber in
einem Baum–Graphen nicht geben kann. Sind w1 und w2 zwei verschiedene Nachbarecken von
v , so sind diese nichtadjazent (sonst gäbe es einen Kreis v − w1 − w2 − v) . Also sind alle
Nachbarecken von v paarweise nichtadjazent und auch nicht adjazent zu u, so dass sie alle mit
gelb gefärbt werden können. Ist nun wi eine Nachbarecke von v, so können alle Nachbarecken
von wi wieder mit rot gefärbt werden. Setzt man dieses Verfahren fort, bis alle Ecken von T
gefärbt sind, so erhält man eine 2–Eckenfärbung von T .

Download Report