TECHNISCHE UNIVERSITÄT MÜNCHEN Zentrum Mathematik P ROF. D R . D R . J ÜRGEN R ICHTER -G EBERT D R . VANESSA K RUMMECK Lineare Algebra und diskrete Strukturen 2 (Sommersemester 2015) — Aufgabenblatt 2 (27. April 2015) — — Präsenzaufgaben — Aufgabe 9. Zählen, die Erste. Fünf Tutoren und 30 Studierende sollen sich in eine Reihe stellen. Wie viele Möglichkeiten gibt es, wenn keine zwei Tutoren nebeneinander stehen sollen? Aufgabe 10. Die Formel aus der Vorlesung. Zeigen Sie, dass für jede natürliche Zahl n ∈ N folgende Formel gilt 2n 1 2n 2n · = − n n+1 n n+1 Aufgabe 11. Nebendiagonalen des Pascalschen Dreiecks. Gegeben sei nebenstehendes Pascalsches Dreieck: 1.) Berechnen Sie die Summe der Elemente auf den rot eingezeichneten Nebendiagonalen. Welche Zahlen ergeben sich dabei? 2.) Erklären Sie das Ergebnis aus Teilaufgabe 1. Aufgabe 12. Graphen, die Erste. 1.) Zeigen Sie: In jedem Graphen G = (E, K) gilt folgende Beziehungen zwischen Eckengrad deg(v) und Kantenanzahl |K|: X deg(v) = 2 · |K| v∈E 2.) Zeigen Sie: In jedem Graphen G = (E, K) mit |E| ≥ 2 gibt es mindestens zwei Ecken mit gleichem Grad. Aufgabe 13. Nicht planare Graphen. Gegeben seien die beiden Graphen K3,3 und K5 . 1.) Zeigen Sie ohne den Satz von Kuratowski: Die beiden Graphen sind nicht planar. K3,3 2.) Zeichnen Sie beide Graphen mit möglichst wenigen Überschneidungen. 3.) Sind diese Graphen überschneidungsfrei auf einem Torus zeichenbar? Falls ja, geben Sie eine Skizze an - falls nein, begründen Sie, warum es nicht geht. K5 — Hausaufgaben — Aufgabe 14. (4 Punkte) Zählen, die Zweite. Auf wie viele Arten kann ein König auf einem (8×8)-Schachbrett von der linken unteren Ecke in die rechte obere Ecke ziehen, wenn er dabei pro Zug entweder ein Feld nach rechts, ein Feld nach oben oder ein Feld (diagonal) nach rechts oben ziehen darf? Aufgabe 15. (8 Punkte) Formel zum Zählen bei Schnitt und Vereinigung endlicher Mengen. Für eine natürliche Zahl n ∈ N seienS n endliche Mengen M1 , M2 , . . . Mn gegeben. Es sei I := {1, 2, . . . , n} und M := i∈I Mi die Vereinigung aller T dieser endlichen Mengen. Ferner sei {} 6= J ⊆ I eine Teilmenge von I und MJ := i∈J Mi der Schnitt über alle endlichen Teilmengen Mi mit i ∈ J. Zeigen Sie, dass dann für die Anzahl |M | der Elemente von M gilt X (−1)|J|+1 |MJ | |M | = {}6=J⊆I Hinweis: Mann kann diese Formel über vollständige Induktion beweisen, aber das ist technisch anstrengend. Einfacher ist der folgende Weg: n P (−1)k nk = 0. a.) Zeigen Sie, dass für jede natürliche Zahl n ∈ N folgendes Lemma gilt: k=0 b.) Zeigen Sie, dass ein beliebiges x ∈ M mit m := |{i ∈ I : x ∈ Mi }| genau m X k+1 m (−1) k k=1 mal auf der rechten Seite der Gleichung gezählt wird und verwenden Sie dann das Lemma aus a.). Aufgabe 16. (3+3+3 = 9 Punkte) Graphen, die Zweite. 1.) Zeigen Sie: In jedem Graphen G = (E, K) ist die Anzahl der Ecken mit ungeradem Grad gerade. 2.) Geben Sie einen Hamiltonkreis für den Kantengraph eines Dodekaeders an. Bemerkung: Ein Hamiltonpfad ist ein Pfad, der jede Ecke eines Graphen genau einmal enthält. Ein Hamiltonkreis ist ein Hamiltonpfad, bei dem Anfangs- und Endpunkt übereinstimmen. 3.) Sei G ein zusammenhängender Graph mit der Eigenschaft, dass der Grad jeder Ecke gerade ist. Zeigen Sie: Ein solcher Graph besitzt einen Eulerpfad, der gleichzeitig auch ein Eulerkreis (Rundweg) ist. Bemerkung: Ein Eulerpfad ist ein Pfad, der jede Kante eines Graphen genau einmal enthält. Ein Eulerkreis ist ein Eulerpfad, bei dem Anfangs- und Endpunkt übereinstimmen. Aufgabe 17. (2 + 13 = 15 Punkte) Muster im Pascalschen Dreieck. 1.) Malen Sie ein Pascalsches Dreieck bis (mindestens) zur Zeile n = 17 auf ein Blatt Papier. Markieren Sie alle geraden Zahlen (z.Bsp. durch einen farbigen Kreis). Welches Muster erhalten Sie? 2.) Gehen Sie auf die Seite http://science-to-touch.com/CJS/examples/Pascal.html Erklären Sie für k = 1, . . . , 13 die jeweils dort entstehenden Muster. Aufgabe 18. ((3+4+5) + 3 = 15 Punkte) Nicht / planare Graphen. 1.) Zeichen Sie für k = 3, k = 4, k = 5 einen k-regulären planeren Graphen. Bemerkung: Ein Graph heißt k-regulär, wenn für jede Ecke v ∈ E gilt, dass deg(v) = k. 2.) Zeichnen Sie nebenstehenden Graphen (Petersengraph) mit möglichst wenigen Überschneidungen. Abgabe der Hausaufgaben: bis Montag, den 04.05.2015 um 12:00 Uhr im Briefkasten im UG.