Einführung in die Diskrete Mathematik

Sommersemester 2014
PD Dr. Nils Rosehr

Inhaltsverzeichnis

I Einleitung 5

II Kombinatorik 5

1 Grundlagen der Kombinatorik 6

1.1 Standardbezeichnungen . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Endliche Mengen . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Potenzmenge . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6 Partitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.8 Schubfachprinzip . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.9 Anwendungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.10 Prinzip der doppelten Abzählung . . . . . . . . . . . . . . . . 10
1.11 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Binomialkoeffizienten 10
2.1 Permutationen und Fakultät . . . . . . . . . . . . . . . . . . . 10
2.3 Stirling-Formel . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.6 Näherung von Binomialkoeffizienten . . . . . . . . . . . . . . . 13
2.8 Ungeordnete Summationen und Multimengen . . . . . . . . . 13
2.9 Wege im Gitter . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.10 Vandermonde-Identität . . . . . . . . . . . . . . . . . . . . . . 14
2.11 Polynommethode . . . . . . . . . . . . . . . . . . . . . . . . . 15
 2

2.13 Differenzieren . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.14 Binomische Reihe . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.15 Multinomialkoeffizienten . . . . . . . . . . . . . . . . . . . . . 17

3 Abbildungen und Auswahlen 18

3.6 Auswahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.8 Abzählbare Wahrscheinlichkeitsräume . . . . . . . . . . . . . . 19
3.10 Erwartungswert und Varianz . . . . . . . . . . . . . . . . . . . 20

4 Inklusion und Exklusion 22

4.1 Siebformel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2 Bonferroni-Ungleichungen . . . . . . . . . . . . . . . . . . . . 22
4.3 Fixpunktfreie Permutationen . . . . . . . . . . . . . . . . . . . 22
4.4 Surjektive Abbildungen . . . . . . . . . . . . . . . . . . . . . . 23
4.5 Partitionen und Stirling-Zahlen . . . . . . . . . . . . . . . . . 23
4.6 Einschub: Endliche Körper . . . . . . . . . . . . . . . . . . . . 23
4.8 Irreduzible Polynome über endlichen Körpern . . . . . . . . . 24

5 Erzeugende Funktionen 26
5.1 (Formale) Potenzreihen . . . . . . . . . . . . . . . . . . . . . . 26
5.4 Anwendung farbige Kugeln . . . . . . . . . . . . . . . . . . . . 26
5.5 Fibonacci-Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.6 Lineare Rekursionsgleichungen . . . . . . . . . . . . . . . . . . 28

III Graphentheorie 29

6 Grundlegende Begriffe 29
6.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6.2 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6.3 Isomorphismen und Automorphismen . . . . . . . . . . . . . . 31
6.4 Teilgraphen und Konstruktionsmethoden . . . . . . . . . . . . 32
6.5 Nachbarschaften und Gradzahlen . . . . . . . . . . . . . . . . 33
6.6 Handshake-Lemma . . . . . . . . . . . . . . . . . . . . . . . . 33
6.7 Gradfolgen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

14.07.2014–13:07
 3

6.9 Der Satz von Turán . . . . . . . . . . . . . . . . . . . . . . . . 34

6.11 Extremale Graphen . . . . . . . . . . . . . . . . . . . . . . . . 35
6.12 Touren und Zusammenhang . . . . . . . . . . . . . . . . . . . 35
6.13 Euler-Touren und Hamilton-Kreise . . . . . . . . . . . . . . . 36
6.15 Kürzeste Wege und der Algorithmus von Dijkstra . . . . . . . 37
6.18 Matrixbeschreibung . . . . . . . . . . . . . . . . . . . . . . . . 38

7 Bäume und Wälder 39

7.1 Charakterisierung von Bäumen . . . . . . . . . . . . . . . . . 39
7.2 Aufspannende Bäume . . . . . . . . . . . . . . . . . . . . . . . 40
7.3 Charakterisierung endlicher Bäume . . . . . . . . . . . . . . . 40
7.4 Der Satz von Cayley und Prüfercodes . . . . . . . . . . . . . . 40

8 Planare Graphen 41
8.1 Die reelle Ebene . . . . . . . . . . . . . . . . . . . . . . . . . . 41
8.2 Jordanscher Kurvensatz . . . . . . . . . . . . . . . . . . . . . 41
8.5 Flächen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
8.6 Formel von Euler für planare Graphen . . . . . . . . . . . . . 42
8.8 Kantenabschätzung . . . . . . . . . . . . . . . . . . . . . . . . 43
8.10 Der Satz von Kuratowski . . . . . . . . . . . . . . . . . . . . . 43

IV Codierungstheorie 43
9.1 Alphabete und Codes . . . . . . . . . . . . . . . . . . . . . . . 44
9.3 Hamming-Abstand . . . . . . . . . . . . . . . . . . . . . . . . 44
9.6 Ein Hamming-Code . . . . . . . . . . . . . . . . . . . . . . . . 46
9.7 Singleton-Schranke . . . . . . . . . . . . . . . . . . . . . . . . 46
9.9 Kugelpackungs-Schranke . . . . . . . . . . . . . . . . . . . . . 47
9.10 Überdeckungs-Schranke . . . . . . . . . . . . . . . . . . . . . . 47
9.11 Lineare Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
9.12 Generator- und Kontrollmatrix . . . . . . . . . . . . . . . . . 48
9.13 Hamming-Codes . . . . . . . . . . . . . . . . . . . . . . . . . . 48
9.14 Reed–Solomon-Codes . . . . . . . . . . . . . . . . . . . . . . . 48
9.15 Anwendungen von Reed–Solomon-Codes . . . . . . . . . . . . 50

14.07.2014–13:07
 4

V Kryptographie 50
10.1 Kryptosysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
10.2 Das AES-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . 51
10.3 Das diskrete Logarithmus-Problem . . . . . . . . . . . . . . . 53
10.4 Der Diffie–Hellman-Schlüsselaustausch . . . . . . . . . . . . . 54
10.5 Das ElGamal-Verfahren . . . . . . . . . . . . . . . . . . . . . . 54
10.6 Elliptische Kurven . . . . . . . . . . . . . . . . . . . . . . . . . 55

VI Übungsaufgaben 57

Index 64

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 08.04.2014 5

I Einleitung
Die diskrete Mathematik ist keine Geheimwissenschaft, sondern vielmehr ist
diskret hier als Abgrenzung zu kontinuierlich zu verstehen. Dabei wird der
Begriff unterschiedlich allgemein gefasst. Häufig geht es um mathematische
Probleme oder Theorien die mit endlichen oder abzählbaren Strukturen zu
tun haben. Am besten wird dies vielleicht an einigen Beispielen deutlich.
Beispiel 1. Nehmen wir an, wir wollen eine Treppe mit 11 Stufen besteigen
und können mit einem Schritt entweder eine oder zwei Stufen nehmen. Für
die ersten drei Stufen haben wir drei Möglichkeiten: 3 = 1 + 1 + 1 = 1 +
2 = 2 + 1. Für die gesamte Treppe von 11 Stufen gibt es 144 Möglichkeiten.
Natürlich ist man in der diskreten Mathematik nicht an der Lösung dieses
speziellen Problems interessiert, sondern fragt sich: Gibt es eine Formel für
die Anzahl der Möglichkeiten in Abhängigkeit der Anzahl der Stufen? Kann
man auch ähnliche Probleme lösen, etwa, wenn man es schafft 3 Stufen (oder
alle) auf einmal zu nehmen? Gibt es ein allgemeines Verfahren, zu solchen
Lösungsformeln zu kommen?
Beispiel 2. Wir wollen ein Schachbrett aus 8 mal 8 Feldern mit 8 Farben
so einfärben, dass in keiner Horizontalen oder Vertikalen eine Farbe doppelt
auftritt. Dies ist auf vielerlei Weisen möglich und hängt auch gar nicht von
der Zahl 8 ab. Solche Einfärbungen werden lateinische Quadrate genannt. Nun
stellen wir die Frage, ob es zwei solche Einfärbungen gibt (sogenannte orthogo-
nale lateinische Quadrate), so dass die von entsprechenden Feldern gebildeten
Farbpaare alle 8 · 8 = 64 Farbkombinationen durchlaufen. Eine einfache (beja-
hende) Antwort lässt sich mit der algebraischen Struktur des endlichen Körpers
mit 8 Elementen geben. Schon 1780 hat Euler die Frage gestellt, ob es auch
orthogonale lateinische Quadrate der Ordnung 6 gibt. Er konnte diese Frage
nicht beantworten und vermutete, dass dies für alle Ordnungen der Form 4k+2
nicht möglich sei. Heute weiß man, dass Euler nur für k = 1 Recht hatte.
Beispiel 3. Viele kennen seit den Kindertagen das Haus vom Nikolaus. Dabei
geht es darum in einem bestimmten Graphen einen Weg zu finden, der alle

Kanten genau einmal durchläuft: oder . Solch ein Weg heißt übrigens
Euler-Tour, nach Euler, der sich mit dem ähnlichen Königsberger Brückenpro-
blem beschäftigt hat. Diese Touren haben durchaus eine praktische Relevanz,
denn z.B. für die Müllabfuhr stellt solch eine Tour einen günstigen Weg dar.
Hier ergeben sich viele Fragen: Ist eine solche Tour auch für andere Graphen
möglich? Wenn nicht, gibt es ein Kriterium? Kann man die Touren auch mit
gleichem Anfangs- und Endpunkt wählen?

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 10.04.2014 6

II Kombinatorik
1 Grundlagen der Kombinatorik
1.1 Standardbezeichnungen. Für die natürlichen Zahlen (ohne Null)
schreiben wir N = {1, 2, 3, . . . }, N0 = {0}∪N und {1, . . . , n} = {k ∈ N : k ≤ n}
für n ∈ N0 . Weiter benutzen wir Z ⊆ Q ⊆ R ⊆ C. Für die Potenzmen-
ge einer Menge X (also die Menge aller Teilmengen von X) schreiben wir
P(X) oder 2X . Wir benutzen die Gaußklammern zum Auf- und Abrunden:
bxc := max{z ∈ Z : z ≤ x} und dxe := min{z ∈ Z : z ≥ x} für x ∈ R.

1.2 Endliche Mengen. Eine Menge A ist endlich, wenn es ein n ∈ N0 und
eine Abzählung, d.h. eine Bijektion f : {1, . . . , n} → A gibt. Die Zahl n ist
eindeutig bestimmt (siehe Übungsaufgabe 1.1) und heißt die Größe, Länge
oder Mächtigkeit von A; wir schreiben |A| für die Mächtigkeit von A und
nennen A eine n-Menge. Falls A nicht endlich ist, setzen wir |A| := ∞ (siehe
Bemerkung nach Satz 1.4) und benutzen ∞ ± x = ±x + ∞ = ∞ + ∞ = ∞
sowie x < ∞ für x ∈ R.

1.3 Lemma. Seien A und B Mengen.

(a) Es gilt |A| = 0 genau dann, wenn A = ∅.
(b) Es ist A ∪ B genau dann endlich, wenn A und B endlich sind.
(c) Es gilt |A ∪ B| + |A ∩ B| = |A| + |B|.
(d) Aus B ( A folgt |B| < |A|, falls A (oder B) endlich ist.
(e) Für eine Abbildung f : A → B gilt |f (A)| ≤ |A|.

Beweis. (a) Die „leere Abbildung“ ∅ → A ist genau dann surjektiv, wenn A
leer ist.
(∗) Seien nun zunächst A und B endlich und disjunkt. Wir zeigen |A ∪ B| =
|A| + |B| per Induktion über |A|: Den Induktionsanfang liefert (a). Für |A| > 0
können wir wieder nach (a) ein a ∈ A wählen. Es folgt |A \ {a}| = |A| − 1, denn
ist f : {1, . . . , |A|} → A ein Abzählung, so ist g : {1, . . . , |A| − 1} → A \ {a}
mit g(x) = f (x) für x 6= f −1 (a) und g(f −1 (a)) = f (|A|), falls f −1 (a) 6= |A|,
eine Abzählung [vertausche a und f (|A|)]. Es folgt |(A \ {a}) ∪ B| = |(A ∪ B) \
{a}| = |A ∪ B| − 1 ebenso, da A und B disjunkt sind, und Induktion liefert die
Behauptung.
(d) In obigem Induktionsbeweis haben wir |A\{a}| = |A|−1 gezeigt für a ∈ A;
daraus folgt die Behauptung per Induktion, wenn wir a ∈ A \ B wählen. [(∗)
lässt sich nicht anwenden, da wir (noch nicht) wissen, dass B und A\B endlich
sind.]
(b) Sind A und B endlich, so folgt aus (∗), dass A ∪ B endlich ist. Aus (d) folgt
die andere Implikation, weil A und B Teilmengen von A ∪ B sind.

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 10.04.2014 7

(c) Wegen (b) müssen wir nur noch den endlichen Fall zeigen: |A ∪ B| =
|A \ (A ∩ B)| + |B| = |A| − |A ∩ B| + |B|.
(e) Für unendliches A ist nichts zu zeigen. Wähle sonst eine Teilmenge A0 ⊆ A,
so dass für jedes b ∈ f (A) die Faser f −1 (b) genau ein Element von A0 enthält
[A0 ist also ein Repräsentantensystem für die Fasern von f .] Da f |A0 injektiv
ist, folgt |f (A)| = |f (A0 )| = |A0 | ≤ |A| nach (d). 2

1.4 Satz. Für endliche Mengen A und B gilt |A| = |B| genau dann, wenn es
eine Bijektion A → B gibt.
Gilt dies, so ist eine Abbildung h : A → B genau dann bijektiv, wenn sie
injektiv oder surjektiv ist.

Beweis. Gilt n := |A| = |B|, so gibt es Bijektionen f : {1, . . . , n} → A und

g : {1, . . . , n} → B, und wir können als Bijektion g ◦f −1 wählen. Ist umgekehrt
eine Bijektion h : A → B gegeben, dann lässt sich diese mit einer Bijektion
f : {1, . . . , |A|} → A verketten zu einer Bijektion h ◦ f : {1, . . . , |A|} → B. Es
folgt |B| = |A|.
Ist h injektiv, so ist h : A → h(A) bijektiv und nach dem schon gezeigten folgt
|h(A)| = |A| = |B| und somit h(A) = B nach 1.3(d). Also ist h surjektiv.
Ist h nicht injektiv, so gibt es ein a ∈ A mit h(A \ {a}) = h(A) und es folgt
|h(A)| = |h(A \ {a})| ≤ |A \ {a}| < |A| = |B| nach 1.3. Also ist h nicht
surjektiv. 2

Die erste Aussage des Satzes ist falsch für unendliche Mengen [die zweite so-
wieso]. Das liegt daran, dass es verschiedene unendliche Mächtigkeiten gibt,
etwa |N| = ∞ = |R|, aber es gibt keine Bijektion N → R (Cantors zweites
Diagonalargument).
Die Forderung der Existenz einer Bijektion zwischen zwei Mengen macht aber
auch für unendliche Menge Sinn und wir nennen daher zwei Mengen gleich-
mächtig, wenn es eine Bijektion zwischen ihnen gibt wie im Satz.
Die Endlichkeit von Mengen lässt sich auch noch auf andere Art definieren:
Eine Menge ist genau dann unendlich, wenn es eine Injektion von ihr in eine
echte Teilmenge gibt. Für eine weitere Möglichkeit siehe Übungsaufgabe 1.4.
1.5 Satz (Potenzmenge). Für eine endliche Menge M gilt |2M | = 2|M | .

Beweis. Wir führen Beweis per Induktion nach |M |. Für |M | = 0 haben wir
M = ∅ und daher 2M = {∅}, also |2M | = 1. Sei nun |M | > 0. Wir können also
m ∈ M wählen und setzen

A := {X ⊆ M : m 6∈ X} und
B := {X ⊆ M : m ∈ X}.

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 15.04.2014 8

Dann gilt 2M = A ∪ B und A ∩ B = ∅. Es folgt |2M | = |A| + |B|. Ferner ist

A = 2M \{m} also |A| = 2|M |−1 per Induktion. Die Abbildung A → B, X 7→
X ∪ {m} ist eine Bijektion mit der Inversen Y 7→ Y \ {m}. Es folgt |A| = |B|
und daher |2M | = 2|A| = 2|M | . 2

1.6 Partitionen. Eine Partition einer Menge M ist eine Menge von paar-
weise disjunkten Teilmengen von M , deren Vereinigung M ist.
Für eine endliche Partition P einer Menge M gilt
X
|M | = |X|.
X∈P

|f −1 (b)| für eine Abbildung f : M → B.

P
Häufige Anwendung: |M | = b∈B

Beweis. Für |P | = 0, 1 ist die Aussage trivial und für |P | = 2 ist die Aussage
ein Spezialfall von 1.3(c). Die Behauptung folgt damit per Induktion über
|P |. 2

1.7 Korollar. Für endliche Mengen A und B gilt |A × B| = |A| · |B| und
|An | = |A|n für n ∈ N0 (mit 00 = 1).

Beweis. Dies folgt aus 1.6, weil A × B die Partition P := {A × {b} : b ∈ B}

hat und |A × {b}| = |A| sowie |P | = |B| gilt. Die zweite Behauptung folgt dann
per Induktion über n. 2

1.8 Schubfachprinzip. Wenn n Objekte auf weniger als n Fächer verteilt

werden, so finden sich in einem Fach mindestens zwei Objekte. Oder: Wenn
n Objekte mit k < n Farben eingefärbt werden, so haben mindestens zwei
Objekte die gleiche Farbe.
Formal: Sind A und B endliche Mengen mit |B| < |A|, so ist jede Abbildung
f : A → B nicht injektiv, d.h. es existiert ein b ∈ B mit |f −1 (b)| ≥ 2.
Allgemeiner: Für f : A → B mit |B| < ∞ existiert ein b ∈ B mit

|A|
|f −1 (b)| ≥ .
|B|

|f −1 (b)| ≤ |B| maxb∈B |f −1 (b)|. 2

P
Beweis. Mit 1.6 folgt |A| = b∈B

1.9 Anwendungen. Wir werden im Laufe der Vorlesung viele Anwendun-

gen sehen; hier sind ein paar Beispiele dieser wichtigen Beweismethode:

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 15.04.2014 9

(a) Unter 15 Personen, sind immer mindestens 2 im gleichen Monat geboren,

oder mindestens 3 am gleichen Wochentag. [Es existieren 70.000 Menschen mit
exakt gleichvielen Haaren auf dem Kopf: ca. 7 · 109 Menschen, ca. 105 Haare]
2
(b) Unter 5 Punkten
√ im Einheitsquadrat [0, 1] gibt es immer zwei mit Ab-
1
stand höchstens 2 2:
Zwei der 5 Punkte liegen in einem der 4 Teilquadrate mit √
Seitenlänge 1/2 wie im Bild und haben daher Abstand ≤ 12 2
(für Punkte auf den Trennlinien wählen wir willkürlich).
(c) Sind a1 , . . . , an+1 ∈ {1, . . . , 2n}, so gibt es Indices i 6= j, so dass ai ein
Teiler von aj ist:
Wir schreiben ai = 2ei ui mit ei ∈ N0 und ui ∈ N ungerade. Wegen 1 ≤ ui ≤ 2n
gibt es n Möglichkeiten für ui und das Schubfachprinzip liefert i 6= j mit
ui = uj und etwa ei ≤ ej . Es folgt ai = ei ui | ej ui = aj .
Für die n Zahlen n + 1, . . . , 2n ist die Folgerung falsch.
(d) Sei n ∈ N und a1 , . . . , an2 +1 eine Folge von n2 + 1 verschiedenen reellen
Zahlen. Dann gibt es eine monoton fallende oder monoton steigende Teilfolge
der Länge n + 1:
Wir definieren [Erdös und Szekeres folgend] zwei Abbildungen f, g : {1, . . . , n2 +
1} → N. Dabei sei f (i) (bzw. g(i)) die Länge der längsten steigenden (bzw.
fallenden) Teilfolge, die bei ai endet (bzw. beginnt). Wir führen einen Wider-
spruchsbeweis, und nehmen daher (f (i), g(i)) ∈ {1, . . . , n}2 für alle i an. Das
Schubfachprinzip liefert uns i < j mit (f (i), g(i)) = (f (j), g(j)). Damit können
wir eine der beiden Folgen verlängern, nämlich, falls ai < aj , am Ende um aj ,
also f (j) > f (i), oder, falls ai > aj , am Anfang um ai , also g(i) > g(j). Beides
ist ein Widerspruch zu (f (i), g(i)) = (f (j), g(j)).

Die y-Koordinaten der 17 Punkte im Bild, sortiert von links

nach rechts, enthalten monotone Folgen der Länge 5 (wie
viele?), aber ohne den zentralen Ausnahmepunkt ist dies
falsch.
(e) Approximationssatz von Dirichlet: Für α ∈ R und n ∈ N existieren
k, l ∈ Z mit 0 < k ≤ n und |kα − l| < 1/n. [(αZ + Z)/Z liegt dicht in R/Z]
[Das Schubfachprinzip wird auch oft als Dirichlet-Prinzip bezeichnet.] Aus
dem Approximationssatz folgt, dass es für irrationale α unendlich viele Brüche
l/k gibt mit 0 < |α − l/k| < 1/k 2 ; für rationale α ist dies falsch.

Beweis. Wir betrachten die n + 1 „Rundungsreste“ ai := iα − biαc ∈ [0, 1[

für i = 0, . . . , n. Nach dem Schubfachprinzip 1.8 liegen also in einem der n
halboffenen Intervalle [r/n, (r + 1)/n[ für r = 0, . . . , n − 1 zwei Reste ai und
aj mit i < j. Es folgt 1/n > |aj − ai | = |(j − i)α − (bjαc − biαc)| = |kα − l|
mit k := j − i und l := bjαc − biαc. 2

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 24.04.2014 10

1.10 Prinzip der doppelten Abzählung. Sei M eine endliche Menge,

und seien P und Q Partitionen von M . Dann liefert 1.6 folgenden Zusammen-
hang: X X
|X| = |M | = |Y |.
X∈P Y ∈Q

Häufig besteht M aus Paaren, also M ⊆ A × B. Dann hat man

X X
|M ∩ ({a} × B)| = |M | = |M ∩ (A × {b})|.
a∈A b∈B

1.11 Beispiel. Bei einem Treffen ist die Anzahl der Personen, die einer un-
geraden Anzahl von Leuten die Hände schütteln, gerade:
Für die Menge A der Personen betrachten wir die Menge M der Paare (a, b) ∈
A2 von Personen die Hände miteinander schütteln. Wir zählen M auf zwei
Weisen. Einerseits gilt für (a, b) ∈ M auch (b, a) ∈ M und a 6= b, also ist |M | =
P wobei h die Anzahl der „Händeschüttelungen“ ist. Andererseits folgt
2h gerade,
|M | = a∈A na , wobei na := |M ∩ ({a} × A)| die Anzahl der Leute ist, die mit
a die Hände schütteln. Also muss die Anzahl der ungeraden na gerade sein.

2 Binomialkoeffizienten
2.1 Permutationen und Fakultät. Für eine Menge M bezeichnet Sym M
die Menge aller Bijektionen von M nach M , die sogenannte symmetrische
Gruppe auf M . Ihre Elemente werden Permutationen genannt. Für uns ist
die endliche symmetrische Gruppe Sn := Sym{1, . . . , n} auf n ∈ N0 Ziffern
interessant. Ihre Mächtigkeit |Sn | wird als Fakultät von n, in Zeichen n!,
bezeichnet. Man überlegt sich leicht, dass die Rekursionsgleichung n! = n ·
(n − 1)! gilt für n ∈ N und zeigt per Induktion n! = n · (n − 1) · (n − 2) · · · 2 · 1 =
Qn−1
i=0 (n − i); beachte 0! = 1. Für ein Element x eines kommutativen Rings
Qk−1 Qk−1
und k ∈ N definieren wir xk := i=0 (x − i) und xk := i=0 (x + i) sowie
x0 := x0 := 1 (steigende und fallende Faktorielle). Die Produkte xk und
xk bestehen also aus k um 1 absteigende bzw. aufsteigende Faktoren beginnend
mit x. Mit dieser Notation gilt n! = nn und nk = n!/(n − k)! .
Erstaunlicherweise lässt sich die Fakultätsfunktion auf R≥0 R ∞fortsetzen [sogar
noch weiter und holomorph] durch die Definition F (x) := 0 tx e−t dt. Es gilt
F (0) = F (1) = 1 und F (x) = xF (x − 1) (partielle Integration). Durch Γ(x) :=
F (x − 1) wird die Gammafunktion definiert.
√
Das Wachstumsverhalten von n! entspricht n( ne )n mit annähernd konstantem
relativen Fehler. Genauer hat man die folgende Abschätzung, die wir ohne
Beweis (mit Gammafunktion) angeben.
√ 1
2.2 Satz. Für n ∈ N und an := 2πn( ne )n gilt an ≤ n! ≤ an e 12n .

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 24.04.2014 11

Die schwächere Abschätzung e( ne )n ≤ n! ≤ en( ne )n lässt sich leicht per Induk-

tion unter Benutzung von 1 + x ≤ ex für x ∈ R zeigen.
n!
2.3 Korollar (Stirling-Formel). Es gilt lim √ = 1.
n→∞ 2πn( ne )n

2.4 Definition. Für eine Menge M und k ∈ Z bezeichnen wir mit

 
M
:= {X ⊆ M : |X| = k}
k
die Menge aller k-Teilmengen von M . Ist |M | = n ∈ N0 , so definieren wir den
Binomialkoeffizient zu n und k durch
   
n M
:= .
k k

Der Binomialkoeffizient nk hängt nicht von M , sondern nur von n = |M |

ab.
Er gibt also die Anzahl der
k-Teilmengen jeder n-Menge an. Daher gilt
n n
n ∈ N0 und nk = 0 für k < 0 und k > n.


0 = 1 = n für

Wir notieren grundlegende Eigenschaften von Binomialkoeffizienten:

2.5 Lemma. Für k, l, n ∈ N0 gilt
n+1 n n




(a) k+1 = k + k+1 ,
n n



(b) k = n−k ,
Pn n

n
(c) k=0 k = 2 ,
n
(x+y)n = k=0 nk xk y n−k für Elemente x, y eines kommutativen Rings
P

(d)
(binomischer Lehrsatz),
n k n n−l





(e) k l = l k−l für l ≤ n,

n(n−1)···(n−k+1) k
n
(f) k = k(k−1)···1 = nk! = k!(n−k)!
n!
für k ≤ n.

M


Beweis. (a) Sei M eine (n + 1)-Menge und m ∈ M . Dann ist k+1 eine
M \{m} M



disjunkte Vereinigung von A := k+1 und B := {X ∈ k+1 : m ∈ X}.
M \{m}


Weil B → k , X 7→ X \ {m} eine Bijektion ist, folgt
       
n+1 M n n
= = |A| + |B| = + .
k+1 k+1 k+1 k

(b) Sei
nun |M | =
n. Die Komplementbildung X 7→ M \ X ist eine Bijektion

von M M
k auf n−k .

(c) folgt aus 1.5 und 1.6, denn M



k : k ∈ {0, . . . , n} ist eine Partition der
Potenzmenge 2M .

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 24.04.2014 12

(d) folgt per Induktion aus (a) [oder direkt über die Definition von Binomial-
koeffizienten durch Ausmultiplizieren des n-fachen Produktes].
(e) Wir zählen X := {(A, B) ∈ Ml × M



k : A ⊆ B} auf zwei Weisen ge-
mäß 1.10: nl n−l n k





k−l = |X| = k l (einerseits wird zuerst A gewählt und dann
durch eine (k − l)-Teilmenge von M \ A zu B ergänzt, und andererseits wird
zuerst B gewählt und darin eine l-Teilmenge gewählt).
(f) Für l = 1 gilt nach (e) die Gleichung nk k = n n−1 n



n n−1

k−1 , also k = k k−1 für
k ∈ N; die Gleichung folgt hieraus per Induktion. 2

Die Rekursionsformel 2.5(a) ist das Bildungsgesetz für das Pascal-Dreieck;

dabei ist jeder Zahl die Summe der beiden Zahlen links und rechts darüber:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 5 10 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
.. ..
. .

Lemma 2.5(b) drückt die Spiegel-Symmetrie des Dreiecks aus. Mit 2.5(f) kann
man leicht zeigen, dass die Koeffizienten bis zur Mitte ansteigen (und dann
fallen).
Die Summe der Zahlen in einer Diagonalen (siehe fett gedruckte Zahlen im
Pk
Pk
Bild) ist wieder ein Binomialkoeffizient, genauer gilt l=0 n+l = l=0 n+l


n l =
n+k+1


k ; dies zeigt man leicht per Induktion.
Vermutung von Singmaster: Jede Zahl ab 2 tritt im Pascal-Dreieck höchstens
10 Mal auf.
Singmaster hat 1975 bewiesen, dass unendlich viele Zahlen mindestens 6 Mal
auftreten. Die Zahl
       
3003 78 15 14
3003 = = = =
1 2 5 6

tritt 8 Mal auf; häufigeres Auftreten ist nicht bekannt.

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 29.04.2014 13

2.6 Näherung von Binomialkoeffizienten. Für m ∈ N gilt

22m 22m
 
2m
√ < <√ .
2 m m 2m

1 2m

√ √
Beweis. Wir betrachten P := 22m m und müssen 1 < 2 mP < 2 zeigen.
Es gilt
(2m)! 1 · 3 · 5 · · · · · (2m − 1)
P = m 2
= ,
(2 m!) 2 · 4 · 6 · · · · · 2m
und daher
32 52 (2m − 1)2
2(2m)P 2 = · ··· >1
2·4 4·6 (2m − 2)(2m)
| {z }
(2m−1)2
= (2m−1)2 −1 >1
sowie
1·3 3·5 (2m − 1)(2m + 1)
(2m)P 2 < (2m + 1)P 2 = 2
· 2 ··· <1
2 4 (2m)2
| {z }
(2m)2 −1
= <1
(2m)2 2

Die Stirling-Formel liefert etwas genauer

  √
2m m 1
lim · 2m = √ ,
m→∞ m 2 π
√ √
was zu 2 < π < 2 passt.
2m 2m



Außerdem lässt sich mit Hilfe der Stirling-Formel zeigen, dass m−t / m
2
durch e−t /m approximiert wird, d.h. die normierten Binomialkoeffizienten ver-
halten sich wie die Gaußsche Glockenkurve.
2.7 Lemma (Erdös-Szekeres 1978). Je zwei Zahlen 6= 1 in einer Zeile des
Pascal-Dreiecks haben einen gemeinsamen Teiler (> 1).

Beweis. Für 0 < l < k < n gilt nk

k
n n−l



l =
l k−l nach 2.5(e), und daher
ist nl ein Teiler von nk kl . Wegen k n n n







l < l haben also l und k einen
gemeinsamen Teiler. 2

2.8 Ungeordnete Summationen und Multimengen. Auf wie viele Ar-

ten kann man 24 gleiche Stücke Schokolade an 5 Kinder verteilen? Allgemeiner
ist dies die Frage nach der Mächtigkeit von

Xn,k := {(s1 , s2 , . . . , sk ) ∈ Nk0 : s1 + s2 + · · · + sk = n}

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 29.04.2014 14

für k, n ∈ N0 . Wir notieren solche Summen durch Zeichenketten gebildet aus

den Symbolen und (für Schokolade und Trenner). Die Summe 1 + 2 + 3 = 6
wird etwa durch und die Summe 0 + 2 + 1 + 0 + 4 = 7 durch
dargestellt. Die Elemente aus Xn,k entsprechen eindeutig den Zei-
chenfolgen der Länge n+k−1 bestehend aus n Einheiten und k−1 Trennsym-
bolen . Das bedeutet aber, sie entsprechen den Teilmengen in {1,...,n+k−1}


k−1 ;
dabei gibt eine Teilmenge an, an welchen Stellen in der Zeichenkette das Sym-
bol steht. Also gilt |Xn,k | = n+k−1


k−1 . Für die Ausgangsfrage gibt es also
24+4
= 28·27·26·25


4 4·3·2·1 = 7 · 9 · 13 · 25 = 20475 Möglichkeiten.
Wir geben noch eine andere Interpretation von Xn,k . Sei A eine Menge. Dann
heißt eine Abbildung M : A → N0 Multimenge über P A, die Werte M (a)
heißen Häufigkeiten oder Gewichte von a, und |M | := a∈A M (a) wird als
Gesamtgewicht oder Mächtigkeit von M bezeichnet. Dann gibt |Xn,k | =
n+k−1
= n+k−1



k−1 n die Anzahl der Multimengen über einer k-Menge mit Ge-
samtgewicht n an.
[In unserem Beispiel haben wir also eine Multimenge von Kindern, und die
Häufigkeit jedes Kindes gibt an, wie viel Stücke Schokolade es erhält.]
Jetzt wollen wir etwas gerechter sein und jedem Kind mindestens ein Stück
Schokolade zukommen lassen, wir suchen also |{(s1 , s2 , . . . , sk ) ∈ Nk : s1 + s2 +
· · ·+sk = n}|. Dies führt zu Zeichenketten, die nicht enthalten und bei denen
nicht am Anfang oder Ende steht, d.h. hinter jedem der ersten n − 1 Symbole
kann jeweils höchstens einer der k − 1 Trenner stehen; dies bedeutet das
Doppelzeichen
muss (k−1)-mal auf n−1
Stellen verteilt werden. Als Anzahl
ergibt sich n−1
k−1 und für das Beispiel 23
4 = 23·22·21·20
4·3·2·1 = 23 · 11 · 7 · 5 = 8855.

2.9 Wege im Gitter. Viele Formeln für Binomialkoeffizienten lassen sich

auch über Wege in Gittern beweisen. Ein kürzester Weg in einem Gitter der
Größe m × n von (0, 0) nach (m, n) besteht aus m + n Schritten, nämlich m
Schritten nach rechts und n Schritten nach oben.
(m, n)

(0, 0)

Jeder Weg ist eindeutig festgelegt durch
die Schritte

nach oben (oder durch
die Schritte nach rechts). Daher gilt m+n
m = m+n
n , siehe 2.5(b). Jeder dieser
Wege läuft entweder durch den Punkt (m, n − 1) oder durch (m − 1, n). Daher
gilt n+m n+m−1 n+m−1




n = n−1 + n für die Anzahl solcher Wege, siehe 2.5(a).
2.10 Satz (Vandermonde-Identität). Für n, m, k ∈ N0 gilt
  X k      X n  2
n+m n m 2n n
= und insbesondere = .
k l k−l n l
l=0 l=0

1. Beweis. Seien N und M disjunkte Mengen mit |N | = n und |M | = m.

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 29.04.2014 15

N M



Die Mengen Sl := {A ∪ B : A ∈ l , B ∈ k−l } für l = 0, . . . , k bilden eine

Pk Pk
Partition von N ∪M n+m
|Sl | = l=0 nl k−l


m

k . Also folgt k = l=0 nach 1.6
und 1.7. 2

2. Beweis. Nach 2.9 ist n+m

k die Anzahl der kürzesten Wege im Gitter von
(0, 0) nach (n + m − k, k). Jeder der Wege verläuft durch genau einen der
Punkte (n − l, l) mit 0 ≤ l ≤ k wie im Bild [auch für l > n].

(n − k, k)
(n + m − k, k)

(0, 0)
(n, 0)

Es gibt genau nl kürzeste Wege von (0, 0) nach (n − l, l), und von (n − l, l)

nach (n + m − k, k) genau (n+m−k)−(n−l)+k−l m

2



k−l = k−l .

2.11 Polynommethode. Häufig lassen sich für natürliche Zahlen definierte

Funktionen auf allgemeinere Zahlbereiche ausdehnen. Für ein Element z eines
kommutativen Ringes, der Q enthält (also etwa Q, R, C oder C[x]), definieren
wir in Verallgemeinerung von 2.5(f)

zk
 
z z(z − 1) · · · (z − k + 1)
:= =
k k! k!

für k ∈ N0 . Insbesondere ist xk z.B. ein Polynom in Q[x]. Für alle k ∈ N0 gilt

die Identität      
z+1 z z
= +
k+1 k k+1
z.B. für alle komplexen Zahlen z, denn f := x+1

x
x


k+1 − k − k+1 ist ein Polynom
vom Grad höchstens k + 1 in Q[x] mit den unendlich vielen Nullstellen n ∈ N
wegen 2.5(a); und daher folgt f = 0, weil ein solches Polynom sonst höchstens
k +1 Nullstellen hätte. Entsprechend gilt z.B. auch die Vandermonde-Identität
für komplexe Zahlen. Direkt aus der Definition folgt
   
−z k z+k−1
= (−1) .
k k

Jedes Polynom xk ∈ Q[x] hat an jeder Stelle x = n ∈ Z einen ganzzahligen

Wert (Definition 2.4 und Formel für −n

k ). Hier ist eine Umkehrung:

2.12 Satz (Pólya). Erfüllt ein Polynom f ∈ Q[x] die Bedingung

f (N0 ) ⊆ Z,
so ist f eine ganzzahlige Linearkombination von Polynomen xk mit k ∈ N0 .

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 06.05.2014 16

Die Polynome xk bilden eine Basis des Q-Vektorraums Q[x]

Beweis.
Pm
wegen
grad xk = k. Daher existieren ak ∈ Q und m ∈ N mit f = k=0 ak xk . Wegen


0


k = 0 für k ∈ N gilt a0 = f (0) ∈ Z. Wir führen Induktion über n und nehmen
an a0 , a1 , . . . , an ∈ Z. Dann folgt
n     m  
X n+1 n+1 X n+1
Z 3 f (n + 1) = ak + an+1 + ak ,
k n+1 k
k=0 | {z } k=n+2 | {z }
| {z } =1 =0
∈Z

also an+1 ∈ Z. 2

2.13 Differenzieren. Aus Polynomidentitäten wie oben lassen sich durch

(formales) Differenzieren neue Identitäten
Pn gewinnen: Z.B. erhält man aus 2.5(d)
n k
n


für y = 1 die Gleichung (1 + x) = k=0 k x . Differenzieren liefert n(1 +
Pn Pn
x)n−1 = k=1 k nk xk−1 und n(n − 1)(1 + x)n−2 = k=2 k(k n k−2



− 1) k x usw.
n−1
Pn n


Durch Einsetzen von x = 1 erhält man n2 = k=1 k k usw.

2.14 Binomische Reihe. Für r ∈ R und x ∈ C mit |x| < 1 gilt

∞  
r
X r
(1 + x) = xk .
k
k=0

Beweisidee. Man differenziert die rechte Seite R(x) und stellt fest, dass sie
der Differentialgleichung rR(x) = (1 + x)R0 (x) genügt; siehe Köhler, Analysis,
Heldermann-Verlag 2006, Satz 16.3. 2

Wir notieren einige Spezialfälle:

∞   ∞  
X −n X n+k−1
(1 − x)−n = (−x)k = xk
k k
k=0 k=0
X∞
(1 − x)−1 = xk (geometrische Reihe)
k=0
∞ 1
√ X
2 xk
1+x= = 1 + 12 x − 81 x2 · · ·
k
k=0

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 06.05.2014 17

Für n ∈ N0 erhalten wir

 1 
2 1 11  1  1 
= · −1 − 2 ··· −n
n+1 (n + 1)! 2 2 2 2
(−1)n
= n+1 · 1 · 3 · 5 · · · (2n − 1)
2 (n + 1)!
(−1)n (2n)!
= n+1 · n
2 (n + 1)! 2 n!
(−1)n
 
1 2n
= 2n+1 ·
2 n+1 n
Dabei besteht der letzte Faktor aus den sogenannten Catalan-Zahlen
     
1 2n 2n 2n
Cn := = − ∈ N0 ,
n+1 n n n+1
die uns später noch wieder begegnen werden. Man kann zeigen, dass Cn die
Anzahl der Zeichenketten der Länge 2n gebildet aus den Klammerzeichen ‘(’
und ‘)’ mit korrekter Klammerung ist, siehe Übungsaufgabe 4.3.

2.15 Multinomialkoeffizienten. Sei t ∈ N0 und M eine n-Menge, und

seien k1 , k2 , . . . , kt ∈ Z. Wir setzen
   
M {A1 , A2 , . . . , At } ist Partition von M
:= (A1 , A2 , . . . , At ) :
k1 , k2 , . . . , kt und für i = 1, 2, . . . , t gilt |Ai | = ki
und nennen die Mächtigkeiten
   
n M
:=
k1 , k2 , . . . , kt k1 , k2 , . . . , kt
Multinomialkoeffizienten [Achtung: Es werden „geordnete“ Partitionen ge-
zählt, und die Partitionen dürfen ∅ enthalten].
Jede Teilmenge A von M definiert die Partition {A, M \ A}, also k1n,k2 =


n n n




k1 ,n−k1 = k1 = n−k1 für k1 + k2 = n. Allgemeiner gilt
       
n n n − k1 n − k1 − k2 kt
= ...
k1 , k2 , . . . , kt k1 k2 k3 kt
n!
= ,
k1 !k2 ! · · · kt !
falls k1 , k2 , . . . , kt ∈ N0 mit k1 + k2 + · · · + kt = n, und sonst k1 ,k2n,...,kt = 0.

Per Induktion zeigt man aus dem Binomischen Lehrsatz den multinomischen
Lehrsatz: In kommutativen Ringen gilt
 
X n
n
(x1 + x2 + · · · + xt ) = xk1 xk2 · · · xkt t .
k1 , k2 , . . . , kt 1 2
k1 ,k2 ,...,kt ∈N0

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 06.05.2014 18

Die Multinomialkoeffizienten k1 ,k2n,...,kt geben auch die Anzahl der Wege in

einem t-dimensionalen Gitter von (0, 0, . . . , 0) nach (k1 , k2 , . . . , kt ) an, sowie

die Anzahl der Zeichenfolgen mit t Buchstaben, die jeweils genau ki -mal für
i = 1, . . . , t vorkommen; vergleiche 2.9 und 2.8.
Wie viele verschiedene Wörter kann man aus dem Wort MISSISSIPPI durch
Umordnen der Buchstaben bilden? Antwort:
 
11 11!
= = 11 · 10 · 9 · 7 · 5 = 34 650
1, 4, 4, 2 1! · 4! · 4! · 2!

3 Abbildungen und Auswahlen

3.1 Definition. Für Mengen A und B sei

B A = {f | f : A → B} = {(ba )a∈A : ba ∈ B}

die Menge aller Abbildungen von A nach B. Wir haben B ∅ = {∅} und B N ist
die Menge aller Folgen in B.

3.2 Satz. Für endliche Mengen A und B gilt B A = |B||A| .

Beweis. Falls a ∈ A existiert, haben wir die Bijektion

B A → B A\{a} × B : f 7→ (f |A\{a} , f (a)).

Daher folgt für |A| < ∞ die Behauptung per Induktion wegen

B A = B A\{a} · |B| = |B||A|−1 · |B| = |B||A| . 2

Aus Abschnitt 1 wiederholen wir:

3.3 Satz. Seien A und B endliche Mengen und f : A → B eine Abbildung.
(a) Ist f injektiv, so gilt |A| ≤ |B| und |A| = |B| ⇐⇒ f bijektiv.
(b) Ist f surjektiv, so gilt |A| ≥ |B| und |A| = |B| ⇐⇒ f bijektiv.
(c) Ist |A| = |B| und f injektiv oder surjektiv, so ist f bijektiv.

Anwendung:

3.4 Satz. Für die Anzahl π(n) aller Primzahlen in {1, . . . , n} gilt

ln n
π(n) ≥
ln 4
für alle n ∈ N, insbesondere gibt es unendlich viele Primzahlen.

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 08.05.2014 19

Beweis (Erdös). Jedes a ∈ {1, . . . , n} lässt sich eindeutig in der Form a =

b2 c schreiben mit b,√
c ∈ N und c ein Produkt von verschiedenen Primzahlen. Für
b gibt es höchstens n Möglichkeiten, und für c höchstens 2π(n) Möglichkeiten.
Weil√ die Abbildung a 7→ (b, c) injektiv ist, liefern 1.7 und 3.3(a) die Ungleichung
n ≤ n · 2π(n) , also n ≤ 4π(n) , also ln n ≤ π(n) ln 4. 2

3.5 Satz. Sind A und B endliche Mengen, dann gibt es genau

 
|A| |B|
|B| = |B|(|B| − 1) · · · (|B| − |A| + 1) = |A|!
|A|

injektive Abbildungen von A in B. Insbesondere gilt | Sym A| = |A||A| = |A|!,

und dies ist auch die Anzahl der linearen Ordnungsrelationen auf der Menge
A.

Beweis. Das zweite Gleichheitszeichen folgt aus 2.5(f), und die Behauptung
ist trivial für |B| < |A|. Andernfalls gibt es zu jeder |A|-Teilmenge X von B
eine Bijektion f0 : A → X und alle Bijektionen von A nach X erhält man
eindeutig als g ◦ f0 für g ∈ Sym X. Wegen | Sym X| = |X|! = |A|! folgt die
Behauptung. 2

3.6 Auswahlen. Auf wie viele Arten kann man k Elemente aus einer n-Men-
ge auswählen? Man muss präzisieren, ob die Reihenfolge berücksichtigt wird,
und ob wiederholte Auswahlen erlaubt sind, d.h. ob sogenanntes Ziehen mit
Zurücklegen vorliegt.
Anzahl Auswahlen k aus n
Reihenfolge wichtig Reihenfolge egal
mathematisches Objekt
n


nk k
ohne Zurücklegen
injektive Abbildungen k-Teilmengen

= −n
n+k−1



nk k k
mit Zurücklegen Abbildungen Multimengen
2-Zeichenfolgen

3.7 Beispiel. Wir zählen normierte Polynome vom Grad d = k über einem
endlichen Körper K mit q = n Elementen, die in Linearfaktoren zerfallen.
Die Linearfaktoren sind von der Form x − a für a ∈ K. Wir müssen also d
Linearfaktoren aus q möglichen mit Zurücklegen und ohne Berücksichtigung
der Reihenfolge (Kommutativität von K) auswählen. Es geht also um
Multi-
mengen über einer q-Menge mit Gesamtgewicht d, also gibt es q+d−1 d solche
Polynome und daher q 2 − q+1 q



2 = 2 > 0 viele normierte irreduzible Polynome
vom Grad 2.

3.8 Abzählbare Wahrscheinlichkeitsräume. Ein abzählbarer Wahr-

scheinlichkeitsraum ist eine abzählbare nichtleere Menge S zusammen mit

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 08.05.2014 20

einer Wahrscheinlichkeitsverteilung P : 2S → R≥0 definiert auf der Po-

tenzmenge 2S von S mit
[  X
P (S) = 1 und P An = P (An )
n∈N n∈N

für jede Folge (An ) paarweise disjunkter Teilmengen von S [beachte absolute
Konvergenz und Vertauschbarkeit]. Die Teilmengen von S heißen Ereignisse
und die Elemente von S Elementarereignisse.
Die Wahrscheinlichkeitsfunktion P istSbestimmt durch
P ihre Werte auf den Ele-
mentarereignissen, denn P (A) = P ( a∈A {a}) = a∈A P ({a}) für A ⊆ S.
Man überlegt sich leicht, dass 0 ≤ P (A) ≤ 1 und P (S \ A) = 1 − P (A) für alle
A ⊆ S gilt, und damit P (∅) = 1 − P (S) = 0.
Gilt P ({s}) = P ({t}) für alle s, t ∈ S, so heißt P PGleichverteilung oder
Laplace-Verteilung P auf S. Für s ∈ S folgt dann 1 = t∈S P ({t}) = |S|P ({s})
und somit P (A) = a∈A P ({a}) = |A|/|S|; insbesondere ist S endlich.
3.9 Beispiele. (a) Durch den Wahrscheinlichkeitsraum S = {1, . . . , 6} mit
der Gleichverteilung wird das Würfeln eines Spielwürfels modelliert. Die Er-
eignisse Z = {2, 4, 6} (eine durch zwei teilbare Zahl zu würfeln) und D = {3, 6}
(eine durch drei teilbare Zahl zu würfeln) sind unabhängig, denn P (Z ∩ D) =
P ({6}) = 16 = 12 · 13 = P (Z)P (D).
(b) Zweimaliges Würfeln modelliert man durch S = {1, . . . , 6}2 und das Er-
eignis „Augensumme ist 4“ wird durch A = {(1, 3), (2, 2), (3, 1)} beschrieben;
seine Wahrscheinlichkeit ist |A| 3 1
|S| = 36 = 12 .

(c) Beim Lotto „6 aus 49“ ist S = {1,...,49}

6 , und es liegt Gleichverteilung
vor mit einer Wahrscheinlichkeit von 1 zu |S| = 49


6 = 13 983 816.
 Das Er-
eignis „j ist eine der 6 gezogenen Zahlen“ ist gegeben durch Aj = {j} ∪ B :
|A | (48
5)
B ∈ {1,...,49}\{j} 6


5 und hat daher die Wahrscheinlichkeit |S|j = 49 = 49 ≈
(6)
0,1224.
(d) Das n-fache Werfen einer gezinkten Münze wird beschrieben durch PnS =
{0, 1}n und P ({s}) = pe (1 − p)n−e für festes p ∈ [0, 1], wobei e := i=1 si
die Anzahl der 1-en in s = (s1 , s2 , . . . , sn ) ist. Hier liegt nur für p = 1/2
Gleichverteilung, also eine ungezinkte Münze, vor. Wenn Sie der Münze Ihres
Gegenspielers misstrauen, lassen Sie ihn zweimal werfen, und werten Sie (0, 1)
als Kopf und (1, 0) als Zahl, und bei den Ausgängen (0, 0) oder (1, 1) lassen
Sie die zwei Würfe wiederholen. Es liegt dann eine Gleichverteilung vor, denn
P ({(0, 1)}) = p(1 − p) = P ({(1, 0)}). [Dieser Trick wird zur Verbesserung von
physikalischen Zufallszahlengeneratoren benutzt.]

3.10 Erwartungswert und Varianz. Sei (S, P ) ein endlicher Wahrschein-

lichkeitsraum [für S abzählbar unendlich müssten wir unten immer die Existenz
der Reihen voraussetzen]. Eine Abbildung X : S → R heißt Zufallsvariable.

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 13.05.2014 21

Wir bezeichnen mit X

E(X) := X(s)P ({w})
s∈S

den Erwartungswert (oder Durchschnitt) von X und mit

V (X) := E((X − E(X))2 )

die Varianz (oder Streuung) von X. Die Abbildung E ist R-linear, daher gilt

V (X) = E(X 2 ) − E(X)2 ,

denn V (X) = E(X 2 − 2XE(X) + E(X 2 )) = E(X 2 ) − 2E(X)2 + E(X)2 .

3.11 Beispiele. (a) Sei X die Augenzahl beim Würfeln. Dann gilt E(X) =
1
P6 3·7 7 1
P6 7 2 2(25+9+1)
6 i=1 i = 6 = 2 und V (X) = 6 i=1 (i − 2 ) = 6·4 = 35
12 ≈ 2,92.
(b) Sei S := Sn = Sym({1, . . . , n}) für n ∈ N und X(s) die Anzahl der
Fixpunkte von s ∈ S. Zur Berechnung von E(X) und V (X) betrachten wir die
Zufallsvariablen Xi : S → {0, 1} mit
(
0 falls s(i) 6= i
Xi (s) =
1 falls s(i) = i

(n−1)! 1
für s ∈ S und i = 1, . . . , n. Es gilt E(Xi ) = n! = n und daher
n n
X X 1
E(X) = E( Xi ) = E(Xi ) = n · = 1.
i=1 i=1
n

Weiter gilt
n
 X 2  n
X n
X X
E(X 2 ) = E Xi = E(Xi Xj ) = E(Xi2 ) + 2 E(Xi Xj )
i=1 i,j=1 i=1 i<j

1
und Xi2 = Xi , also E(Xi2 ) = E(Xi ) = n. Für i 6= j ist

1 (n − 2)! 1
E(Xi Xj ) = {s ∈ S : s(i) = i und s(j) = j} = =
n! n! n(n − 1)
und zusammen für n ≥ 2
 
2 1 n 1
E(X ) = n · + 2 = 1 + 1 = 2,
n 2 n(n − 1)
also
V (X) = E(X 2 ) − E(X)2 = 2 − 1 = 1.
Permutationen haben also im Durchschnitt einen Fixpunkt, oder man sagt
auch 1 ± 1 viele Fixpunkte.

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 13.05.2014 22

4 Inklusion und Exklusion

In diesem kurzen Abschnitt wollen wir ein weiteres Prinzip der Kombinatorik
behandeln:
4.1 Satz (Siebformel). Für endliche Mengen A1 , A2 , . . . , An gilt
n
[ X \
Ai = (−1)|I|−1 Ai .
i=1 ∅6=I⊆{1,...,n} i∈I
T
Alternative Formulierung für endliches M ⊇ Ai mit Abkürzung i∈∅ Ai := M :
n
[ X \
M\ Ai = (−1)|I| Ai .
i=1 I⊆{1,...,n} i∈I

Beweis. Für n = 1 ist die Aussage klar. Wir führen Induktion über n und
nutzen die Induktionsvoraussetzung für A2 , . . . , An und A1 ∩ A2 , . . . , A1 ∩ An :
n n n
[ 1.3(c) [ [
|A1 ∪ Ai | = |A1 | + Ai − (A1 ∩ Ai )
i=2 i=2 i=2
X \ X \
= |A1 | + (−1)|I|−1 Ai − (−1)|I|−1 Ai .
∅6=I⊆{2,...,n} i∈I ∅6=I⊆{2,...,n} i∈{1}∪I
2
4.2 Bemerkung (Bonferroni-Ungleichungen). Für endliche Mengen
A1 , A2 , . . . , An , ungerades u ∈ N und gerades g ∈ N gilt
n
[ m
X X \
βg ≤ Ai ≤ β u mit βm := (−1)k−1 Ai .
i=1 k=1 I∈( {1,...,n}
) i∈I
k

Für u, g ≥ n gilt Gleichheit wegen 4.1. Man erhält z.B.

n
X X n
[ n
X
|Ai | − |Ai ∩ Aj | ≤ Ai ≤ |Ai |.
i=1 i<j i=1 i=1

4.3 Fixpunktfreie Permutationen. Wir wollen die Anzahl dn der Per-

mutationen aus Sn ohne Fixpunkte (derangements) bestimmen. Für Ai :=
{σ ∈ Sn : σ(i) = i} haben wir AI := i∈I Ai ∼
T
= Sym({1, . . . , n} \ I) für
I ⊆ {1, . . . , n}, also |AI | = (n − |I|)! nach 2.1. Mit Satz 4.1 folgt
n
[ X
dn = Sn \ Ai = (−1)|I| (n − |I|)!
i=1 I⊆{1,...,n}
n n
(−1)k
 
X n X
= (−1)k (n − k)! = n!
k k!
k=0 k=0

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 13.05.2014 23

Für die Wahrscheinlichkeit dn /n! der Fixpunktfreiheit in Sn gilt demnach

∞
X (−1)k
dn
lim = = e−1 ≈ 0,37.
n→∞ n! k!
k=0

Ferner haben wir mit der Restgliedabschätzung des Leibnizkriteriums

∞
X (−1)k Leibniz (−1)n+1 1 1
|dn − n!e−1 | = n! < n! = ≤ ,
k! (n + 1)! n+1 2
k=n+1

also ist dn die nächste bei n!/e liegende ganze Zahl.

4.4 Surjektive Abbildungen. Die Anzahl der surjektiven Pk Abbildungen ei-

l k

n
ner n-Menge auf eine k-Menge ist gegeben durch (−1)
l=0
l (k − l) =
Pk k−l k n

Pn l n n
(−1) l . Insbesondere gilt n! = l=0 (−1) l (n − l) und 0 =
Pkl=0 l k

l n
l=0 (−1) l (k − l) für n < k; siehe 3.3(b).

Beweis. Sei M = {1, . . . , k}{1,...,n} , also |M | = k n nach 3.2. Für l ∈ {1, . . . , k}

sei Al = {f ∈ M : lT6∈ im f } = ({1, . . . , k} \ {l}){1,...,n} . Wieder folgt |Al | =
(k−1)n und ebenso | l∈I Al | = (k−|I|)n für I ⊆ {1, . . . , k}. Die Siebformel 4.1
Sk Pk
liefert |M \ l=1 Al | = I⊆{1,...,k} (−1)|I| (k − |I|)n = l=0 (−1)l kl (k − l)n
P

für die Menge der surjektiven Abbildungen. 2

4.5 Partitionen und Stirling-Zahlen. Für n, k ∈ N0 sei Sn,k die Anzahl

der Partitionen einer n-Menge, die aus k nichtleeren Teilmengen bestehen, also
Sn,k := |{X ⊆ 2{1,...,n} \ {∅} : X ist Partition von {1, . . . , n}, |X| = k}|.
Beachte S0,0 = 1 und S0,k := 0 für k ∈ N. Diese Zahlen heißen Stirling-
Zahlen 2. Art (die Stirling-Zahlen 1. Art sind die Anzahlen sn,k der Permu-
tationen aus Sn mit genau k Zyklen einschließlich der Länge 1).
Ist f : {1, . . . , n} → {1, . . . , k} surjektiv, so ist {f −1 (l) : l ∈ {1, . . . , k}} eine
Partition von {1, . . . , n} mit genau k nichtleeren Komponenten. Umgekehrt
bestimmt jede solche Partition genau k! solche surjektiven Abbildungen, denn
wir betrachten ungeordnete Partitionen.
Pk Pk
Nach 4.4 gilt also k!Sn,k = l=0 (−1)l kl (k − l)n = l=0 (−1)k−l kl ln .

4.6 Einschub: Endliche Körper. Sei n eine natürliche Zahl, und für z ∈ Z
sei rn (z) ∈ {0, 1, . . . , n − 1} der eindeutig bestimmte Rest bei Division von z
durch n. Damit definieren wir eine Addition und Multiplikation auf Zn =
{0, 1, . . . , n − 1} durch a ⊕ b := rn (a + b) und a b := rn (a · b) und (Zn , ⊕, )
wird damit zu einem kommutativen Ring, dem Restklassenring modulo n. Es
ist Zn genau dann ein Körper, wenn n eine Primzahl ist; siehe Algebra WS11,
Satz 10.7.

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 15.05.2014 24

Sei nun K ein beliebiger Körper, z.B. der Restklassenkörper Zp für p ∈ P

wie oben, und sei f ∈ K[x] ein Polynom über K mit grad f ≥ 1. Analog
zur obigen Definition sei rf (g) der eindeutig bestimmte Rest bei Division von
g durch f mit grad rf (g) < grad f . Ganz analog zu Zn definieren wir auf
K[x]f := {g ∈ K[x] : grad g < grad f } eine Addition und Multiplikation durch
a⊕b := rf (a+b) = a+b und a b := rf (a·b) und erhalten einen kommutativen
Ring (K[x]f , ⊕, ), der genau dann ein Körper ist, wenn f ein irreduzibles
Polynom ist, d.h. aus f = gh mit g, h ∈ K[x] folgt grad g = 0 oder grad h = 0,
siehe Algebra WS11, Satz 10.4.
Ist K ein endlicher Körper, so gilt |K[x]f | = |K|grad f .
[Wie immer schreiben wir für ⊕ und meisten einfach + bzw. · .]
Beispiele. Es gilt R[x]x2 +1 ∼
= C, denn (ax + b) (cx + d) = rx2 +1 (ac(x2 + 1) +
(ad + bc)x + bd − ac) = (ad + bc)x + bd − ac. Der Ring Z4 ist kein Körper, denn
2 2 = 0, aber Z2 [x]x2 +x+1 = {0, 1, x, x + 1} mit x2 = x + 1 ist ein Körper
mit 4 Elementen.
4.7 Satz. (a) Für jeden endlichen Körper K ist die Ordnung |K| eine Prim-
zahlpotenz, und umgekehrt gibt es zu jeder Primzahlpotenz ab 2 einen Körper
mit dieser Ordnung; zwei endliche Körper von gleicher Ordnung q sind iso-
morph. Man bezeichnet solch einen Körper mit Fq oder GF(q) von „Galois-
Feld“.
(b) Genau dann hat Fpa mit p ∈ P einen Teilkörper der Ordnung q, wenn
q = pb und b | a; in dem Fall gibt es genau einen solchen Teilkörper.
(c) Die multiplikative Gruppe K ∗ = K \ {0} eines endlichen Körpers K ist
∗ ∗
zyklisch, d.h. es gibt ein a ∈ K ∗ mit K ∗ = {a1 , a2 , . . . , a|K | } mit a|K | = 1.

Beweis. Zitate aus Algebra WS11: Satz 17.2, Satz 17.3., Satz 9.5. 2

Beispiele: Es gibt Körper der Ordnungen 2, 3, 4, 5, 7, 8, 9, 11, . . . aber nicht

6 oder 10. Der Körper F128 = F27 hat nur die Teilkörper F2 , F128 wegen 7 ∈ P
und F256 = F28 hat genau die Teilkörper F2 , F4 F16 , F256 .

4.8 Irreduzible Polynome über endlichen Körpern. Sei K ein endli-

cher Körper mit q = |K| und IK (n) die Menge der irreduziblen normierten
Polynome in K[x] vom Grad n ∈ N und Iq (n) := |IK (n)|. Seien p1 , . . . , pr die
sämtlichen Primteiler von n. Dann gilt
1 X n
Iq (n) = (−1)|I| q nI mit nI := Q .
n i∈I pi
I⊆{1,...,r}

Beweis. Nach 4.7(b) hat L := Fqn einen zu Fq ∼

= K isomorphen Teilkörper,
und wir können daher K ⊆ L annehmen. Weil L∗ = L \ {0} eine Gruppe

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 20.05.2014 25

n
mit q n − 1 Elementen ist (oder mit 4.7(c)), gilt aq −1 = 1 für alle a ∈ L∗
n
und daher aq = a für alle a ∈ L. Also sind alle Elementen von L Nullstellen
n
des Polynoms g := xq − Q x, und daher zerfällt g in paarweise verschiedene
Linearfaktoren, also g = a∈L x − a.
Wir betrachten die Menge
E := {a ∈ L : L ist einziger Teilkörper X mit K ∪ {a} ⊆ X ⊆ L}.
Gewöhnlich schreibt man K(a) = {h(a) : h ∈ K[x]} für den kleinsten Teilkör-
per von L, der K ∪ {a} enthält, es gilt also a ∈ E ⇐⇒ K(a) = L. Ist f ∈ K[x]
das Minimalpolynom von a ∈ E, so folgt f | g wegen g(a) = 0. Also zerfällt mit
g auch f über L in paarweise verschiedene Linearfaktoren. Da f irreduzibel ist,
folgt, dass f das Minimalpolynom all dieser Nullstellen ist. Ferner überlegt man
sich, dass K(a) ∼ = K[x]f gilt mit Isomorphismus h ∈ K[x]f 7→ h(a) ∈ K(a)
(siehe Algebra WS11, Satz 13.6). Es folgt grad f = n wegen |L| = |K|n , also
f ∈ IK (n).
Ist umgekehrt f ∈ IK (n), so ist x ∈ L0 := K[x]f eine Nullstelle von f im
Körper L0 . Wegen |L0 | = q n erhalten wir wie oben f | g, und daher zerfällt f
auch über L in Linearfaktoren der Form x − a. Zu all diesen Nullstellen a ∈ L
ist f Minimalpolynom, und wegen K(a) ∼ = L0 folgt a ∈ E.
Wir haben gezeigt, dass E partitioniert wird in n-Mengen, die aus Nullstellen
zu Polynomen f ∈ IK (n) bestehen, also gilt n · Iq (n) = |E|. Wir bestimmen
|E|: Die Elemente von L \ E liegen in maximalen echten Teilkörpern von L.
Nach 4.7(b) sind dies genau die Teilkörper T Ai von L mit |Ai | = q n/pi = q n{i} für
nI
I ⊆ {1, . . . , r} folgt | i∈I Ai | = q wegen ggTi∈I n/pi = nI
i = 1, . . . , r. Für T
mit 4.7(b), denn i∈I Ai ist der größte gemeinsame Teilkörper der Ai für i ∈ I,
und daher X
|E| = (−1)|I| q nI .
I⊆{1,...,r} 2

Beispiele. Es gilt I2 (2) = 21 (22 − 21 ) = 1 mit x2 + x + 1 ∈ IF2 (2), I2 (6) =

1 6 3 2 1 54 1 8 4 240
6 (2 − 2 − 2 + 2 ) = 6 = 9 und I2 (8) = 8 (2 − 2 ) = 8 = 30. Die
einfachste Abschätzung nach Bonferroni [oder |E| ≤ |L| in obigem Beweis]
liefert Iq (n) ≤ n1 q n , und für große n ist diese Abschätzung recht gut. Da es
genau q n normierte Polynome vom Grad n gibt, ist die Wahrscheinlichkeit für
Irreduzibilität also etwa 1/n.
4.9 Bemerkung. Es gilt die Rekursionsformel
X
qn = dIq (d),
d|n

denn das Produkt der normierten irreduziblen Polynome über Fq vom Grad
n
d | n ist genau g = xq − x (Algebra WS11, Übungsaufgabe 12.2). [Man kann
Sie auch rein analytisch mit erzeugenden Funktionen beweisen; siehe Cameron,
Combinatorics, Abschnitt 4.7.]

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 20.05.2014 26

5 Erzeugende Funktionen
5.1 (Formale) Potenzreihen. Wir betrachten hier Potenzreihen meist et-
was anders als in der Analysis. Soweit möglich verzichten wir auf Konver-
genzbetrachtung und rechnen lediglich formal mit ihnen wie es in der Alge-
bra präzisiert wird, siehe AlgebraP WS11, Definition 9.1. Formale Potenz-
an xn = n∈N0 an xn = n≥0 an xn und
P P
reihen sind Ausdrücke der Form
können als Verallgemeinerungen von Polynomen betrachtet werden; dabei ist
(an )n∈N0 eine Folge in einem kommutativen Ring R, etwa Z, Q, R oder C.
Wir rechnenPmit ihnen P wie aus derPAnalysis P bekannt und P durch Polynome
n n n n
motiviert: c an x = (can )x
Pn , a n x + b n x = (an + bn )xn und
n n n
P P P
( an x )( bn x ) = n∈N0 ( k=0 ak bn−k )x . Auf diese Weise erhält man
den Ring R[[x]] der formalen Potenzreihen, welcher den Polynomring R[x]
enthält.
Beispiel. Wir berechnen das Produkt ( xn )(1 − P
P n P
x − n≥1 xn =
P
x) =
n
1. Dies bedeutet, dass die geometrische Reihe P nx invertierbar
1
ist mit
Inversem 1 − x. Wir können also auch schreiben x = 1−x im Ring Z[[x]].
1
Quadrieren wir beide Seiten erhalten wir (n + 1)xn = (1−x)
P
2 , was sich auch

durch formales Differenzieren ergibt.

5.2 Definition. Sei a = (an )n∈N0 eine Folge in P

einem kommutativen Ring
(z.B. Z, R oder C). Die (formale) Potenzreihe an xn heißt erzeugende
Funktion von a.

Idee von erzeugenden Funktionen: Eigentlich will man die Folge a besser ver-
stehen – z.B. eine einfache Formel finden. Anstatt sich mit den unendlich vielen
Folgengliedern herum zu schlagen ordnet man der Folge ein einziges Objekt
zu, die erzeugende Funktion, und untersucht dieses, z.B. mit Hilfsmitteln der
Analysis oder Algebra. Einfache Versionen dieser Methode haben wir schon
in 2.11 und 2.13 kennen gelernt.
5.3 Beispiele. (a) P Die Folge (1, 1, 1, . . . ) hat als erzeugende Funktion die geo-
metrische Reihe xn = (1 − x)−1 . Wie wir oben gesehen haben, hat also
(1, 2, 3, . . . ) die erzeugende Funktion (1 − x)−2 .
(b) Nach 2.14 (binomische Reihe) ist (1 + x)r für r ∈ R die erzeugende
Funktion von kr k∈N0 ; speziell ist (1 − x)−n die erzeugende Funktion von



n+k−1
= n−1+k





k k∈N0 n−1 k∈N0
für n ∈ N.
√
1− 1−4x
(c) Für die erzeugende Funktion der Catalan-Zahlen Cn erhält man x ,
siehe 2.14.

5.4 Anwendung farbige Kugeln. Eine Kiste enthält 30 rote, 40 blaue

und 50 grüne Kugeln, jeweils nicht unterscheidbar. Auf wie viele Arten kann
man Kugeln 70 entnehmen?

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 20.05.2014 27

Wir suchen also alle Tupel i, j, k mit i ∈ {0, . . . , 30}, j ∈ {0, . . . , 40}, k ∈
{0, . . . , 50} und i + j + k = 70. Die Anzahl dieser Tupel entspricht genau dem
Koeffizienten von x70 in
f := (1 + x + · · · + x30 )(1 + x + · · · + x40 )(1 + x + · · · + x50 ).
Zunächst gilt
X X X 1 − xk+1
1 + x + · · · + xk = xn − xk+1 xn = (1 − xk+1 ) xn = .
1−x
und damit

f = (1 − x31 )(1 − x41 )(1 − x51 )(1 − x)−3

5.3(b) X n + 2
31 41 51
= (1 − x − x − x + · · · ) xn ,
2

so dass x70 den Koeffizienten 72 41 31 21 1

2 − 2 − 2 − 2 = 2 (72 · 71 − 41 · 40 −
31 · 30 − 21 · 20) = 1061 hat.

5.5 Fibonacci-Zahlen. Die Folge der Fibonacci-Zahlen ist rekursiv de-

finiert:
F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn für n ∈ N0 .
Hier ist eine Tabelle:
n 0 1 2 3 4 5 6 7 8 9 10 11 12 ···
Fn 0 1 1 2 3 5 8 13 21 34 55 89 144 ···

Diese Folge taucht so häufig in Mathematik und Natur auf, dass ihr eine eigene
Zeitschrift, der Fibonacci Quarterly gewidmet ist. Wir wollen die erzeugende
Funktion F bestimmen und rechnen (mit Fk = 0 für k ≤ 0)
X X X
F = Fn x n = Fn−1 xn + Fn−2 xn + x = xF + x2 F + x.

Auflösen nach F gibt

x
F = .
1 − x − x2
Wir wollen nun die Koeffizienten der formalen Potenzreihe F direkt bestim-
men, um eine explizite Darstellung für Fn zu erhalten. Seien α und β die
Nullstellen von x2 − x − 1. Dann gilt 1 − x − x2 = (1 − αx)(1 − βx), denn
Division durch x2 liefert 1 − x1 − x12 = (1 − αx )(1 − β1 ). Jetzt machen wir eine
Partialbruchzerlegung, also den Ansatz
a b
F = + ,
1 − αx 1 − βx
dabei bestimmen wir a und b später durch Koeffizientenvergleich. Wir erhalten
X X X
F =a (αx)n + b (βx)n = (aαn + bβ n )xn ,

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 22.05.2014 28

und daher die explizite Darstellung

Fn = aαn + bβ n (∗)

der Fibonacci-Folge. Die Nullstellen von x2 − x − 1 ergeben sich zu

√ √
1+ 5 1− 5
α= und β =
2 2
und durch Koeffizientenvergleich
√ mit F0 = 0 und F1 = 1 ergibt sich a = −b =
1/(α − β) = 1/ 5 aus (∗), also
 √ n  √ n 
1 1+ 5 1− 5
Fn = √ − .
5 2 2

Dies ist eine erstaunliche Beschreibung der Fibonacci-Zahlen, denn diese na-
türlichen Zahlen werden durch Potenzen
√ von irrationalen Zahlen dargestellt.
Die Potenzen der Zahl β = 21 (1 − 5) = −0,618 . . . werden sehr schnell klein
wegen |β| < 1, so dass aαn eine sehr gute Näherung für Fn darstellt, es gilt
etwa aα12 = 144, 001 . . . . Außerdem ist das Verhältnis aufeinander folgender
Fibonacci-Zahlen ungefähr α.
√
Die Zahl α = 12 (1+ 5) = 1,618 . . . wird als Goldener Schnitt bezeichnet. Sie
ist das Seitenverhältnis eines Rechtecks, das nach Abschneiden eines Quadrates
in ein Rechteck mit gleichem Seitenverhältnis übergeht.
α
1
2
1
1 5
3

1/α 1

5.6 Bemerkung (Lineare Rekursionsgleichungen). Ähnlich wie die Fol-

ge der Fibonacci-Zahlen lassen sich auch lineare Rekursionsgleichungen der
Länge d ∈ N mit Koeffizienten zi ∈ C vom Typ

f (n + d) = z1 f (n + d − 1) + z2 f (n + d − 2) + · · · + zd f (n)

für alle n ∈ N0 durch erzeugende Funktionen lösen. Das Problem wird dabei
zurück geführt auf die Bestimmung von Nullstellen von Polynomen vom Grad
d. Siehe Aigner, Diskrete Mathematik, Satz 3.1.

5.7 Beispiel. Wir bestimmen für n ∈ N0 die Anzahl an der Abbildungen

f : {1, . . . , n} → {1, . . . , n} mit im f = {1, . . . , k} für ein k ∈ N0 . Es gilt a0 =
a1 = 1 und a2 = 3. Angenommen f bildet genau k Elemente auf 1 ab, dann

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 22.05.2014 29

können wir diese Elemente auf nk Arten wählen, und der Rest kann auf an−k

Weisen auf {2, . . . , n} abgebildet werden. Wir erhalten die Rekursionsgleichung

n   n  
(
X n X n 1 für n = 0,
an = an−k oder 2an = an−k +
k k 0 für n > 0
k=1 k=0

und betrachten die erzeugende Funktion  von (an /n!)n∈N0 , die sogenannte
exponentielle erzeugende Funktion von (an )n∈N0 und berechnen
n   n
X 1 X n XX 1 an−k n
2Â(x) = an−k xn +1 = x +1 = ex Â(x)+1,
n
n! k n
k! (n − k)!
k=0 k=0

also
∞ ∞ ∞
1 1 X  ex k X 1 X k n xn
Â(x) = = = ,
2 − ex 2 2 2k+1 n=0 n!
k=0 k=0
n
und durch Koeffizientenvergleich für x erhalten wir
∞
X kn
an = .
2k+1
k=0

III Graphentheorie
6 Grundlegende Begriffe
6.1
Definition. Ein Graph ist ein Paar G = (V, E) von Mengen mit E ⊆
V
2 . Die Menge V heißt Eckenmenge oder Vertexmenge und E heißt Kan-
tenmenge [englisch: edge set]. Für V und E schreiben wir auch V (G) bzw.
E(G) [auch wenn die Mengen V und E anders heißen]. Ferner heißt G endlich,
falls |V | < ∞.

Endliche Graphen lassen sich gut durch Bilder angeben: Für jede Ecke zeichnet
man einen Punkt und für jede Kante {v, w} eine Linie, die die Ecken v und w
verbindet. So wird der Graph
2 1
({1, 2, 3, 4, 5}, {{1, 2}, {1, 5}, {2, 3}, {2, 5}}) durch
3 5 4
dargestellt. Für eine Kante {v, w} schreiben wir auch vw. Zwei Ecken v und
w heißen Nachbarn oder benachbart oder adjazent, falls {v, w} ∈ E gilt,
verschiedene Kanten heißen adjazent, falls ihr Schnitt nicht leer ist, und eine
Ecke v und eine Kante e heißen inzident, falls v ∈ e gilt.
6.2 Beispiele. (a) Für eine Menge V heißt K(V ) := (V, V2 ) der vollstän-

dige Graph auf V . In ihm sind je zwei Ecken benachbart, und jeder solche

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 22.05.2014 30

Graph heißt vollständig. Für K({1, . . . , n}) mit n ∈ N0 schreiben wir Kn .

Als anderes Extrem hat man den Graphen K(V ) = (V, ∅) ohne Kanten. Ferner
heißt K0 = (∅, ∅) leerer Graph.

K5
K2
K3 K4

(b) Für disjunkte Mengen V und W heißt jeder Graph der Form (V ∪W, {{v, w} :
v ∈ V, w ∈ W }) vollständig bipartit; speziell betrachtet man Kn,m für
V = {1, . . . , n} und W = {n + 1, n + 2, . . . , n + m} mit n, m ∈ N0 .

K1,1 K1,2 K1,3 K2,2 K2,3 K3,3

(c) Für n ∈ N0 heißt der Graph Pn := ({0, 1, . . . , n}, {{i − 1, i} : i = 1, . . . , n})

Weg der Länge n, und 0 und n heißen Enden von Pn . Er hat n + 1 Ecken
und n Kanten.

P5

(d) Für n ≥ 3 heißt Cn := ({1, . . . , n}, {{1, 2}, {2, 3}, . . . , {n − 1, n}, {n, 1}})
Kreis der Länge n; für n = 3, 4, . . . sagt man auch Dreieck, Viereck, etc.
Der Kreis Cn besteht aus n Ecken und n Kanten. Es gilt C3 = K3 .

C4 C5
C3

(e) Der Graph J(n, k, i) für n ≥ k ≥ i ≥ 0 hat als Eckenmenge die Men-
ge der k-elementigen Teilmengen von {1, . . . , n}, und zwei Ecken sind genau
dann benachbart, wenn ihr Schnitt genau i Elemente enthält. Die Graphen
K(n, k) := J(n, k, 0) heißen Kneser-Graphen, und einer der wichtigsten Gra-
phen ist der Petersen-Graph K(5, 2). Er hat 10 Ecken und 15 Kanten, und
jede Ecke hat genau drei Nachbarn.

K(5, 2)

(f) Der d-dimensionale Würfel Qd ist gegeben durch V (Qd ) = {0, 1}d , die

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 27.05.2014 31

Eckenmenge ist also die Menge der 0-1-Folgen der Länge d, und zwei Folgen
sind genau dann adjazent, wenn sie sich an genau einer Stelle unterscheiden.

Q1 Q2 Q3

(g) Ein interessanter unendlicher Graph ist der sogenannte zufällige Graph
 
R := N0 , {k, n2k+1 + 2k + r} | k, n, r ∈ N0 , r < 2k .


Man überlegt sich leicht, dass zwei Ecken k und l genau dann adjazent sind,
wenn an der k-ten Stelle bk in der Binärdarstellung bm bm−1 . . . b1 b0 von l eine 1
steht, oder umgekehrt an der l-ten Stelle in derjenigen von k. Dieser Graph ist
universell in dem Sinne, dass jeder endliche oder abzählbar unendliche Graph
[als induzierter Teilgraph] in ihm enthalten ist. [Erklärung des Namens zufäl-
liger Graph: Wählt man zufällig einen Graphen mit Eckenmenge N0 (dies ist
nicht ganz leicht zu präzisieren), so erhält man mit Wahrscheinlichkeit 1 einen
zu R isomorphen Graphen.]

6.3 Definition. Zwei Graphen G = (V, E) und G0 = (V 0 , E 0 ) heißen iso-

morph, in Zeichen G ∼ = G0 , wenn es einen Isomorphismus von G nach G0
gibt, d.h. eine Bijektion f : V → V 0 , die die Äquivalenz

{v, w} ∈ E ⇔ {f (v), f (w)} ∈ E 0 (∗)

erfüllt; dies bedeutet, dass f eine Bijektion E → E 0 induziert. Ein Isomor-

phismus von G nach G heißt Automorphismus von G, und die Menge aller
Automorphismen von G ist eine Untergruppe der Gruppe Sym(V ) aller Bijek-
tionen von V , die Automorphismengruppe Aut G von G.

Die Bedingung (∗) bedeutet, dass die Menge der Nachbarn von jeder Ecke v
von G durch f auf die Menge der Nachbarn der Ecke f (v) von G0 abgebildet
wird. Insbesondere sind die Grade, also die Anzahlen der Nachbarn von v
bzw. f (v) gleich; die Umkehrung gilt nicht, denn zwischen den Eckenmengen
der beiden Graphen

6∼
=

gibt es zwar eine Bijektion, die Ecken mit gleich vielen Nachbarn aufeinander
abbildet, aber sie ist kein Isomorphismus, da im linken Graphen die beiden
Ecken mit genau drei Nachbarn benachbart sind und im rechten nicht.
Alle Bijektionen von V sind Automorphismen von K(V ) und K(V ), also gilt
Aut(K(V )) = Aut(K(V )) = Sym(V ).

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 27.05.2014 32

Für n ≥ 1 gilt | Aut Pn | = 2, denn jeder Automorphismus muss die Enden des
Weges aufeinander abbilden, da die Anzahl der Nachbarn erhalten bleibt.
Es gelten die trivialen Isomorphien K1 ∼ = P0 ∼ ∼ P1 ∼
= Q0 , K2 = = Q1 , K3 = C 3 ,
∼ ∼ ∼ ∼
C4 = Q2 und K(n, 1) = Kn . Falls G = Pn oder G = Cn , etc., sagen wir auch
G ist ein Weg bzw. ein Kreis, etc. Es gibt genau 64 Graphen (V, E) mit
V 4
V = {1, 2, 3, 4}, denn die Menge V2 hat 2|( 2 )| = 2(2) = 26 = 64 Teilmengen;

jeder dieser Graphen ist zu einem der folgenden 11 Graphen isomorph:

Wir wollen uns überlegen, dass die Anzahl der Isomorphieklassen von Graphen
n
mit n Ecken trotzdem fast so schnell wächst wie 2( 2 ) . Auf der Eckenmenge V =
{1, 2, . . . , n} gibt es n! Bijektionen. Jeder Graph (V, E) kann also höchstens
zu n! Graphen (V, E 0 ) isomorph sein [genau n!, falls Aut(V, E) = {id}, sonst
(n2 ) n
weniger]. Also gibt es mindestens 2 n! und höchstens 2( 2 ) Isomorphieklassen.
2
Für die Anzahl A(n) der Isomorphieklassen gilt also wegen n2 = n2 (1 − n1 )

n n n
n2 1 2( 2 ) 2( 2 ) 2( 2 ) n2 1 2 log2 n
2 2 (1− n )
≥ A(n) ≥ ≥ n = n log n = 2 2 (1− n − n ) .
n! n 2 2

2 1
Für jedes ε > 0 und n hinreichend groß wächst A(n) also schneller als 2n ( 2 −ε) ,
2
also z.B. schneller als 1,4n . [All diese Graphen sind in R aus 6.2(g) enthalten.]

6.4 Teilgraphen und Konstruktionsmethoden. Für zwei Graphen G =

(V, E) und G0 = (V 0 , E 0 ) definieren wir die Vereinigung G∪G0 := (V ∪V 0 , E ∪
E 0 ) und den Schnitt G∩G0 := (V ∩V 0 , E ∩E 0 ) von Graphen. Ist G∩G0 = (∅, ∅)
der leere Graph, so sagen wir
G und G0 sind disjunkt. Das Komplement von
G ist der Graph G := (V, V2 \ E). Leichte Übungsaufgaben: Aut G ∼ = Aut G,
C5 = ∼ C5 . In obiger Liste der 11 Graphen auf 4 Ecken ist der i-te Graph
Komplement vom (12 − i)-ten Graphen (für i ∈ 3, 6, 9 nur bis auf Isomorphie).
Der Graph G0 heißt Teilgraph von G, in Zeichen G0 ⊆ G, wenn V 0 ⊆ V
und
E 0 ⊆ E gilt. Für eine Teilmenge U ⊆ V heißt der Teilgraph G[U ] := (U, U2 ∩E)
auf U induzierter Teilgraph von G, und G0 heißt aufspannender Teil-
graph von G falls V 0 = V und E 0 ⊆ E gilt. Ein Teilgraph G0 ⊆ G ist also
genau dann induziert, falls zwei Ecken von G0 genau dann adjazent in G0 sind,
wenn sie dies in G sind.

induzierter aufspannender
Teilgraph Teilgraph Teilgraph

Der Kantengraph L(G) von G = (V, E) ist der Graph mit Eckenmenge E,
in dem zwei Ecken (also Kanten von G) benachbart sind, wenn sie adjazent in
G sind.

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 03.06.2014 33

Q3 L(Q3 )

Es gilt L(Kn ) = J(n, 2, 1) und L(Cn ) ∼

= Cn .

6.5 Nachbarschaften und Gradzahlen. Sei G = (V, E) ein Graph. Die

Menge der Nachbarn einer Ecke v von G wird mit N (v) = NG (v) bezeichnet.
Der Grad d(v) = dG (v) := |N (v)| ∈ N0 ∪ {∞} einer Ecke v ∈ V ist die
Anzahl der Nachbarn von v. Eine Ecke mit Grad 0 heißt isoliert. Die Zahl
δ(G) := min d(V ) heißt Minimalgrad von G und die Zahl ∆(G) := max d(V )
heißt Maximalgrad für nichtleeres G. Wenn alle Ecken von G den gleichen
Grad k haben, wird G regulär oder genauer k-regulär genannt.
Der Würfel Qd ist d-regulär, die vollständigen (bipartiten) Graphen Kn+1 bzw.
Kn,n sind n-regulär, Cn ist 2-regulär für n ≥ 3 und Pn ist nur für n ≤ 1 regulär.
Für einen nichtleeren Graphen G = (V, E) gilt die Ungleichung δ(G) ≤ d(v) ≤
∆(G) ≤ |V | − 1 für alle v ∈ V .
Durch doppeltes Abzählen (siehe Übungsaufgabe 7.1) beweist man folgendes
Lemma.
P
6.6 Lemma. Es gilt v∈V d(v) = 2|E| für jeden Graphen (V, E) mit endli-
cher Kantenmenge. Insbesondere ist in jedem Graphen mit endlich vielen Kan-
ten die Anzahl der Ecken mit ungeradem Grad gerade (Handshake-Lemma).

6.7 Gradfolgen. Für einen endlichen Graphen G = (V, E) mit n := |V | sei

v1 , v2 , . . . , vn eine Aufzählung von V ; für die Grade di := d(vi ) nennen wir
D = (d1 , d2 , . . . , dn ) eine Gradfolge von G, und wenn zusätzlich d1 ≤ d2 ≤
· · · ≤ dn gilt, nennen wir D die geordnete Gradfolge von G.
Die geordnete Gradfolge ist eine Invariante des Graphen, d.h. isomorphe Gra-
phen haben die gleiche geordnete Gradfolge. Wir haben schon andere Invarian-
ten kennengelernt: |V |, |E|, δ(G), ∆(G); sie lassen sich alle aus D bestimmen.
Es sind nicht alle endlichen Folgen in N0 Gradfolgen (z.B. wegen 6.6); zu
(1, 1, 2, 4, 4) gibt es keinen Graphen, denn der auf {v1 , v2 , v3 , v4 } induzierte
Teilgraph hätte die Gradfolge (0, 0, 1, 3), aber d1 = 0 und d4 = 3 widersprechen
sich. Dieses Vorgehen ist die Idee für den folgenden Satz, der einen Algorithmus
liefert zur Entscheidung, ob eine Folge eine Gradfolge ist.
6.8 Satz. Für eine Folge ganzer Zahlen D = (d1 , d2 , . . . , dn ) mit n > 1 und

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 03.06.2014 34

d1 ≤ d2 ≤ · · · ≤ dn definieren wir D0 := (d01 , d02 , . . . , d0n−1 ) durch

(
di für i < n − dn und
d0i :=
di − 1 für i ≥ n − dn [dn viele Grade vermindert].

Dann ist D genau dann Gradfolge eines Graphen, wenn dies für D0 der Fall
ist.

Beweis. Eine Implikation ist einfach und motiviert die Definition von D0 : Sei
G0 = ({1, 2, . . . , n − 1}, E) ein Graph mit Gradfolge D0 und d(i) = d0i für alle i.
Dann hat der Graph G = G0 ∪(V (G0 )∪{n}, {{i, n} : i = n−1, n−2, . . . , n−dn })
die Gradfolge D.
Für die Umkehrung sei G die Menge aller Graphen G mit V (G) = {1, 2, . . . , n}
und dG (i) = di für i ∈ V (G). Für G ∈ G definieren wir
 
j(G) := max {0, 1, 2, . . . , n − 1} \ N (n) ≥ n − 1 − dn .

Es gilt dann {j(G) + 1, . . . , n − 1} ⊆ N (n). Nach Voraussetzung ist G nicht

leer, und wir können einen Graphen G mit minimalem j := j(G) wählen.

...
1 2 k i j n

Wir zeigen nun j = n − 1 − dn , womit die Behauptung folgt, denn dann

gilt N (n) = {j + 1, . . . , n − 1}, und der Graph G0 = G[{1, 2, . . . , n − 1}] hat
die Gradfolge D0 . Wir nehmen j > n − 1 − dn an. Dann gibt es ein i < j
mit i ∈ N (n). Ferner gibt es eine Ecke k ∈ N (j) \ N (i) wegen di ≤ dj und
n ∈ N (i) \ N (j). Wir erhalten einen Widerspruch, denn der Graph G̃ ∈ G mit
E(G̃) = (E(G) \ {in, jk}) ∪ {jn, ik} erfüllt j(G̃) < j(G) wegen jn ∈ E(G̃). 2

Wir wollen entscheiden, ob es einen Graphen mit der Gradfolge (1, 1, 1, 2, 2, 3, 4,

5, 5) gibt. Durch fortgesetzte Bestimmung von D0 wie im Satz und nötigen-
falls Umsortieren erhält man: (1, 1, 1, 2, 2, 3, 4, 5, 5) → (1, 1, 1, 1, 1, 2, 3, 4) →
(1, 1, 1, 0, 0, 1, 2) → (0, 0, 1, 1, 1, 1, 2) → (0, 0, 1, 1, 0, 0) → (0, 0, 0, 0, 1, 1) →
(0, 0, 0, 0, 0). Die letzte Folge ist die Gradfolge von K5 , also existiert der ge-
suchte Graph.
6.9 Satz (Turán 1941). Sei 1 < t ∈ N und (V, E) ein endlicher Graph, der
keine t-Clique, also keinen zu Kt isomorphen Teilgraphen, enthält. Dann gilt
  2
1 |V | 1t−2 2
|E| ≤ 1 − = |V | .
t−1 2 2t−1

Beweis. Wir führen Induktion über die Eckenzahl n = |V |. Für n = 1 ist die
Behauptung klar wegen |E| = 0. Sei nun G = (V, E) ein Graph ohne t-Cliquen

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 05.06.2014 35

mit |V | = n und maximalem |E|. Der Graph G enthält eine (t − 1)-Clique C,

da wir sonst Kanten hinzufügen könnten. Dann enthält C genau t−1


2 Kanten
und V \C höchstens 21 t−2 2
t−1 (n−t+1) per Induktion. Da es keine t-Cliquen gibt,
hat jede Ecke in V \ C höchstens t − 2 Nachbarn in C. Also gibt es höchstens
(t − 2)(n − t + 1) Kanten zwischen C und V \ C. Wir erhalten
 
t−1 1t−2
|E| ≤ + (n − t + 1)2 + (t − 2)(n − t + 1)
2 2t−1
1t−2
(t − 1)2 + (n − t + 1)2 + 2(t − 1)(n − t + 1)


=
2t−1
1t−2 2
= n .
2t−1 2

6.10 Korollar (Mantel 1907). Jeder endliche Graph (V, E) mit |E| > 14 |V |2
enthält ein Dreieck, also einen Teilgraphen isomorph zu C3 ∼
= K3 .

6.11 Extremale Graphen. Nach 6.10 gilt |E| ≤ 14 |V |2 für alle Graphen
(V, E), die kein Dreieck enthalten. In der extremalen Graphentheorie fragt
man sich allgemein: Für welche Graphen, die eine Ungleichung erfüllen, gilt die
Gleichheit? Man kann zeigen, dass in 6.10 genau für die vollständig bipartiten
Graphen Kn,n Gleichheit gilt. [Für |E| ≤ b 14 |V |2 c erhält man Kn,n oder Kn,n+1
als extremale Graphen und für 6.9 entsprechend „multipartite Graphen“.]

6.12 Touren und Zusammenhang. Eine Tour der Länge n von v

nach w in einem Graphen G ist eine Folge p = (v0 , v1 , . . . , vn ) von Ecken
mit v = v0 und w = vn , so dass vi−1 und vi für i = 1, 2, . . . , n benachbart
sind. Die Ecken v und w heißen dann verbindbar; diese Relation ist eine
Äquivalenzrelation.
Die Tour p heißt einfach, wenn die Ecken v0 , . . . , vn paarweise verschieden
sind, geschlossen, wenn v0 = vn gilt, und einfach geschlossen, wenn p
geschlossen und (v1 , v2 , . . . , vn ) einfach ist. Die einfachen Touren definieren
Wege in G und die einfach geschlossenen Touren definieren Kreise (jeweils mit
Isomorphismus i 7→ vi ). Die Tour p stottert, falls es ein i ∈ {0, 1, . . . , n − 2}
gibt mit vi = vi+2 .
Der Abstand dG (v, w) = d(v, w) der Ecken v und w in G = (V, E) ist die
kürzeste Länge einer Tour von v nach w (solch eine Tour ist einfach und kann
somit als Weg aufgefasst werden); gibt es keine Tour von v nach w setzen wir
d(v, w) = ∞. Das Supremum diam(G) := sup dG (V × V ) wird als Durch-
messer von G bezeichnet. Es gilt etwa diam Kn = 1, diam Cn = bn/2c und
diam Qd = d.
Ein Graph G heißt zusammenhängend, wenn je zwei Ecken v und w ver-
bindbar sind, und seine Zusammenhangs-Komponenten sind die Äquiva-
lenzklassen bezüglich der Relation Verbindbarkeit.

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 05.06.2014 36

Ein Graph G = (V, E) heißt k-zusammenhängend für k ∈ N, wenn G[V \ X]

zusammenhängend ist für jede Teilmenge X ⊆ V mit |X| < k. Die Wege Pn
für n ≥ 2 sind zusammenhängend, aber nicht 2-zusammenhängend, die Kreise
Cn sind 2-zusammenhängend.

6.13 Euler-Touren und Hamilton-Kreise. Hier geht es um Rundwege

in einem endlichen Graphen G = (V, E).
Eine Euler-Tour von G ist eine geschlossene Tour c = (v0 , v1 , . . . , vn ), die
jede Kante genau einmal durchläuft, d.h. {{vi−1 , vi } : i = 1, . . . , n} = E und
|E| = n.
Nach Euler (1736) existiert eine Euler-Tour in einem Graphen G ohne isolierte
Punkte genau dann, wenn G zusammenhängend und jeder Grad d(v) für v ∈ V
gerade ist; siehe Übungsaufgabe 9.1.

Königsberger Brückenproblem

Ein Hamilton-Kreis von G ist eine einfach geschlossene Tour der Länge |V |;
für |V | ≥ 3 bedeutet dies, dass G einen aufspannenden Kreis enthält; es werden
alle Ecken genau einmal durchlaufen. Man nennt G hamiltonsch, falls in G
ein Hamilton-Kreis existiert. Es ist keine Charakterisierung der hamiltonschen
Graphen bekannt. Das Problem der Existenz eines Hamilton-Kreises für einen
beliebigen Graphen ist NP-vollständig (Karp 1972). Dies ist sogar dann noch
richtig, wenn man die Klasse der Graphen z.B. auf planare Graphen (siehe 8.3)
mit Maximalgrad 3 einschränkt. Allerdings ist jeder 4-zusammenhängende pla-
nare Graph hamiltonsch (Tutte 1956).

6.14 Satz (Dirac 1952). Jeder endliche nichtleere Graph G mit Minimal-
grad δ(G) ≥ 21 |V (G)| ist hamiltonsch.

Beweis. Sei G = (V, E) ein Graph mit n = |V | ∈ N und δ(G) ≥ n/2. Dann
ist G zusammenhängend, denn andernfalls hätte eine Zusammenhangskompo-
nente C mit |C| ≤ n/2 Maximalgrad kleiner als n/2.
Sei nun p = (v0 , v1 , . . . , vk ) eine einfache Tour maximaler Länge. Alle min-
destens n/2 Nachbarn von v0 und von vk liegen auf dieser Tour. Also gibt es
nach dem Schubfachprinzip unter den k < n Indizes i mit 0 ≤ i < k einen mit
vi vk ∈ E und v0 vi+1 ∈ E wie im Bild.

vi+1
... ...
v0 v1 vi vk

Die Tour c := (c0 , . . . , ck+1 ) := (v0 , vi+1 , vi+2 , . . . , vk , vi , vi−1 , . . . , v0 ) ist ein-

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 12.06.2014 37

fach geschlossen. Sie ist ein Hamilton-Kreis, denn andernfalls könnte man we-
gen des Zusammenhangs von G eine Ecke ci von c mit einer Ecke v außerhalb
von c verbinden und erhält so eine einfache Tour (v, ci , . . . , ck+1 =c0 , . . . , ci−1 )
der Länge k + 1 im Widerspruch zur Wahl von p. 2

[Verallgemeinerungen: Ore (1960), Bondy–Chvátal (1972), Chvátal (1972, siehe

Diestel Theorem 10.2.1)]

6.15 Kürzeste Wege und der Algorithmus von Dijkstra. Ein gewich-
teter Graph ist ein Paar (G, w) bestehend aus einem Graphen G = (V, E)
und einer Gewichtsfunktion w : E → R≥0 . Dieser Begriff hat viele praktische
Anwendungen, z.B. lässt sich das Straßennetz modellieren: Straßenkreuzungen
als Ecken, Straßen als Kanten und z.B. Längen der Straßen oder mittlere Fahr-
zeit zwischen zwei Kreuzungen als Gewichte der Kanten. Ist p = (v0 , v1 , . . . , vn )
eine Tour, so ist
X n
w(p) := w({vi−1 , vi })
i=1
das Gesamtgewicht von p. In obigen Beispielen liefert w(p) die Gesamtdi-
stanz von v0 nach vn bzw. die mittlere Fahrzeit entlang der Tour. In Anlehnung
an das erste Beispiel spricht man auch von der Distanz von v0 nach vn entlang
p. Wählt man für alle Kanten Gewicht 1, erhält man die Länge von p.
Sei ein endlicher gewichteter Graph (G, w) mit G = (V, E) und eine Startecke
v0 ∈ V gegeben. Der Dijkstra-Algorithmus bestimmt [für nichtnegative
Gewichte] für jede Ecke v in der Zusammenhangskomponente von v0 eine Tour
p von v0 nach v mit minimalem Gesamtgewicht, also eine Tour minimaler
Distanz [oft auch „kürzester Weg“].
Initialisierung: Wir benötigen die folgenden drei Funktionen und Mengen,
um während der Laufzeit des Algorithmus Buch zu führen:
dist : V → R≥0 ∪ {∞} (aktuelle Distanz zu v0 )
vorg : X → V mit X ⊆ V \ {v0 } (Vorgänger in aktuell kürzestem Weg)
Perm ⊆ V (Ecken, für die obige Daten endgültig)
Setze dist(v0 ) := 0, dist(v) := ∞ für alle v ∈ V \ {v0 }, Perm := ∅, und sei vorg
die leere Abbildung.
Schleife: Solange dist(V \ Perm) \ {∞} 6= ∅ führe folgende Schritte aus.
• Wähle eine Ecke cur ∈ V \ Perm mit minimalem dist(cur).
• Füge cur zu Perm hinzu.
• Für alle v ∈ N (cur) \ Perm bestimme d := dist(cur) + w({cur, v}) und,
falls d < dist(v), setze dist(v) := d und vorg(v) := cur.
Ergebnis: Die Menge Perm ist die Zusammenhangs-Komponente von G, die
v0 enthält. Ferner gibt dist(v) für alle v ∈ Perm die Minimaldistanz zu v0 be-

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 12.06.2014 38

züglich der Gewichtsfunktion w an, und durch (v, vorg(v), vorg(vorg(v)), . . . , v0 )

ist rekursiv eine Tour von v nach v0 mit Gesamtgewicht dist(v) definiert.
6.16 Beispiel. Ein gewichteter Graph mit aufspannendem Baum [siehe Ab-
schnitt 7] minimaler Distanzen von v0 :
a 6 a
k k
8 1 f 1 f
10 b b
4 4
2 7 5 2
4 4
7 4
v0 h v0 h
c c
3 4 4
3 d 4 3 d
2 2
5 2 2
1 1
6
g g
e e

6.17 Satz. Dijkstras Algorithmus ist korrekt.

Beweis. Es sind die drei Behauptungen unter Ergebnis zu zeigen.

Wir zeigen per Induktion über die Anzahl der Schleifendurchläufe, dass am En-
de eines Schleifendurchlaufs die Tour (cur, vorg(cur), vorg(vorg(cur)), . . . , v0 )
eine minimale Tour mit Distanz dist(cur) von cur ∈ Perm nach v0 liefert:
Sei p = (v0 , v1 , . . . , vn−1 , vn ) irgendeine Tour von v0 nach cur, und bezeichne
die Anfangstücke mit pi := (v0 , v1 , . . . , vi ) für i = 0, . . . , n. Wähle nun i < n
maximal mit vi ∈ Perm \ {cur}. Per Induktion gilt w(pi ) ≥ dist(vi ). Wegen
vi ∈ Perm \ {cur} folgt aus der Definition von dist(vi+1 ) für vi+1 ∈ N (vi ) im
Schleifendurchlauf auch dist(vi+1 ) ≤ dist(vi ) + w({vi , vi+1 }), und somit nach
Wahl von cur und wegen w(E) ≥ 0 die gewünschte Abschätzung

w(p) ≥ w(pi+1 ) = w(pi ) + w({vi , vi+1 }) ≥ dist(vi+1 ) ≥ dist(cur).

Weil ferner per Induktion (vorg(cur), vorg(vorg(cur)), . . . , v0 ) eine Tour mini-

maler Distanz von vorg(cur) nach v0 ist, gilt dies auch für (cur, vorg(cur), . . . , v0 ).
Wir müssen noch zeigen, dass am Ende Perm die Zusammenhangskomponente
von v0 ist. Andernfalls können wir eine Tour (v0 , . . . , vn ) minimaler Länge n
wählen, so dass vn 6∈ Perm. Dann folgt wegen der Minimalität vn−1 ∈ Perm
und daher dist(vn ) < ∞, ein Widerspruch zu dist(V \ Perm) \ {∞} = ∅. 2

6.18 Matrixbeschreibung. Sei G = (V, E) ein endlicher Graph. Die Ad-

jazenzmatrix von G ist die quadratische (V × V )-Matrix A mit
(
1 falls vw ∈ E
Avw :=
0 falls vw 6∈ E.

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 17.6.2014 39

Die Inzidenzmatrix von G ist die (V × E)-Matrix B mit

(
1 falls v ∈ e
Bve :=
0 falls v 6∈ e.

Fasst man A und B als reelle Matrizen auf, so ist BB t −A eine Diagonalmatrix
mit den Eckengraden auf der Diagonalen; auch die Potenzen Ak haben eine
graphentheoretische Bedeutung, siehe Übungsaufgabe 11.1.

7 Bäume und Wälder

Ein Wald ist ein Graph, der keine Kreise als Teilgraphen hat, und ein Baum
ist ein zusammenhängender Wald. Ein Wald ist also ein Graph, dessen Zusammenhangs-
Komponenten Bäume sind. Hier ist ein Wald, der aus zwei Bäumen besteht:

Weitere Beispiele für Bäume: Pn , K1,n , PV := (V, {{z, z + 1} : z ∈ V }) für

V ∈ {N, Z}.
Die Ecken vom Grad 1 in einem Wald heißen Blätter. Jeder endliche Baum
mit mindestens zwei Ecken hat mindestens zwei Blätter, nämlich die Enden
eines maximalen Weges. Für unendliche Bäume ist dies falsch: PN , PZ .

7.1 Satz (Charakterisierung von Bäumen). Die folgenden Aussagen für

einen Graphen T = (V, E) sind äquivalent.
(a) T ist ein Baum.
(b) Je zwei Ecken von T sind durch einen eindeutigen Weg verbunden.
(c) T ist minimal-zusammenhängend, d.h. T ist zusammenhängend, und
für jede Kante e ist T−e := (V, E \ {e}) unzusammenhängend.
(d) T ist maximal-azyklisch, d.h. T enthält keinen Kreis, aber für je zwei
nicht-benachbarte Ecken v und w enthält T+vw := (V, E ∪ {vw}) einen
Kreis.

Beweis. (a) ⇒ (b): Da T zusammenhängend ist, sind je zwei Ecken durch eine
Tour verbunden, und damit auch durch einen Weg (Übungsaufgabe 10.4(a)).
Dieser Weg ist eindeutig nach Übungsaufgabe 10.4(b).

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 17.6.2014 40

(b) ⇒ (c): Wäre T−e zusammenhängend, so gäbe es in T−e einen Weg zwischen
den beiden Ecken von e und in T zusätzlich noch den Weg (e, {e}), was der
Eindeutigkeit widerspricht.
(c) ⇒ (d): Enthielte T einen Kreis C, so wäre T−e für eine Kante e von C
zusammenhängend, da wir jede Tour in T , die die Kante e „enthält“ durch
eine Tour die stattdessen den Weg C−e [definiert wie T−e ] „enthält“ ersetzen
können. Enthielte T+vw keinen Kreis, so wäre T+vw ein Baum und somit nach
dem schon Gezeigten minimal-zusammenhängend, und somit T nicht zusam-
menhängend.
(d) ⇒ (a): Wir müssen zeigen, dass T zusammenhängend ist. Seien v und w
zwei Ecken von T . Sind v und w nicht benachbart, so gibt es einen Kreis C in
T+vw . Da T keine Kreise enthält, ist vw eine Kante von C und C−vw ist ein
Weg von v nach w in T . 2

7.2 Korollar. Jeder zusammenhängende Graph hat einen aufspannenden

Baum.

Beweis. Ein maximaler azyklischer aufspannender Teilgraph des gegebenen

Graphen ist nach 7.1 ein Baum. Die Existenz eines solchen Teilgraphen ist im
endlichen Fall klar und folgt im unendlichen Fall mit dem Zornschen Lemma. 2

7.3 Korollar. Ein zusammenhängender endlicher nichtleerer Graph (V, E) ist

genau dann ein Baum, wenn |V | = |E| + 1 gilt.

Beweis. Ist (V, E) ein Baum, so zeigt man leicht per Induktion durch sukzes-
sives Entfernen von Blättern, dass |V | = |E| + 1 gilt. Für die andere Impli-
kation sei T ein aufspannender Baum von (V, E). Nach dem schon gezeigten
gilt |V (T )| = |E(T )| + 1, und wegen V (T ) = V folgt |E(T )| = |V (T )| − 1 =
|V | − 1 = |E| und somit (V, E) = T . 2

Nach 7.2 und 7.3 gilt für alle zusammenhängenden Graphen |V | ≤ |E| + 1.
Bäume sind also die extremalen zusammenhängenden Graphen.
Für einen endlichen Graphen G bezeichne T (G) die Anzahl der aufspannenden
Bäume von G.
7.4 Satz (Cayley 1889). Für jede n-Menge V 6= ∅ existieren genau nn−2
Bäume (V, E), d.h. T (Kn ) = nn−2 für n ∈ N.

Beweisskizze mit Prüfercode. Wir können V = {1, . . . , n} und n ≥ 2 an-

nehmen. Wir ordnen nun jedem Baum G0 = (V, E) eine Folge (v1 , v2 , . . . , vn−2 )
in V der Länge n − 2 zu. Dazu wählen wir das kleinste Blatt w1 von G0
(im Sinne der Ordnung auf V ⊆ N) und als v1 seinen eindeutigen Nach-
barn. Nun entfernen wir w1 und definieren G1 := G0 [V \ {w1 }] und fahren
so fort: Ist i < n − 2 und sind v1 , . . . , vi und G1 , . . . , Gi schon definiert, so

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 24.06.2014 41

wählen wir das kleinste Blatt wi+1 von Gi , für vi+1 den Nachbarn und setzen
Gi+1 := Gi [V (Gi )\{wi+1 }]. So ist rekursiv der Prüfercode c = (v1 , . . . , vn−2 )
von G definiert. Es lässt sich zeigen, dass c den Baum G eindeutig bestimmt
und dass jede Folge in V der Länge n − 2 so vorkommt. Also gibt es genauso
viele solche Folgen wie Bäume auf V . Für einen Beweis mit „Wirbeltieren“
(also Bäumen mit zwei ausgezeichneten Ecken) siehe Übungsaufgabe 11.2. 2

7.5 Beispiel. 6 4 hat Prüfercode (6, 4, 4, 1).

2 3 5

8 Planare Graphen
8.1 Die reelle Ebene. Eine Kurve von f (0) nach f (1) ist das Bild
f ([0, 1]) ⊆ R2 einer stetigen injektiven Abbildung f : [0, 1] → R2 (bezüg-
lich der üblichen Metrik auf R2 ), und man nennt f ([0, 1]) eine Jordankurve
wenn f : [0, 1] → R2 stetig ist, f (0) = f (1) gilt und f |[0,1[ injektiv ist. Die
Zusammenhangskomponenten einer offenen Teilmenge U ⊆ R2 sind die
Äquivalenzklassen bezüglich Verbindbarkeit durch Kurven C ⊆ U .

8.2 Jordanscher Kurvensatz. Sei C ⊆ R2 eine Jordankurve. Dann hat

R2 \ C genau eine beschränkte und eine unbeschränkte Zusammenhangskom-
ponente (das Innere bzw. Äußere von C), und C ist der gemeinsame Rand
dieser beiden Zusammenhangskomponenten.
8.3 Definition. Ein Graph (V, E) heißt eben, falls V ⊆ R2 und zu jeder
Kante e = {v, w} ∈ E eine Kurve Ce von v nach w gegeben ist mit Ce ∩ Ce0 =
e ∩ e0 für alle e, e0 ∈ E mit e 6= e0 . Ein Graph heißt planar, falls er isomorph
zu einem ebenen Graphen ist.

Die planaren Graphen sind also die Graphen die sich in der Ebene über-
schneidungsfrei zeichnen lassen. Man kann zeigen, dass es möglich ist die
Ce als Strecken zu wählen [Satz von Fáry, Wagner 1936, Fáry 1948, sogar
V ⊆ {1, . . . , |V | − 1}2 ist möglich, Schnyder 1989].

8.4 Beispiele. (a) Jeder Teilgraph eines planaren Graphen ist planar.
(b) Q3 , K4 sind planar, K5 nicht (siehe 8.9), also auch Kn für n ≥ 5 nicht.

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 24.06.2014 42

(c) Alle Ecken-Kanten-Graphen von konvexen Polyedern sind planar [zuerst

auf umhüllende Sphäre projezieren, dann stereographische Projektion in
die Ebene].
(d) Der Petersen-Graph K(5, 2) ist nicht planar, siehe Übungsaufgabe 11.3

8.5 Flächen. Jeder ebene Kreis definiert eine Jordankurve und zerlegt da-
her die Ebene R2 in zwei Teile, das Innere und das Äußere des Kreises. Ist
G = (V, E) ein endlicher ebener Graph mit Kurven S Ce wie in 8.3, so nennen
wir die Zusammenhangskomponenten von R2 \ e∈E Ce die Flächen von G;
es gibt eine unbeschränkte (äußere) Fläche, die anderen (inneren) Flächen sind
beschränkt.

8.6 Satz (Formel von Euler für planare Graphen, 1752). Sei (V, E) ein
endlicher zusammenhängender ebener Graph mit f Flächen und V 6= ∅. Dann
gilt
|V | − |E| + f = 2.
Insbesondere ist f endlich und unabhängig von der Einbettung in R2 .

Beweis. Wir führen Induktion nach der Anzahl k der Kreise in G = (V, E).
Für k = 0 ist G ein Baum und daher f = 1 [Induktion über |E| durch „entlang
hangeln“ an Kante mit Blatt]; die Formel folgt mit 7.3. Sei nun k > 0 und
e ∈ E eine Kante in einem Kreis C von G. Der Teilgraph G0 = (V, E \ {e}) ist
zusammenhängend wegen e ∈ E(C), und per Induktion folgt

|V | − |E \ {e}| + f 0 = 2

für die Anzahl f 0 der Flächen von G0 . Da e nach dem Jordanschen Kurvensatz
im Rand der zwei Flächen liegt, die C begrenzen, zerlegt e genau eine Fläche
von G0 ; es folgt f = f 0 + 1. Damit folgt |V | − (|E| − 1) + f − 1 = 2. 2

8.7 Korollar. Für jeden endlichen ebenen Graphen (V, E) mit f Flächen z
Zusammenhangskomponenten gilt |V | − |E| + f = 1 + z.

[Komponenten können in einer Fläche einer anderen Komponente liegen.]

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 26.06.2014 43

Beweis. Jede Zusammenhangskomponente (Vi , Ei ) hat nach 8.6 genau 1 −

|Vi | + |Ei | innere Flächen, und somit hat (V, E) genau z − |V | + |E| innere
Flächen, also 1 + z − |V | + |E| Flächen. 2

8.8 Satz (Kantenabschätzung). Sei (V, E) ein endlicher zusammenhängen-

der planarer Graph, und sei g ≥ 3 die Eckenanzahl eines kleinsten Kreises in
(V, E). Dann gilt
g
|E| ≤ (|V | − 2) ≤ 3|V | − 6.
g−2

Beweis. Der Rand jeder Fläche enthält mindestens g Kanten, und jede Kante
liegt im Rand von höchstens zwei Flächen. Doppeltes Abzählen der Menge M
der angrenzenden Kanten-Flächen-Paare liefert f g ≤ |M | ≤ 2|E|. Mit der
Euler-Formel 8.6 folgt
2
2 = |V | − |E| + f ≤ |V | − |E| + |E|
g
und daher |E| ≤ (1 − g2 )−1 (|V | − 2) ≤ 3(|V | − 2). 2

8.9 Korollar. Die Graphen K5 und K3,3 sind nicht planar.

Beweis. Für K5 wäre |E| = 52 = 10 ≤ 3 · 5 − 6 = 9 und für K3,3 ist g = 4

(bipartit) und man hätte |E| = 9 ≤ 24 (6 − 2) = 8. 2

Eine Unterteilung eines Graphen ist ein Graph, der entsteht durch wieder-
holtes Ersetzen einer Kante {v, w} durch zwei Kanten {v, x} und {x, w}, wobei
x eine neue Ecke ist.

v w −→ v x w
Eine Unterteilung eines Graphen ist genau dann planar, wenn der Ausgangs-
graph planar ist.
8.10 Satz (Kuratowski 1930). Ein endlicher Graph ist genau dann planar,
wenn er keinen Teilgraphen enthält, der zu einer Unterteilung von K5 oder K3,3
isomorph ist. Insbesondere lässt sich die Planarität rein graphentheoretisch
entscheiden.

Beweis. Die eine Richtung ist 8.9, für die andere siehe Diestel, Satz 3.4.6. 2

IV Codierungstheorie
Bei der Übertragung oder Speicherung von digitalen Daten (über Funk, auf
CD, etc.) entstehen in der Regel Fehler. Um trotzdem eine fehlerfreie Übertra-

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 26.06.2014 44

gung über einen fehlerhaften Kanal zu gewährleisten, werden die Daten durch
Codierung mit redundanter Information angereichert, so dass sich nach der
Übertragung die Fehler wieder eliminieren lassen; siehe folgendes Schema und
Beispiel:

P Paul Baul P
Sender Codierer Kanal Decodierer Empfänger
T Tom Dom T

Im Folgenden soll diese Art von fehlerkorrigierenden Codes behandelt wer-

den. [Codes werden auch zur Komprimierung oder effizienten Darstellung von
Daten, etc. verwandt, nicht zu verwechseln mit Chiffren in der Kryptologie.]
9.1 Definition. Ein Alphabet ist eine endliche Menge A mit q := |A| ≥
2; die Wörter über A der Länge n ∈ N0 sind die Elemente von An . Ein
Blockcode oder einfach Code der Länge n ist eine nichtleere Teilmenge C ⊆
An , die Elemente von C sind die Codewörter. Eine Bijektion c : B k → C für
ein weiteres Alphabet B und k ∈ N heißt Codierung. Die Rate von C ist der
Quotient
log |C| 1
r := rC := = logq |C|.
log |A|n n

9.2 Bemerkungen. (a) Ist |A| = 2, etwa A = {0, 1}, so nennt man C einen
binären Code, für |A| = 3 ternären Code.
(b) Ist |C| = q k für k ∈ N0 , so gibt es eine Codierung c : Ak → C ⊆ An ; statt
k-Tupel werden n-Tupel übermittelt, und es folgt rC = k/n für die Rate.
(c) Der binäre Code
n
X
C := {(a1 , . . . , an ) ∈ {0, 1}n : ai ist gerade}
i=1

heißt Parity-check-Code. Mit ihm kann man erkennen, ob eine ungerade

Anzahl von Fehlern vorliegt, aber keine korrigieren.
(d) Für ein beliebiges Alphabet A heißt

C := {(a, a, . . . , a) ∈ An : a ∈ A}

der n-fache Wiederholungscode. Es gilt |C| = |A|, und die Rate ist
1/n. Der Code kann bis zu n − 1 Fehler erkennen und bis zu b n−1
2 c Fehler
korrigieren.
(e) Für einen beliebigen Code C ⊆ An ist {(c, c, . . . , c) ∈ C m : c ∈ C} der
m-fache Wiederholungscode von C.

9.3 Definition. Sei A eine Menge und n ∈ N. Man nennt

d(x, y) := |{i ∈ {1, . . . , n} : xi 6= yi }|

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 26.06.2014 45

den Hamming-Abstand von x, y ∈ An und Br (x) := {y ∈ An : d(x, y) ≤ r}

die Hamming-Kugel mit Radius r ∈ R.
Sei nun C ⊆ An ein Code und e ∈ N0 . Dann heißt

d(C) := min{d(c, c0 ) : c, c0 ∈ C, c 6= c0 } (mit d(C) := 0 für |C| = 1)

Minimalabstand von C, und C heißt e-fehlererkennend, falls Be (c) ∩ C =

{c} für alle c ∈ C gilt, und e-fehlerkorrigierend, falls Be (c) ∩ Be (c0 ) = ∅ für
alle c, c0 ∈ C mit c 6= c0 .

9.4 Bemerkung. (a) Die Abbildung d : An × An → N0 ist eine Metrik auf

An , denn die Dreiecksungleichung d(x, z) ≤ d(x, y) + d(y, z) gilt wegen

{i : xi 6= zi } ⊆ {i : xi 6= yi } ∪ {i : yi 6= zi }.

(b) Wegen B0 (c) = {c} ist jeder Code 0-fehlererkennend und 0-fehlerkorrigie-
rend.
(c) Sei C ⊆ An und e ∈ N. Ist x ∈ An aus einem Codewort c ∈ C durch
höchstens e Fehler entstanden, so gilt d(c, x) ≤ e, also x ∈ Be (c).
Ist C ein e-fehlererkennender Code, so folgt Be (c) ∩ C = {c}, und daher
x 6∈ C oder x = c, also können wir feststellen, ob x Fehler hat.
Ist C ein e-fehlerkorrigierender Code, so folgt Be (c)∩Be (c0 ) = ∅ für alle an-
deren Codeworte c0 ∈ C, also x 6∈ Be (c0 ) für c0 ∈ C \ {c}. Somit ist c durch
x eindeutig bestimmt, und wir können also die Fehler in x korrigieren. [In
der Praxis gibt es allerdings nur für spezielle Codes gute Algorithmen zur
Fehlerkorrektur.]

9.5 Satz. Sei C ⊆ An ein Code mit Minimalabstand δ := d(C) und e ∈ N0 .

(a) Es ist C genau dann e-fehlererkennend, wenn δ > e; d.h. C kann höchstens
δ − 1 Fehler erkennen.
(b) Es ist C genau dann e-fehlerkorrigierend, wenn δ > 2e; d.h. C kann höchs-
tens b δ−1
2 c Fehler korrigieren.

Beweis. (a) Es ist Be (c)∩C = {c} für alle c ∈ C genau dann, wenn d(x, c) > e
für alle x, c ∈ C mit x 6= c gilt.
(b) Falls x ∈ Be (c) ∩ Be (c0 ) für c 6= c0 aus C, liefert die Dreiecksungleichung
δ ≤ d(c, c0 ) ≤ d(c, x) + d(x, c0 ) ≤ e + e = 2e. Es folgt δ ≤ 2e.
Falls δ ≤ 2e, existieren c 6= c0 in C mit d(c, c0 ) = δ ≤ 2e und weiter x ∈ An
mit d(c, x), d(c0 , x) ≤ e. Es folgt x ∈ Be (c) ∩ Be (c0 ). 2

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 01.07.2014 46

9.6 Ein Hamming-Code. Der binäre Code

C :={c ∈ F72 : c1 + c4 + c6 + c7 = c2 + c4 + c5 + c7 = c3 + c5 + c6 + c7 = 0}
   
 1 0 0 1 0 1 1 
= c ∈ F72 : 0 1 0 1 1 0 1 c = 0
0 0 1 0 1 1 1
 

über dem Alphabet F2 = {0, 1} ist ein 4-dimensionaler Unterraum des 7-di-
mensionalen Vektorraums F72 , da die Matrix zum definierenden linearen Glei-
chungssystem vollen Rang hat. Daher gilt |C| = 24 = 16 und die Rate ist 4/7.
Ferner gilt d(C) = 3 (siehe 9.13), d.h. C erkennt bis zu zwei Fehler und kann
einen korrigieren. [Zum Vergleich: Der 2-fache Wiederholungscode kann einen
Fehler erkennen und keinen korrigieren, erst der 3-fache Wiederholungscode
kann zwei Fehler erkennen und einen korrigieren; seine Rate ist nur 1/3.]

9.7 Satz (Singleton-Schranke). Für einen Code C ⊆ An über dem Alpha-

bet A gilt
|C| ≤ |A|n−d(C)+1 ,
und für |C| = |A|k ist dies äquivalent zu

d(C) ≤ n − k + 1.

Gilt in obiger Ungleichung die Gleichheit, so nennt man C einen MDS-Code

für maximum distance separable.

Beweis. Sei f : An → An−d(C)+1 , c 7→ (c1 , c2 , . . . , cn−d(C)+1 ) die Projektion

auf die ersten n − d(C) + 1 Koordinaten. Dann ist f |C injektiv nach Definition
von d(C), und es folgt |C| ≤ |An−d(C)+1 | = |A|n−d(C)+1 . 2

Für |A| = q kann man die Singleton-Schranke auch schreiben als logq |C| +
d(C) ≤ n + 1, oder als rC + n1 d(C) ≤ 1 + n1 . Bei festem n beschränken sich
also die Rate rC und der Minimalabstand gegenseitig.
9.8 Lemma. Seien r, q, n ∈ N und A ein Alphabet mit q = |A|. Für alle
x ∈ An gilt dann für die Hamming-Kugeln [unabhängig von x]
r  
X n
|Br (x)| = (q − 1)j .
j=0
j

r r  
X X n
Beweis. |Br (x)| = n
|{y ∈ A : d(x, y) = j}| = (q − 1)j . 2
j=0 j=0
j

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 01.07.2014 47

9.9 Satz (Hamming-Schranke, Kugelpackungs-Schranke). Sei A ein Al-

phabet und q := |A|. Ist C ⊆ An ein e-fehlerkorrigierender Code, so gilt
e  
X n
q n ≥ |C| (q − 1)j .
j=0
j

Gilt in obiger Ungleichung die Gleichheit, so nennt man C perfekt oder ge-
nauer perfekt e-fehlerkorrigierend.

Beweis. Nach Definition 9.3 sind die Hamming-Kugeln Be (c) mit c ∈ C paar-
9.8 Pe
weise disjunkt und daher |An | ≥ c∈C |Be (c)| = |C| j=0 nj (q − 1)j . 2
P

Der Hamming-Code aus 9.6 ist perfekt 1-fehlerkorrigierend wegen 27 = 24 ·

(1 + 7).
9.10 Satz (Gilbert–Varshamov-Schranke, Überdeckungs-Schranke).

Sei n, δ, q ∈ N mit δ ≤ n und A ein Alphabet mit q = |A|. Dann existiert

ein Code C ⊆ An mit d(C) ≥ δ und
δ−1  
n
X n
q ≤ |C| (q − 1)j .
j=0
j

Beweis. Für C = {(x, x, . . . , x), (y, y, . . . , y)} ⊆ An mit x 6= y in A gilt d(C) =

n ≥ δ. Daher können wir C ⊆ An wählen mit d(C) ≥ δ und |C| maximal.
Für jedes x ∈ An existiert ein c ∈ C mit d(x, c) < δ, denn sonst gibt es ein x,
so dass d(x, c) ≥ δ für alle c ∈ C gilt, also auch x 6∈ C, und man könnte x zu C
hinzufügen im Widerspruch zur maximalen Wahl von C. Wir haben also An ⊆
9.8 Pδ−1 n

n j
2
S P
c∈C Bδ−1 (c) und daher q ≤ c∈C |Bδ−1 (c)| = |C| j=0 j (q − 1) .

9.11 Lineare Codes. Wir wählen nun als Alphabet den endlichen Körper
Fq für eine Primzahlpotenz q (siehe Satz 4.7(a)), und betrachten den Vektor-
raum Fnq über Fq für n ∈ N. Ein linearer Code C ist ein Unterraum von
Fnq .
Die Hamming-Metrik d auf Fnq ist translationsinvariant, d.h. es gilt d(x, y) =
d(x + t, y + t) für x, y, t ∈ Fnq ; daher gilt für den Minimalabstand (falls |C| > 1)
δ = d(C) = min{d(c, c0 ) : c, c0 ∈ C, c 6= c0 }
= min{d(c − c0 , 0) : c, c0 ∈ C, c 6= c0 }
= min{d(c, 0) : 0 6= c ∈ C}.
Für die Dimension k := dim C gilt 0 ≤ k ≤ n. Wir nennen C dann einen
[n, k]-Code, oder genauer einen [n, k, δ]-Code, oder noch genauer einen
[n, k, δ]q -Code (diese Notation soll immer implizieren, dass C linear ist).

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 03.07.2014 48

9.12 Generator- und Kontrollmatrix. Unterräume von Vektorräumen,

also auch Codes, lassen sich durch Kerne und Bilder von linearen Abbildungen
beschreiben. Die Codeworte eines (linearen) Codes werden generell als Zeilen-
vektoren aufgefasst. Eine Matrix G ∈ Fk×n q wird als Generatormatrix von
C bezeichnet, wenn ihre Zeilen C erzeugen [praktisch für Codierung]. Es gilt
dann C = {(a1 , a2 , . . . , ak )G : a1 , . . . , ak ∈ Fq }. Hat G den Rang k, so gilt
dim C = k und C ist ein [n, k]-Code. Eine Matrix H ∈ Fm×n q heißt Kontroll-
matrix von C, falls C = {c ∈ Fnq : Hct = 0} [praktisch für Decodierung]. Hat
H den Rang m, so gilt n = m + dim C, also dim C = n − m, und C ist ein
[n, n − m]-Code.
Für den Minimalabstand (falls |C| > 1) gilt

δ = d(C) = min{d(c, 0) : 0 6= c ∈ C}
= min{d(c, 0) : Hct = 0, c ∈ Fnq \ {0}}
= min{s ∈ N : es gibt s linear abhängige Spalten von H}
= 1 + max{t ∈ N : je t Spalten von H sind linear unabhängig}.

9.13 Hamming-Codes. Sei q eine Primzahlpotenz und m ∈ N mit 2 ≤ m.

Wähle aus jedem eindimensionalen Unterraum von Fm q einen Vektor ungleich
m
−1
0; man erhält so n := qq−1 Vektoren. Sei nun H die m × n-Matrix mit diesen
n Vektoren als Spalten. Der Code C = {c ∈ Fnq : Hct = 0} mit Kontrollmatrix
H heißt Hamming-Code.
Die Matrix H hat den Rang m, also gilt dim C = n − m, und C hat die
Rate n−mn . Je zwei Spalten von H sind linear unabhängig, und es gibt drei
linear abhängige Spalten. Also gilt d(C) = 3 nach 9.12, und somit ist C ein
m
−1
[n, n − m, 3]-Code mit n = qq−1 .
Wegen
|Fnq | = q n = q n−m (1 + n(q − 1)) = |C|(1 + n(q − 1))
ist C nach Satz 9.9 ein perfekter 1-fehlerkorrigierender Code. Im Fall von
binären Hamming-Codes stehen in den Spalten von H alle Vektoren ungleich
0, also gilt n = 2m − 1. In Abschnitt 9.6 hatten wir die Kontrollmatrix
 
1 0 0 1 0 1 1
H = 0 1 0 1 1 0 1
0 0 1 0 1 1 1

benutzt.

9.14 Reed–Solomon-Codes. Sei q eine Primzahlpotenz und δ, n ∈ N mit

2 ≤ δ ≤ n ≤ q. Sei a = (a1 , a2 , . . . , an ) ∈ Fnq mit paarweise verschiedenen ai ,

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 03.07.2014 49

und sei v = (v1 , v2 , . . . , vn ) ∈ (Fq \ {0})n . Die Kontrollmatrix

 
v1 v2 ... vn
 a1 v1 a2 v2 . . . a n vn 
 2 2
. . . a2n vn 

 a1 v1 a v
H :=  2 2  ∈ F(δ−1)×n
q
 .. .. .. .. 
 . . . . 
aδ−2
1 v1 aδ−2
2 v2 . . . aδ−2
n vn

definiert den verallgemeinerten Reed–Solomon-Code

GRSδ (a, v) := {c ∈ Fnq : Hct = 0}.
Die quadratische Untermatrix U der ersten δ − 1 Spalten ist das Produkt einer
Vandermonde-Matrix und einer Diagonalmatrix, und deren Determinante lässt
sich daher wie folgt berechnen:
Y
det U = v1 v2 . . . vδ−1 (ak − al ) 6= 0.
1≤k<l<δ

Entsprechend ist jede (δ − 1) × (δ − 1)-Untermatrix regulär. Daher sind je

δ − 1 Spalten linear unabhängig, und nach 9.12 ist GRSδ (a, v) ein [n, n − δ +
1, δ]-Code. In der Singleton-Schranke gilt also Gleichheit, und GRSδ (a, v) ist
ein MDS-Code.
Nach Satz 4.7(c) ist die multiplikative Gruppe F∗q = Fq \ {0} von Fq zyklisch,
d.h. es existiert ein α ∈ F∗q mit F∗q = {α, α2 , α3 , . . . , αq−1 }. Wir können also
a = v = (1, α, α2 , . . . , αq−2 ) für n = q − 1 setzen und erhalten den Reed–
Solomon-Code RSδ (q) := GRSδ (a, v). Es ist ein [q − 1, q − δ, δ]-Code und
seine Kontrollmatrix H ergibt sich zu Hij = vj ai−1 j = αi(j−1) . Daher gilt
q−1
X
RSδ (q) = {c ∈ Fq−1
q : αi(j−1) cj = 0 für i = 1, 2, . . . , δ − 1}. (∗)
j=1

Man kann zeigen, dass man als Generatormatrix von RSδ (q) wieder eine Vandermonde-
Matrix wählen kann; siehe Willems 3.1.3. Dies liefert die Darstellung
RSδ (q) = {(f (u1 ), f (u2 ), . . . , f (uq−1 )) : f ∈ Fq [x], grad f < q − δ},
wobei u1 , . . . , uq−1 eine geeignete Auflistung der Elemente von F∗q ist. Die Zu-
ordnung von f auf das Codewort liefert eine Codierung. Ferner lässt sich auch
an dieser Darstellung direkt die Minimaldistanz ablesen, denn ein Polynom
vom Grad höchstens q − δ − 1 ist durch q − δ Werte eindeutig bestimmt.
Schließlich sei noch bemerkt, dass C = RSδ (q) ein sogenannter zyklischer
Code ist, d.h. (c1 , . . . , cn ) ∈ C impliziert (cn , c1 , c2 , . . . , cn−1 ) ∈ C, wie man
leicht mit (∗) nachrechnet. Diese Eigenschaft führt dazu, dass C einem Ide-
al im Hauptidealring K[x]xn −1 entspricht (siehe 4.6), und sich daher durch
ein einziges Polynom, das sogenannte Generatorpolynom beschreiben lässt.
Dies ist Grundlage für effiziente Decodieralgorithmen, etwa den Peterson–
Gorenstein–Zierler-Algorithmus; siehe Willems, Kapitel 9.

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 08.07.2014 50

9.15 Anwendungen von Reed–Solomon-Codes. Reed–Solomon-Codes

wurden schon zu Beginn der 1980-er Jahre in der Voyager 2-Mission zum Ura-
nus benutzt [nach Umprogrammierung von Golay- zu RS-Codes Erhöhung der
Datenrate um 70%]. Reed–Solomon-Codes werden auch bei Audio-CDs, DVDs
und im Mobilfunk benutzt, auch QR-Codes wie etwa

basieren auf diesen Codes. Der zugrunde liegende endliche Körper ist immer
F28 mit 28 = 256 Elementen [für die QR-Codes wird z.B. F2 [x]x8 +x4 +x3 +x2 +1
benutzt]. Für die QR-Codes wird ein Sammelsurium verschiedener GRS-Codes
benutzt, um unterschiedliche QR-Code-Größen und korrigierbare Fehleranzah-
len zu realisieren, z.B. [153, 123, 31]-und [26, 9, 18]-Codes mir Korrekturraten
von 7% bzw. 30% [beim Vorliegen von höchstens so vielen Fehlern können diese
korrigiert werden].
Interessanter ist die Fehlerkorrektur bei der CD. Hier geht man von RS5 (28 ),
also einem [255, 251, 5]28 -Code aus. Diese werden verkürzt durch Streichen von
Spalten der Kontrollmatrix (und entsprechender Einträge der Codeworte) zu
einem [32, 28, 5]-Code und einem [28, 24, 5]-Code. Etwas vereinfacht dargestellt
werden nun die Daten in eine 28 × 24-Matrix über F28 geschrieben, dann die
Zeilen mit dem zweiten Code codiert und ersetzt, so dass man eine 28×28-Ma-
trix erhält, und dann die Spalten dieser Matrix mit dem ersten Code codiert.
Das Ergebnis wird noch weiter codiert, um eine möglichst gleichmäßige Ver-
teilung von 0-en und 1-en zu erreichen und auf die CD geschrieben. Durch die
zeilen- und spaltenweise Codierung wird erreicht, dass die Information rela-
tiv großflächig auf der CD verteilt wird. So ist es möglich 9408 aufeinander
folgende Kanalbits (entspricht 4096 Datenbits), was einer Spurlänge auf der
CD von 9408 × 0,3µm = 2,8mm entspricht zu korrigieren. Durch weitere tech-
nische Tricks und Interpolation lassen sich sogar Auslöschungen von bis zu
7,5mm rekonstruieren. Für weitere Details und Literatur siehe Willems, Ab-
schnitt 1.2.14.

V Kryptographie
Die Kryptologie ist die Wissenschaft vom Verschlüsseln (Chiffrieren) und au-
torisiertem Entschlüsseln (Dechiffrieren) von Nachrichten mit dem Zweck der
Geheimhaltung des Inhaltes (häufig als Kryptographie bezeichnet), sowie
von der Sicherheit von Verschlüsselungsverfahren (Chiffren) und von Metho-
den verschlüsselte Nachrichten unautorisiert zu entschlüsseln (Kryptoanaly-

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 08.07.2014 51

se). Der Versuch geheime Nachrichten zu übermitteln sowie der Versuch diese
unautorisiert zu lesen ist wohl so alt wie die menschliche Zivilisation. Jedoch ist
sie erst seit Ende der 1940er Jahre durch eine grundlegende Arbeit von Claude
Shannon zu einer mathematischen Disziplin geworden. Für das Ver- und Ent-
schlüsseln werden häufig Methoden aus der Zahlentheorie und Algebra und in
jüngster Zeit auch der Geometrie verwendet. Die Kryptoanalyse bedient sich
der Wahrscheinlichkeitstheorie und Statistik, um statistische Schwankungen
in Nachrichten für das unautorisierte Entschlüsseln zu nutzen. Ferner ist die
Komplexitätstheorie von Bedeutung, denn häufig ist es sehr wohl möglich ein
kryptographisches Verfahren prinzipiell zu brechen, aber der Aufwand wäre so
hoch, dass er mit aktueller Technik nicht zu bewältigen ist.
10.1 Definition. Ein Kryptosystem C = (P, C, K, E, D) besteht aus Men-
gen P , C, K, den Klartexten, Geheimtexten bzw. den Schlüsseln, und
Abbildungen E : P × K → C und D : C × K → P , der Verschlüsse-
lungsabbildung bzw. der Entschlüsselungsabbildung, so dass zu jedem
Verschlüsselungsschlüssel e ∈ K ein Entschlüsselungsschlüssel d ∈ K
existiert mit
D(E(p, e), d) = p für alle p ∈ P .

Die Verschlüsselungsabbildung Ee = E( · , e) : P → C ist dann eine injektive

Abbildung und Dd = D( · , d) eingeschränkt aufs Bild Ee (P ) ihre Umkehrung.
Wenn es einfach ist d aus e zu bestimmen, muss der Verschlüsselungsschlüs-
sel e geheim gehalten werden, und man nennt C ein private-key Krypto-
system oder symmetrisch und andernfalls ein public-key Kryptosystem
oder asymmetrisch.

10.2 Das AES-Verfahren. Im Jahre 2000 ging der Algorithmus Rijndael

(gesprochen Rehndahl) der belgischen Kryptologen Joan Daemen und Vincent
Rijmen als Gewinner aus einem von NIST [National Institute of Standards and
Technology, Nachfolge von NBS] ausgeschriebenen Wettbewerb hervor. Unter
den 25 Bewerbern waren auch Mars (IBM), RC6 (RSA), Serpent (Adi Shamir
et al.) und Twofish (Bruce Schneier), welche als genauso sicher wie Rijndael
gelten, aber sich nicht so effizient implementieren lassen. Ein Spezialfall von
Rijndael mit einer Klartextlänge von 128 Bit wurde dann als Standard AES
(advanced encryption standard) verabschiedet.
AES ist ein symmetrisches Kryptosystem mit gleichem Klar- und Geheimtext-
raum
P := F128
2 = F284×4 ,
[den man sich am besten als Menge der (4 × 4)-Matrizen über F28 (entspricht
Bytes) vorstellt, siehe ShiftRow für genaue Zuordnung] und wählbarem Schlüs-
32N 4×N
selraum K := F2 key = F28 key für Nkey ∈ {4, 6, 8} und zugehöriger Run-
denzahl r := Nkey + 6 ∈ {10, 12, 14}. Das Kryptosystem ist durch interne

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 08.07.2014 52

Abbildungen folgendermaßen gegeben:

Eki : P → P, p 7→ ki + MixColumn ◦ ShiftRow ◦ SubBytes(p),

AESk : P → P, p 7→ E
gkr ◦ Ekr−1 ◦ Ekr−2 ◦ · · · ◦ Ek1 (k0 + p),

wobei in E
g kr die Abbildung MixColumn weggelassen ist und die internen Run-
denschlüssel k0 , . . . , kr ∈ P durch die Rundenschlüsselabbildung aus k ∈ K
generiert werden, siehe unten. Die Bijektionen

MixColumn, ShiftRow, SubBytes : P → P

werden wie folgt definiert. Am einfachsten ist die Abbildung

   
b1 b5 b9 b13 b1 b5 b9 b13
b2 b6 b10 b14   b6 b10 b14 b2 
ShiftRow : P → P,  b3 b7 b11 b15  7→ b11 b15
  ,
b3 b7 
b4 b8 b12 b16 b16 b4 b8 b12

sie verschiebt die i-te Zeile der Klartextmatrix um i − 1 Positionen zyklisch

nach links.
Für die Abbildung MixColumn benutzen wir die Darstellung F28 = F2 [x]g mit
dem irreduziblen Polynom g = x8 + x4 + x3 + x + 1 ∈ F2 [x] (siehe 4.6) und
definieren
 
x x+1 1 1
 1 x x+1 1 
MixColumn : P → P, A 7→   A.
 1 1 x x + 1
x+1 1 1 x

Wesentlich für AES ist die Bijektion

SubBytes : P → P, (aij ) 7→ (S(aij ));

dabei besteht S : F28 → F28 im Kern aus dem multiplikativen Invertieren von
F28 : Wir benutzen wieder die Darstellung F28 = F2 [x]g , identifizieren zusätzlich
P7
die Körperelemente i=0 si xi ∈ F2 [x]g mit der Bitfolge (s7 , s6 , . . . , s0 ) ∈ F82
und definieren (setze 0−1 := 0)
   
1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 0 0 1
   
0 0 1 1 1 1 1 0 1
   
0 0 0 1 1 1 1 1 −1 0
S : F28 → F28 , b 7→ 

 b + 0 .
  
1 0 0 0 1 1 1 1  
1 1 0 0 0 1 1 1 0
   
1 1 1 0 0 0 1 1 1
1 1 1 1 0 0 0 1 1

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 08.07.2014 53

[Der affine Bestandteil von S ist die Abbildung b−1 7→ (x4 + x3 + x2 + x +

1)b−1 + x6 + x5 + x + 1 in Z2 [x]x8 +1 .]
Wir müssen noch die Rundenschlüssel k0 , . . . , kr ∈ P angeben. Sei Nkey ∈
4×N
{4, 6, 8} gegeben. Dann ist K = F28 key und r = Nkey + 6. Wir werden eine
4 × Nkey -Schlüsselmatrix über F28 zu einer 4 × 4(r + 1)-Matrix erweitern.
Die Rundenschlüssel sind dann einfach aufeinander folgende 4 × 4-Blöcke in
dieser Matrix. Für k ∈ K seien w0 , . . . , wNkey −1 ∈ (F28 )4 die Spalten der
Schlüsselmatrix. Für i ∈ N mit i ≥ Nkey und eine Spalte s ∈ (F28 )4 definieren
wir

i/Nkey −1
S̃(R(s)) + (x
 , 0, 0, 0)t falls Nkey | i
0
s := S̃(s) falls Nkey = 8 und i ≡ 4 mod Nkey

s sonst;


und dann rekursiv

0
wi := wi−Nkey + wi−1 ,
dabei ist S̃ : (F28 )4 → (F28 )4 , (b1 , . . . , b4 ) 7→ (S(b1 ), . . . , S(b4 )) für die Abbil-
dung S aus der Definition von SubBytes, x ∈ F28 = F2 [x]g und die Abbildung
R : (F28 )4 → (F28 )4 , (b1 , b2 , b3 , b4 )t 7→ (b2 , b3 , b4 , b1 )t verschiebt die Kompo-
nenten zyklisch nach links (eigentlich nach oben).
Schließlich setzen wir ki := (w4i , w4i+1 , w4i+2 , w4i+3 ) für i = 0, . . . , r.
Bis auf S in SubBytes sind alle Abbildung, die in der Definition von AESk
benutzt werden linear bzw. affine über F2 . Sie sorgen für die sogenannte Dif-
fusion, d.h. das Ändern eines Bits im Klartext bewirkt das Ändern von vielen
Bits im Geheimtext. Konfusion besagt, dass der Geheimtext zufällig erscheint
und keine statistischen Abhängigkeiten zwischen Klar- und Geheimtext beste-
hen; dies wird durch die nichtlineare Abbildung S bewirkt.
Eine sehr gut lesbare Beschreibung von AES stellt FIPS-197 (Federal Informa-
tion Processing Standards) vom 26.11.2001 dar oder Joan Daemen, Vincent
Rijmen, The design of Rijndael. In dem Artikel zur Einreichung von Rijndael
für AES und dem Buch finden sich auch Gründe und Literaturangaben für das
spezielle Design.

10.3 Das diskrete Logarithmus-Problem. Für asymmetrische Krypto-

systeme benötigt man sogenannte Falltürfunktionen, also Bijektionen, die
sich gut berechnen lassen, aber deren Umkehrabbildung sich nur sehr schwer
berechnen lässt.
Sei G eine endliche zyklische Gruppe mit Erzeuger g ∈ G, also G = {1, g, g 2 , . . . ,
g n−1 } für n = |G|. Somit gibt es für jedes a ∈ G ein x = 0, 1, . . . , n − 1 mit
g x = a. Die Zahl x heißt diskreter Logarithmus von a zur Basis g, und die
Bestimmung dieses Logarithmus ist das diskrete Logarithmus-Problem.
Je zwei zyklische Gruppen mit der gleichen Elementanzahl n sind isomorph,
nämlich zu (Zn , +), siehe 4.6. Ob das diskrete Logarithmus-Problem schwer

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 09.07.2014 54

zu lösen ist, hängt nicht so sehr von der Gruppe, also der Zahl n ab, sondern
davon, wie die Gruppe G gegeben ist. Nach 4.7(c) ist die multiplikative Grup-
pe F∗p = Z∗p für eine Primzahl p zyklisch [sie hat ϕ(p − 1) Erzeuger]; für das
diskrete Logarithmus-Problem von F∗p ist kein allgemeiner polynomialer Algo-
rithmus bekannt. Ist allerdings die „gleiche“ Gruppe als (Zp−1 , +) gegeben,
so ist das Logarithmus-Problem für die Basis g = 1 trivial, denn der diskrete
Logarithmus von a ∈ Zp−1 ist a. Ist g ein beliebiger Erzeuger von (Zp−1 , +),
so ist g teilerfremd zu p − 1, und der erweiterte euklidische Algorithmus liefert
in polynomialer Zeit x, y ∈ Z mit gx + (p − 1)y = 1. Es folgt rp−1 (gx) = 1, und
damit rp−1 (gxa) = a, so dass rp−1 (xa) der diskrete Logarithmus von a ist.
1994 hat Shor einen Algorithmus für Quantencomputer angegeben, der den
diskreten Logarithmus polynomial berechnet. [Der Algorithmus findet in O(n3 )
Rechenschritten den diskreten Logarithmus mit Wahrscheinlichkeit 3/4.]

10.4 Der Diffie–Hellman-Schlüsselaustausch. A und B wollen sich auf

einen Schlüssel einigen, haben aber keinen abhörsicheren Kanal zur Verfügung.
Sie einigen sich zunächst öffentlich auf eine zyklische Gruppe G und einen Er-
zeuger g (siehe oben), so dass einerseits die Gruppenoperation effizient bere-
chenbar ist und andererseits das diskrete Logarithmus-Problem (eigentlich das
sogenannte Diffie–Hellman-Problem) schwer ist, z.B. auf eine Primzahl p und
einen Erzeuger g von Z∗p . Nun wählt A zufällig eine Zahl a ∈ {0, 1, . . . , n − 1}
für n = |G|, schickt
A := g a
an B und hält a geheim. B wählt zufällig eine Zahl b ∈ {0, 1, . . . , n − 1}, schickt

B := g b

an A und hält b geheim. Nun können A und B beide den gemeinsamen Schlüssel

k := g ab = Ab = B a

berechnen. Ein Angreifer erfährt die Gruppe G, den Erzeuger g und die Grup-
penelemente A und B. Er muss den geheimen Schlüssel k = g ab bestimmen; das
nennt man das Diffie–Hellman-Problem. Die einzig bekannte Methode das
Diffie–Hellman-Problem zu lösen, ist die Bestimmung der diskreten Logarith-
men von A oder B, aber es ist nicht bewiesen, dass es keine andere allgemeine
Methode gibt.
Diesen gemeinsamen Schlüssel kann man für ein symmetrisches Verfahren, wie
z.B. AES benutzen.

10.5 Das ElGamal-Verfahren. Aus der Idee von Diffie und Hellman lässt
sich auch ein Kryptosystem machen. A will an B eine geheime Nachricht
verschicken. Dazu wählt B eine zyklische Gruppe G und einen Erzeuger g,
so dass das Diffie–Hellman-Problem schwer ist, und wählt zufällig eine Zahl
b ∈ {0, 1, . . . , n − 1} mit n = |G|. Dann berechnet B die Potenz B := g b

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 09.07.2014 55

und schickt an A den öffentlichen Schlüssel (G, g, B). Nun wählt sich A eine
Zufallszahl a ∈ {0, 1, . . . , n − 1} und berechnet aus dem Klartext m ∈ G die
Gruppenelemente A := g a sowie c := B a m, d.h. A multipliziert den Diffie–
Hellman-Schlüssel k wie oben mit dem Klartext. Der Geheimtext ist (A, c).
Zur Entschlüsselung berechnet B den Klartext durch An−b c, denn es gilt

An−b c = An−b B a m = g a(n−b) g ba m = g an m = m.

Das ElGamal-Verfahren ist schon ein randomisiertes Verfahren, allerdings führt

dies zu einer Expansion, d.h. der Geheimtext ist länger als der Klartext.
Als zyklische Gruppe im ElGamal-Verfahren lässt sich gut die multiplikative
Gruppe eines Körper Z∗p von Primzahlordnung benutzen. Auch Gruppen auf
elliptischen Kurven über endlichen Körpern sind gut geeignet.

10.6 Elliptische Kurven. Elliptische Kurven sind Lösungsmengen gewis-

ser kubischer nicht-singulärer (keine Spitzen oder Überschneidungen) Glei-
chungen in 2 Variablen über einem beliebigen Körper.

Elliptische Kurven y 2 = x3 − x und y 2 = x3 − x + 1 über R.

Sie wurden 1985 von Koblitz und Miller für die Kryptologie vorgeschlagen.
Dies beruht darauf, dass sich auf ihnen eine Gruppenstruktur definieren lässt,
für die das diskrete Logarithmusproblem schwer ist.
Eine wichtige Eigenschaft elliptischer Kurven besagt, dass jede Gerade, die
zwei Punkte der Kurve enthält, auch noch einen dritten enthält; dabei muss
man allerdings Punkte, in denen die Kurve tangential zur Gerade ist, doppelt
oder sogar dreifach zählen und außerdem noch einen Punkt bei „Unendlich“
hinzufügen (siehe Bild). Wir werden hiermit eine Gruppenoperation definieren.
Sei E eine elliptische Kurve über einem Körper K und o ∈ E. Für Punkte
p, q ∈ E sei pq der dritte (mit Doppelzählungen wie oben) Punkt auf der

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 09.07.2014 56

Geraden durch p und q (für p = q sei hier die Tangente an E in p gewählt).

Nun definieren wir p + q := (pq)o.

10.7 Satz. Sei eine elliptische Kurve E gegeben. Dann ist (E, +) bezüglich
oben definierter Operation + eine abelsche Gruppe mit Neutralelement o.

Der folgende Satz besagt, dass es große elliptische Kurven gibt.

10.8 Satz (Der Satz von Hasse). Für eine p elliptische Kurve E über einem
endlichen Körper K gilt |E| − |K| − 1 ≤ 2 |K|.

Der folgende Satz besagt, dass es große zyklische Untergruppen gibt.

10.9 Satz. Für jede elliptische Kurve E über einem endlichen Körper K gibt
es n1 , n2 ∈ N mit n2 | n1 und (E, +) ∼
= Zn1 × Zn2 .

Tatsächlich ist das diskrete Logarithmus-Problem im Allgemeinen schwer zu

lösen, so dass sich elliptische Kurven für das ElGamal-Verfahren oder den
Diffie-Hellman-Schlüsselaustausch eignen.
In der Praxis geht man davon aus, dass eine elliptische Kurve zur Körper-
Ordnung etwa 2163 , die einen Primfaktor größer als 2160 hat, die gleiche Si-
cherheit bietet wie ein RSA-Verfahren mit Modul in der Größenordnung 21024 .
Dies bietet Effizienz-Vorteile, die es z.B. ermöglichen kryptographische Ver-
fahren mit elliptischen Kurven auf den wesentlich billigeren Smart-Cards ohne
Koprozessor zu implementieren.

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 09.07.2014 57

VI Übungsaufgaben
1.1 Aufgabe. Beweisen Sie die folgende Aussage: Für n, m ∈ N0 existiert
genau dann eine Bijektion f : {1, . . . , n} → {1, . . . , m}, wenn n = m gilt.

1.2 Aufgabe. Die folgende Figur ist aus zwei Quadraten und vier gleichseiten
Dreiecken mit gleicher Seitenlänge zusammengesetzt. Finden Sie eine Zerle-
gung in 7 kongruente Teile (das sind bis auf Verschiebungen, Drehungen oder
Spiegelungen gleiche Teile).

1.3 Aufgabe. Zwei Spieler spielen folgendes Spiel. Als Vorbereitung werden
sechs Punkte auf ein Blatt Papier gezeichnet, so dass keine drei auf einer Gera-
den liegen. Jeder Spieler hat eine Farbe, und die Spieler zeichnen abwechselnd
eine Strecke mit ihrer Farbe zwischen zwei noch nicht verbundene Punkte. Ver-
loren hat, wer zuerst ein Dreieck komplett in seiner Farbe fertig stellen muss.
Zeigen Sie, dass ein Unentschieden nicht möglich ist.

1.4 Aufgabe. Zeigen Sie, dass eine Menge M genau dann endlich ist, wenn
es eine Abbildung f : M → M gibt, so dass für jede Teilmenge X ⊆ M die
Inklusion f (X) ⊆ X nur für die offensichtlichen Fälle X = ∅ oder X = M gilt.

2.1 Aufgabe. Zeigen Sie, dass eine endliche nichtleere Menge genauso viele
Teilmengen gerader wie ungerader Länge hat.

2.2 Aufgabe. Endlich viele Personen begrüßen sich mit einem Handschlag.
Zeigen Sie, dass es zu jedem Zeitpunkt zwei Personen gibt, die der gleichen
Anzahl von Leuten die Hände geschüttelt haben.

2.3 Aufgabe. Sei n ∈ N, und seien a1 , a2 , . . . , an ∈ Z. ZeigenP

Sie, dass es eine
nichtleere Teilmenge I ⊆ {1, . . . , n} gibt, so dass die Summe i∈I ai durch n
teilbar ist.

2.4 Aufgabe. In der Ebene sei ein regelmäßiges n-Eck gegeben, n ≥ 3. Dabei
seien R viele Ecken rot und B viele Ecken blau, so dass R + B = n gilt. Eine
Kante sei rot, wenn sie zwischen zwei roten Punkten liegt und blau, wenn
sie zwischen zwei blauen Punkten liegt. Kanten, die zwischen zwei Punkten
verschiedener Farbe liegen, seien farblos. Sei r die Anzahl der roten und b die
Anzahl der blauen Kanten. Zeigen Sie, dass R − B = r − b gilt.

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 09.07.2014 58

3.1 Aufgabe. Das Letzte Lexikon zählt in alphabetischer (lexikographischer)

Reihenfolge alle Wörter auf, welche jeden der 26 Grossbuchstaben genau einmal
enthalten; es beginnt demnach mit dem Wort ABCDEFGHIJKLMNOPQRSTUVWXYZ
und es endet mit dem Wort ZYXWVUTSRQPONMLKJIHGFEDCBA.
(a) Wie lautet das letzte Wort der ersten Hälfte des Letzten Lexikons?
(b) Welches Wort folgt unmittelbar auf den Eintrag
JMZORTXLBPSYWVINGDUEQKHFCA?

3.2 Aufgabe. Erklären Sie wie folgender Trick mathematisch funktioniert:

Die Zauberin benutzt ein französisches Blatt mit 52 Karten (also mit 13 Kar-
tenwerten in jeweils 4 Farben) und fordert eine beliebige Person im Publikum
auf, aus dem Blatt 5 Karten zufällig zu entnehmen und sie verdeckt ihrem
Assistenten zu geben. Dieser wählt nach Inspektion eine Karte aus und gibt
sie verdeckt ins Publikum zurück. Die übrigen 4 Karten deckt er nacheinander
auf und die Zauberin nennt daraufhin Farbe und Kartenwert der Karte, die ins
Publikum zurück ging. Dabei tauschen die Zauberin und ihr Assistent keine
weiteren Informationen aus.
Tipp: Es ist hilfreich, an das Schubfachprinzip und Permutationen von drei
Elementen zu denken.

3.3 Aufgabe. Zeigen Sie, dass das Produkt von n aufeinander folgenden gan-
zen Zahlen durch n! teilbar ist.

3.4 Aufgabe. Bestimmen Sie für k, n ∈ N die Anzahl alle k-Teilmengen von
{1, . . . , n}, deren verschiedene Elemente mindestens den Abstand 3 haben.

4.1 Aufgabe. Zeigen Sie, dass eine natürliche
Zahl n ∈ N genau dann eine
Primzahl ist, wenn alle Binomialkoeffizienten nk mit 1 ≤ k ≤ n − 1 durch n
teilbar sind.

4.2 Aufgabe. Sei M eine endliche n-Menge. Finden Sie einen möglichst ein-
fachen Ausdruck (ohne Summenzeichen) für
(a) die Anzahl der Paare (A, B) ∈ 2M × 2M mit A ∩ B = ∅;
(b) die Anzahl der Teilmengen A von M mit |A| ≡ 0 mod 4.
Tipp: Setzen Sie in der binomischen Formel (x + 1)n = . . . für x geeignete
komplexe Zahlen ein.

4.3 Aufgabe. Für n ∈ N0 definieren wir die n-te Catalan-Zahl durch

     
1 2n 2n 2n
Cn := = − .
n+1 n n n+1
(a) Zeigen Sie, dass Cn die Anzahl der Zeichenketten der Länge 2n bestehend
aus den Zeichen „(“ und „)“ mit korrekter Klammerung ist; diese Zei-
chenketten haben also n öffnende und n schließende Klammern, und jedes

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 09.07.2014 59

Anfangsstück enthält höchstens so viele schließende wie öffnende Klam-

mern.
n
P
(b) Leiten Sie die Rekursionsgleichung Cn+1 = Ck Cn−k für n ∈ N0 her.
k=0

4.4 Aufgabe. Sieben Geometer und fünf Algebraiker sollen auf einer Kon-
ferenz in einer Reihe mit zwölf Plätzen sitzen. Wie viele Möglichkeiten gibt
es, die Sitzplätze so zu verteilen, dass kein Algebraiker neben einem anderen
Algebraiker sitzt? Wie viele Möglichkeiten der Sitzverteilung gibt es, so dass
kein Geometer neben einem anderen Geometer sitzt?
∞
1
P
5.1 Aufgabe. Sei e = k! die eulersche Zahl und für n ∈ N sei fn die
k=0
Anzahl der Folgen der Länge 0 bis n von verschiedenen Zahlen aus {1, 2, . . . , n}.
Zeigen Sie fn = be · n!c.

5.2 Aufgabe. Sei k ∈ N.

(a) Zeigen Sie, dass jedes n ∈ N0 eine eindeutige Darstellung der Form
       
xk xk−1 x2 x1
n= + + ··· + +
k k−1 2 1
mit xi ∈ N0 und xk > xk−1 > · · · > x2 > x1 für i = 1, . . . , k besitzt.


(b) Beweisen Sie nun, dass Nk0 eine abzählbare Menge ist.

5.3 Aufgabe. Eine Warenlieferung enthält 50 intakte und 10 defekte Stücke.

Wie groß ist die Wahrscheinlichkeit dafür, dass eine Stichprobe vom Umfang
10
(a) genau zwei defekte Stücke enthält?
(b) mindestens zwei defekte Stücke enthält?

5.4 Aufgabe. Angenommen Sie spielen Lotto »6 aus 49« und ein Bekannter
schlägt vor, dass er Ihnen zwei Euro gibt, falls keine der gezogenen sechs Zahlen
mit keiner der sechs getippten Zahlen übereinstimmt; andernfalls geben Sie ihm
einen Euro. Würden Sie diesen Deal eingehen?

6.1 Aufgabe. Bei einer Befragung von 100 Personen ergibt sich folgendes
Meinungsbild: Drei Politiker A, B und C werden von jeweils 65, 57 und 58 der
Befragten für wählbar gehalten. Weiter halten 28 der Befragten sowohl A als
auch B für wählbar, 30 halten A und C, und 27 halten B und C für wählbar.
Ferner sind alle drei Politiker für 12 der Befragten wählbar. Was halten Sie
von dieser Meinungsumfrage?

6.2 Aufgabe. Ein Stapel von n Spielkarten enthält drei Asse. Es wird ge-
mischt bis Gleichverteilung vorliegt. Die Karten werden nun eine nach der

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 09.07.2014 60

anderen aufgedeckt bis das zweite Ass erscheint. Bestimmen Sie den Erwar-
tungswert der Anzahl der dabei aufgedecken Karten.

6.3 Aufgabe. Beweisen Sie folgende Aussagen:

(a) Seien n, r ∈ N, und seien a1 , a2 , . . . , ar ∈ N paarweise teilerfremd. Dann
sind genau  
|I| Q n
X
(−1)
I⊆{1,2,...,r} i∈I ai

Zahlen in {1, 2, . . . , n} enthalten, die durch keine der Zahlen a1 , a2 , . . . , ar

teilbar sind.
(b) Für jede natürliche Zahl n definieren wir die eulersche ϕ-Funktion als die
Anzahl der zu n teilerfremden Zahlen aus {1, . . . , n}. Sind p1 , p2 , . . . , pr
die sämtlichen Primteiler von n, so gilt
r  
Y 1
ϕ(n) = n 1− .
i=1
pi

6.4 Aufgabe. Das Spiel »Dual« geht so: Zwei Mathematikerinnen X und Y
treten gegen einander an und müssen eine Aufgabe lösen. Es gibt drei Ausgän-
ge des Duells: X löst die Aufgabe zuerst, Y löst die Aufgabe zuerst oder beide
können die Aufgabe nicht lösen. Das Spiel Dual spielen 17 Mathematikerinnen
und jede tritt genau ein Mal gegen jede andere an. Kann es passieren (nach-
dem alle Spiele gespielt wurden), dass jede Spielerin genau so oft gewonnen
wie unentschieden gespielt hat? Ändert sich die Antwort, wenn es nur 16 Ma-
thematikerinnen sind? Tipp: Zählen Sie gewonnene und unentschiedene Spiele
aus der Sicht einer jeden Mathematikerin.

7.1 Aufgabe. Sei (V, E) ein endlicher Graph. Beweisen Sie folgende Aussa-
gen:
P
(a) Es gilt v∈V d(v) = 2|E|;
(b) Die Anzahl der Ecken mit ungeradem Grad ist gerade;
(c) Für |V | ≥ 2 kommen die Grade 0 und |V | − 1 beide nicht vor;
(d) Für |V | ≥ 2 existieren zwei Ecken mit gleichem Grad.

7.2 Aufgabe. Bestimmen Sie alle Graphen mit n ≥ 2 Ecken, deren Ecken
n − 1 verschiedene Grade haben.

7.3 Aufgabe. Finden Sie alle nicht-isomorphen Graphen mit genau 7 Ecken,
so dass jede Ecke Grad 4 hat. Tipp: Das Problem ist einfacher mit Grad 2
anstelle von 4.

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 09.07.2014 61

7.4 Aufgabe. Betrachten Sie den Graphen G mit Ecken V = {1, . . . , 10} und
Kanten

{i, i + 1} für 1 ≤ i ≤ 7; {i, i + 5} für 1 ≤ i ≤ 3; {1, 4}, {5, 8}, {4, 9}, {2, 10}.

(a) Bestimmen Sie |Aut(G)| und beschreiben Sie die Elemente von Aut(G).
(b) Wie ändert sich die Anzahl der Automorphismen in a), wenn Sie statt G
den Teilgraphen G0 betrachten, in dem die Ecke 10 und die Kante {2, 10}
entfernt wurden?
(c) Wie ändert sich die Antwort in b), wenn Sie im Graphen G0 zusätzlich die
Ecke 9 und die Kante {4, 9} entfernen?

Tipp: Finden Sie zuerst eine passende graphische Darstellung von G.

8.1 Aufgabe. (Über Konstruktion und Existenz von Graphen)

(a) Gibt es einen Graphen mit 17 Ecken und Gradfolge (1, 5, 5, . . . , 5)?
(b) Für welche n ∈ N gibt es einen Graphen mit Gradfolge (2, 3, . . . , 3, 4)?
| {z }
n Mal

8.2 Aufgabe. Ein Graph G mit |Aut G| = 1 heißt asymmetrisch.

(a) Finden Sie einen asymmetrischen Graphen mit mindestens zwei Ecken.
(b) Zeigen Sie, dass kein Graph G mit 2 ≤ |V (G)| ≤ 5 asymmetrisch ist.

8.3 Aufgabe. Sei G ein endlicher k-regulärer Graph mit n Ecken.

(a) Zeigen Sie, dass k oder n gerade sind.
(b) Zeigen Sie, dass das Komplement G von G ein (n − k − 1)-regulärer Graph
ist.
(c) Bestimmen Sie bis auf Isomorphie alle endlichen 2-regulären Graphen.
(d) Bestimmen Sie bis auf Isomorphie alle 3-regulären Graphen mit n ≤ 6.

∼ S5 .
8.4 Aufgabe. Zeigen Sie Aut K(5, 2) =

9.1 Aufgabe. Sei G = (V, E) ein endlicher Graph, dessen sämtliche Ecken
einen geraden Grad haben. Zeigen Sie folgende Aussagen:
(a) Zu jeder Kante {v0 , v1 } ∈ E existiert eine geschlossene Tour (v0 , v1 , . . . , vk ),
so dass die Kanten {vi−1 , vi } mit 1 ≤ i ≤ k paarweise verschieden sind.
(b) Ist G zusätzlich zusammenhängend, so ist jede Tour wie in a) der maxi-
malen Länge eine Euler-Tour von G.

9.2 Aufgabe. Zeigen Sie folgende Aussagen:

(a) Der Kantengraph L(K4 ) des vollständigen Graphen K4 hat einen Euler-
kreis.

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 09.07.2014 62

(b) Hat ein Graph einen Eulerkreis, so auch sein Kantengraph.

(c) Gilt die Umkehrung von (b)?

9.3 Aufgabe. (Existenz von k-regulären Graphen) Für welche Paare (k, n) ∈
N × N existiert ein k-regulärer Graph G auf n Ecken?

9.4 Aufgabe. Eine Färbung eines Graphen G = (V, E) ist eine Abbildung
f : V → F mit F eine Menge von Farben, so dass aus {u, v} ∈ E folgt f (v) 6=
f (w). Die chromatische Zahl χ(G) sei die kleinste Anzahl an Farben, die zur
Färbung von G benötigt wird, d. h. χ(G) := min{| im f | : f Färbung von G}.
Bestimmen Sie χ(Pn ), χ(Cn ), χ(Kn ) und χ(Qn ).

10.1 Aufgabe. Beweisen oder widerlegen Sie: Ein endlicher Baum, der eine
Ecke der Valenz k besitzt, hat mindestens k Blätter.

10.2 Aufgabe. Ein Graph heißt k-färbbar, wenn k Farben genügen, um diesen
Graphen zu färben im Sinne der Aufgabe 9.4. Eine projektive Ebene ist ein 2-
färbarer Graph G mit diam(G) = 3 = δ(G), der keine Kreise der Länge 4
enthält. Zeigen Sie, dass jede projektive Ebene regulär ist.
Tipp: Zeigen Sie zunächst, dass zwei Ecken im Abstand 3 gleichen Grad haben.

10.3 Aufgabe. Für einen Körper K sei der Graph G definiert, dessen Ecken
die Unterräume des Vektorraums K 3 ungleich 0 und K 3 sind und in dem zwei
Ecken genau dann benachbart sind, wenn die eine echt in der anderen enthalten
ist.
(a) Zeichnen Sie G für den Körper K = F2 = {0,1} und geben Sie einen
Hamiltonkreis an.
(b) Zeigen Sie, dass G eine projektive Ebene ist im Sinne der Aufgabe 10.2.

10.4 Aufgabe. (a) Zeigen Sie, dass es für zwei verbindbare Ecken v und w
eines Graphen einen Teilgraphen W gibt, der isomorph zu einem Weg ist
und dessen Enden v und w sind.
(b) Seien P und Q zwei verschiedene Teilgraphen eines Graphen, die isomorph
zu Wegen sind und gleiche Enden haben. Zeigen Sie, dass dann ein Kreis
in P ∪ Q existiert.

11.1 Aufgabe. Sei G = (V, E) ein endlicher Graph mit |V | = n und seien
v, w ∈ V. Sei A die Adjazenzmatrix von G. Zeigen Sie folgende Aussagen:
(a) Für k ∈ N0 ist (Ak )vw die Anzahl der Touren der Länge k von v nach w.
(b) Es gilt SpurA2 = 2|E|.
1
(c) Die Anzahl der Kreise der Länge 3 in G ist gegeben durch 6 Spur A3 .

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 09.07.2014 63

11.2 Aufgabe. Sei n ∈ N mit n ≥ 2, V = {1, 2, . . . , n} und

W := {(E, a, b) | (V, E) ist Baum und a, b ∈ V }

die Menge der »Wirbeltiere« auf V. Für (E, a, b) ∈ W definiere eine Abbildung
f : V → V wie folgt: Sei (w0 , w1 , . . . , wt ) die einfache Tour von a nach b
im Baum (V, E). Wir wählen nun eine Nummerierung der »Wirbelsäule«
W := {w0 , w1 , . . . , wt } = {v0 , v1 , . . . , vt } mit v0 < v1 < · · · < vt und definieren
f (vi ) := wi für i = 0, 1, . . . , t (d. h. f|W sortiert W ); ferner sei f (v) für v ∈
V \ W die mit v benachbarte Ecke in der eindeutigen Tour von v nach a in
(V, E).
(a) Bestimmen Sie das Wirbeltier, das als Urbild der Abbildung f : i 7→
max{b 2i c, 1} entsteht.
(b) Zeigen Sie, dass die Abbildung W → V V , (E, a, b) 7→ f bijektiv ist.

11.3 Aufgabe. Zeigen Sie, dass der Petersen-Graph nicht planar ist. Können
Sie auch zeigen, dass der Graph rechts oben auf diesem Blatt mit 30 Ecken
und 45 Kanten nicht planar ist?

11.4 Aufgabe. Für welche d ∈ N ist der d-dimensionale Würfel Qd planar?

14.07.2014–13:07
 64

Index
Äußere, 41 [n, k]-Code, 47
[n, k, δ]-Code, 47
Abbildungen [n, k, δ]q -Code, 47
injektive, 19 Codewort, 44
Abstand, 35 Codierung, 44
abzählbarer Wahrscheinlichkeitsraum,
19 Diffie–Hellman-Schlüssel, 55
Abzählung, 6 Diffusion, 53
adjazent, 29 Dijkstra-Algorithmus, 37
Advanced Encryption Standard, 51 Dirichlet-Prinzip, 9
AES, 51 disjunkte Graphen, 32
Algorithmus von Dijkstra, 37 diskrete Logarithmus-Problem, 53
Alphabet, 44 diskreter Logarithmus, 53
Approximationssatz von Dirichlet, 9 Distanz, 37
asymmetrischer Graph, 61 doppelte Abzählung, 10
asymmetrisches Kryptoverfahren, 51 Dreieck, 30
aufspannender Teilgraph, 32 Durchmesser, 35
Automorphismengruppe, 31
Automorphismus, 31 eben, 41
Eckenmenge, 29
Basis, 53 einfach, 35
Baum, 39 einfach geschlossen, 35
benachbart, 29 Elementarereignisse, 20
binärer Code, 44 Enden, 30
Binomialkoeffizient, 11 endlich, 6
binomischer Lehrsatz, 11 endlicher Graph, 29
Blätter, 39 Entschlüsselungsabbildung, 51
Blockcode, 44 Entschlüsselungsschlüssel, 51
Bonferroni-Ungleichungen, 22 Ereignisse, 20
unabhängig, 20
Catalan-Zahlen, 17 Erwartungswert, 21
t-Clique, 34 erzeugende Funktion, 26
Code, 44 exponentielle, 29
binärer, 44 Euler-Tour, 36
e-fehlererkennender, 45 Exklusion, 22
e-fehlerkorrigierender, 45 Expansion, 55
linearer, 47 exponentielle erzeugende Funktion, 29
perfekter, 47 extremal, 40
perfekter e-fehlerkorrigierender, 47 extremale Graphen, 35
Reed–Solomon, 49
ternärer, 44 n-facher Wiederholungscode, 44
verallgemeinerter Reed–Solomon, Faktorielle
49 fallende, 10
zyklisch, 49 steigende, 10

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 09.07.2014 65

Fakultät, 10 Häufigkeit, 14
fallende Faktorielle, 10 Hamilton-Kreis, 36
Falltürfunktionen, 53 hamiltonsch, 36
e-fehlererkennender Code, 45 Hamming-Abstand, 45
e-fehlerkorrigierender Code, 45 Hamming-Code, 48
Fibonacci-Zahlen, 27 Hamming-Kugel, 45
Flächen, 42 Hamming-Metrik, 45
Formale Potenzreihen, 26 Handshake-Lemma, 33
Funktion
erzeugende, 26 induzierter Teilgraph, 32
injektive Abbildungen, 19
Gammafunktion, 10 Inklusion, 22
Geheimtext, 51 Inklusion und Exklusion, 22
Generatormatrix, 48 Innere, 41
Generatorpolynom, 49 Invariante, 33
geometrische Reihe, 16, 26 inzident, 29
geordnete Gradfolge, 33 irreduzibles Polynom, 24
Gesamtgewicht, 14, 37 isoliert, 33
geschlossen, 35 isomorph, 31
Gewicht, 14 Isomorphismus, 31
gewichteter Graph, 37
gleichmächtig, 7 Jordankurve, 41
Gleichverteilung, 20 Jordanscher Kurvensatz, 41
Goldener Schnitt, 28
Größe, 6 Kantengraph, 32
Grad, 31, 33 Kantenmenge, 29
Gradfolge, 33 Klartext, 51
geordnet, 33 Kneser-Graphen, 30
Graph, 29 Komplement, 32
k-regulär, 33 Konfusion, 53
asymmetrisch, 61 Kontrollmatrix, 48
disjunkt, 32 k-regulärer Graph, 33
endlich, 29 Kreis, 32
extremal, 40 Kreis der Länge n, 30
gewichtet, 37 Kryptoanalyse, 50
isomorph, 31 Kryptographie, 50
leer, 30 Kryptologie, 50
planar, 41 Kryptosystem, 51
regulär, 33 asymmetrisch, 51
universell, 31 private-key, 51
Unterteilung, 43 public-key, 51
vollständig, 30 symmetrisch, 51
zufälliger, 31 Kurve, 41
Graphen k-zusammenhängend, 36
extremale, 35
Länge, 6

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 09.07.2014 66

Laplace-Verteilung, 20 Rate, 44
leerer Graph, 30 Reed–Solomon-Code, 49
Lehrsatz regulärer Graph, 33
binomischer, 11 k-regulärer Graph, 33
multinomischer, 17 Rekursionsgleichungen, lineare, 28
lineare Rekursionsgleichungen, 28 Restklassenring, 23
linearer Code, 47 Rundenschlüssel, 52
Rundenzahl, 51
Mächtigkeit, 6, 14
maximal-azyklisch, 39 Schlüssel, 51
Maximalgrad, 33 Schnitt, 32
MDS-Code, 46 Schubfachprinzip, 8
n-Menge, 6 Sn , 10
minimal-zusammenhängend, 39 steigende Faktorielle, 10
Minimalabstand, 45 Stirling-Zahlen, 23
Minimalgrad, 33 Stirlings Formel, 11
Multimenge, 14, 19 stottert, 35
Multinomialkoeffizienten, 17 Sym M , 10
multinomischer Lehrsatz, 17 symmetrisch, 51
Symmetrische Gruppe, 10
Nachbar, 29
n-facher Wiederholungscode, 44 T (G), 40
[n, k]-Code, 47 Teilgraph, 32
[n, k, δ]-Code, 47 aufspannend, 32
[n, k, δ]q -Code, 47 induziert, 32
ternärer Code, 44
Parity-check-Code, 44 Tour, 35
Partialbruchzerlegung, 27 translationsinvariant, 47
Partition, 8
Pascal-Dreieck, 12 unabhängige Ereignisse, 20
perfekter e-fehlerkorrigierender Code, Ungleichungen von Bonferroni, 22
47 universeller Graph, 31
perfekter Code, 47 Unterteilung, 43
Permutationen, 10
Petersen-Graph, 30 Vandermonde-Identität, 15
Peterson–Gorenstein–Zierler-Algorith- Varianz, 21
mus, 49 verallgemeinerter Reed–Solomon-Code,
planarer Graph, 41 49
Polynom verbindbar, 35
irreduzibel, 24 Vereinigung, 32
Polynommethode, 15 Verschlüsselungsabbildung, 51
Potenzmenge, 6 Verschlüsselungsschlüssel, 51
Prüfercode, 41 Vertexmenge, 29
Prinzip der doppelten Abzählung, 10 Viereck, 30
private-key Kryptosystem, 51 vollständig, 30
public-key Kryptosystem, 51 vollständig bipartit, 30

14.07.2014–13:07
Vorlesung Einführung in die Diskrete Mathematik — 09.07.2014 67

vollständiger Graph, 29

Wahrscheinlichkeitsraum
abzählbarer, 19
Wahrscheinlichkeitsverteilung, 20
Wald, 39
Weg, 32
Weg der Länge n, 30
Wiederholungscode
n-facher, 44
Wirbeltieren, 41
Wort, 44

zufälliger Graph, 31
Zufallsvariable, 20
zusammenhängend, 35
k-zusammenhängend, 36
Zusammenhangs-Komponenten, 35
Zusammenhangskomponente, 41
zyklischer Code, 49

14.07.2014–13:07