Transcript
¨ ETH Zurich, D-INFK HS 2015, 26. Oktober 2015
Prof. Ueli Maurer Daniel Tschudi
Diskrete Mathematik ¨ Ubung 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 moglichen G.
(7 Punkte) (1 Punkt) (3 Punkte)
c) (? ? ?) Zeigen oder widerlegen Sie: Die beiden unten gegebenen Graphen sind isomorph. (3 Punkte)
7.2
Regul¨are Graphen
(6 Punkte)
Ein k-regul¨arer Graph ist ein Graph, bei dem von jedem Knoten k Kanten ausgehen. a) (? ?) Sei G = (V, E) ein k-regul¨arer Graph mit n := |V | Knoten und sei k ≥ n−1 2 . Beweisen Sie, dass G zusammenh¨angend 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 zusammenh¨angenden planaren 6-regul¨aren Graphen gibt. (2 Punkte) 7.3
Bipartite Graphen (? ? ?)
Zeigen Sie, dass ein zusammenh¨angender Graph genau dann bipartit ist, wenn er keinen Kreis mit ungerader L¨ange enth¨alt.
7.4
Adjazenzmatrix (? ? ?)
Sei G ein Graph und AG seine Adjazenzmatrix. Was erh¨alt man, wenn man die Spur1 von A2G berechnet? 7.5
Planare Graphen (? ?)
a) Zeichnen Sie alle (nicht-isomorphen) B¨aume 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 k¨ampft Herakles gegen eine Hydra, ein schlangen¨ahnliches Wesen mit vielen ¨ Kopfen. Diese kann als Baum T = (V, E) mit Wurzel r ∈ V dargestellt werden: Die Wurzel entspricht ihrem ¨ Rumpf und die Bl¨atter den Kopfen. Mit p(v) bezeichnen wir den Elternknoten eines Knotens v ∈ V − {r} in dem Baum. Schl¨agt Herakles der Hydra einen Kopf l ∈ V mit p(l) 6= r ab, wachsen der Hydra nach folgender ¨ ¨ zwei nach: Sei Tl der Teilbaum mit Wurzel p(l) nachdem das Blatt l entfernt wurde. Fuge Regel weitere Kopfe Kopien von Tl an p(p(l)) an. Die Hydra ist besiegt, wenn sie nur noch aus ihrem Rumpf besteht.2 ¨ Ist es moglich, 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 schlupfen und versuchen, die Hydra zu besiegen. Das sollte auch beim ¨ das Nachwachsen der Kopfe ¨ Verst¨andnis der Regeln fur helfen. 2
