Diskrete Mathematik (D-ITET)

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<j≤6
1≤i<j≤6
wobei die erste Abschätzung aus der Voraussetzung folgt, dass jedes Paar von Aufgaben von echt
mehr als 25 der Studenten gelöst wurde.
Wir berechnen jetzt T auf eine andere Weise. Bezeichnen wir mit bn die Anzahl der Aufgaben, die
der n-te Student gelöst hat, so trägt dieser Student mit genau b2n zu T bei, es gilt also
T =
N X
bn
n=1
2
.
Hätte jeder Student höchstens vier Aufgaben gelöst, so wären alle bn ≤ 4 und damit
T ≤
N X
4
n=1
2
= 6N.
Dies ist aber ein Widerspruch zu (1). Also muss mindestens ein Student mehr als vier Aufgaben
gelöst haben. Da nach Voraussetzung kein Student alle 6 Aufgaben gelöst hat, muss es also einen
Studenten geben, der genau 5 Aufgaben lösen konnte.
Aufgabe 2
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.
1
Aufgabe 3
(2)
(a) Mit den Bezeichnungen AG = (aij ), A2G = (aij ), V = V (G) ergibt sich
|V |
X
(2)
aii
=
i=1
|V | |V |
X
X
|V |
X
aij aji =
i=1 j=1
i,j=1
a2ij
=
|V |
X
aij = 2|E(G)|,
i,j=1
das heisst die Summe der Diagonalelemente in A2G ist zweimal die Kantenanzahl von G. Das ist
(2)
auch klar, wenn man aii als die Anzahl Wege vom Knoten vi zu sich selbst der Länge 2 interpretiert (siehe Satz 2.29). Jeder solche Weg ist von der Form (vi , vj , vi ), beschreibt also die Kante
{vi , vj }. Wir bekommen zweimal die Kantenanzahl, weil auch der Weg (vj , vi , vj ) die gleiche Kante
{vj , vi } = {vi , vj } beschreibt.
(b) Behauptung: Der Graph G besitzt ein Dreieck genau dann, wenn die Summe der Diagonalelemente von A3G positiv ist.
Beweis: Ein Dreieck {vi , vj , vk } ∈ V3 erzeugt zum Beispiel den Spaziergang (vi , vj , vk , vi ) der
(3)
Länge 3. Deshalb ist (wieder mit Satz 2.29) aii > 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

Download Report