Transcript
ETH Zürich Institut für Theoretische Informatik Prof. Dr. Angelika Steger Dr. Uli Wagner
HS 2011 Lösungsvorschlag zu Übungsblatt 4
Diskrete Mathematik (D-ITET)
Aufgabe 1 Wir numerieren die Studenten von 1, . . . , N . Es sei T die Anzahl der Tripel (i, j, n) (1 ≤ i < j ≤ 6, 1 ≤ n ≤ N ) für die gilt: Student n hat Aufgabe i und Aufgabe j erfolgreich gelöst. Bezeichnen wir mit ai,j die Anzahl der Studenten, die Aufgabe i und Aufgabe j gelöst haben, so gilt X X 2 6 2 T = ai,j > N= N = 6N, (1) 5 2 5 1≤i 0 und folglich auch die Summe der Diagok 3 nalelemente von AG positiv (die Einträge in AG sind immer nicht-negativ). Umgekehrt, wenn die (3) Summe der Diagonalelemente von A3G positiv ist, ist auch mindestens ein aii positiv, insbesondere existiert ein Spaziergang der Länge 3 von vi zu sich selbst. Man sieht sofort, dass ein Spaziergang der Länge 3 mit gleichem Anfangs- und Endknoten immer ein Dreieck beschreibt (eine Kante kann nicht zweimal durchlaufen werden). P|V | (3) Behauptung: Die Anzahl der Dreiecke in G ist 61 i=1 aii . (3)
Dies folgt wieder unmittelbar aus der Interpretation von aii unter Berücksichtigung der Tatsache, dass ein Dreieck {vi , vj , vk } durch die 6 Spaziergänge (vi , vj , vk , vi ), (vi , vk , vj , vi ), (vj , vi , vk , vj ), (vj , vk , vi , vj ), (vk , vi , vj , vk ) und (vk , vj , vi , vk ) beschrieben wird.
Aufgabe 4 (a) Uhr
Unterhose
Unterhemd
Hose
Gürtel
Socken
Schuhe
Hemd
Krawatte
Jackett (b) Eine Möglichkeit ist Unterhose → Unterhemd → Uhr → Hose → Socken → Hemd → Gürtel → Schuhe → Krawatte → Jackett.
2
(c) Die Anzahl der Anziehreihenfolgen entspricht genau der Anzahl topologischer Sortierungen des Graphen aus (a) und lässt sich wie folgt berechnen. Zunächst ist der Knoten Uhr nicht mit dem restlichen Graphen verbunden, ihm kann also eine beliebige Position zugeordnet werden, wofür es 10 Möglichkeiten gibt. Da ausserdem der Teilgraph aus Socken, Unterhose, Hose, Gürtel und Schuhen einerseits, und der Teilgraph aus Unterhemd, Hemd, Krawatte und Jackett andererseits nicht miteinander verbunden sind, können wir frei bestimmen, welche der 9 übrigen Positionen durch Knoten des ersten Teilgraphs ausgefüllt werden. Dafür gibt es offenbar 95 Wahlmöglichkeiten. Um die Knoten des ersten Teilgraphen intern zu sortieren (auf den dafür ausgewählten fünf Positionen), stellt man zum Beispiel fest, dass die Hose in diesem Teilgraphen einen Vorgängerknoten und zwei Nachfolgerknoten hat. Also kann sie nur an zweiter oder dritter Stelle auftreten. Nun gibt es genau vier Möglichkeiten, bei der die Hose an dritter Stelle kommt (Gürtel und Schuhe kommen in beliebiger Reihenfolge später, Socken und Unterhemd in beliebiger Reihenfolge früher), und drei Möglichkeiten, bei denen die Hose an zweiter Stelle kommt (die Reihenfolge ist durch die Position des Gürtels an Position 3, 4 oder 5 eindeutig festgelegt). Insgesamt ergeben sich also 7 Möglichkeiten, den ersten Teilgraphen zu sortieren. Die Knoten des zweiten Teilgraphen können schliesslich auf genau 2 verschiedene Arten auf die dafür ausgewählten vier Positionen verteilt werden. Insgesamt ergeben sich daher 10 ·
9 · 7 · 2 = 17640 5
mögliche Anziehreihenfolgen. Der Professor kann sich also mehr als 48 Jahre lang täglich anders anziehen.
Aufgabe 5 (a) Offenbar summieren sich in jedem Graphen die Knotengrade zur doppelten Kantenzahl, in P einem Baum T = (V, E) muss also v∈V deg(v) = 2|E| = 2(|V | − 1) = 2|V | − 2 gelten. Summieren sich andererseits vorgegebene Knotengrade d1 , . . . , dn zu 2n − 2, so lässt sich ein Kodewort Pn erstellen, in dem jede Zahl i genau di − 1 mal vorkommt. Dieses Kodewort hat die Länge i=1 (di − 1) = (2n − 2) − n = n − 2. Interpretiert man dieses Kodewort als Prüferkode und konstruiert den dazugehörigen Baum, so hat dieser die gewünschte Gradsequenz. (b) Die Anzahl markierter Bäume zu einer gegebenen Gradsequenz lässt sich aus der Anzahl Kodewörter der Länge n − 2 ermitteln, die jede Zahl i genau di − 1 mal enthalten. Deren Anzahl ist offenbar (n − 2)! Qn . i=1 (di − 1)! (c) Im Prüferkode eines Baumes kommen genau die Blätter nicht vor. Kommt jede Zahl aus {1, 2, . . . , n} höchstens einmal im Kodewort vor, so kommen genau zwei Zahlen nicht vor. Ein Baum mit genau zwei Blättern ist ein Pfad. Demnach haben genau alle Pfade auf n Knoten einen Prüferkode mit den geforderten Eigenschaften.
3
