Musterlösung für den

“Diskrete Strukturen”-Teil der Vordiploms-Klausur Mathematik II für Informatiker (15.3.1999)

Professor Dr. G. Hiß, Lehrstuhl D für Mathematik, RWTH Aachen Professor Dr. E. Triesch, Lehrstuhl II für Mathematik, RWTH Aachen

Aufgabe 10. (8 Punkte) Es seien a_{1}, ..., a_{n} beliebige natürliche Zahlen. Zeigen Sie die folgenden Aussagen.

a) Zwei der Zahlen aus der Menge N = {0, a_{1}, a_{1} + a_{2}, ..., a_{1} + a_{2} + ... + a_{n}} ergeben bei Division durch n denselben Rest.

b) Es gibt zwei Zahlen 0 ≤ k < l ≤ n, so daß ∑_{i=k+1}^{l} a_{i} ein Vielfaches von n ist.

Lösung: zu a) Es gibt genau die n verschiedenen Reste {0, 1, 2, ..., n − 1} bei Division durch n. Da nun |N| = n + 1 > n folgt sofort nach dem ‘Schubfachprinzip’, daß zwei der Zahlen in N denselben Rest modulo n ergeben. Setzt man a_{0} = 0, so gibt es zwei Zahlen 0 ≤ k < l ≤ n, so daß die beiden Zahlen mit demselben Rest ∑_{i=0}^{k} a_{i} und ∑_{i=0}^{l} a_{i} sind. zu b) Die Zahl ∑_{i=k+1}^{l} a_{i} = ∑_{i=0}^{l} a_{i} − ∑_{i=0}^{k} a_{i} > 0 hat den Rest 0 bei Division durch n und ist daher ein Vielfaches von n.

Aufgabe 11. (8 Punkte) Es sei a_{n} für n ∈ N die Anzahl der Mengen S ⊆ {1, ..., n} mit der Eigenschaft, daß {x, x + 1| x ∈ S} = {1, ..., n} ist. Drücken Sie die Zahlen a_{n} für n ∈ N mit Hilfe der Fibonacci-Zahlen aus. (Hinweis: Beweisen Sie eine Rekursion für die a_{n}.)

Lösung: Es gilt a_{1} = 0, denn für n = 0 gibt es keine derartige Menge. Ferner a_{2} = 1 und a_{3} = 1, denn {1} und {1, 2} sind die einzigen derartigen Mengen. Es sei nun S_{n} für n ≥ 4 die Menge aller Mengen mit der gewünschten Eigenschaft. Weiter sei

S′_{n} = {S ∈ S_{n}|n − 2 ∈ S}
S′′_{n} = S_{n} \ S′_{n}.

Es gilt n − 3 ∈ S für alle S ∈ S′′_{n}. Nun folgt |S′_{n}| = |S_{n−1}|, denn für jedes S ∈ S′_{n} ist S − {n − 1} ∈ S_{n−1} und für jedes S′ ∈ S_{n−1} ist S′ ∪ {n − 1} ∈ S′_{n}. Weiter folgt |S′′_{n}| = |S_{n−2}|, denn für jedes S ∈ S′′_{n} ist S − {n − 1} ∈ S_{n−2} und für jedes S′′ ∈ S_{n−2} ist S′′ ∪ {n − 1} ∈ S′′_{n}. Daher folgt

a_{n} = |S_{n}| = |S′_{n}| + |S′′_{n}| = |S_{n−1}| + |S_{n−2}| = a_{n−1} + a_{n−2},

d.h. die a_{n} genügen der Rekursion der Fibonaccizahlen F_{n′} bei verschobenen Anfangsbedingungen (a_{1} = 0, a_{2} = 1 und a_{3} = 1 statt F_{0} = 0, F_{1} = 1 und F_{2} = 1) und es folgt a_{n} = F_{n−1} für n ≥ 1.

Aufgabe 12. (8 Punkte) Gegeben sei eine Folge von Graphen (G_{n})_{n≥1}, so daß G_{1} = ({v_{1}}, ∅) und für n ≥ 2 der Graph G_{n} = (V_{n}, E_{n}) aus G_{n−1} = (V_{n−1}, E_{n−1}) entsteht, indem man zu V_{n−1} eine Ecke v_{n} hinzufügt und mit mehr als \frac{n−1}{2} Ecken von G_{n−1} verbindet, d.h. |N(v_{n})| > \frac{n−1}{2}. Zeigen Sie, daß G_{n} für n ≥ 3 hamiltonsch ist.

Lösung: (Induktion) Es gilt G_{1} = K_{1}, G_{2} = K_{2} und G_{3} = K_{3}, womit die Aussage für n = 3 richtig ist. Es sei nun G_{n−1} hamiltonsch und O.B.d.A.

C = x_{1}x_{2}...x_{n−1}x_{1}

ein Hamiltonkreis in G_{n−1}. Da |N(v_{n})| > \frac{n−1}{2}, existiert ein Index 1 ≤ i ≤ n − 1 mit x_{i}, x_{i+1} ∈ N(v_{n}) (Indizes modulo (n − 1)). Daher ist

C′ = x_{1}x_{2}...x_{i}v_{n}x_{i+1}...x_{n−1}x_{1}

ein Hamiltonkreis in G_{n} und die Behauptung ist bewiesen.

Aufgabe 13. (9 Punkte) Zeigen Sie, daß P_{n,k} für n, k ∈ N die Anzahl der ungeordneten Zahlpartitionen

n + k^{2} − k = n_{1} + n_{2} + ... + n_{k}

von n + k^{2} − k in genau k Summanden ist, für die |n_{i} − n_{j}| ≥ 2 für alle 1 ≤ i < j ≤ k gilt.

Lösung: Es sei P_{n,k} die Menge aller ungeordneten k-Zahlpartitionen von n. Es sei weiter P′_{n,k} die Menge aller ungeordneten k-Zahlpartitionen

n = n_{1} + n_{2} + ... + n_{k}

von n mit |n_{i} − n_{j}| ≥ 2 für alle 1 ≤ i < j ≤ k. Gegeben sei der Ferrergraph eines Elementes aus P_{n,k}. O.B.d.A. enthalte die Zeile i + 1 mehr Sterne als die Zeile i für 1 ≤ i ≤ k − 1. Fügt man nun für 1 ≤ i ≤ k in der i-ten Zeile jeweils 2(i − 1) Sterne hinzu, dann erhält man ein Element aus P′_{n′,k} mit

n′ = n + ∑_{i=1}^{k} 2(i − 1) = n + 2 ∑_{i=1}^{k−1} i = n + 2\frac{k(k − 1)}{2} = n + k^{2} − k.

*  *
*  ***
**  *******
**** ⟶ ***********
****  *************
*****  ****************

Nun sei umgekehrt der Ferrergraph eines Elementes aus P′_{n′,k} gegeben. O.B.d.A. enthalte wieder die Zeile i+1 mehr Sterne als die Zeile i für 1 ≤ i ≤ k−1. Wegen der Definition von P′_{n′,k} folgt sofort, daß für 1 ≤ i ≤ k die i-te Zeile mindestens 2(i − 1) + 1 Sterne enthalten muß. Streicht man nun für 1 ≤ i ≤ k in der i-ten Zeile jeweils 2(i − 1) Sterne, dann erhält man ein Element aus P_{n,k}. Die Mengen P_{n,k} und P′_{n′,k} stehen daher in Bijektion und es folgt

|P′_{n′,k}| = |P′_{n+k^{2}−k,k}| = |P_{n,k}| = P_{n,k}.
*  *
*  ***
**  *******
**** ⟵ ***********
****  *************
*****  ****************

Aufgabe 14. (7 Punkte) Die Folge (a_{n})_{n≥0} genüge der Rekursion a_{n+4} + 3a_{n+3} + a_{n+2} = 3a_{n+1} + 2a_{n} mit den Anfangsbedingungen a_{0} = 8, a_{1} = −8 und a_{2} = 24. Bestimmen Sie eine explizite Darstellung dieser Folge.

Lösung: Gemäß dem Satz über Rekursionen aus der Vorlesung gilt q(z) = 1 + 3z + z^{2} − 3z^{3} − 2z^{4}. Die Nullstellen z = 1 und z = −1 kann man leicht erraten. Damit ergibt sich q(z) = 1+3z +z^{2} −3z^{3} −2z^{4} = (1−z)(1+z)^{2}(1+2z) und daher α_{1} = 1, d_{1} = 1, α_{2} = −1, d_{2} = 2 und α_{3} = −2, d_{3} = 1. Daher genügt a_{n} dem Ansatz

a_{n} = a + (b + c · n) · (−1)^{n} + d · (−2)^{n}.

Mit den Anfangsbedingungen ergibt sich nun folgendes GLS für a, b, c und d.

a +b  +d = 8
a -b -c -2d = -8
a +b +2c +4d = 24
a -b -3c -8d = a_{3}.

Dies hat die Lösung:

\begin{aligned}a & & & & = & 6 + \frac{a_{3}}{12} \\ & b & & & = & 10 + \frac{a_{3}}{4} \\ & & c & & = & 20 + \frac{a_{3}}{2} \\ & & & d & = & −8 − \frac{a_{3}}{3} \end{aligned} und damit gilt für n ≥ 0

a_{n} = (6 + \frac{a_{3}}{12}) + ((10 + \frac{a_{3}}{4} ) + (20 + \frac{a_{3}}{2} ) · n) · (−1)^{n} + (−8 − \frac{a_{3}}{3} ) · (−2)^{n}.

Aufgabe 15. (12 Punkte) Die Mengen A_{1}, ..., A_{n} ⊆ {1, ..., n} mit n ∈ N bilden eine “Kette”, falls A_{i} ⊆ A_{i+1} und A_{i} ≠ A_{i+1} für 1 ≤ i ≤ n − 1 gilt. Zeigen Sie die folgenden Aussagen.

a) Für jede Kette A_{1}, ..., A_{n} gilt |A_{i}| = i für 1 ≤ i ≤ n und es gibt genau n! verschiedene Ketten.

b) Zu einer Menge B ⊆ {1, ..., n} gibt es genau |B|! · (n − |B|)! verschiedene Ketten A_{1}, ..., A_{n} mit A_{|B|} = B.

c) Gilt für die Mengen B_{1}, ..., B_{m} ⊆ {1, ..., n}, daß B_{i} ⊈ B_{j} für 1 ≤ i ≠ j ≤ m, dann gilt

∑_{i=1}^{m} \frac{1}{\binom{n}{|B_{i}|}} ≤ 1.

Lösung: zu a) Es gilt |A_{i}| < |A_{i+1}| ≤ n für 1 ≤ i ≤ n − 1. Daraus folgt sofort |A_{i}| = i für 1 ≤ i ≤ n und A_{n} = {1, ..., n}. Man kann nun alle Ketten bilden, indem man ausgehend von A_{n} sukzessive Elemente streicht. Für das i-te zu streichende Element hat man dabei jeweils genau n − i + 1 Möglichkeiten für 1 ≤ i ≤ n − 1. Daher gibt es

∏_{i=1}^{n−1}(n − i + 1) = ∏_{i=2}^{n} i = n!

verschiedene Ketten. zu b) Man erhält die Mengen A_{1}, ..., A_{|B|−1} aller gewünschten Ketten, indem man ausgehend von A_{|B|} = B sukzessive Elemente streicht. Dabei hat man wie oben |B|! Möglichkeiten. Weiter erhält man die Mengen A_{|B|+1}, ..., A_{n} aller gewünschten Ketten, indem man ausgehend von A_{|B|} = B sukzessive Elemente hinzufügt. Analog ergibt sich, daß man dabei (n − |B|)! Möglichkeiten hat. Insgesamt gibt es also |B|! · (n − |B|)! der gesuchten Ketten. zu c) Da B_{i} ⊈ B_{j} für 1 ≤ i ≠ j ≤ m sind alle Ketten A_{1}, ..., A_{n} mit A_{|B_{i}|} = B_{i} verschieden von den Ketten A′_{1}, ..., A′_{n} mit A′_{|B_{j}|} = B_{j}. Daher gilt nach den Teilen a) und b)

∑_{i=1}^{m} |B_{i}|! · (n − |B_{i}|)! ≤ n! ⇔ ∑_{i=1}^{m} \frac{|B_{i}|! · (n − |B_{i}|)!}{n!} ≤ 1 ⇔ ∑_{i=1}^{m} \frac{1}{\binom{n}{|B_{i}|}} ≤ 1.

Aufgabe 16. (8 Punkte) Es sei G = (U ∪ W, E) ein bipartiter Graph mit den Partitionsmengen U und W mit |U| = |W | = n. Es sei d(x, G) = |N(x, G)| ≥ \frac{n}{2} für alle x ∈ U ∪ W. Zeigen Sie, daß G ein perfektes Matching besitzt. (Hinweis: Betrachten Sie eine minimale Eckenüberdeckung.)

Lösung: Angenommen G habe kein perfektes Matching, dann gilt für eine minimale Eckenüberdeckung V′ nach dem Satz von König, daß |V′| < n. Es gilt nun entweder |V′ ∩ U| < \frac{n}{2} oder |V′ ∩ W | < \frac{n}{2}. O.B.d.A. Gelte |V′ ∩ U| < \frac{n}{2}. Weiter gilt V′ ∩ W ≠ ∅. Sei x ∈ V′ ∩ W, dann enden alle Kanten, die von x ausgehen in V′ ∩ U und es gilt

d(x, G) ≤ |V′ ∩ U| < \frac{n}{2},

was der Voraussetzung widerspricht. Daher folgt die Behauptung.

Aufgabe 17. (8 Punkte) Bestimmen Sie einen maximalen Fluß und einen minimalen Schnitt in dem Netzwerk N = (V, B, q, s, c) mit

V = {q = 1, 2, 3, ..., 8, s = 9},
B = {(1, 2), (1, 5), (2, 3), (2, 6), (2, 9), (3, 4), (4, 7), (5, 4),
(5, 7), (5, 8), (6, 3), (6, 7), (7, 9), (8, 6), (8, 9)},

c((1, 2)) = 5, c((1, 5)) = 10, c((2, 3)) = 1, c((2, 6)) = 2, c((2, 9)) = 1, c((3, 4)) = 2, c((4, 7)) = 7, c((5, 4)) = 5, c((5, 7)) = 2, c((5, 8)) = 3, c((6, 3)) = 3, c((6, 7)) = 1, c((7, 9)) = 8, c((8, 6)) = 2 und c((8, 9)) = 1.

Lösung: Die Funktion f : B → R mit f((1, 2)) = 3, f((1, 5)) = 7, f((2, 3)) = 1, f((2, 6)) = 1, f((2, 9)) = 1, f((3, 4)) = 2, f((4, 7)) = 7, f((5, 4)) = 5, f((5, 7)) = 0, f((5, 8)) = 2, f((6, 3)) = 1, f((6, 7)) = 1, f((7, 9)) = 8, f((8, 6)) = 1 und f((8, 9)) = 1 ist ein Fluß der Stärke 10 in N. Die Menge V − {s = 9} definiert einen Schnitt C der Kapazität 1 + 8 + 1 = 10 in N. Daher ist f maximal und C minimal.