Transcript
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
