ETH Zürich
Institut für Theoretische Informatik
Prof. Dr. Emo Welzl
Dr. Johannes Lengler
HS 2014
Lösungsvorschlag zu Übungsblatt 3
Diskrete Mathematik (D-ITET)
Aufgabe 1
Der Petersengraph P kann wie unten abgebildet gezeichnet werden.
{2,3}
{1,4}
{4,5}
{1,5}
{1,3}
{2,4}
{3,5}
{2,5}
{1,2}
{3,4}
Ein Kreis in P der Länge l ist eine Folge ({a1 , b1 }, {a2 , b2 }, . . . , {al , bl }) paarweise verschiedener
Zweiermengen mit {ai , bi } ∩ {ai+1 , bi+1 } = ∅ für alle i = 1, 2, . . . , l − 1 und {al , bl } ∩ {a1 , b1 } = ∅.
Angenommen, es gäbe einen Kreis der Länge 3 in P , dieser hat die Form ({a, b}, {c, d}, S), wobei
a, b, c, d paarweise verschieden sind und S eine zweielementige Teilmenge von M . Nun folgt aus
{c, d} ∩ S = ∅, dass S ⊆ {a, b, e}, und aus S ∩ {a, b} = ∅, dass S ⊆ {c, d, e}. Insgesamt gilt also
S ⊆ {e}, offenbar ein Widerspruch.
Angenommen, es gäbe einen Kreis der Länge 4 in P , dieser hat o.B.d.A. die Form ({a, b}, {c, d},
{a, e}, S), wobei a, b, c, d, e paarweise verschieden sind und S eine zweielementige Teilmenge von
M . Nun folgt aus {a, e} ∩ S = ∅, dass S ⊆ {b, c, d}. Wegen S 6= {c, d} gilt demnach b ∈ S, im
Widerspruch zu S ∩ {a, b} = ∅.
Offenbar gibt es aber viele Kreise der Länge 5 in P (siehe Abbildung).
Aufgabe 2
Die Aussage ist falsch. Knoten 2 in folgendem Graph ist ein Gegenbeispiel:
3
1
2
4
Beachten Sie, dass die Aussage eine “genau dann, wenn”-Aussage war. Daher ist auch Knoten 1 in
folgendem Graph ein gültiges Gegenbeispiel. Dieser liegt nicht auf einem Kreis, aber trotzdem ist
der Graph nach seinem Entfernen noch zusammenhängend.
1
1
2
Aufgabe 3
Wie im Skript beschrieben, besteht die Knotenmenge von Qd aus allen Bitfolgen der Länge d;
ausserdem sind zwei Knoten genau dann durch eine Kante verbunden, wenn sich ihre Folgen an
genau einer Stelle unterscheiden.
Vorbemerkung: Man kann den Zusammenhang von Qd zerstören, indem man d Knoten entfernt,
nämlich alle Nachbarn eines ausgewählten Knotens. Also ist Qd nicht d + 1-zusammenhängend.
Es gibt (mindestens) zwei Wege, zu beweisen, dass ein Graph d-zusammenhängend ist. Entweder
arbeitet man direkt mit der Definition, oder man benutzt den Satz von Menger. Wir illustrieren
im Folgenden beide Alternativen.
Direkter Beweis
Wir beweisen mit Induktion über d, dass das Entfernen einer Menge von d − 1 Knoten den Zusammenhang von Qd nicht zerstört. Für d = 2 stimmt die Aussage offensichtlich (entfernt man
einen Knoten aus Q2 = C4 , so ist der verbleibende Graph immer noch zusammenhängend). Wir
nehmen nun die Gültigkeit der Aussage für ein festes d ≥ 2 an, und zeigen, dass sie dann auch
für d + 1 stimmt. Sei X ⊆ V (Qd+1 ) eine Menge von d Knoten, und sei k eine Stelle, an der sich
die Bitfolgen von zwei Knoten aus X unterscheiden. Wir betrachten jetzt die beiden Teilgraphen
H0 und H1 von Qd+1 , die durch alle Knoten induziert werden, deren k-tes Bit eine 0 bzw. eine 1
ist. Sowohl H0 als auch H1 sind offenbar Kopien von Qd . Ausserdem verlaufen genau 2d Kanten
zwischen den beiden Teilgraphen H0 und H1 ; alle Endknoten dieser Kanten sind verschieden. Es
seien X0 und X1 die Knoten der Menge X in den beiden Teilgraphen H0 bzw. H1 . Nach Wahl der
Koordinate k sind die Mengen X0 und X1 beide nichtleer. Da sie zusammen genau d Knoten enthalten, enthält jede höchstens d − 1 Knoten. Nach Induktionsvoraussetzung ist also, wenn man aus
H0 alle Knoten der Menge X0 entfernt, der verbleibende Graph noch zusammenhängend. Gleiches
gilt für den Graphen, der verbleibt, wenn man aus H1 alle Knoten der Menge X1 entfernt. Wir
müssen nun noch zeigen, dass wenigstens eine Kante verbleibt, auf der man zwischen den beiden
Hälften “hin- und herspringen” kann. Dies folgt aber leicht, da von den 2d Kanten zwischen den
beiden Teilgraphen H0 und H1 höchstens d viele zerstört werden und sicher 2d > d gilt.
Beweis mit Menger
Um zu zeigen, dass Qd d-zusammenhängend ist, genügt es nach dem Satz von Menger, zwischen je
zwei verschiedenen Knoten d intern knotendisjunkte Pfade zu finden. Seien daher x = (x1 , . . . , xd )
und y = (y1 , . . . , yd ) zwei beliebige Bitfolgen der Länge d, die sich in genau k ∈ {1, . . . , d} Bits
unterscheiden. Wir können ohne Einschränkung annehmen, dass die ersten k Bits verschieden
sind, während die letzten d − k Bits gleich sind. Darüber hinaus können wir ohne Einschränkung
annehmen, dass x = (0, . . . , 0) und y = (1, . . . , 1, 0, . . . , 0) ist.
| {z } | {z }
k
d−k
Nun definieren wir d Pfade P1 bis Pd zwischen x und y. Für i ≤ k definieren wir einen Pfad Pi
der Länge k wie folgt:
• Wir starten in x.
• Im s-ten Schritt (1 ≤ s ≤ k) ändern wir das (i + s)-te Bit von 0 auf 1, falls i + s ≤ k ist;
andernfalls ändern wir das (i + s − k)-te Bit. Im Vorgriff auf spätere Teile der Vorlesungen
kann man äquivalent sagen: “Wir ändern das Bit mit Index (i + s mod k).”
Es ist offensichtlich, dass Pi ein Pfad von x nach y ist, da jedes Bit von 1 bis k in genau einem Schritt
von 0 auf 1 gesetzt wird. Als nächstes zeigen wir, dass die Pfade knotendisjunkt sind. Dazu stellen
wir fest, dass nach dem s-ten Schritt genau s Bits auf 1 gesetzt sind. Gäbe es in zwei Pfaden Pi
und Pj zwei gleiche interne Knoten x1 und x2 , so müssten diese natürlich insbesondere in der Zahl
2
der 1-Bits übereinstimmen. Also würden die Knoten nach gleich vielen Schritten s ∈ {1, . . . k − 1}
erreicht. Wieder ohne Einschränkungen nehmen wir an, dass i > j. In x1 ist das i-te Bit ein 1-Bit.
Damit es auch in x2 ein 1-Bit ist, müssen nach Konstruktion von x2 alle Bits zwischen j und i
ebenfalls auf 1 gesetzt worden sein. Umgekehrt ist in x2 das j-te Bit ein 1-Bit. Damit es auch
in x1 ein 1-Bit ist, müssen alle Bits mit Index > j oder < i ebenfalls auf 1 gesetzt worden sein.
Insgesamt müssen damit alle Bits in x1 und x2 auf 1 gesetzt sein, was ein Widerspruch zu s ≤ k −1
ist.
Nun definieren wir die weiteren Pfade Pi , k + 1 ≤ i ≤ d wie folgt:
• Wir starten in x.
• Im ersten Schritt ändern wir das i-te Bit auf 1.
• In den nächsten k Schritten ändern wir die Bits 1, . . . , k nacheinander von 0 auf 1.
• Im letzten Schritt ändern wir das i-te Bit zurück auf 0.
Wieder ist offensichtlich, dass alle Pi Pfade von x nach y sind. Weiter gilt, dass in alle internen
Knoten des Pfades i das i-te Bit auf 1 gesetzt ist. Dagegen ist das i-te Bit jedes Knoten in jedem
anderen Pfad (egal ob vom ersten oder vom zweiten Typ) auf 0 gesetzt. Also hat keiner der Pfade
Pi einen gemeinsamen internen Knoten mit irgendeinem anderen Pfad.
Damit haben wir bewiesen, dass es zwischen je zwei Knoten d intern knotendisjunkte Pfade gibt.
Nach dem Satz von Menger ist der Graph damit d-zusammenhängend.
Aufgabe 4
Wir betrachten den vollständigen Graphen mit den sechs Knoten 1, 2, . . . , 6. Zusätzlich fügen wir
eine Schleife an jeden Knoten an. Jede Kante dieses Graphen steht für einen der 21 Dominosteine
(Die Schleifen stehen für die Steine, welche zweimal die gleiche Augenzahl aufweisen). Jede Anordnung der Dominosteine, welche die verlangte Bedingung erfüllt, entspricht einem Eulerspaziergang
in diesem Graphen. Ein Eulerspaziergang ist ein Weg, der jede Kante des Graphen genau einmal
enthält, dessen Anfangs- und Endpunkt aber nicht notwendigerweise identisch sind (bei einer Eulertour sind Anfangs- und Endpunkt identisch). Es lässt sich leicht zeigen, dass in einem Graphen
ein Eulerspaziergang existiert, genau dann wenn der Graph zusammenhängend ist und höchstens
zwei Knoten ungeraden Grad haben. In unserem Graphen haben alle sechs Knoten Grad 7 (die
Schleifen zählen doppelt), eine ungerade Zahl. Also enthält unser Graph keinen Eulerspaziergang.
Aufgabe 5
(a) Wir interpretieren die Städte und Strassen als die Knoten und Kanten eines Graphen G =
(V, E). Dann ist G zusammenhängend, und jeder Knoten hat geraden Grad, also verfügt G
über eine Eulertour. Wir starten in einem beliebigen Knoten v0 und laufen die Eulertour ab.
Beim Verlassen eines Knotens v durch eine Kante e entscheiden wir wie folgt, ob wir e säubern.
Wenn von v vor dem Verlassen eine gerade Zahl von sauberen Kanten ausgehen, dann säubern
wir e, bei einer ungeraden Zahl säubern wir e nicht. Auf diese Weise gehen von jedem Knoten
beim Verlassen eine ungerade Zahl an sauberen Kanten aus.
Wenn wir die Eulertour beendet haben, dann gehen von jedem Knoten v 6= v0 eine ungerade
Zahl von sauberen Kanten ab, denn nach dem letzten Besuch von v war die Zahl ungerade.
Für v0 funktioniert dieses Argument nicht. Wir zeigen daher auf andere Weise, dass von v0
eine ungerade Zahl von sauberen Kanten ausgeht. Für jeden Knoten v sei s(v) die Zahl der von
v ausgehenden sauberen Kanten, und es sei S die Gesamtzahl der sauberen Kanten. Dann ist
P
v∈V s(v) = 2S, denn auf der linken Seiten zählen wir jede saubere Kanten genau zweimal.
Nun wissen wir für alle 199PKnoten in V \ {v0 } schon, das s(v) ungerade ist. Wäre s(v0 )
gerade, so wäre die Summe v∈V s(v) insgesamt ungerade und könnte nicht mit der rechten
Seite übereinstimmen. Also ist s(v0 ) ebenfalls ungerade.
3
(b) Wir nehmen an, es gäbe eine Lösung. Wie in (a) bezeichnen
wir dann mit s(v) die Anzahl der
P
von v ausgehenden sauberen Strassen. Es gilt dann v∈V s(v) = 2S. Nach Voraussetzung ist
jedes s(v) ungerade Bei der linken Seite der Gleichung handelt es sich also um eine ungerade
Anzahl ungerader Zahlen; damit ist die gesamte linke Seite ungerade. Dagegen ist die rechte
Seite gerade. Wir haben also eine Widerspruch, womit unsere Annahme, es gäbe eine Lösung,
falsch gewesen sein muss.
Zur Anmerkung: Man kann die Aussage in der Anmerkung wie folgt aus (a) herleiten. Wie in (a)
identifizieren wir Städte und Strassen als die Knoten und Kanten eines Graphen G = (V, E). Nun
betrachten wir den Multigraphen G0 = (V, E 0 ), der entsteht, wenn wir jede Kante in G verdoppeln.
Man kann sich leicht überlegen, dass auch Multigraphen über eine Eulertour verfügen, wenn sie
zusammenhängend sind und alle Knotengrade gerade sind. Wir betrachten also eine Eulertour in
G0 . Mit derselben Konstruktion wie in (a) säubern wir einige der Kanten in G0 , sodass am Ende
von jedem Knoten in G0 eine ungerade Anzahl Kanten ausgeht.
Nun legen wir wie folgt fest, welche Kanten des ursprünglichen Graphen G wir säubern wollen.
Einer Kante e von G entsprechen zwei Kanten e1 und e2 in G0 . Wir säubern e falls genau eine der
beiden Kanten e1 und e2 sauber ist. (Beachten Sie, dass wir e also nicht säubern, wenn sowohl e1
als auch e2 sauber sind.) Auf diese Weise ist sichergestellt, dass auch in G von jedem Knoten eine
ungerade Anzahl sauberer Kanten ausgehen. Damit ist die Behauptung bewiesen.
4
© Copyright 2024 ExpyDoc
