ETH Zürich, D-INFK HS 2015, 26. Oktober 2015 Prof. Ueli Maurer Daniel Tschudi Diskrete Mathematik Übung 7 7.1 Graphenisomorphie Sei G = (V, E) mit G ∼ = G und |V | = 4. a) (?) Zeigen Sie, dass G keine Knoten von Grad 0 oder 3 enthalten kann. b) (? ?) Bestimmen Sie (bis auf Isomorphie) alle möglichen G. (7 Punkte) (1 Punkt) (3 Punkte) c) (? ? ?) Zeigen oder widerlegen Sie: Die beiden unten gegebenen Graphen sind isomorph. (3 Punkte) 7.2 Reguläre Graphen (6 Punkte) Ein k-regulärer Graph ist ein Graph, bei dem von jedem Knoten k Kanten ausgehen. a) (? ?) Sei G = (V, E) ein k-regulärer Graph mit n := |V | Knoten und sei k ≥ n−1 2 . Beweisen Sie, dass G zusammenhängend ist. Hinweis: Betrachten Sie zwei Knoten u, v ∈ V die nicht verbunden sind, d.h. {u, v} ∈ / E und die Menge N (u) ∩ N (v) ihrer gemeinsamen Nachbarn. (4 Punkte) b) (? ?) Zeigen Sie, dass es keinen zusammenhängenden planaren 6-regulären Graphen gibt. (2 Punkte) 7.3 Bipartite Graphen (? ? ?) Zeigen Sie, dass ein zusammenhängender Graph genau dann bipartit ist, wenn er keinen Kreis mit ungerader Länge enthält. 7.4 Adjazenzmatrix (? ? ?) Sei G ein Graph und AG seine Adjazenzmatrix. Was erhält man, wenn man die Spur1 von A2G berechnet? 7.5 Planare Graphen (? ?) a) Zeichnen Sie alle (nicht-isomorphen) Bäume mit 6 Knoten. b) Entscheiden Sie, ob folgender Graph planar ist, und beweisen Sie Ihre Antwort. 7.6 Fakultativ: Kampf gegen die Hydra (? ? ? ? ?) Auf einer griechischen Insel kämpft Herakles gegen eine Hydra, ein schlangenähnliches Wesen mit vielen Köpfen. Diese kann als Baum T = (V, E) mit Wurzel r ∈ V dargestellt werden: Die Wurzel entspricht ihrem Rumpf und die Blätter den Köpfen. Mit p(v) bezeichnen wir den Elternknoten eines Knotens v ∈ V − {r} in dem Baum. Schlägt Herakles der Hydra einen Kopf l ∈ V mit p(l) 6= r ab, wachsen der Hydra nach folgender Regel weitere Köpfe nach: Sei Tl der Teilbaum mit Wurzel p(l) nachdem das Blatt l entfernt wurde. Füge zwei Kopien von Tl an p(p(l)) an. Die Hydra ist besiegt, wenn sie nur noch aus ihrem Rumpf besteht.2 Ist es möglich, jede Hydra zu besiegen? Beweisen Sie Ihre Antwort. Abgabe am 2. November 2015 Korrigiert werden Aufgaben 7.1 und 7.2 1 Die Spur einer Matrix ist die Summe ihrer Diagonalelemente. Auf der Vorlesungswebseite (http://www.crypto.ethz.ch/teaching/lectures/DM15/) kann man selbst in die Rolle des Herakles schlüpfen und versuchen, die Hydra zu besiegen. Das sollte auch beim Verständnis der Regeln für das Nachwachsen der Köpfe helfen. 2