| INHALTSVERZEICHNIS | öffnen |
Inhaltsverzeichnis
1 Grundlagen 1
1.1 Eine kleine Problemsammlung 2
1.2 Notation 8
1.3 Vollständige Induktion 18
1.4 Funktionen 28
1.5 Relationen 35
1.6 Äquivalenz und andere spezielle Relationen 40
2 Ordnungen 47
2.1 Ordnungen und wie man sie zeichnen kann 47
2.2 Ordnungen und lineare Ordnungen 53
2.3 Die Teilmengenrelation 57
2.4 Groß heißt lang oder dick 59
3 Zähltheorie 64
3.1 Funktionen und Teilmengen 64
3.2 Permutationen 70
3.3 Binomialkoemzienten 73
3.4 Näherungen: Eine Einführung 85
3.5 Näherungen: Fakultät 93
3.6 Näherungen: Binomialkoeffizienten 101
3.7 Inklusion-Exklusion 106
3.8 Vertauschte Hüte 112
4 Graphen 119
4.1 Definition eines Graphen; Isomorphismus 119
4.2 Teilgraphen, Komponenten, Adjazenzmatrix 129
4.3 Gradfolgen 136
4.4 Eulersche Graphen 142
4.5 Gerichtete Eulersche Graphen 151
4.6 2-Zusammenhang 156
4.7 Dreiecksfreie Graphen: ein Extremalproblem 163
5 Bäume 168
5.1 Definition und Charakterisierungen 168
5.2 Isomorphismen von Bäumen 175
5.3 Aufspannende Bäume eines Graphen 182
5.4 Minimal aufspannende Bäume 188
5.5 Die Algorithmen von Jarnik und Boruvka 195
6 Graphen in der Ebene 201
6.1 Zeichnungen in die Ebene und andere Flächen 201
6.2 Kreise in ebenen Graphen 209
6.3 Die Euler-Formel 217
6.4 Das Vier Farben-Problem 227
7 Die Methode des Doppelten Abzählens 240
7.1 Paritätsargumente 240
7.2 Der Satz von Sperner 250
7.3 Ein Problem der extremalen Graphentheorie 258
8 Die Anzahl aufspannender Bäume 264
8.1 Die Cayley-Formel 264
8.2 Ein Beweis mit Gradfolgen 266
8.3 Ein Beweis mit Wirbeltieren 268
8.4 Ein Beweis mit dem Prüfer-Code 270
8.5 Beweise mit Determinanten 274
8.6 Der zurzeit wohl einfachste Beweis 285
9 Endliche projektive Ebenen 289
9.1 Definition und grundlegende Eigenschaften 289
9.2 Existenz endlicher projektiver Ebenen 300
9.3 Orthogonale lateinische Quadrate 306
9.4 Kombinatorische Anwendungen 310
10 Wahrscheinlichkeit und probabihstische Beweise 314
10.1 Beweis durch Zählen 314
10.2 Endliche Wahrscheinlichkeitsräume 321
10.3 Zufallsvariable und Erwartungswert 333
10.4 Einige Anwendungen 339
11 Ramsey-Theorie 350
11.1 Eine Party zu sechst 351
11.2 Der Satz von Ramsey für Graphen 352
11.3 Eine untere Schranke für die Ramsey-Zahlen 355
12 Erzeugende Funktionen 358
12.1 Polynome 358
12.2 Potenzreihen 362
12.3 Fibonacci -Zahlen und der goldene Schnitt 375
[weiter lesen] |
|
|
|
|
| REGISTER | öffnen |
Stichwortverzeichnis
(v 2), 120
(xk), 74(3.3.1)
(nk). 73
(k 1 , ...km), 79
-<; 48
^, 47
E, 9, 13
Π , 9
a | b, 49(2.1.2)
(a, b), 8
[a, b], 8
[x], 8
[x] .9
{x, y}, 11
(x, y), 11 0, 122 X , 13
C, 14
C, 14
\X\, 13, 35(Aufg. 7)
X 2 , 16
xüy, 14
X x Y, 16
{...}, 10
R[x], 44
R 1 , 42
RoS, 38
xRy, 36
f(X) , 30
f(x), 29
f 1 , 34
X-->Y, 29
F: X-->Y, 32
f'.x-->y, 29
AT , 436
G + e, 158(4.6.2)
G%e, 158(4.6.2)
G-e, 157(4.6.2)
G-u, 158(4.6.2)
G.e, 235(4.6.2)
G-H, 124(4.1.2)
ab, 290
Ax, 42
∩ (.), 91
e(.), 91
a(n), 186
a(G), 341(10.4.2)
a(P), 60
X (.), 229(6.4.2) 6 p, 420
S(.), 237(Aufg. 2)
w(G), 351
W(P), 60
n, 99
Berechnung, 100(Aufg. 8)
n(n), 105(3.6.3)
AAG , 132(4.2.3)
Abbildung, siehe Funktion
Abschluss, transitiver, 45(Aufg. 4)
Abstand (in Graphen), 132
adjazente Ecken, 121
Adjazenzmatrix, 37, 132(4.2.3)
Äquivalenzrelation, 42(1.6.2)
Anzahl, 117(Aufg. 8)
- Datenstruktur, 186(5.3.4), 187(Aufg. 1)
- äußeres Land, 204
affine Ebene, 299(Aufg. 10), 406, 407(Aufg. 2) Algebra, lineare (Anwendung), 274-284,...
Algorithmus
- Borüvka, 197(5.5.3)
- Greedy, 190(5.4.2), 192, 194(Aufg. 10), 194(Aufg. 11), 194(Aufg. 12)
- Jarnik, 195(5.5.1)
- Kruskal, 190(5.4.2) Prim, siehe
- Jarnik-Algorithmus QUICKSORT, 345 348
- randomisierter, 424
- Sortier- 73(Aufg. 6), 345-348
Antikette, 60, 251, 257(Aufg. 5)antisymmetrische Relation, 41(1.6.1)
Anzahl Abbildungen, 65(3.1.1)
Äquivalenzrelationen, 117(Aufg. 8)
Alkylradikale, 387(Aufg. 12)
Anordnungen, 79
aufspannende Bäume, siehe Anzahl Bäume für beliebige Graphen, 274(8.5.1) Bäume, 264-2...
- mit gegebener Gradfolge, 266(8.2.1)- nicht isomorphe, 182(Aufg. 6), 265(Aufg. 1), 3...
- binäre Wurzelbäume, 387(Aufg. 11)
- geordnete /c-Tupel, 82(Aufg. 17)
- gepflanzte Bäume, 387(Aufg. 8), 387(Aufg. 9)- gerade Mengen, 417(13.4.4)
- Graphen, 118(Aufg. 13), 125
- nicht isomorphe, 126, 128(Aufg. 8)- injektive Abbildungen, 68(3.1.4)
- Kanten eines ebenen Graphen, 221(6.3.3)
- Kugelverteilungen, 75, 83(Aufg. 18)- Lösungen, 75, 359
- lateinische Rechtecke, 310(Aufg. 6)
- monotone Funktionen, 81(Aufg. 7)
- Partitionen von n, 393-400
- surjektive Abbildungen, 116(Aufg. 7)
- Teiler, 117(Aufg. 11)
- Teilmengen, 66(3.1.2), 74(3.3.2), 82(Aufg. 16)
- ungerade, 67(3.1.3), 78
- Triangulierungen (eines Vielecks), 84(Aufg. 24), 386(Aufg. 6)- ungeordnete n-Tupel,...
arithmetischer Mittelwert, 95
assoziativ (Operation), 14, 438
asymmetrisch
- Baum, 181(Aufg. 1)
- Graph, 127(Aufg. 3)
asymptotische Analyse, 88
aufspannender Baum, 182 188
Algorithmus, 183(5.3.2), 187(5.3.5)- maximal, 193(Aufg. 1)- minimal, 188-200
aufspannender Wald, 415
aufsteigendes Segment einer
- Permutation, 72(Aufg. 5)
Ausgrad, 152
außerplanarer Graph, 237(Aufg. 3)
Automorphismus
- eines Graphen, 127(Aufg. 3)- eines Poset, 254, 257(Aufg. 5)
azyklische Relation, 52(Aufg. 2)
BBn, 59
Bäume, Anzahl, 182(Aufg. 6), 264-288, 383-385, 387(Aufg. 8), 387(Aufg. 9), 387(Aufg. ...
Baum, 169(5.1.1)
- asymmetrischer, 181(Aufg. 1)
- aufspannender, 182-188
- Algorithmus, 183(5.3.2)
- minimal, 188-200
binärer, 383-385
- Code, 176
- gepflanzter, 176
- Steiner, 189
- Wurzel- 176
Bedeckung, Kanten- 194(Aufg. 11)
Bedingungen an Parameter, 404(13.1.3)
Beil-Zahl, 117(Aufg. 8), 374(Aufg. 15)
Bernoulli-Ungleichung, 101
Bertrandsches Postulat, 106
Betti-Zahl, siehe zyklomatische Zahl Bijektion, 31(1.4.3) Bild, 29
binäre Operation, 427, 438
binärer Baum, 383-385
Binet-Cauchy, Satz, 281(8.5.4) Binomialkoeffizient, 73-84, 360-361, 362(Aufg. 6)
- Näherung, 101-106
- verallgemeinerter, 365(12.2.3)
Binomialsatz, 77(3.3.3)
- kombinatorische Bedeutung, 360
- verallgemeinerter, 365(12.2.3), 384
bipartiter Graph, 123, 135(Aufg. 4), 285(Aufg. 4)
- vollständiger, 122
Blatt, 171
Blockplan, 404, 406
Bonferroni-Ungleichung , 111
Boolesche Funktion, 316, 321(Aufg. 1)
Borsuk-Ulam, Satz, 246
Borüvka, Algorithmus, 197(5.5.3)
Breitensuche, 132
Brouwerscher Fixpunktsatz, 244(7.1.3), 249(Aufg. 5)
CC(G), 180
Gn , 122 Cn , 324(10.2.2)
Catalan-Zahl, 385-386
Cauchy-Schwarzsche Ungleichung, 259(7.3.2), 262(Aufg. 4)
Cayley-Formel, 264(8.1.1)
charakteristische Funktion, 67
charakteristisches Polynom, 378
chromatische Zahl, 229(6.4.2), 237(Aufg. 2)
- listen- 239(Aufg. 12) Code
- eines Baums, 176
- Prüfer, 270
DdG (., .), 132
Datenstruktur für
- Äqui valenzrelationen, 186(5.3.4), 187(Aufg. 1)
de Bruijn Graph, 155
de Moivre, Satz, 397
de Morgansche Gesetze, 15
degG (.), 136
deg+(.), 152
degöO, 152
Derangement, 113
Design, 401-409
Determinante, 437
- entwickeln, 437
Diagonale, 42, 436
Diagonalmatrix, 436
Diagramm
- Ferrers, 393
- Hasse, 51
- Pfeil- 28
Differenz, symmetrische, 415
Digraph, siehe gerichteter Graph Dilworth, Satz, 63(Aufg. 7)
Dimension, 440
distributiv (Operation), 15, 439
dominierende Menge, 194(Aufg. 12)
doppeltes Abzählen, 74, 240 263, 299(Aufg. 8), 405
dreiecksfreier Graph, 163-167, 341
Dreiecksmatrix, 436
dual
- Graph, 231(6.4.3)
- aufspannende Bäume, 265(Aufg. 4)
- projektive Ebene, 296
Dualität, 296, 304
Durchmesser, 135(Aufg. 8)
EE, 335(10.3.6) e, 96
E(G), 120
Ebene
- affine, 299(Aufg. 10), 406, 407(Aufg. 2)
- Fano, 292
- projektive, siehe projektive Ebene ebene Zeichnung, 202(6.1.1)
ebener Graph, 201-239
- Gradfolge, 224(6.3.4)
- Kantenzahl, 221(6.3.3)
[weiter lesen] |
|
|
|