Diskrete Strukturen Sommersemester 2002

RWTH Aachen Priv.-Doz. Dr. Yubao Guo

Mitschrift von Oswald Jaskolla E-Mail: traxer@gmx.net

10. Juli 2002

Dieses Skript spiegelt meine Aufzeichnungen aus der Vorlesung ”Diskrete Strukturen“, gehalten von Dr. Yubao Guo an der RWTH Aachen im Sommersemester 2002, wider. Es handelt sich nicht um ein offizielles Skript von Dr. Guo oder einer Einrichtung der RWTH Aachen. Für die Richtigkeit der hier präsentierten Ergebnisse (und für evtl. nicht bestandene Prüfungen) übernehme ich selbstverständlich keine Haftung. Falls du Fehler, Ungenauigkeiten oder Unklarheiten entdeckst würde ich mich über eine Mitteilung freuen.

Die Numerierung entspricht der in der Vorlesung benutzten, ich habe lediglich ”Punkt n.k“ durch ”n.k Punkt“ ersetzt, da mir dies für eine Präsentation in gedruckter Form sinnvoller erschien. Außerdem habe ich den meisten Punkten eine mir sinnvoll erscheinende Beschreibung hinzugefügt, soweit nicht schon in der Vorlesung eine solche angegeben wurde. Hauptsächlich möchte ich dadurch die Lesbarkeit des Inhaltsverzeichnisses erhöhen.

Diese Mitschrift wurde mit dem Textsatzsystem L^{A}TEX erstellt, unter Verwendung der Benutzeroberfläche LYX.

Viel Spaß beim büffeln.

Inhaltsverzeichnis

Abzählung, Rekursion, Erzeugende Funktionen 9

1.1 Elementare Zählprinzipien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.1 Lemma (Rechenregeln für Mächtigkeiten) . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2 Folgerung (Anzahl der Abbildungen) . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Definition (Permutation) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 Lemma (Mächtigkeit der symmetrischen Gruppe) . . . . . . . . . . . . . . . . . . . . 10 1.5 Satz (Mächtigkeit der Potenzmenge) . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.6 Definition (Menge der k-Teilmengen) . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.7 Bemerkung (Partitionierung der Potenzmenge) . . . . . . . . . . . . . . . . . . . . . 11 1.8 Lemma (Anzahl der k-Teilmengen) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.9 Lemma (Pascal-Dreieck) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.10 Satz (Vandermonde’sche Identität) . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Anwendung (Bezierkurven) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.11 Lemma (doppeltes Abzählen) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.12 Satz (Schubfachprinzip) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.13 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.14 Satz (verallgemeinertes Schubfachprinzip) . . . . . . . . . . . . . . . . . . . . . . . 14 Rückblick (Verallgemeinerungen von Lemma 1.11) . . . . . . . . . . . . . . . . . . . . . 14 1.15 Satz (Prinzip der Inklusion und Exklusion / Siebformel) . . . . . . . . . . . . . . . . 15 1.16 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.2 Mengenpartitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.17 Definition (Partition, Stirlingzahlen zweiter Art) . . . . . . . . . . . . . . . . . . . . 16 1.18 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.19 Satz (Stirling-Dreieck zweiter Art) . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.20 Satz (Anzahl der injektiven und surjektiven Abbildungen) . . . . . . . . . . . . . . . 17 1.21 Satz (Potenzen und Stirlingzahlen) . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.3 Permutationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Wiederholung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.22 Definition (k-Zyklus) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4 INHALTSVERZEICHNIS

1.23 Bemerkung (Zykeldarstellung von Permutationen) . . . . . . . . . . . . . . . . . . . 20 1.24 Definition (Stirlingzahlen erster Art) . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.25 Satz (Stirling-Dreieck erster Art) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.4 Erzeugende Funktionen / Formale Potenzreihen . . . . . . . . . . . . . . . . . . . . . . . . 21 1.27 Definition (formale Potenzreihe, erzeugende Funktion) . . . . . . . . . . . . . . . . . 21 1.28 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.29 Definition (Rechnen mit Potenzreihen) . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.30 Lemma (Verschieben von Folgengliedern) . . . . . . . . . . . . . . . . . . . . . . . 22 1.31 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.32 Satz (Eigenschaften von K[[x]]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.33 Bemerkung (Invertierbarkeit in Ringen) . . . . . . . . . . . . . . . . . . . . . . . . 23 1.34 Lemma (Invertierbarkeit der geometrischen Reihe) . . . . . . . . . . . . . . . . . . . 23 1.35 Beispiel (Code mit variabler Wortlänge zur Datenkompression) . . . . . . . . . . . . 23 1.36 Satz (Invertieren von Potenzreihen) . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.37 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.38 Definition (formale Ableitung) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.39 Lemma (Linearität und Produktregel der formalen Ableitungen) . . . . . . . . . . . . 25 1.40 Folgerung (Ableitung des Inversen) . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.41 Folgerung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.42 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

1.5 Rekursionsgleichungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.43 Definition (lineare Rekursionsgleichung) . . . . . . . . . . . . . . . . . . . . . . . . 27 1.44 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.45 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.46 Beispiel (Fibonacci-Zahlen) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.47 Bemerkung (goldener Schnitt) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.48 Satz (homogene lineare Rekursionsgleichungen zweiter Ordnung) . . . . . . . . . . . 30 Schema (zum Lösen linearer Rekursionsgleichungen) . . . . . . . . . . . . . . . . . . . . 30 1.49 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.50 Beispiel (Catalan-Zahlen) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.51 Lemma (Rekursionsformel für Catalan-Zahlen) . . . . . . . . . . . . . . . . . . . . 32 1.52 Satz (explizite Darstellung der Catalan-Zahlen) . . . . . . . . . . . . . . . . . . . . 33 Schema (zum Lösen allgemeiner Rekursionsgleichungen) . . . . . . . . . . . . . . . . . . 34 Graphentheorie 35

2.1 Grundbegriffe der Graphentheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.1 Definition (Graph) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.2 Beispiel (einige Beispielgraphen) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3 Bemerkung (Graph, Multigraph, schlichter Graph) . . . . . . . . . . . . . . . . . . . 38 2.4 Definition (Nachbarschaft, Eckengrad, regulärer Graph) . . . . . . . . . . . . . . . . 38 2.5 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.6 Satz (Handschlaglemma, Euler 1736) . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.7 Folgerung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.8 Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.9 Definition (Isomorphie zwischen Graphen) . . . . . . . . . . . . . . . . . . . . . . . . 40 2.10 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2.2 Darstellung von Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.11 Definition (Adjazenzmatrix, Inzidenzmatrix) . . . . . . . . . . . . . . . . . . . . . . 40 2.12 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.13 Satz (Zusammenhang zwischen Adjazenz- und Inzidenzmatrix) . . . . . . . . . . . . 41 2.14 Definition (Teilgraph, induzierter Teilgraph) . . . . . . . . . . . . . . . . . . . . . . 42 2.15 Definition (Zusammenhang, Komponenten) . . . . . . . . . . . . . . . . . . . . . . . 42 2.16 Satz (Abschätzung der Komponenten nach unten) . . . . . . . . . . . . . . . . . . . 43 2.17 Folgerung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.18 Satz (Anzahl der Kanten in zusammenhängenden Graphen) . . . . . . . . . . . . . . 43 2.19 Satz (Abschätzung der Kanten nach oben) . . . . . . . . . . . . . . . . . . . . . . . 44

2.3 Bäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.20 Definition (Baum, Wald) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.21 Lemma (Endecken in Bäumen) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.22 Satz (Charakterisierung von Bäumen) . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.23 Definition (Wurzelbaum) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.24 Definition (Tiefe) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.25 Definition (binärer Baum) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.26 Satz (Anzahl der Ecken in binären Bäumen) . . . . . . . . . . . . . . . . . . . . . . 47 2.27 Folgerung (Tiefe von binären Bäumen) . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.28 Definition (Gerüst eines Graphen) . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.29 Satz (Existenz von Gerüsten) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.30 Satz (Cayley’s Tree Formula) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

2.4 Matching in Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.31 Definition (Matching) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.32 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.33 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.34 Bemerkung (bipartite Graphen) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.35 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.36 Satz (Biparität und Kreise) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.37 Satz (Matchings in bipartiten Graphen) . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.38 Folgerung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.39 Folgerung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.40 Definition (Multipartite Graphen) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

2.5 Hamilton Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.41 Definition (Hamiltonkreis, Hamilton-Weg) . . . . . . . . . . . . . . . . . . . . . . . 52 2.42 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.43 Satz (notwendige Bedingung für hamiltonsche Graphen) . . . . . . . . . . . . . . . . 52 2.44 Satz (Lemma von Ore, 1960) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.45 Folgerung (hinreichende Bedingung für hamiltonsche Graphen) . . . . . . . . . . . . 53 2.46 Folgerung (Dirac, 1052) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.47 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

2.6 Eulersche Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.48 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.49 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.50 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.51 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.52 Folgerung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.53 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

2.7 Planare Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.54 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.55 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.56 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.57 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.58 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.59 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.60 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.61 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.62 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.63 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

2.8 Digraphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.64 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.65 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.66 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.67 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.68 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.69 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.70 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

Algebraische Strukturen 57

3.1 Universelle Algebren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.1 Definition (Operation, Stelligkeit) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.2 Definition (Algebra, Signatur) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.3 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.4 Definition (neutrale Elemente) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.5 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.6 Lemma (Existenz und Eindeutigkeit neutraler Elemente) . . . . . . . . . . . . . . . . 58 3.7 Beispiel (Fortsetzung von Beispiel 3.3) . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.8 Definition (inverse Elemente) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.9 Definition (Halbgruppe) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.10 Definition (Monoid) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.11 Definition (Gruppe) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.12 Definition (abelsche Algebren) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.13 Definition (Ring) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.14 Definition (Körper) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.15 Definition (boolsche Algebra) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.16 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

3.2 Unteralgebren, Homomorphismen, Kongruenzen . . . . . . . . . . . . . . . . . . . . . . . 61 3.17 Definition (Unteralgebra) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.18 Definition (Untergruppe, Teilring) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.19 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.20 Lemma (Abgeschlossenheit von Unteralgebren bezüglich Durchschnitt) . . . . . . . . 62 3.21 Definition (erzeugte Unteralgebra) . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.22 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.22 Definition (Homomorphismus) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.23 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.24 Definition (Isomorphismus, Automorphismus) . . . . . . . . . . . . . . . . . . . . . 63 3.25 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.26 Lemma (Strukturerhaltung durch Isomorphismen) . . . . . . . . . . . . . . . . . . . 63 3.27 Lemma (Umkehrabbildung von Isomorphismen) . . . . . . . . . . . . . . . . . . . . 63 8 INHALTSVERZEICHNIS

Abzählung, Rekursion, Erzeugende Funktionen

1.1 Elementare Zählprinzipien

Sei M eine endliche Menge. Dann wird mit |M|die Anzahl der Elemente von M bezeichnet.

|M|= n ∈ ℕ ⇔ ∃f : M → {1...n},f ist Bijektion

Eine Menge M mit n Elementen heißt n-Menge.

|M|= 0 ⇔ M = ∅

1.1 Lemma (Rechenregeln für Mächtigkeiten)

Seien A,B Mengen

a) |A|= |B|⇔ ∃f : A → B bijektiv

b) |A ⊎ B|= |A|+ |B| A ⊎ B heißt ”disjunkte Vereinigung von A und B“. Die disjunkte Vereinigung von A und B ist nur definiert wenn A und B disjunkt sind, d.h. A ∩ B = ∅. Es gilt dann A ⊎ B = A ∪ B.

c) |A × B| = |A|· |B| A × B heißt ”kartesisches Produkt von A und B“.

A × B = {(a,b)|a ∈ A ∧ b ∈ B}

1.2 Folgerung (Anzahl der Abbildungen)

Seien A, B endliche Mengen und Abb(A,B) := B^{A}:= {f : A → B}. Dann gilt:

|B^{A}|= |B|^{|A|} 10 ABZÄHLUNG, REKURSION, ERZEUGENDE FUNKTIONEN Beweis: Sei |A|= n ∈ ℕ, A = {a_{1},...,a_{n}}. Es gibt eine Bijektion von B^{A}nach B^{n}, z.B.

f : B^{A}→ B^{n},g ↦ (g(a_{1}),...,g(a_{n}))

nach Lemma 1.1 folgt

|B^{A}|= |B^{n}|= |B|^{n} = |B|^{|A|}
♢

1.3 Definition (Permutation)

Sei A eine Menge. Eine bijektive Abbildung f : A → A heißt ”Permutation von A“.

1.4 Lemma (Mächtigkeit der symmetrischen Gruppe)

Sei S_{n}:= {a: {1,...,n} → {1,...,n}|a bijektiv} (S_{n} heißt ”symmetrische Gruppe vom Grad n“). Dann gilt: |S_{n}|= n!

Beweis siehe LA1

Bemerkung n! =Anzahl der Möglichkeiten, eine n-Menge anzuordnen.

1.5 Satz (Mächtigkeit der Potenzmenge)

℘(A) := {B ⊆ A} heißt ”Potenzmenge von A“, z.B A = {1,2} ⇒ ℘(A) = {∅,{1},{2},A}. Ist |A|= n ∈ ℕ, dann gilt:

|℘(A)| = 2^{n}

Beweis Definiere für jedes B ⊆ A

Υ_{B}: A → {0,1}
Υ_{B}(x) = \{ \begin{matrix}1 & falls x ∈ B \\ 0 & falls x ∉ B \end{matrix}

Es gilt f : ℘(A) → {0,1}^{A}mit f(B) = Υ_{B} ist eine Bijektion von ℘(A) nach {0,1}^{A}, und somit

|℘(A)| = |{0,1}^{A}| = 2^{|A|}= 2^{n}

♢

1.6 Definition (Menge der k-Teilmengen)

Sei A eine Menge, k ∈ ℕ, k ≤ |A|

℘_{k}(A) := ( \begin{matrix}A \\ k \end{matrix} ) := \{B ⊆ A||B|= k\}

℘_{k}(A) heißt ”Menge der k-Teilmengen von A“.

1.1 ELEMENTARE ZÄHLPRINZIPIEN 11

1.7 Bemerkung (Partitionierung der Potenzmenge)

℘(A) = ⨄_{k=0}^{|A|} ℘_{k}(A)

|℘(A)| = ∑_{k=0}^{|A|} |℘_{k}(A)|

1.8 Lemma (Anzahl der k-Teilmengen)

Sei A eine n-Menge. Dann gilt:

( \begin{matrix}n \\ k \end{matrix} ) := \frac{n!}{k! · (n − k)!} = \frac{n · (n − 1) · ...· (n − k + 1)}{k!} = |℘_{k}(A)|

( \begin{matrix}n \\ k \end{matrix} ) heißt ”Binomialkoeffizient“.

Beweis |{(a_{1}...a_{k}) ∈ A^{k}|a_{i} ≠ a_{j}∀i ≠ j}| = n · (n − 1) · ...· (n − k + 1). Es gibt jedoch k! Anordnungen von {a_{1}...a_{k}} ⇒ |℘_{k}(A)| = \frac{n·(n−1)·...·(n−k+1)}{k!}.

♢

Dieses Lemma ermöglicht es, einen alternativen Beweis für Satz 1.5 anzugeben:

|℘(A)| = ∑ _{k=0}^{n} ( \begin{matrix}n \\ k \end{matrix} ) = ∑ _{k=0}^{n} ( \begin{matrix}n \\ k \end{matrix} ) · 1^{k}· 1^{n−k} = (1 + 1)^{n} = 2^{n}.

1.9 Lemma (Pascal-Dreieck)

Behauptung ∀n,k ∈ ℕ mit n > k gilt ( \begin{matrix}n \\ k \end{matrix} ) = ( \begin{matrix}n − 1 \\ k − 1 \end{matrix} ) + ( \begin{matrix}n − 1 \\ k \end{matrix} )

Beweis (kombinatorisch) ( \begin{matrix}n \\ k \end{matrix} ) =Anzahl der k-Teilmengen einer n-Menge Sei A = {a_{1}...a_{n}}, |A|= n. Dann gilt:

℘_{k}(A) = {M ⊆ A||M|= k}
= {M′⊎ {a_{n}}|M′⊆ A \ {a_{n}} ∧ |M′|= k − 1} ⊎ {M′′⊆ A \ {a_{n}}||M′′|= k}
⇒ |℘_{k}(A)| = ( \begin{matrix}n − 1 \\ k − 1 \end{matrix} ) + ( \begin{matrix}n − 1 \\ k \end{matrix} )
♢

1.10 Satz (Vandermonde’sche Identität)

( \begin{matrix}n + m \\ k \end{matrix} ) = ∑_{l=0}^{k} ( \begin{matrix}n \\ l \end{matrix} ) · ( \begin{matrix}m \\ k − l \end{matrix} )

1  n=0
1  1  n=1
1  2  1  n=2
1  3  3  1  n=3
1  4  6  4  1  n=4
1  5  10  10  5  1  n=5
1  6  15  20  15  6  1  n=6
1  7  21  35  35  21  7  1  n=7
1  8  28  56  70  56  28  8  1 n=8
⋮

Tabelle 1: Pascal-Dreieck

Beweis Sei A eine Menge, A = B⊎C, |B|= n, |C|= m. Ferner sei ( \begin{matrix}A \\ k \end{matrix} ) _{l} := \{X ⊆ A||X|= k ∧|X ∩ B|=

l}. Dann gilt:

( \begin{matrix}A \\ k \end{matrix} ) = ⨄_{l=0}^{k} ( \begin{matrix}A \\ k \end{matrix} ) _{l}

also:

( \begin{matrix}m + n \\ k \end{matrix} ) = ∑_{l=0}^{k} |( \begin{matrix}A \\ k \end{matrix} ) _{l}| = ∑_{l=0}^{k} ( \begin{matrix}n \\ l \end{matrix} ) ( \begin{matrix}m \\ k − l \end{matrix} )

♢

Anwendung (Bezierkurven)

Seien P_{1}...P_{n} Stützstellen. Dann ist p(t) = ∑ _{i=1}^{n} B_{n,i}(t) · P_{i} t ∈ [0,1] mit B_{n,i}(t) = ( \begin{matrix}n \\ i \end{matrix} ) · t^{i} · (1 − t)^{n−i}

eine Bezierkurve. Nach Satz 1.9 gilt B_{n,i}(t) = t · B_{(n−1),(i−1)} (t) + (1 − t)B_{(n−1),i} (t). Man erreicht eine effiziente Berechnung der Kurve, da man zur Berechnung eines Summanden von p(t) auf bereits berechnete Koeffizienten B_{p,q}(t) zurückgreifen kann.

Abbildung 1: Bezierkurve

1.11 Lemma (doppeltes Abzählen)

Seien S und T Mengen und R ⊆ S × T eine Relation. Es gilt:

|R|= \underbrace{∑_{s∈S}|\{t ∈ T |(s,t) ∈ R\}|}_{Zeilensumme}= \underbrace{∑_{t∈T}|\{s ∈ S|(s,t) ∈ R\}|}_{Spaltensumme}

1.12 Satz (Schubfachprinzip)

Seien X und Y Mengen mit |X|> |Y |und f : X → Y eine Abbildung. Dann gilt:

∃y ∈ Y : |f^{−1} (y)| ≥ 2

Verteilt man n Elemente auf m Fächer (wobei n > m), so gibt es ein Fach, das mindestens zwei Elemente erhält.

1.13 Beispiel

1) In jeder Gruppe von 13 Personen befinden sich mindestens zwei, die im gleichen Monat Geburtstag haben.

2) In jeder Gruppe P von Personen gibt es zwei Personen, die die gleiche Anzahl von Personen kennen. ”Kennen“ ist dabei als symmetrische Relation gemeint, d.h A kennt B ⇒ B kennt A. Dieser Sachverhalt kann anhand eines ungerichteten Graphen veranschaulicht werden (siehe Abbildung 2). Die Knoten stellen die Personen dar, Wenn zwei Personen einander kennen wird dies durch eine Kante zwischen den entsprechenden Knoten gekennzeichnet.

Abbildung 2: Ungerichteter Graph

Beweis: Setze P = {p_{1},...,p_{n}} und f : P → {0,...,n − 1} so daß

f(x) = y ⇔ Person x kennt genau y Personen aus P 14 ABZÄHLUNG, REKURSION, ERZEUGENDE FUNKTIONEN

Fall 1: f(p_{i}) = 0 für ein p_{i} ∈ P ⇒ ∀j ≠ i: f(p_{j}) ≠ n − 1 ⇒ f(P) ⊆ {0,...,n − 2}

Fall 2: ∀p ∈ P : f(p) ≠ 0 ⇒ f(P) ⊆ {1,...,n − 1} In jedem Fall gilt also |P|> |f(P)|. Nach dem Schubfachprinzip gilt also ∃p_{k},p_{l} ∈ P : f(p_{k}) = f(p_{l}).

♢

1.14 Satz (verallgemeinertes Schubfachprinzip)

Ist f : X → Y eine Abbildung, so gibt es ein y ∈ Y mit |f^{−1} (y)| ≥ ⌈ \frac{|X|}{|Y |} ⌉.

Beweis (indirekt): Angenommen ∀y ∈ Y : |f^{−1} (y)| ≤ ⌈ \frac{|X|}{|Y |} ⌉− 1. Dann gilt:

|X| = |⨄ _{y∈Y}f^{−1} (y)|
= ∑_{y∈Y} |f^{−1} (y)|
≤ |Y |· ( ⌈ \frac{|X|}{|Y |} ⌉− 1)
≤ |Y |· ( ( \frac{|X|−1}{|Y |} + 1) − 1)
= |X|− 1
♢

Rückblick (Verallgemeinerungen von Lemma 1.11)

c) Sei M = A_{1}× ...× A_{n}. Dann gilt: |M|= ∏ _{i=1}^{n} A_{i} (Produktregel).

b) Seien A_{1},...,A_{n} paarweise disjunkt (d.h. gilt ∀i ≠ j: A_{i}∩ A_{j} = ∅) und S = ⨄ _{i=1}^{n} A_{i}. Dann gilt: |S|= ∑ _{i=1}^{n} |A_{i}|(Summenregel).

Problem: Wie bestimmt man die Mächtigkeit von S wenn A_{1},...,A_{n} nicht paarweise disjunkt sind? Für zwei Mengen A_{1} und A_{2} gilt |A_{1}∪ A_{2}|= |A_{1}|+ |A_{2}|− |A_{1}∩ A_{2}|. Für drei Mengen A_{1},A_{2} und A_{3} gilt

\begin{aligned}|A_{1}∪ A_{2}∪ A_{3}| = & & |A_{1}|+ |A_{2}|+ |A_{3}| \\ & − & |A_{1}∩ A_{2}|− |A_{1}∩ A_{3}|− |A_{2}∩ A_{3}| \\ & + & |A_{1}∩ A_{2}∩ A_{3}| \end{aligned}

(a) 2 Mengen  (b) 3 Mengen

Abbildung 3: Schnittmengen

1.15 Satz (Prinzip der Inklusion und Exklusion / Siebformel)

Für endliche Mengen A_{1},...,A_{n} gilt

|⋃_{i=1}^{n} A_{i}|= ∑_{r=1}^{n} (−1)^{r−1} · ∑_{1≤i_{1}<...<i_{r}≤n} |⋂_{j=1}^{r} A_{i_{j}} |

Beweis: Sei a ∈ ⋃ _{i=1}^{n} A_{i}. Auf der linken Seite der Behauptung wird a genau ein mal gezählt. Es genügt, zu zeigen, daß auf der rechten Seite a auch genau ein mal gezählt wird. o.B.d.A gilt a ∈ A_{t_{j}} für j = 1...l (d.h. a ∈ ⋂ _{j=1}^{l} A_{t_{j}} und a ∉ (⋃ _{i=1}^{n} A_{i})\( ⋂ _{j=1}^{l} A_{t_{j}})). Dann wird a in der Summe ∑_{1≤i_{1}<...<i_{r}≤n} |⋂ _{j=1}^{r} A_{i_{j}} |genau ( \begin{matrix}l \\ r \end{matrix} ) mal gezählt, denn \{t_{1},...,t_{l}\} enthält genau ( \begin{matrix}l \\ r \end{matrix} ) r-Teilmengen. Es folgt, a wird auf der rechten Seite genau ∑ _{r=1}^{l} (−1)^{r−1} · ( \begin{matrix}l \\ r \end{matrix} )

= 1 + (−1 + ∑ _{r=1}^{l} (−1)^{r−1} · ( \begin{matrix}l \\ r \end{matrix} )

= 1 − ∑ _{r=0}^{l} (−1)^{r} · ( \begin{matrix}l \\ r \end{matrix} )

= 1 − ∑ _{r=0}^{l} ( \begin{matrix}l \\ r \end{matrix} ) · (−1)^{r} · 1^{r−l}

= 1 − (−1 + 1)^{l} = 1 mal gezählt.

♢

1.16 Beispiel

Sei k ∈ N und M_{k} = {n ∈ ℕ|1 ≤ n ≤ 100 ∧ n|k}. Bestimme |M_{2}∪ M_{3}∪ M_{5}|. Lösung: |M_{k}|= ⌊\frac{100}{k}⌋ da genau jede k-te natürliche Zahl durch k teilbar ist.

|M_{2}∪ M_{3}∪ M_{5}| = |M_{2}|+ |M_{3}|+ |M_{5}|− |M_{2}∩ M_{3}|− |M_{2}∩ M_{5}|− |M_{3}∩ M_{5}|+ |M_{2}∩ M_{3}∩ M_{5}|
= |M_{2}|+ |M_{3}|+ |M_{5}|− |M_{6}|− |M_{10}|− |M_{15}|+ |M_{30}|
= 50 + 33 + 20 − 16 − 10 − 6 + 3

16 ABZÄHLUNG, REKURSION, ERZEUGENDE FUNKTIONEN

1.2 Mengenpartitionen

1.17 Definition (Partition, Stirlingzahlen zweiter Art)

Sei M eine n-Menge.

• Eine ”Partition von M“ ist eine Zerlegung von M in disjunkte, nicht leere Teilmengen. P = {A_{1},...,A_{k}} ist Partition von M ⇔ ⋃ _{i=1}^{k} A_{i} = M ∧ ∀i ≠ j ∈ {1,...,k}: A_{i} ≠ ∅ ∧ A_{i}∩ A_{j} = ∅.

• Eine Partition P von M heißt k-Partition von M genau dann wenn |P|= k.

• Part_{k}(M) := {P ⊆ ℘(M)|P ist k− Partition von M}.

• \{ \begin{matrix}n \\ k \end{matrix} \} := S_{n,k}:= |Part_{k}(M)|wenn M eine n-Menge ist und n,k > 0. S_{0,0} := 1 Die Zahlen S_{n,k} heißen ”Stirlingzahlen zweiter Art“.

1.18 Beispiel

i) Sei M = {1,2,3,4}.

Part_{1}(M) = {{M}}
Part_{2}(M) = {{{1},{2,3,4}},{{2},{1,3,4}},{{3},{1,2,4}},
{4},{1,2,3}}{{1,2},{3,4}},{{1,3},{2,4}},
{{1,4},{2,3}}}
= {{A,M \ A}|A ≠ ∅ ∧ A ≠ M}

Im allgemeinen gilt |Part_{2}(M)⊧ \frac{1}{2} · (2^{n}− 2) für jede n-Menge M.

ii) Für n ≥ 1 gilt:

\begin{aligned}S_{n,,0} & = & 0 \\ S_{n,1} & = & 1 \\ S_{n,n−1} & = & ( \begin{matrix}n \\ 2 \end{matrix} ) \\ S_{n,n} & = & 1 \\ S_{n,k} & = & 0∀k > n \end{aligned}

1.19 Satz (Stirling-Dreieck zweiter Art)

∀n,k ∈ ℕ mit 1 ≤ k ≤ n gilt:

S_{n,k}= S_{n−1,k−1} + k · S_{n−1,k}

Beweis (kombinatorisch): Sei A = {a_{1},...,a_{n}}. Die Idee des Beweises ist, die Menge aller k-Partitionen von A in zwei disjunkte Teilmengen T_{1} und T_{2} zu zerlegen, daß |T_{1}|= S_{n−1,k−1} und |T_{2}|= k · S_{n−1,k}. Nach 1.2 MENGENPARTITIONEN 17 Summenregel (Lemma 1.1) gilt dann S_{n,k}= S_{n−1,k−1} + k · S_{n−1,k}.

Part_{k}(A) = {P ∈ Part_{k}(A)|{a_{n}} ∈ P} ⊎

{P ∈ Part_{k}(A)|{a_{n}} ∉ P}

= {P′∪ {a_{n}}|P′∈ Part_{k−1}(A \ {a_{n}})} ⊎

⨄_{i=1}^{k} {{B_{1},...,B_{i}∪ {a_{n}},...,B_{k}}|{B_{1},...,B_{k}} ist k− Partition von A \ {a_{n}}}

⇒ |Part_{k}(A)| = |{P′∪ {a_{n}}|P′∈ Part_{k−1}(A \ {a_{n}})}|+
∑_{i=1}^{k} |{{B_{1},...,B_{i}∪ {a_{n}},...,B_{k}}|{B_{1},...,B_{k}} ist k− Partition von A \ {a_{n}}}|
= S_{n−1,k−1} +

k · |{{B_{1},...,B_{k}} ∈ Part_{k}(A \ {a_{n}})}|

= S_{n−1,k−1} + k · S_{n−1,k}
♢
1  n=0
0  1  n=1
0  1  1  n=2
0  1  3  1  n=3
0  1  7  6  1  n=4
⋮  ...

Tabelle 2: Stirling-Dreieck zweiter Art

1.20 Satz (Anzahl der injektiven und surjektiven Abbildungen)

Seien M und N Mengen mit |M|= m ∈ ℕ und |N|= n ∈ ℕ, so gilt:

a) |Abb(M,N)⊧ n^{m}.

b) |Inj(M,N)|= n\underline{m}= n · (n − 1) · ...· (n − (m + 1)). n\underline{m} wird ausgesprochen ”n hoch m fallend“. Inj(M,N) ist die Menge der injektiven Abbildungen von M nach N.

c) |Surj(M,N)|= n! · S_{m,n}. Beweis: Sei M = {a_{1},...,a_{m}} eine m-Menge.

a) siehe Folgerung 1.2 b) f : M → N ist injektiv ⇔ ∀i ≠ j: f(a_{i}) ≠ f(a_{j})

Mit der Produktregel (Lemma 1.1) folgt aus

|Inj(M,N)|= |N × N \ {f(a_{1})} × N \ {f(a_{1}),f(a_{2})} × ...× N \ {f(a_{1}),...,f(a_{m−1})}| die Behauptung.

♢

c) Sei N = {b_{1},...,b_{n}} eine n-Menge und f : M → N surjektiv.

Die Menge {f^{−1} (b_{i})|b_{j} ∈ N} bildet eine n-Partition von M. Jede n-Partition von M induziert allerdings durch jede Permutation von N eine unterschiedliche surjektive Funktion. Es folgt:

|Surj(M,N)| = Anzahl der Permutationen von N · Anzahl der n− Partitionen von M
= n! · S_{m,n}
♢

1.21 Satz (Potenzen und Stirlingzahlen)

n^{m}= ∑_{k=0}^{n} n\underline{k}· S_{m,k}

1.3 PERMUTATIONEN 19 Beweis: Sei M eine m-Menge und N eine n-Menge. Jede Abbildung f : M → N kann dann als surjektive Abbildung f′: M → Bild(f) interpretiert werden. Es gilt dann:

Abb(M,N) = ⨄_{A⊆N}Surj(M,A)
⇒ |Abb(M,N)| = ∑_{A⊆N}|Surj(M,A)|
= ∑_{k=0}^{n} ∑_{A∈( \begin{matrix}N \\ k \end{matrix} )} |Surj(M,A)|
= ∑_{k=0}^{n} ∑_{A⊆( \begin{matrix}N \\ k \end{matrix} )} k! · S_{m,k}
= ∑_{k=0}^{n} ( \begin{matrix}n \\ k \end{matrix} ) k! · S_{m,k}
= ∑_{k=0}^{n} \frac{n\underline{k}}{k!}k! · S_{m,k}
⇒ n^{m} = ∑_{k=0}^{n} n\underline{k}· S_{m,k}
♢

1.3 Permutationen

Wiederholung

S_{n}:= Sym({1,...,n}) := {σ: {1,...,n} → {1,...,n}|σ ist bijektiv}, |S_{n}|= n!.

Bemerkung Jede Permutation σ ∈ S_{n} kann wie folgt dargestellt werden:

• durch eine Wertetabelle

σ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 4 & 3 & 7 & 2 & 1 & 9 & 5 & 8 & 11 & 6 & 10 \end{matrix} )

• als Produkt von Zyklen

σ = (142375) ∘ (8) ∘ (691110)

1.22 Definition (k-Zyklus)

Ein k-Zyklus (i_{1} ... i_{k}) ist eine Permutation σ ∈ S_{n} mit

σ(i_{j}) = σ(i_{j+1} )∀j = 1,...,k − 1
σ(i_{k}) = i_{1}
σ(i) = i∀i ∉ {i_{1},...,i_{k}}

1.23 Bemerkung (Zykeldarstellung von Permutationen)

1) Ein Zyklus ist durch die (zyklische) Reihenfolge der Elemente des Zykels eindeutig bestimmt. (1234) = (2341)

2) Jede Permutation σ ∈ S_{n} läßt sich als Produkt von Zyklen schreiben.

Beispiel: S_{3} = {(1)(2)(3),(1)(23),(2)(13),(3)(12),(123),(132)}, |S_{3}|= 3! = 6.

1.24 Definition (Stirlingzahlen erster Art)

Die Anzahl der Permutationen von \{1,...,n\} mit genau k ∈ ℕ Zyklen wird mit s_{n,k}oder [ \begin{matrix}n \\ k \end{matrix} ] bezeichnet.

Die Zahlen s_{n,k} heißen ”Stirlingzahlen erster Art“. Es gilt:

s_{0,0} := 1
s_{n,0} = 0 ∀n ∈ ℕ
s_{n,k} = 0 ∀k > n

1.25 Satz (Stirling-Dreieck erster Art)

∀n,k ∈ ℕ mit n ≥ k ≥ 1 gilt:

s_{n,k}= s_{n−1,k−1} + (n − 1) · s_{n−1,k}

Beweis (kombinatorisch): Der Beweis funktioniert ähnlich wie der Beweis von Satz 1.19. Die Menge aller Permutationen mit genau k Zyklen wird in zwei disjunkte Teilmengen T_{1} und T_{2} zu zerlegen, daß |T_{1}|= s_{n−1,k−1} und T_{2} = (n − 1) · S_{n−1,k}.

{σ_{1}∘ ...∘ σ_{k}|σ_{1}∘ ...∘ σ_{k} ist Permutation von {1,...,n} mit genau k Zyklen}
= {σ′_{1}∘ ...∘ σ′_{k−1} ∘ (n)|σ′_{1}∘ ...∘ σ′_{k−1} ist Permutation von {1,...,n − 1} mit genau k − 1 Zyklen} ⊎
⨄ _{i=1}^{n−1} {σ′′_{1}∘ ...∘ σ′′_{k}|σ′′_{1}∘ ...∘ σ′′_{k}ist Permutation von ({1,,n − 1} \ {i}) ∪ {(in)}}
⇒ s_{n,k}= s_{n−1,k−1} + (n − 1) · s_{n−1,k}
♢

Beispiel (zum Beweis) Betrachte die Permutationen von {1,2,3,4,5} mit genau 3 Zyklen [... Beispiel fehlt ...]

1  n=0
0  1  n=1
0  1  1  n=2
0  2  3  1  n=3
0  6  11  6  1  n=4
0  24  15  35  10  1 n=5
⋮  ...

Tabelle 3: Stirling-Dreieck erster Art

1.4 Erzeugende Funktionen / Formale Potenzreihen

Bei der Komplexitätsanalyse von Algorithmen entstehen oft Rekursionsgleichungen, z.B. a_{0} = 0, a_{1} = 1, a_{i} = a_{i−1} + a_{i−2} ∀i ≥ 2. Um die Lösung einer Rekursionsgleichung zu finden benutzen wir erzeugende Funktionen. Rekursionsgleichungen beschreiben eine unendliche Folge (a_{n})_{n∈ℕ} := a_{1},a_{2},.... Wir führen für Folgen eine andere Schreibweise ein:

∑_{n=0}^{∞} a_{n}x^{n}:= (a_{n})_{n∈ℕ}

1.27 Definition (formale Potenzreihe, erzeugende Funktion)

Sei K ein Körper (z.B. K = ℝ oder K = ℂ) und (a_{n})_{n∈ℕ} eine Folge. Die formale Potenzreihe

A(x) := ∑_{n=0}^{∞} a_{n}x^{n}

heißt ”erzeugende Funktion der Folge (a_{n})_{n∈ℕ} “. Die Menge aller formalen Potenzreihen über K wird mit K [[x]]bezeichnet.

K [[x]]:= { ∑_{n=0}^{∞} a_{n}x^{n}|a_{n} ∈ K∀n ∈ ℕ_{0}}

1.28 Bemerkung

1) Für k ∈ ℕ_{0} gilt x^{k} = (a_{n})_{ℕ_{0}} mit a_{n} = \{ \begin{matrix}1 & falls n = k \\ 0 & sonst \end{matrix} .

δ_{n,k} := \{ \begin{matrix}1 & falls n = k \\ 0 & sonst \end{matrix} heißt′Kronecker− Symbol′
x^{k} = (δ_{n,k})_{n∈ℕ_{0}}

2) Für m ∈ ℕ_{0} gilt ∑ _{n=m}^{∞} a_{n}x^{n} = (b_{j})_{j∈ℕ_{0}} mit b_{j} = \{ \begin{matrix}0 & falls j < m \\ a_{j} & falls j ≥ m \end{matrix} .

3) ∑ _{n=0}^{∞} a_{n}x^{kn}= (b_{j})_{j∈ℕ_{0}} mit b_{j} = \{ \begin{matrix}a_{n} & falls j = kn für ein n ∈ ℕ_{0} \\ 0 & sonst \end{matrix} .

4) Unterschiede zwischen Potenzreihen der Analysis und formalen Potenzreihen:

Potenzreihen in der Analysis  formale Potenzreihe
• f(x) = ∑ _{n=0}^{∞} a_{n}x^{n}  • A(x) = ∑ _{n=0}^{∞} a_{n}x^{n} = (a_{n})_{n∈ℕ_{0}}
• beschreibt eine unendliche Summe • beschreibt eine unendliche Folge
• Funktion in der Variable x  • für x wird im allgemeine nichts eingesetzt
• Konvergenz als zentrale Frage  • Konvergenz interessiert nicht

5) Seien (a_{n})_{n∈ℕ_{0}} , (b_{n})_{n∈ℕ_{0}} Folgen und A(x) = ∑ _{n=0}^{∞} a_{n}x^{n}, B(x) = ∑ _{n=0}^{∞} b_{n}x^{n} formale Potenzreihen.

A(x) = B(x) :⇔ ∀n ∈ ℕ_{o} : a_{n} = b_{n}

22 ABZÄHLUNG, REKURSION, ERZEUGENDE FUNKTIONEN

1.29 Definition (Rechnen mit Potenzreihen)

Sei K ein Körper und (a_{n})_{n∈ℕ_{0}} ,(b_{n})_{n∈ℕ_{0}} ∈ K^{∞}, a ∈ K.

• Die Addition von Potenzreihen ist definiert durch:

∑_{n=0}^{∞} a_{n}x^{n}+ ∑_{n=0}^{∞} b_{n}x^{n}:= ∑_{n=0}^{∞}(a_{n}+ b_{n})x^{n}

• Die Multiplikation von Potenzreihen ist definiert durch:

( ∑_{n=0}^{∞} a_{n}x^{n}) · ( ∑_{n=0}^{∞} b_{n}x^{n}) := ∑_{n=0}^{∞} ( ∑_{k=0}^{n} a_{k}b_{n−k}) x^{n}

Die Multiplikation heißt auch ”Faltung“ oder ”Konvolution“ von (a_{n})_{n∈ℕ_{0}} und (b_{n})_{n∈ℕ_{0}} , und ist analog zum Cauchy-Produkt der Analysis definiert.

• Die Multiplikation einer Potenzreihe mit einem Skalar ist definiert als:

a · ( ∑_{n=0}^{∞} a_{n}x^{n}) := ∑_{n=0}^{∞} a · a_{n}x^{n}

1.30 Lemma (Verschieben von Folgengliedern)

x^{m}· ∑_{n=0}^{∞} a_{n}x^{n} = ∑_{n=m}^{∞}a_{n}x^{n}

das heißt:

x^{m}· (a_{0}a_{1} ...) = (\underbrace{0 ... 0}_{m mal} a_{0}a_{1} ...)

Beweis: x^{m}= (δ_{m,n})_{n∈ℕ_{0}}

x^{m}· ∑_{n=0}^{∞} a_{n}x^{n} = ( ∑_{n=0}^{∞} δ_{m,n}x^{n}) · ( ∑_{n=0}^{∞} a_{n}x^{n})
= ∑_{n=0}^{∞} ( ∑_{k=0}^{n} δ_{n,k}a_{k}) x^{n}
= ∑_{n=m}^{∞}a_{n−m}x^{n}
♢

1.31 Beispiel

Es gilt x^{m}· x^{n} = x^{m+n} ∀m,n ∈ ℕ_{0}.

1.32 Satz (Eigenschaften von K[[x]])

a) K[[x]] ist ein K-Vektorraum.

1.4 ERZEUGENDE FUNKTIONEN / FORMALE POTENZREIHEN 23 b) (K[[x]],+,·) ist ein kommutativer Ring mit Nullelement 0 = 0 · x^{0} und Einselement 1 = 1 · x^{0}.

Beweis Nachrechnen.

♢

1.33 Bemerkung (Invertierbarkeit in Ringen)

Gilt in einem kommutativen Ring mit Eins A · B = 1, so ist B durch A eindeutig bestimmt. Ebenso ist dann auch A durch B eindeutig bestimmt. B = A^{−1} = \frac{1}{A} und A = B^{−1} = \frac{1}{B}. A und B heißen ”invertierbar“.

1.34 Lemma (Invertierbarkeit der geometrischen Reihe)

In K[[x]] ist ∑ _{i=0}^{∞} c^{i}x^{i} für jedes c ∈ K invertierbar und es gilt:

∑_{i=0}^{∞} c^{i}x^{i} = \frac{1}{1 − cx}

Beweis

(1 − cx) · ∑_{i=0}^{∞} c^{i}x^{i} = ∑_{i=0}^{∞} c^{i}x^{i}− cx∑_{i=0}^{∞} c^{i}x^{i}
= ∑_{i=0}^{∞} c^{i}x^{i}− ∑_{i=0}^{∞} cxc^{i}x^{i}
= ∑_{i=0}^{∞} c^{i}x^{i}− ∑_{i=0}^{∞} c^{i+1} x^{i+1}
= ∑_{i=0}^{∞} c^{i}x^{i}− ∑_{i=1}^{∞} c^{i}x^{i}
= c^{0}x^{0}
= 1
♢

Bemerkung Wegen der Gleichheit ∑ _{i=0}^{∞} c^{i}x^{i} = \frac{1}{1−cx} ist \frac{1}{1−cx} auch eine formale Potenzreihe. ∑ _{i=0}^{∞} c^{i}x^{i} heißt ”geometrische Reihe“.

1.35 Beispiel (Code mit variabler Wortlänge zur Datenkompression)

Sei Bn = {a,b,c}, Zi = {0,1}. Für k ∈ ℕ sei W_{k} = {Folge aus i Buchtaben gefolgt von k − i Ziffern |1 < i < k}. Es gilt

w_{k}:= |W_{k}| = ∑_{i=1}^{k−1} 3^{i}2^{k−i}
= \underbrace{∑_{i=0}^{k} 3^{i}2^{k−i}}_{=:c_{k}}−2^{k}− 3^{k}

24 ABZÄHLUNG, REKURSION, ERZEUGENDE FUNKTIONEN Behauptung: c_{k} = 3^{k+1} − 2^{k+1} Beweis:

∑_{k=0}^{∞} c_{k}x^{k} = ∑_{k=0}^{∞} ( ∑_{i=0}^{k} 3^{i}2^{k−i}) x^{k}
= ( ∑_{i=0}^{∞} 3^{i}x^{i}) · ( ∑_{i=0}^{∞} 2^{i}x^{i})
= \frac{1}{1 − 3x} · \frac{1}{1 − 2x}
= \frac{3}{1 − 3x} − \frac{2}{1 − 2x}
= ( 3 · ∑_{k=0}^{∞} 3^{k}x^{k}) − ( 2 · ∑_{k=0}^{∞} 2^{k}x^{k})
= ∑_{k=0}^{∞} ( 3^{k+1} − 2^{k+1}) x^{k}
⇒ c_{k} = 3^{k+1} − 2^{k+1}
♢

⇒ w_{k} = 3^{k+1} − 2^{k+1} − 2^{k}− 3^{k} = 2 · 3^{k}− 2^{k}

1.36 Satz (Invertieren von Potenzreihen)

A = ∑ _{i=0}^{∞} a_{n}x^{n} ∈ K[[x]] ist genau dann invertierbar wenn a_{0} ≠ 0. Beweis: A ist invertierbar ⇔ ∃B = ∑ _{i=0}^{∞} b_{n}x^{n} ∈ K[[x]] : A · B = 1.

A · B = ∑_{n=0}^{∞} ( ∑_{k=0}^{n} a_{k}b_{n−k}) x^{n} = 1

⇔ ∑_{k=0}^{n} a_{k}b_{n−k} = \{ \begin{matrix}1 & , für n = 0 \\ 0 & , sonst \end{matrix}
⇔  a_{0}b_{0} = 1 ; a_{0}b_{1}+ a_{1}b_{0} = 0 ; a_{0}b_{2}+ a_{1}b_{1}+ a_{2}b_{0} = 0 ; ⋮

Ist A invertierbar, so muß also a_{0} ≠ 0 gelten. Ist umgekehrt a_{0} ≠ 0, so definiere:

b_{0} = \frac{1}{a_{0}}
⋮
b_{n} = −\frac{1}{a_{0}}(a_{1}b_{n−1} + a_{2}b_{n−2} + ...+ a_{n}b_{0})∀n ∈ ℕ
♢

1.4 ERZEUGENDE FUNKTIONEN / FORMALE POTENZREIHEN 25

1.37 Beispiel

a) A = 1 − cx = ∑ _{n=0}^{∞} a_{n}x^{n} mit a_{0} = 1, a_{1} = −c, a_{i} = 0∀i > 1. Bestimme A^{−1} . Lösung: Sei A^{−1} = ∑ _{n=0}^{∞} b_{n}x^{n}. Dann gilt:

a_{0}b_{0} = 1 ⇒ b_{0} = 1
a_{0}b_{1}+ a_{1}b_{0} = 0 ⇒ b_{1} = c
a_{0}b_{2}+ a_{1}b_{1}+ a_{2}b_{0} = 0 ⇒ b_{2} = c^{2}
⋮
... ⇒ b_{n} = c^{n}

Also gilt \frac{1}{1−cx} = ∑ _{n=0}^{∞} c^{n}x^{n}. b)

\frac{1}{(1 − cx)^{2}} = \frac{1}{1 − cx} · \frac{1}{1 − cx}
= ( ∑_{n=0}^{∞} c^{n}x^{n}) · ( ∑_{n=0}^{∞} c^{n}x^{n})
= ∑_{n=0}^{∞} ( ∑_{k=0}^{n} c^{k}c^{n−k}) x^{n}
= ∑_{n=0}^{∞}(n + 1)c^{n}x^{n}

Insbesonders gilt \frac{c}{(1−cx)^{2}} = ∑ _{n=0}^{n} (n + 1)c^{n+1} x^{n}.

1.38 Definition (formale Ableitung)

Die Abbildung D: K[[x]] → K[[x]], ∑ _{n=0}^{∞} a_{n}x^{n} ↦ ∑ _{n=0}^{∞} (n + 1)a_{n+1} x^{n} heißt ”formale Ableitung“. Bemerkung D ist eine Operation auf Folgen mit

D: (a_{0}a_{1}a_{2} ... a_{n} ...) ↦ (a_{1}2a_{2}3a_{3}... na_{n} ...)

1.39 Lemma (Linearität und Produktregel der formalen Ableitungen)

Die Abbildung formale Ableitung ist K-linear und es gilt

a) D(x^{n}) = nx^{n−1}

b) D(A · B) = D(A) · B + A · D(B) Beweis: Nachrechnen!

♢

1.40 Folgerung (Ableitung des Inversen)

Ist A ∈ K[[x]] eine invertierbare erzeugende Funktion, so gilt:

D(A^{−1} ) = −\frac{D(A)}{A^{2}}

Beweis:

A · A^{−1} = 1 und D(1) = 0
⇒ 0 = D(1) = D(A · A^{−1} ) = D(A) · A^{−1} + A · D(A^{−1} )
⇒ A · D(A^{−1} ) = −D(A) · A^{−1}
⇒ D(A^{−1} ) = −D(A) · A^{−2} = −\frac{D(A)}{A^{2}}
♢

Beispiel (ein alternativer Beweis für Beispiel 1.37 2)): Ist A = 1−cx, dann gilt A^{−1} = ∑ _{n=0}^{∞} c^{n}x^{n}, D(A) = −c und \frac{1}{1−cx} = ∑ _{n=0}^{∞} c^{n}x^{n}. Nach Definition 1.38 gilt D(A^{−1} ) = ∑ _{n=0}^{∞} (n + 1)c^{n+1} x^{n}.

⇒  D(A^{−1} ) = \frac{D(A)}{A^{2}}= −\frac{c}{(1 − cx)^{2}} = ∑_{n=0}^{∞}(n + 1)c^{n+1} x^{n}

⇒  \frac{1}{(1 − cx)^{2}} = ∑_{n=0}^{∞}(n + 1)c^{n}x^{n}

♢

1.41 Folgerung

∀m ∈ ℕ: \frac{1}{(1 − cx)^{m}} = ∑_{n=0}^{∞} ( \begin{matrix}n + m − 1 \\ n − 1 \end{matrix} ) c^{n}x^{n}

Beweis: Übung.

♢

1.42 Bemerkung

• Erzeugende Funktionen können im Prinzip wie normale Funktionen behandelt werden.

• Falls zu einer Funktion F eine Potenzreihe existiert, dann kann man diese durch Taylor-Entwicklung um 0 beschreiben.

F (x) = ∑_{n=0}^{∞} \frac{F^{(n)}(0)}{n!}= ( \frac{F^{(n)}(0)}{n!}) _{n∈ℕ_{0}}

• Einige wichtige Potenzreihen und ihre erzeugenden Funktionen sind in Tabelle 4 aufgelistet. Dabei gilt

( \begin{matrix}r \\ 0 \end{matrix} ) := 1, ( \begin{matrix}r \\ k \end{matrix} ) := \frac{r · (r − 1) · ...· (r − k + 1)}{k!} ∀r ∈ ℝ

( \begin{matrix}r \\ k \end{matrix} ) heißt ”verallgemeinerter Binomialkoeffizient“ und es gilt (1 + x)^{y} = ∑ _{k=0}^{∞} ( \begin{matrix}y \\ k \end{matrix} ) x^{k}∀y ∈ ℝ.

1.5 REKURSIONSGLEICHUNGEN 27

a_{n}  Folge  Potenzreihe  erzeugende Funktion
1  1,1,1,1,...  ∑ _{n=0}^{∞} x^{n}  \frac{1}{1−x}
n  1,2,3,4,...  ∑ _{n=0}^{∞} nx^{n}  \frac{x}{(1−x)^{2}}
c^{n}  1,c,c^{2},c^{3}...  ∑ _{n=0}^{∞} c^{n}x^{n}  \frac{1}{c−x}
n^{2}  0,1,4,9,...  ∑ _{n=0}^{∞} n^{2}x^{n}  \frac{x(1+x)}{(1−x)^{3}}
( \begin{matrix}r \\ n \end{matrix} )  1,r,( \begin{matrix}r \\ 2 \end{matrix} ) ,( \begin{matrix}r \\ 3 \end{matrix} ) ,...  ∑ _{n=0}^{∞} ( \begin{matrix}r \\ n \end{matrix} ) x^{n}  \frac{1}{(1+x)^{r}}
( \begin{matrix}r + n \\ n \end{matrix} ) 1,r + 1,( \begin{matrix}r + 2 \\ 2 \end{matrix} ) ,( \begin{matrix}r + 3 \\ 3 \end{matrix} ) ,... ∑ _{n=0}^{∞} ( \begin{matrix}r + n \\ n \end{matrix} ) x^{n}  \frac{1}{(1−x)^{r+1}}
\frac{1}{n}  0,1, \frac{1}{2}, \frac{1}{3},...  ∑ _{n=0}^{∞} \frac{1}{n}x^{n}  ln \frac{1}{1−x}
\frac{1}{n!}  1,1, \frac{1}{2}, \frac{1}{6},...  ∑ _{n=0}^{∞} \frac{1}{n!}x^{n}  e^{x}

Tabelle 4: Formale Potenzreihen und ihre erzeugenden Funktionen

1.5 Rekursionsgleichungen

In einigen grundlegenden algorithmischen Verfahren kommen Rekursionsgleichungen vor:

• ”Divide and Conquer“-Algorithmen

Idee:

– teile das Problem in kleinere Teilprobleme auf (Divde)

– löse die Teilprobleme

– berechne aus den Lösungen der Teilprobleme die Gesamtlösung (Conquer) Diese Strategie wird zum Beispiel bei binärer Suche, Mergesort oder dem euklidischen Algorithmus verwendet.

• dynamische Programmierung (Optimierungsprobleme)

• Greedy-Algorithmen

1.43 Definition (lineare Rekursionsgleichung)

Eine Rekursionsgleichung der Form

a_{n} = c_{1}a_{n−1} + c_{2}a_{n−2} + ...+ c_{k}a_{n−k} + b_{k}∀n ≥ k

mit Anfangsbedingungen a_{i} = b_{i}∀i = 0,...,k − 1 heißt ”lineare Rekursionsgleichung k-ter Ordnung”. • gilt b_{k} = 0, so heißt die Gleichung ”homogene lineare Rekursionsgleichung“

• gilt b_{k} ≠ 0, so heißt die Gleichung ”inhomogene lineare Rekursionsgleichung“

1.44 Beispiel

1) eine homogene lineare Rekursionsgleichung:

a_{n} = ca_{n−1} ∀n ≥ 1, a_{0} = 0
a_{1} = ca_{0} = cb_{0}
a_{2} = ca_{1} = c^{2}b_{0}
⋮
⇒ a_{n} = c^{n}b_{0}

2) eine inhomogene lineare Rekursionsgleichung:

a_{0} = b_{0}, a_{n} = ca_{n−1} + b_{1}wobei c,b_{0},b_{1} konstant sind

Behauptung:

a_{n} = \{ \begin{matrix}b_{0}c^{n}+ b_{1} \frac{c^{n}−1}{c−1} & falls c ≠ 1 \\ b_{0}+ nb_{1} & falls c = 1 \end{matrix}

Beweis: Induktion über n

Induktionsverankerung: Sei n = 1

a_{1} = ca_{0}+ b1 = \{ \begin{matrix}b_{0}c^{1}+ b_{1} \frac{c^{1}−1}{c−1} & falls c ≠ 1 \\ b_{0}+ 1b_{1} & falls c = 1 \end{matrix}

Induktionsschluß: Sei n > 1 und für alle m < n gelte a_{m}= \{ \begin{matrix}b_{0}c^{m}+ b_{1} \frac{c^{m}−1}{c−1} & falls c ≠ 1 \\ b_{0}+ mb_{1} & falls c = 1 \end{matrix}

1. Fall: c ≠ 1. Es gilt

a_{n} = ca_{n−1} + b_{1}
= c( b_{0}c^{n−1} + b_{1} \frac{c^{n−1} − 1}{c − 1} ) + b_{1}
= b_{0}c^{n}+ b_{1}( \frac{c^{n}− c}{c − 1} + 1)
= b_{0}c^{n}+ b_{1} \frac{c^{n}− 1}{c − 1}

2.Fall: c = 1.

a_{n} = a_{n−1} + b_{1} = b_{0}+ (n − 1)b_{1}+ b_{1} = b_{0}+ nb_{1}

1.45 Beispiel

Sei a_{n}:=Anzahl der Wörter der Länge n über dem Alphabet {a,b} die keine zwei aufeinanderfolgende a’s enthalten.

a_{n} = a_{n−1} + a_{n−1} ∀n ≥ 3

1.46 Beispiel (Fibonacci-Zahlen)

Ein Kaninchen bringt ab seinem zweiten Lebensmonat jeden Monat ein weiteres Kaninchen zur Welt. Falls die Kaninchen unsterblich wären, wie viele Kaninchen gibt es nach n-Monaten wenn es im ersten Monat ein Kaninchen gibt.

Bezeichnet man die Anzahl der Kaninchen nach n Monaten mit F_{n}, so gilt:

F_{0} = 0, F_{1} = 1, F_{2} = 1, F_{3} = 1 + 1 = 2, F_{4} = 2 + 1 = F_{3}+ F_{2}

und allgemein

F_{n} = F_{n−1} + F_{n−2}

1.5 REKURSIONSGLEICHUNGEN 29 Die Zahlen F_{n} definiert durch

F_{0} := 0, F_{1} := 1, ∀n > 1 : F_{n}:= F_{n−1} + F_{n−2}

heißen ”Fibonacci-Zahlen“. Wir werden nun eine explizite Darstellung der Fibonacci Zahlen herleiten. Sei F = F (x) = ∑ _{n=0}^{∞} F_{n}x^{n}. Dann gilt:

F = ∑_{n=0}^{∞} F_{n}x^{n}
= F_{0}x^{0}+ F_{1}x^{1}+ ∑_{n=2}^{∞} F_{n}x^{n}
= F_{0}x^{0}+ F_{1}x^{1}+ ∑_{n=2}^{∞}(F_{n−1} + F_{n−2} )x^{n}
= F_{0}+ F_{1}x + x ∑_{n=1}^{∞} F_{n}x^{n}+ x^{2} ∑_{n=0}^{∞} F_{n}x^{n}
= F_{0}+ F_{1}x + x ∑_{n=0}^{∞} F_{n}x^{n}− xF_{0}+ F x^{2}
= F_{0}+ F_{1}x + xF − xF_{0}+ F x^{2}
= x + xF + x^{2}F
⇒ F = \frac{x}{1 − x − x^{2}}

Hat man nun α,β,a,b ∈ ℂ gefunden mit \frac{x}{1−x−x^{2}} = \frac{a}{1−αx} + \frac{b}{1−βx} , dann gilt

∑_{n=0}^{∞} F_{n}x^{n} = \frac{a}{1 − αx} + \frac{b}{1 − βx}
= a ∑_{n=0}^{∞} α^{n}x^{n}+ b ∑_{n=0}^{∞} β^{n}x^{n}
= ∑_{n=0}^{∞}(aα^{n}+ bβ^{n})x^{n}
und somit F_{n} = aα^{n}+ bβ^{n}

Wegen \frac{x}{1−x−x^{2}} = _{\frac{x}{\frac{5}{4}−(x+ \frac{1}{2}x)^{2}}} = _{\frac{x}{(^{\frac{\sqrt{5}}{2}}−(x+ \frac{1}{2}))·(^{\frac{\sqrt{5}}{2}}+(x+ \frac{1}{2}))}} folgt mittels Partialbruchzerlegung und AfI Übung 9 Aufgabe 8:

\frac{x}{1 − x − x^{2}} = \frac{\frac{1}{\sqrt{5}}}{1 −^{\frac{1+\sqrt{5}}{2}} x} + \frac{−\frac{1}{\sqrt{5}}}{1 −^{\frac{1−\sqrt{5}}{2}} x}

also α = ^{\frac{1+\sqrt{5}}{2}} , β = ^{\frac{1−\sqrt{5}}{2}} , a = \frac{1}{\sqrt{5}}, b = −\frac{1}{\sqrt{5}}. Es folgt

F_{n} = \frac{1}{\sqrt{5}} ( \frac{1 + \sqrt{5}}{2} ) ^{n}− \frac{1}{\sqrt{5}} ( \frac{1 − \sqrt{5}}{2} ) ^{n}

1.47 Bemerkung (goldener Schnitt)

Die Zahl Φ := ^{\frac{1+\sqrt{5}}{2}} ≈ 1.61803 heißt ”goldener Schnitt“ und taucht in verschiedenen Untersuchungen auf. Beispiel 1) Einige Papierformate sind nach folgendem Schema aufgebaut:

Dies wird durch die Bedingung s\frac{s}{t} = \frac{t}{s−t} = \frac{1}{\frac{s}{t}−1} , 0 < t < s charakterisiert. Setze x:= \frac{s}{t}, dann gilt:

x = \frac{1}{x − 1}

⇔ x = \frac{1 + \sqrt{5}}{2} ∨ x = \frac{1 − \sqrt{5}}{2}

2)

\frac{1}{x} = \frac{x}{1−x} ⇔ x^{2}+ x − 1 = 0 ⇔ x = ^{\frac{−1+\sqrt{5}}{2}} ∨ x = ^{\frac{−1−\sqrt{5}}{2}} ⇒ x = ^{\frac{\sqrt{5}−1}{2}} = \frac{2}{1+\sqrt{5}} = \frac{1}{Φ} .

1.48 Satz (homogene lineare Rekursionsgleichungen zweiter Ordnung)

Sei a_{0} = b_{0}, a_{1} = b_{1} und ∀n > 1 : a_{n}= c_{1}a_{n−1} +c_{2}a_{n−2} . Ferner seien α, β zwei Lösungen von x^{2}−c_{1}x−c_{2} = 0 und

A := \{ \begin{matrix}\frac{b_{0}−b_{0}β}{α−β} & , falls α ≠ β \\ \frac{b_{1}−b_{0}α}{α} & , falls α = β \end{matrix}
B := \{ \begin{matrix}\frac{b_{1}−b_{0}α}{α−β} & , falls α ≠ β \\ b_{0} & , falls α = β \end{matrix}

Dann gilt

a_{n} = \{ \begin{matrix}Aα^{n}− Bβ^{n} & , falls α ≠ β \\ (An + B)α^{n} & , falls α = β \end{matrix}

Beweis: Induktion über n, analog zu Beweis von Beispiel 1.44 2).

♢

Schema (zum Lösen linearer Rekursionsgleichungen)

Eine lineare Rekursionsgleichung a_{n}= c_{1}a_{n−1} +c_{2}a_{n−2} +...+c_{k}a_{n−k} ∀n ≥ k mit a_{i} = b_{i}für i = 0,1,...,k− 1 kann nach folgendem Schema gelöst werden:

1) Aufstellen einer erzeugenden Funktion

A(x) = ∑_{n=0}^{∞} a_{n}x^{n}

1.5 REKURSIONSGLEICHUNGEN 31 2) Anwendung der Rekursionsformel

A(x) = a_{0}+ a_{1}x_{1}+ a_{2}x^{2}+ ...+ a_{k−1}x^{k−1} + ∑_{n=k}^{∞} a_{n}x^{n}
= b_{0}+ b_{1}x_{1}+ b_{2}x^{2}+ ...+ b_{k−1}x^{k−1} + ∑_{n=k}^{∞}(c_{1}a_{n−1} + c_{2}a_{n−1} + ...+ c_{k}a_{n−k})x^{n}
= b_{0}+ ...+ b_{k−1}x^{k−1} + \underbrace{∑_{n=k}^{∞} c_{1}a_{n−1} x^{n}}_{=c_{1}x\underbrace{∑_{n=k}^{∞} a_{n−1} x^{n−1}}_{=A(x)−∑ {k−2 \atop i=0} a_{i}x^{i}}} + \underbrace{∑_{n=k}^{∞} c_{2}a_{n−2} x^{n}}_{=c_{2}x^{2} \underbrace{∑_{n=k}^{∞} a_{n−2} x^{n−2}}_{=A(x)−∑ {k−3 \atop i=0} a_{i}x^{i}}} +...+ \underbrace{∑_{n=k}^{∞} c_{k}a_{n−k}x^{n}}_{=c_{k}x^{k} \underbrace{∑_{n=k}^{∞} a_{n−k}x^{n−k}}_{=A(x)}}

= b_{0}+ ...+ b_{k−1}x^{k−1} + c_{1}x( A(x) − ∑_{i=0}^{k−2} a_{i}x^{i}) + c_{2}x^{2}( A(x) − ∑_{i=0}^{k−3} a_{i}x^{i}) + ...+ c_{k}x^{k}A(x)

3) Auflösen nach A(x)

A(x) = \frac{d_{0}+ d_{1}x + d_{2}x^{2}+ ...+ d_{k−1}x^{k−1}}{1 − c_{1}x − c_{2}x^{2}− ...− c_{k}x^{k}}

für geeignete d_{0},...,d_{k−1}.

4) Partialbruchzerlegung (in ℂ, vgl AfI Übung 9, Aufgabe 8) Sei 1 − c_{1}x − c_{2}x^{2}− ...− c_{k}x^{k} = (1 − α_{1}x)^{m_{1}}· ...· (1 − α_{t}x)^{m_{t}} mit ∑ _{i=1}^{t} m_{i} = k. Dann gilt

A(x) = \frac{d_{0}+ d_{1}x + d_{2}x^{2}+ ...+ d_{k−1}x^{k−1}}{1 − c_{1}x − c_{2}x^{2}− ...− c_{k}x^{k}}
= \frac{g_{1}(x)}{(1 − α_{1}x)^{m_{1}}} + ...+ \frac{g_{t}(x)}{(1 − α_{t}x)^{m_{t}}}
= ∑_{i=1}^{t} \frac{g_{i}(x)}{(1 − α_{i}x)^{m_{i}}}

für geeignete Polynome g_{i} mit Grad(g_{i}) ≤ m_{i}− 1∀i = 1,...,t.

5) Nach Tabelle 4 in Bemerkung 1.42 gilt

A(x) = ∑_{i=0}^{t} \frac{g_{i}(x)}{(1 − α_{i}x)^{m_{i}}} = ∑_{i=0}^{t} g_{i}(x) ∑_{n=0}^{∞} ( \begin{matrix}n + m_{i−1} \\ m_{i−1} \end{matrix} ) (α_{i}x)^{n} = ∑_{n=0}^{∞} q_{n}x^{n}

q_{n} ist eine nicht rekursive Darstellung von a_{n} ∀n ≥ k.

♢

1.49 Beispiel

Gegeben sei folgende Rekursionsgleichung:

a_{0} = 1
a_{1} = 5
a_{2} = 19
a_{n} = 5a_{n−1} − 7a_{n−1} + 3a_{n−3} ∀n ≥ 3

Lösung: Sei A(x) = ∑ _{n=0}^{∞} a_{n}x^{n}. Dann gilt

A(x) = a_{0}+ a_{1}x + a_{2}x^{2}+ ∑_{n=3}^{∞}(5a_{n−1} − 7a_{n−2} + 3a_{n−3} )x^{n}
= a_{0}+ a_{1}x + a_{2}x^{2}+ 5x ∑_{n=3}^{∞} a_{n−1} x^{n−1} − 7x^{2} ∑_{n=3}^{∞} a_{n−2} x^{n−2} + 3x^{3} ∑_{n=3}^{∞} a_{n−3} x^{n−3}
= 1 + 5x + 19x^{2}+ 5x(A(x) − (1 + 5x)) − 7x^{2}(A(x) − 1) + 3x^{3}A(x)
⇒ A(x) = \frac{1 + x^{2}}{1 − 5x + 7x^{2}− 3x^{3}}
= \frac{1 + x^{2}}{(1 − x)^{2}· (1 − 3x)}
= \frac{\frac{1}{2}x − \frac{3}{2}}{(1 − x)^{2}} + \frac{\frac{5}{2}}{(1 − 3x)}
= \frac{1}{2}(x − 3) − \frac{1}{(1 − x)^{2}} + \frac{5}{2} \frac{1}{(1 − 3x)}
= \frac{1}{2}(x − 3) − ∑_{n=0}^{∞} ( \begin{matrix}n + 1 \\ 1 \end{matrix} ) x^{2}+ \frac{5}{2} ∑_{n=0}^{∞}(3x)^{n}
= 1 + 5x + ∑_{n=0}^{∞} ( \frac{5}{2}3^{n}− n + \frac{3}{2}) x^{n}
⇒ a_{n} = \frac{5}{2}3^{n}− n + \frac{3}{2} ∀n ≥ 2

Dieses Verfahren funktioniert auch für nicht homogene Rekursionsgleichungen.

1.50 Beispiel (Catalan-Zahlen)

Klammerketten sind Worte über dem Alphabet {(,)}, zum Beispiel (())(), () und ()((). Zulässige Klammerketten sind Klammerketten die die gleiche Anzahl von öffnenden und schließenden Klammern enthalten, und bei denen in jedem Präfix mindestens so viele öffnende wie schließende Klammern vorkommen. C_{n}:= |{c|c ist zulässige Klammerkette mit 2n Klammern}| Berechne C_{n}∀n ∈ ℕ wenn C_{0} := 1 C_{1} = 1 {()} C_{2} = 2 {()(), (())} C_{3} = 5 {()()(), ()(()), (())(), ((())), (()())}

1.51 Lemma (Rekursionsformel für Catalan-Zahlen)

C_{n} = ∑_{k=1}^{n} C_{k−1}C_{n−k} ∀n ≥ 1

Beweis Die zulässigen Klammerketten der Länge 2n können danach kategorisiert werden, wo die zur ersten öffnenden Klammer korospondierende schließende Klammer steht.

(  \overbrace{(...)}^{zulässige Klammerkette der Länge 2(k−1)} \underbrace{)}_{\begin{matrix}↑ \\ 2k \end{matrix}} \underbrace{(...)}_{zulässige Klammerkette der Länge 2(n−k)}

1.5 REKURSIONSGLEICHUNGEN 33 Sei für ein beliebiges n ∈ ℕ

A_{k} := {zulässige Klammerketten der Länge n, deren

erste Klammer an Stelle 2k geschlossen wird}.

Dann gilt |A_{k}|= C_{k−1}C_{n−k}. Es folgt

C_{n} = |⨄_{k=1}^{n} A_{k}|
= ∑_{k=1}^{n} |A_{k}|
= ∑_{k=1}^{n} C_{k−1}C_{n−k}
♢

1.52 Satz (explizite Darstellung der Catalan-Zahlen)

C_{n} = \frac{1}{(n + 1)} ( \begin{matrix}2n \\ n \end{matrix} )

Beweis:

c(x) := ∑_{n=0}^{∞} C_{n}x^{n}
⇒ c(x) = C_{0}x^{0}+ ∑_{n=1}^{∞} C_{n}x^{n}
(Lemma 1.51) = C_{0}+ ∑_{n=1}^{∞} ( ∑_{k=1}^{n} C_{k−1}C_{n−k}) x^{n}
= C_{0}+ x ∑_{n=1}^{∞} ( ∑_{k=1}^{n} C_{k−1}C_{n−k}) x^{n−1}
(t := n − 1) = C_{0}+ x∑_{t=0}^{∞} ( ∑_{k=1}^{t+1} C_{k−1}C_{t+1−k} ) x^{t}
(s:= k − 1) = C_{0}+ x∑_{t=0}^{∞} ( ∑_{s=0}^{t} C_{s}C_{t−s}) x^{t}
(Definition1.29) = C_{0}+ x(c(x) · c(x))

Somit gilt

xc^{2}(x) − x(x) = −1
x^{2}c^{2}(x) − xc(x) = −x
⇒ (xc(x) − \frac{1}{2})^{2} = \frac{1}{4} − x
⇒ xc(x) − \frac{1}{2} = ±(1 − 4x)^{\frac{1}{2}}

34 ABZÄHLUNG, REKURSION, ERZEUGENDE FUNKTIONEN

\underbrace{∑_{n=0}^{∞} C_{n}x^{n−1}}_{=0+C_{0}x+C_{1}x^{2}+...} = x\underbrace{c(x)}_{=∑ _{n=0}^{∞} C_{n}x^{n}}
= \frac{1}{2}(1 ± (1 − 4x)^{\frac{1}{2}})
(nach Tabelle 4) = \frac{1}{2}(1 ± ∑_{n=0}^{∞} ( n^{\frac{1}{2}} ) (−4x)^{n})
= \frac{1}{2}(1 ± (1 + ∑_{n=1}^{∞} ( n^{\frac{1}{2}} ) (−4)^{n}x^{n}))

Der Koeffizient von x^{0} ist 0, also gilt C_{0}+ C_{1}x^{2}+ ... = −\frac{1}{2} ∑ _{n=1}^{∞} ( n^{\frac{1}{2}} ) (−4)^{n}x^{n}

C_{n} = −\frac{1}{2} ( n + 1^{\frac{1}{2}} ) (−4)^{n+1}
= −\frac{1}{2} \frac{(\frac{1}{2} − 1) · (\frac{1}{2} − 2) · ...· (\frac{1}{2} − n)}{(n + 1)!} (−1)^{n+1} 4^{n+1}
= (−1)^{n+2} \frac{(\frac{1}{2} − 1) · (\frac{1}{2} − 2) · ...· (\frac{1}{2} − n)}{(n + 1)!} 4^{n}
= \frac{(2 − 1) · (4 − 1) · ...· (2n − 1)}{(n + 1)! · n!} 2^{n}n!
= \frac{\overbrace{1 · 3 · ...· (2n − 1) · 2 · 4 · ...· 2n}^{=(2n)!}}{(n + 1)! · n! · n!}
= \frac{1}{(n + 1)} \frac{(2n)!}{n! · n!}
= \frac{1}{(n + 1)} ( \begin{matrix}2n \\ n \end{matrix} )
♢

Schema (zum Lösen allgemeiner Rekursionsgleichungen)

1) Aufstellen der erzeugenden Funktion A(x) = ∑ _{n=0}^{∞} a_{n}x^{n}

2) Umformen, so daß Anfangswerte und Rekursionsgleichung eingesetzt werden können

3) Weiter umformen bis auf der rechten Seite die noch vorhandenen unendlichen Summen (und mit ihnen alle Vorkommen von Folgegliedern a_{n}) durch A(x) ersetzt werden können

4) Auflösen der erhaltenen Gleichung nach A(x). Dadurch erhält man eine Gleichung der Form A(x) = g(x), wobei g eine (hoffentlich einfache) Funktion ist.

5) Umschreiben der Funktion g als Potenzreihe (z.B. durch Partialbruchzerlegung und/oder Tabelle 4)

6) Ablesen der expliziten Darstellung für die a_{n} (durch Koeffizientenvergleich)

Graphentheorie

2.1 Grundbegriffe der Graphentheorie

2.1 Definition (Graph)

Ein Graph ist ein Paar G = (V,E) aus einer endlichen Menge V und einer Menge E ⊆ ( \begin{matrix}V \\ 2 \end{matrix} ) (( \begin{matrix}V \\ 2 \end{matrix} ) =

{{x,y} ⊆ V |x! = y}, vgl. Definition 1.6). Die Elemente von V heißen Ecken, Punkte oder Knoten. Der Bezeichnung V kommt aus dem englischen Begriff ”Vertices“. Die Elemente von E heißen Kanten (englisch: Edges).

Konvention: Für {x,y} ∈ E schreiben wir auch xy ∈ E

Ein Graph wird im allgemeinen als Diagramm dargestellt. Jede Ecke wird durch einen Punkt repräsentiert und zwei Punkte x, y werden genau dann durch eine Linie verbunden, wenn xy ∈ E.

2.2 Beispiel (einige Beispielgraphen)

1) G:= ({a,b,c,d},{{a,b},{b,c},{c,a},{b,d}})

2) ”Vollständige Graphen“ sind Graphen in denen jede Ecke mit jeder anderen durch eine Kante verbunden ist. Ein vollständiger Graph mit n ∈ ℕ Ecken wird mit K_{n} bezeichnet. Ist V eine n-Menge, so gilt:

K_{n}:= (V,( \begin{matrix}V \\ 2 \end{matrix} ) )

3) ”Wege“ sind Graphen G = (V,E) mit V = {v_{0},...,v_{m}}, |V |= m+1, E = {p_{1},...,p_{m}}, |E|= m und p_{i} = v_{i−1} v_{i} für alle i ∈ {1,...,m}. Ein Weg der Länge m (d.h. bestehend aus m Kanten) wird mit P_{m} bezeichnet.

Für einen Weg P_{m} schreiben wir P_{m}= p_{1}...p_{m}.

4) ”Kreise“ sind Graphen G = (V,E) mit V = {v_{1},...,v_{n}}, |V |= n, E = {p_{1},...,p_{n}}, |E|= n und p_{i} = v_{i}v_{i+1} für alle i ∈ {1,...,n − 1} sowie p_{n} = v_{n}v_{1}. Ein Kreis aus n Kanten wird mit C_{n} bezeichnet.

2.1 GRUNDBEGRIFFE DER GRAPHENTHEORIE 37 5) In ”Gittergraphen“ aus m · n Ecken werden die Ecken in m Zeilen und n Spalten angeordnet und untereinander, bzw. nebeneinander liegende Ecken durch Kanten verbunden.

6) Ein ”d-dimensionaler Hyperwürfel“ Q_{d} ist ein Graph G = (V,E) mit

V = {0,1}^{d}
E = {{x,y} ⊆ V |x = (x_{1},...,x_{d}) unterscheidet sich an genau einer Stelle von y = (y_{1},...,y_{d})}

2.3 Bemerkung (Graph, Multigraph, schlichter Graph)

1) Allgemeinere Graphen können auch Mehrfachkanten und Schlingen enthalten. Um solche Graphen zu betrachten müßte die Definition 2.1 angepaßt werden, zum Beispiel durch E = {X ⊆ V ||X|= 1 ∨ |X|= 2} um Schlingen zu erlauben.

Ein Graph mit Schlingen und Mehrfachkanten

Ein Graph ohne Schlingen heißt ”Multigraph“. Ein Multigraph ohne Mehrfachkanten heißt ”schlichter Graph“. In der Vorlesung werden nur schlichte Graphen betrachtet.

2) Im Falle G = (∅,∅) nennt man G ”leerer Graph“ und im Falle G = (E,∅) ”Nullgraph“.

3) Sei G = (V,E) ein Graph mit Kante e ∈ V.

• x und y heißen ”Endecken von e“

• e ”inzidiert“ mit den Ecken x und y

• x und y sind durch e verbunden

• x und y heißen ”benachbart“ oder ”adjazent“

2.4 Definition (Nachbarschaft, Eckengrad, regulärer Graph)

Sei G = (V,E) ein Graph mit Ecke x ∈ V.

• N_{G}(x) := {y ∈ V |xy ∈ E} heißt ”Nachbarschaft von x in G“

• d_{G}(x) := |N_{G}(x)|heißt ”Eckengrad von x in G“

– d_{G}(x) = 1 ⇔:x ist ”Endecke in G“

– d_{G}(x) = 0 ⇔:x ist ”isolierte Ecke in G“

• δ(G) := min_{x∈V}d(x) heißt ”minimaler Eckengrad von G“

• Δ(G) := max_{x∈V}d(x) heißt ”maximaler Eckengrad von G“

– gilt für einen Graphen δ(G) = Δ(G) = k, so heißt G ”k-regulärer Graph“ . So ist z.B jeder vollständige Graph K_{n} (n − 1)-regulär.

2.5 Beispiel

1) Betrachte folgenden Graphen G:

Es gilt:

N(x_{3}) = {x_{1},x_{2}x_{4}}
N(x_{1}) = {x_{2},x_{3}}
d(x_{1}) = 2 d(x_{2}) = 2 d(x_{3}) = 3
d(x_{4}) = 1 (x_{4} ist Endecke)
d(x_{5}) = 0 (x_{5} ist isolierte Ecke)
δ(G) = 0 Δ(G) = 3

2) Jeder Kreis C_{n} ist 2-regulär.

2.6 Satz (Handschlaglemma, Euler 1736)

Sei G = (V,E) ein Graph. Dann gilt:

∑_{x∈V}d(x) = 2|E|

Beweis (doppeltes Abzählen): In ∑_{x∈V}d(x) wird jede Kante yz ∈ V genau zwei mal gezählt (ein mal in d(y), zum zweiten mal in d(z)). Auf der rechten Seite wird jede Kante ebenfalls zwei mal gezählt.

♢

2.7 Folgerung

In jedem Graphen ist die Anzahl der Ecken mit ungeraden Grad gerade.

Beweis: Sei G = (V,E) und V_{1} = {x ∈ V |d(x) ungerade}, V_{2} = {x ∈ V |d(x) gerade} (⇒ V = V_{1} ⊎ V_{2}). Nach Satz 2.6 gilt:

\underbrace{2|E|}_{gerade} = \underbrace{∑_{x∈V}d(x)}_{gerade}= \underbrace{∑_{x∈V_{2}}d(x)}_{gerade}+ ∑_{x∈V_{1}}d(x)

Die Summanden in ∑_{x∈V_{1}}d(x) sind per Definition von V_{1} ungerade. ∑_{x∈V_{1}}d(x) selbst ist jedoch gerade. ∑_{x∈V_{1}}d(x) muß demnach eine gerade Anzahl an Summanden enthalten, also ist |V_{1}|gerade.

♢

40 GRAPHENTHEORIE

2.8 Lemma

Sei G = (V,E) ein Graph mit |V |≥ 2. Dann gibt es zwei Ecken x,y ∈ V mit d(x) = d(y)

Beweis: siehe Beispiel 1.13 2)

♢

2.9 Definition (Isomorphie zwischen Graphen)

Seien G = (V,E) und G′= (V′,E′) Graphen. G und G′heißen ”isomorph“ (in Zeichen G ≅ G′) genau dann wenn eine bijektive Abbildung ϕ: V → V existiert mit xy ∈ E ⇔ ϕ(x)ϕ(y) ∈ E′.

2.10 Beispiel

1) Nicht isomorphe Graphen mit 3 Ecken:

2) Werden die Namen von Ecken (und Kanten) eines Graphen berücksichtigt, so Sprich man von einem ”markierten“ oder ”benannten“ Graphen.

2.2 Darstellung von Graphen

2.11 Definition (Adjazenzmatrix, Inzidenzmatrix)

Ist G = (V,E) ein Graph mit V = {v_{1},...,v_{n}} und E = {e_{1},...,e_{m}}, so heißt die n × n-Matrix

A = (a_{ij}) ∈ {0,1}^{n×n} mit
a_{ij} = 1 ⇔ v_{i}v_{j} ∈ E

”Adjazenzmatrix von G“. Die n × m-Matrix

I = (b_{ij}) ∈ {0,1}^{n×m} mit
b_{ij} = 1 ⇔ e_{j} inzidiert mit v_{i}

heißt ”Inzidenzmatrix von G“.

2.12 Beispiel

Betrachte folgenden Graphen:

Für jede Adjazenzmatrix A eines Graphen G = (V,E) gilt:

• a_{ii} = 0 (wir betrachten nur Graphen ohne Schlingen)

• a_{ij} = a_{ji} (v_{i}v_{j} ∈ E ⇒ v_{j}v_{i} ∈ E). Für jede Inzidenzmatrix I eines Graphen G = (V,E) gilt

• Die Summe einer Spalte ist immer zwei (jede Kante inzidiert mit genau zwei Ecken)

• Die Summe einer Zeile ist gleich dem Eckengrad der jeweiligen Ecke.

I · I^{t} = ( \begin{matrix}2 & 1 & 0 & 1 \\ 1 & 3 & 1 & 1 \\ 0 & 1 & 2 & 1 \\ 1 & 1 & 1 & 3 \end{matrix} ) = A + diag(\underbrace{(d(v_{i}))_{1≤i≤n}}_{Gradfolge von G})

2.13 Satz (Zusammenhang zwischen Adjazenz- und Inzidenzmatrix)

Ist G = (V,E) ein Graph mit Adjazenzmatrix A = (a_{ij}), Inzidenzmatrix I = (b_{ij}) und Eckenmenge V = {v_{1},...,v_{n}}, dann gilt

I · I^{t} = A + diag(d(v_{1}),...,d(v_{n}))

Beweis: Fall 1 i ≠ j

(I · I^{t})_{ij} = ∑_{k=1}^{m} b_{ik}b_{jk} = \{ \begin{matrix}1 & v_{i}v_{j} ∈ E \\ 0 & sonst \end{matrix} = a_{ij}

da b_{ik} = b_{jk} = 1 ⇔ e_{k} = v_{i}v_{j} Fall 2 i = j

(I · I^{t})_{ii} = ∑_{k=1}^{m} \underbrace{b_{ik}b_{ik}}_{=\{ \begin{matrix}1 ⇔ b_{ik} = 1 \\ 0 ⇔ b_{ik} = 0 \end{matrix}} = \underbrace{∑_{k=1}^{m} b_{ik}}_{Summe i−te Zeile von I} = d(v_{i})

♢

2.14 Definition (Teilgraph, induzierter Teilgraph)

Sei G = (V,E) ein Graph und V′⊆ V.

• Der Graph G′= (V′,E′) heißt ”Teilgraph von G“ wenn E′⊆ E ∩ ( \begin{matrix}V′ \\ 2 \end{matrix}) . Man schreibt dann auch

G′⊆ G.

• G[V′] := (V′,E ∩ ( \begin{matrix}V′ \\ 2 \end{matrix}) ) heißt ”der von V′induzierte Teilgraph“.

Beispiel

G′⊆ G, G′′= G[{v_{1},v_{2},v_{3},v_{4}}]

2.15 Definition (Zusammenhang, Komponenten)

1) Sei G = (V,E) ein Graph. G heißt ”zusammenhängend“ genau dann wenn zwischen je zwei Ecken ein Weg existiert.

2) In einem (eventuell nicht zusammenhängenden) Graphen heißt jeder bezüglich der Anzahl von Ecken und Kanten maximaler zusammenhängender Teilgraph ”Komponente von G“ oder ”Zusammenhangskomponente von G“. Sind G_{1},...,G_{k} die Komponenten von G, so schriebt man auch G = ⋃ _{i=1}^{k} G_{i}. Die Anzahl der Komponenten von G wird mit κ(G) bezeichnet.

3) Sei G = (V,E) ein zusammenhängender Graph. Eine Ecke x ∈ V heißt ”Schnittecke von G“ falls G[V \ {x}] nicht zusammenhängend ist.

Eine Kante k ∈ E heißt ”Brücke“ falls (V,E \ {k}) nicht zusammenhängend ist.

Beispiel

Die Ecken 3 und 4 sind Schnittecken, die Kante {3,4} ist eine Brücke

2.16 Satz (Abschätzung der Komponenten nach unten)

Sei G = (V,E) ein Graph. Dann gilt:

κ(G) ≥ |V |− |E|

Beweis (per Induktion über |E|) Für |E|= 0 gilt

κ(G) = |V |= |V |− 0 = |V |− |E|≥ |V |− |E|

Sei nun |E|> 0, e = ab ∈ E und κ(F′) ≥ |V′|−|E′|für alle Graphen F′= (V′,E′) mit |E′|< |E|. Der Graph G′:= (V,E \ {e}) := (V,E′) hat weniger Kanten als G, somit gilt nach Induktionsvoraussetzung

κ(G′) ≥ |V |− |E \ {e}|= |V |− (|E|− 1) = |V |− |E′|

Die Anzahl der Komponenten verringert sich durch Hinzufügen der Kante e zu G′ genau dann, wenn a und b in unterschiedlichen Komponenten von G′liegen. Dann verringert sich die Anzahl der Komponenten jedoch genau um 1, da e zwei Komponenten von G′zu einer Komponente von G zusammenfaßt.

G = G′+ e ⇒ κ(G) = \{ \begin{matrix}κ(G′) & falls e keine Brücke ist \\ κ(G) − 1 & falls e Brücke ist \end{matrix}
≥ \underbrace{|V |− |E′|}_{=κ(G′)}−1

= |V |− (|E′|+ 1)
= |V |− |E|
♢

2.17 Folgerung

Sei G = (V,E) ein zusammenhängender Graph mit |V |= n und |E|= m. Dann gilt

n − 1 ≤ m ≤ ( \begin{matrix}n \\ 2 \end{matrix} )

Beweis selber machen.

2.18 Satz (Anzahl der Kanten in zusammenhängenden Graphen)

Sei G = (V,E) ein Graph mit n = |V |und m = |E|. Gilt m > \underbrace{\frac{1}{2}(n − 1)(n − 2)}_{=Anzahl der Kanten von K_{n−1}} so ist G zusam-

menhängend.

Beweis Angenommen G ist nicht zusammenhängend. Seien G_{1}...G_{k}die Komponenten von G mit |V (G_{i})⊧ n_{i}∀i = 1...k. Dann gilt k ≥ 2 und ∑ _{i=1}^{k} n_{i} = n.

m = ∑_{i=1}^{k} |E(G_{i})|

≤ ∑_{i=1}^{k} \frac{n_{i}(n_{i}− 1)}{2} (nach Folgerung 2.17)

= \frac{1}{2} ( ∑_{i=1}^{k} n_{i}^{2}− ∑_{i=1}^{k} n_{i})

= \frac{1}{2} ( \underbrace{∑_{i=1}^{k} n_{i}^{2}+ 2 ∑_{1≤i<j≤k} n_{i}n_{j}}_{=(∑ _{i=1}^{k} n_{i})^{2}=n^{2}}−2 ∑_{1≤i<j≤k} n_{i}n_{j} − \underbrace{∑_{i=1}^{k} n_{i}}_{=n})

= \frac{1}{2} ( n^{2}− 2 ∑_{1≤i<j≤k} n_{i}n_{j} − n)

≤ \frac{1}{2} (n^{2}− 2n_{1}(n_{2}+ n_{2}+ ...+ n_{k}) − n)
≤ \frac{1}{2} (n^{2}− 2(n − 1) − n)
= \frac{1}{2} (n^{2}− 3n + 2)
= \frac{1}{2}(n − 1)(n − 2)

Zusammenfassend:

G nicht zusammenhängend ⇒ m(G) ≤ \frac{1}{2}(n − 1)(n − 2) also auch
G zusammenhängend ⇒ m(G) > \frac{1}{2}(n − 1)(n − 2)
♢

2.19 Satz (Abschätzung der Kanten nach oben)

Ist G = (V,E) ein Graph mit |V |= n und |E|= m, so gilt

m ≤ ( \begin{matrix}n − κ(G) + 1 \\ 2 \end{matrix} )

Beweis (siehe auch Lutz Volkmann: ”Diskrete Strukturen“ Satz 3.6)

Die Idee des Beweises ist, herauszufinden wann m maximal ist. Ohne Beschränkung der Allgemeinheit können alle Komponenten von G als vollständig angenommen werden, da dies keine Auswirkung auf

( \begin{matrix}n − κ(G) + 1 \\ 2 \end{matrix} ) hat, die Anzahl der Kanten jedoch nicht weniger wird. Die Anzahl der Kanten von G

kann nun weiter erhöht werden indem man zwei Komponenten G[V_{1}] und G[V_{2}] mit |V_{1}|≤ |V_{2}|und v ∈ V_{1}

ersetzt durch zwei Komponenten G_{1} = (V_{1} \ \{v\},( \begin{matrix}V_{1}\ \{v\} \\ 2 \end{matrix}) ) und G_{2} = (V_{2} ∪ \{v\},( \begin{matrix}V_{2}∪ \{v\} \\ 2 \end{matrix} ) ). Da-

durch werden zwar |V_{1}|− 1 Kanten aus G entfernt, allerdings werden auch |V_{2}|Kanten hinzugefügt, insgesamt erhöht sich dadurch die Anzahl der Kanten. Die Anzahl der Komponenten sowie die der Ecken bleibt jedoch konstant. Die Anzahl der Kanten wächst durch wiederholtes Ersetzen solange bis G aus einem vollständigen Graphen mit n − κ(G) + 1 Ecken und κ(G) − 1 isolierten Ecken besteht, und ist dann

maximal. In diesem Fall gilt jedoch m = ( \begin{matrix}n − κ(G) + 1 \\ 2 \end{matrix} )

♢

Bemerkung Aus Satz 2.19 folgt unmittelbar Satz 2.18.

2.3 Bäume

Abbildung 4: Dateisystem eines UNIX Systems als Baum

2.20 Definition (Baum, Wald)

Ein ”Baum“ ist ein zusammenhängender Graph ohne Kreise. Ein ”Wald“ ist ein Graph dessen Komponenten Bäume sind.

2.21 Lemma (Endecken in Bäumen)

Eine Endecke eines Graphen G = (V,E) ist eine Ecke x ∈ V mit d(x) = 1. Jeder Baum T = (V,E) mit |V |≥ 2 enthält mindestens 2 Endecken.

Beweis Sei P = v_{1}...v_{k} ein längster Weg in T. Angenommen es existiert ein v ∈ V so daß v_{k}v ∈ E. Dann ist v ∉ {v_{1},...,v_{k−2}} da aus v = v_{i} für ein i ∈ {1,...,k −2} folgt v_{i}...v_{k}v_{i} ist ein Kreis. Außerdem gilt auch nicht v ∈ V \{v_{1},...,v_{k}} da in diesem Fall v_{1}...v_{k}v ein Weg wäre der länger als P ist. Es folgt also v = v_{k−1} und somit d(v_{k}) = 1, womit v_{k} eine Endecke ist. Analog zeigt man daß v_{1} ebenfalls Endecke ist.

♢

2.22 Satz (Charakterisierung von Bäumen)

Sei G = (V,E) ein Graph mit |V |= n und |E|= m. Folgende Aussagen sind äquivalent:

(1) G ist ein Baum

(2) G ist zusammenhängend und kreisfrei

(3) G ist zusammenhängend und m = n − 1 (4) G ist kreisfrei und m = n − 1

(5) zwischen zwei Ecken von G existiert genau ein Weg

(6) G ist maximal kreisfrei (d.h durch Hinzufügen einer weiteren Kante entsteht ein Kreis)

(7) G ist minimal zusammenhängend (d.h durch Herausnehmen einer Kante zerfällt G in zwei Komponenten)

Beweis Üblicherweise werden Beweise dieser Art geführt daß man zeigt (1) ⇒ (2) ⇒ (3) ⇒ (4) ⇒ (5) ⇒

(6) ⇒ (7) ⇒ (1). Hier bietet es sich jedoch an, zu zeigen daß (2) ⇔ (1) ⇒ (3) ⇒ (4) ⇒ (5) ⇒ (6) ⇒ (7) ⇒ (2)

(2) ⇔ (1) folgt unmittelbar aus der Definition von Bäumen. Wir zeigen deshalb nur exemplarisch (1) ⇒ (3) (per Induktion über n).

Induktionsanfang: Für n = 2 gilt m = 1 = 2 − 1 = n − 1.

Induktionsschluß: Sei n ≥ 2 und für alle Bäume T′= (V′,E′) mit |V′|= n gelte |E′|= |V′|− 1. Sei T = (V,E) ein Baum mit |V |= n+1 und x eine Endecke von G (eine Endecke existiert nach Lemma 2.21). G− x:= G[V \ {x}] ist ein Baum mit genau n Ecken und somit gilt nach Induktionsvoraussetzung |E(G − x)| = n − 1. Durch Hinzufügen von x zu G − x wird auch genau eine Kante zu G − x hinzugefügt (d(x) = 1) und somit gilt |E(G)|= |E(G − x)|+ 1 = (n − 1) + 1 = (n + 1) − 1

♢

2.23 Definition (Wurzelbaum)

Ein ”Wurzelbaum“ T = (V,E) ist ein Baum in dem eine Ecke w ∈ V als Wurzel ausgezeichnet ist.

Sei T = (V,E) ein Wurzelbaum mit Wurzel w und x eine Ecke von T.

• Jede Ecke y auf dem Weg von w nach x heißt ”Vorgänger von x“ (es existiert genau ein Weg von w nach x, da T ein Baum ist).

• Ist y Vorgänger von x und ist x ≠ y, so heißt y ”Nachfolger von x“.

• Ist y Nachfolger von x und gilt yx ∈ E, so heißt y ”unmittelbarer Nachfolger von x“ und x heißt ”unmittelbarer Vorgänger von y“.

• Ein ”geordneter Baum“ ist ein Wurzelbaum in dem für die unmittelbaren Nachfolger jeder Ecke eine Ordnung festegelegt ist.

2.24 Definition (Tiefe)

Die Tiefe depth(T) eines Wurzelbaumes T ist die maximale Länge eines Weges von der Wurzel zu einer Endecke.

Ein Wurzelbaum T mit der Tiefe t heißt ”balanciert“ wenn jeder Weg von einer Endecke zu der Wurzel die Länge t oder t − 1 hat.

Beispiel Ein Fußballturnier mit 7 Mannschaften

Ein balancierter Baum der Tiefe 3

2.25 Definition (binärer Baum)

Ein Wurzelbaum heißt ”binärer Baum“ wenn jede Ecke höchstens zwei unmittelbare Nachfolger hat. Ein balancierter binärer Baum in dem jede Ecke entweder keine oder 2 Nachfolger hat, heißt ”vollständiger binärer Baum“.

2.26 Satz (Anzahl der Ecken in binären Bäumen)

Sei T = (V,E) ein binärer Baum mit Tiefe t und |V |= n. Dann gilt

t + 1 ≤ n ≤ 2^{t+1} − 1.

Beweis Sei p_{k}:= Anzahl der Ecken die von der Wurzel die Entfernung k haben. Es gilt ∑ _{k=0}^{t} p_{k} = n. Da für binäre Bäume weiterhin gilt 1 ≤ p_{k} ≤ 2p_{k−1} ∀1 ≤ k ≤ t und p_{0} = 1, folgt ∑ _{k=0}^{t} 1 ≤ ∑ _{k=0}^{t} p_{k} ≤ ∑ _{k=0}^{t} 2p_{k}, und somit t + 1 ≤ n ≤ 2^{t+1} − 1.

♢

2.27 Folgerung (Tiefe von binären Bäumen)

Sei T = (V,E) ein binärer Wurzelbaum mit Tiefe t und |V |= n. Dann gilt

t ≥ ⌈lg_{2} \frac{n + 1}{2} ⌉

Beweis Übung

2.28 Definition (Gerüst eines Graphen)

Ein Teilgraph T eines zusammenhängenden Graphen G heißt ”Gerüst von T “ (oder spannender Baum oder Baumfaktor) wenn T ein Baum ist und V (T) = V (G).

Beispiel

Ein Graph und 2 seiner Gerüste

2.29 Satz (Existenz von Gerüsten)

Jeder zusammenhängende Graph enthält ein Gerüst.

Beweis Sei G = (V,E) ein zusammenhängender Graph.

Enthält G keinen Kreis, dann ist T ein Baum. Setzte T = G. T ist ein Baum mit V (T) = V (G), also ist T ein Gerüst von G.

Enthält G eine Kreis dann entferne aus einem Kreis C = v_{0}v_{1}...v_{k}v_{0} eine beliebige Kante, z.B G′ = (V,E \ {v_{i}}). G′ ist dann immer noch zusammenhängend, da alle Wege die v_{i} als Kannte enthalten über v_{i+1} ...v_{k}v_{0}...v_{i−1} umgelenkt werden können. Wiederholt man dieses Entfernen so lange bis kein Kreis mehr enthalten ist, so ist der resultierende Graph ein Baum der aus allen Ecken von G besteht, also ein Gerüst von G.

♢

Algorithmus 1 Breitensuche (BFS: Breadth-First-Search)

Algorithmus 2 Tiefensuche (DFS: Depth-First-Search)

Beide Algorithmen haben Laufzeit O(|V |+ |E|)

Im Computer benutzt man auch gerne ein andere Darstellung von Graphen, die Darstellung als Adjazenzliste.

Adjazenzmatrix  Adjazenzliste
Speicherverbrauch  O(|V |^{2})  O(|V |+ |E|)
Test ob xy ∈ E  O(1)  O(min{d(x),d(y)})
Bestimmen von N(x)  O(|V |)  O(d(x))

Tabelle 5: Komplexität von Graphenoperationen

2.30 Satz (Cayley’s Tree Formula)

Sei G ein vollständiger markierter Graph mit n ≥ 2 Ecken. Dann besitzt G n^{n−2} verschieden Gerüste.

Beweis folgt

2.4 Matching in Graphen

2.31 Definition (Matching)

Sei G = (V,E) ein Graph. Ein ”Matching von G“ ist eine Kantenmenge M ⊆ E mit ∀k_{1} ≠ k_{2} ∈ M : V (k_{1}) ∩ V (k_{2}) = ∅, d.h. M ist eine Kantenmenge in der keine zwei Kanten inzident sind.

• Ein Matching M von G heißt ”maximales Matching“, wenn es in G kein Matching M′gibt mit M ⊂ M′.

• Ein Matching M von G heißt ”Maximum-Matching“, wenn es in G kein Matching M′gibt mit |M|< |M′|.

• Ein Matching M von G heißt ”perfektes Matching“ wenn V (M) = V (G).

2.32 Beispiel 2.33 Bemerkung

1) Jedes perfekte Matching ist ein Maximum-Matching.

2) Für jedes Matching M gilt |V (M)⊧ 2|M|.

3) Für jedes perfektes Matching M von G gilt 2|M|= V (G).

4) G hat ein perfektes Matching ⇒ V (G) ist gerade.

2.34 Bemerkung (bipartite Graphen)

Ein Graph G = (V,E) heißt ”bipartit“ wenn man V so in zwei dijunkte Teilmengen A und B zerlegen kann, daß G[A] und G[B] Nullgraphen sind.

• A und B heißen Partitionsmengen.

• Ein vollständiger bipartiter Graph K_{pq} ist ein bipartiter Graph G = (A⊎B,E) mit |A|= p, |B|= q und ∀x ∈ A: ∀y ∈ B: xy ∈ E.

2.35 Beispiel

Grafiken fehlen.

2.36 Satz (Biparität und Kreise)

Ein Graph G ist genau dann bipartit wenn G keine Kreise ungerader Länge hat.

Beweis Sei G = (A ⊎ B,E) ein bipartiter Graph mit einem Kreis ungerader Länge C = (v_{0}...v_{2k}v_{0}). Weiterhin gelte (o.B.d.A.) v_{0} ∈ A.

v_{i} und v_{i+1(mod 2k+1)} können nicht in der selben Partitionsmenge sein, da v_{i} und v_{i+1(mod 2k+1)} adjanzent sind, der durch diese Partitionsmenge induzierte Teilgraph wäre also kein Nullgraph. Somit gilt:

v_{0} ∈ A ⇒ v_{1} ∈ B
⇒ v_{2} ∈ A
⇒ ...
⋮
⇒ v_{2k−1} ∈ B
⇒ v_{2k} ∈ A
⇒ v_{0} ∈ B

was offensichtlich ein Widerspruch ist. Ein bipartiter Graph kann also keinen Kreis ungerader Länge enthalten.

Sei nun G = (V,E) ein Graph ohne Kreise ungerader Länge mit a ∈ V. Definiere

A := {v ∈ V |der kürzeste Weg von v nach a hat gerade Länge}
B := {v ∈ V |der kürzeste Weg von v nach a hat ungerade Länge}

Offensichtlich gilt A ∩ B = ∅ und A ∪ B = V, somit genügt es zu zeigen:

v_{1} ∈ A ∧ v_{2} ∈ A ⇒ v_{1}v_{2} ∉ E
v_{1} ∈ B ∧ v_{2} ∈ B ⇒ v_{1}v_{2} ∉ E

Angenommen es gibt eine Kante uv ∈ E mit u ∈ A und v ∈ A. Sei dann P_{au} ein kürzester Weg von a nach u und W_{av} ein kürzester Weg von a nach v. Ferner sei y die letzte gemeinsame Ecke von P_{au} und W_{av} (P_{au} = P_{ay}+P_{yu}, W_{av}= P_{ay}+W_{yv}wie in Abbildung 5) Bezeichnet man die Länge eines Weges W mit L(W),

Abbildung 5: Kürzeste Wege

so gilt:

L(P_{au}) + L(W_{av}) = 2L(P_{ay}) + L(P_{yu}) + L(W_{yv})

L(P_{au}) + L(W_{av}) ist nach Konstruktion gerade, ebenso ist 2L(P_{ay}) gerade. Demnach muß auch L(P_{yu}) + L(W_{yv}) gerade sein. P_{yu}+W_{yv}+uv bildet dann aber einen Kreis ungerader Länge. Da solche aber in G nach Vorraussetzung nicht existieren ist uv ∉ E. G ist also ein bipartiter Graph mit Partitionsmengen A und B.

♢

2.37 Satz (Matchings in bipartiten Graphen)

Sei G = (A⊎B,E) ein bipartiter Graph. G besitzt ein Matching M mit |M|= |A|genau dann wenn ∀S ⊆ A: |N(S)|≤ |S|.

Beweis fehlt

2.38 Folgerung

Sei G = (A ⊎ B,E) ein r-regulärer bipartiter Graph mit r ≥ 1, so enthält G ein perfektes Matching.

Beweis Es gilt |A|= |B|, sowie ∀S ⊆ A: |N(S)|≥ |S|. Aus Satz 2.37 folgt dan die Behauptung.

2.39 Folgerung

Ein r-regulärer bipartiter Graph läßt sich in r kantendisjunkte perfekte Matchings zerlegen.

Beweis sukzessives Anwenden von Folgerung 2.38

2.40 Definition (Multipartite Graphen)

Ein Graph G = (V,E) heißt ”k-partit“ (allgemein auch ”multipartit“), wenn man V so in k disjunkte Teilmengen V_{1},...,V_{k} zerlegen kann, daß G[V_{i}] für i ∈ {1,...,k} Nullgraphen sind.

2.5 Hamilton Graphen

2.41 Definition (Hamiltonkreis, Hamilton-Weg)

Sei G = (V,E) ein Graph.

• Ein ”Hamiltonkreis“ ist ein Kreis C mit V (C) = V (G). Ein Graph der einen Hamiltonkreis enthält heißt ”hamiltonscher Graph“.

• Ein ”Hamilton-Weg“ ist ein Weg W mit V (W) = V (G). Ein Graph der einen Hamilton-Weg enthält heißt ”semi-hamiltonscher Graph“

2.42 Beispiel

1) K_{n} ist hamiltonsch für n > 2.

2) D_{20} ist hamiltonsch.

3) Der Peterson-Graph ist nicht hamiltonsch, aber semi-hamiltonsch.

2.43 Satz (notwendige Bedingung für hamiltonsche Graphen)

Sei G = (V,E) ein hamiltonscher Graph. Dann gilt für jede nicht leere Menge S ⊆ V

κ(G − S) ≤ |S|

Beweis Ist G selbst ein Kreis, so erhält man einen Weg durch Herausnemen einer Ecke. Sukzessives Herausnemen weiterer Ecken erhöht die Anzahl der Komponenten jeweils höchstens um 1 (pro Ecke). Entfernt man also p Ecken, so erhält man höchstens p Komponenten.

Ist G kein Kreis, so ist die Anzahl der erhaltenen Komponenten sogar noch geringer, da es mehr Kanten gibt, die den Graphen zusammenhalten.

♢

2.44 Satz (Lemma von Ore, 1960)

Sei G = (V,E) ein Graph mit |V |= n. Ferner seien u und v zwei nicht adjazente Ecken von G mit d(u) + d(v) ≥ n. Dann gilt

G ist hamiltonsch ⇔ G + uv ist hamiltonsch

Beweis^{1} ”⇒“: trivial (durch Hinzufügen von Kanten zu einem hamiltonschen Graphen geht der Hamiltonkreis nicht verloren)

”⇐“: Existiert ein Hamiltonkreis von G der nicht die Kante uv enthält, so ist offensichlich auch G hamiltonsch.

Da jedoch G + uv hamiltonsch ist existiert in G ein Hamilton-Weg (u,x_{1},...,x_{n−2} ,v). Sei nun S := {i ∈ {1,...,n−3}|ux_{i+1} ∈ E} und T := {i ∈ {1,...,n−3}|x_{i}v ∈ E}. Wegen 1 ≤ |S|≤ n−3 und 1 ≤ |T |≤ n−3 und d(u) + d(v) ≥ n gilt S ∩ T ≠ ∅. Also existiert ein p ∈ {1,...,n − 3} mit ux_{p+1} ∈ E und x_{p}v ∈ E. Dann ist aber auch (u,x_{1},...x_{p},v,x_{n−2} ,...x_{p+1} ,u) ein Hamiltonkreis.

♢

1Der Beweis der Vorlesung ging etwas anders, den hab ich aber nicht verstanden

2.45 Folgerung (hinreichende Bedingung für hamiltonsche Graphen)

Sei G = (V,E) ein Graph mit |V |= n ≥ 3 in dem für alle Ecken u und v gilt d(u) + d(v) ≥ n, so ist G hamiltonsch.

Beweis Nach Satz 2.44 kann man zu dem Graphen G Kanten hinzufügen ohne dabei zu verändern ob der resultierende Graph hamiltonsch ist oder nicht. Man fügt Kanten solange hinzu bis der vollständige Graph K_{n} entstanden ist, welcher offensichlich hamiltonsch ist.

2.46 Folgerung (Dirac, 1052)

Sei G = (V,E) ein Graph mit |V |= n und d(v) ≥ \frac{n}{2}∀v ∈ V. Dann ist G hamiltonsch.

Beweis Wegen d(v) ≥ \frac{n}{2}∀v ∈ V gilt auch für ∀u ≠ v: d(u)+d(v) ≥ \frac{n}{2}+ \frac{n}{2} = n womit die Voraussetzungen von Folgerung 2.45 erfüllt sind.

2.47 Bemerkung

1) Eine bekannte Anwendung ist das Travelling Salesman Problem (TSP). Darin geht es darum in einem gewichteten Graphen (ein Graph in dem die Kanten mit Kosten belegt sind) einen günstigsten Hamiltonkreis zu finden. TSP benötigt exponentielle Laufzeit, es existieren jedoch effiziente Heuristiken die zwar nicht unbedingt den besten, denoch aber einen recht preiswerten Hamiltonkreis finden.

2) Das Entscheidungsproblem ob ein Graph einen Hamiltonkreis enthält ist NP-vollständig, das heist es kann in polynomieller Zeit entschieden werden ob ein Lösungskandidat (in diesem Fall eine Folge von Ecken) ein korrekte Lösung ist (also ein Hamiltonkreis), eine korrekte Lösung kann allerdings nach dem gegenwärtigen Stand der Forschung in polynomieller Zeit nicht gefunden werden.

2.6 Eulersche Graphen

2.48 Definition

2.49 Definition

2.50 Beispiel

2.51 Satz

54 GRAPHENTHEORIE

2.52 Folgerung 2.53 Bemerkung

2.7 Planare Graphen

2.54 Definition 2.55 Satz 2.56 Satz 2.57 Beispiel 2.58 Definition 2.59 Satz 2.60 Definition 2.61 Beispiel 2.62 Satz

2.8 DIGRAPHEN 55

2.63 Bemerkung

2.8 Digraphen

2.64 Definition 2.65 Definition 2.66 Definition 2.67 Definition 2.68 Satz 2.69 Satz 2.70 Bemerkung

56 GRAPHENTHEORIE

Algebraische Strukturen

In diesem Kapitel werden, wie in der Linearen Algebra, Körper, Ringe, Gruppen, etc. vorgestellt, allerdings in einer umgekehrter Reihenfolge.

3.1 Universelle Algebren

Allgemein ist einer Algebra ein Menge auf der Operationen definiert sind.

3.1 Definition (Operation, Stelligkeit)

Sei M eine Menge.

• Eine Abbildung f : M^{n} → M heißt ”n-stellige Operation auf M“ oder auch ”n-stelliger Operator auf M“.

• s(f) := n heißt ”Stelligkeit von f“.

• Eine zweistellige Operation f : M × M → M heißt auch ”Verknüpfung auf M“ (englisch: ”binary operation“).

3.2 Definition (Algebra, Signatur)

Sei M eine Menge und für i ∈ I sei f_{i} eine n_{i}-stellige Operation auf M.

• (M,(f_{i})_{i∈I}) heißt ”universelle Algebra vom Typ (n_{i})_{i∈I}“.

• (n_{i})_{i∈I} heißt ”Signatur der Algebra (M,(f_{i})_{i∈I})“.

3.3 Beispiel

1) Die boolsche Algebra ({T,F},(∧,∨,¬)) ist einer universelle Algebra mit Signatur (2,2,1).

x_{1} x_{2} x_{1}∧ x_{2} x_{1}∨ x_{2} ¬x_{1} ¬x_{2}
F F  F  F  T  T
F T  F  T  T  F
T F  F  T  F  T
T T  T  T  F  F

Tabelle 6: Wahrheitstabelle 2) Mit den üblichen arithmetischen Operationen wie ”+“ und ”·“ können folgende Algebren definiert werden:

• (ℕ,+), (ℕ,+,·)

• (ℤ,·)

• ({x ∈ ℕ|∃n ∈ ℕ: n^{2} ∈ ℕ},·) = ({n^{2}|n ∈ ℕ},·)

x = a^{2}, y = b^{2} ⇒ x · y = a^{2}· b^{2} = ab · ab = (ab)^{2}, also ·: M × M → M

({n^{2}|n ∈ ℕ},+) ist keine Algebra, da z.B 2^{2}+ 3^{2} = 13 ≠ x^{2}∀x ∈ ℕ

3) Sei Σ eine endliche Menge (ein Alphabet) und Σ^{∗}:= {(a_{1}...a_{n})|n ∈ ℕ_{0},a_{i} ∈ Σ∀i = 1...n} eine formale Sprache. Ferner sei ∘: Σ^{∗}× Σ^{∗} → Σ^{∗}mit (a_{1}...a_{n}) ∘ (b_{1}...b_{m}) = (a_{1}...a_{n}b_{1}...b_{m}).

Dann ist (Σ^{∗},∘) eine universelle Algebra.

4) Sei U eine Menge und F (U) = {f : U → U} die Menge aller Funktionen von U nach U. Ferner sei ∘ die übliche Komposition von Funktionen: (f ∘ g)(x) = f(g(x))∀x ∈ U.

Dann ist (F (U),∘) eine universelle Algebra auf F (U).

3.4 Definition (neutrale Elemente)

Sei (M,∘) eine 2-stellige Algebra.

• Ein Element e ∈ M heißt ”linksneutrales Element für den Operator ∘“ falls gilt ∀a ∈ M : e ∘ a = a.

• Ein Element e ∈ M heißt ”rechtsneutrales Element für den Operator ∘“ falls gilt ∀a ∈ M : a ∘ e = a.

• Ein Element e ∈ M heißt ”neutrales Element für den Operator ∘“ falls e sowohl links- als auch rechts-

neutral ist.

e ∘ a = a ∘ e = a ∀a ∈ M

3.5 Beispiel

Sei ({b,c},∘) eine universelle Algebra mit ∘ definiert durch Tabelle 7.

\begin{matrix}∘ & b & c \\ b & b & b \\ c & c & c \end{matrix}

Tabelle 7: Wertetabelle von ∘

Es gilt:

b ∘ b = b ∧ c ∘ b = c ⇒ b ist rechtsneutral
b ∘ c = b ∧ c ∘ c = c ⇒ b ist rechtsneutral

Wegen c ∘ b = c ist c nicht linksneutral, wegen b ∘ c = b ist b nicht linksneutral.

3.6 Lemma (Existenz und Eindeutigkeit neutraler Elemente)

Sei (M,∘) eine universelle Algebra vom Typ (2). Ist c ∈ M linksneutral und d ∈ M rechtsneutral, so gilt c = d. Insbesonders gilt: (M,∘) enthält höchstens ein neutrales Element.

3.1 UNIVERSELLE ALGEBREN 59

Beweis:

\begin{matrix}c linksneutral & ⇒ & c ∘ d & = & d \\ d rechtsneutral & ⇒ & c ∘ d & = & c \end{matrix} \} ⇒ c = d

Seien nun e_{1} und e_{2} neutrale Elemente von (M,∘) bezüglich ∘. Dann ist insbesonders auch e_{1} linksneutral. Ebenso ist e_{2} rechtsneutral, und somit e_{1} = e_{2}.

♢

3.7 Beispiel (Fortsetzung von Beispiel 3.3)

• (ℕ,+) hat neutrales Element 0.

• (ℤ,·) hat neutrales Element 1.

• (ℕ,+,·) hat neutrale Elemente 0 (bezüglich +) und 1 (bezüglich ·)

3.8 Definition (inverse Elemente)

Sei (M,∘) eine universelle Algebra vom Typ (2) mit neutralem Element e.

• x ∈ M heißt ”Linksinverses“ von a ∈ M falls x ∘ a = e.

• x ∈ M heißt ”Rechtsinverses“ von a ∈ M falls a ∘ x = e.

• x ∈ M heißt ”Inverses“ von a ∈ M falls x Links- und Rechtsinverses von a ist.

Aufgabe: Eindeutigkeit von Inversen.

3.9 Definition (Halbgruppe)

Eine universelle Algebra A = (M,∘) vom Typ (2) heißt ”Halbgruppe“ falls ∘ assoziativ ist, d.h ∀a,b,c ∈ M : (a ∘ b) ∘ c = a ∘ (b ∘ c).

Beispiel: (Σ^{∗},∘) aus Beispiel 3.3 ist eine Halbgruppe.

3.10 Definition (Monoid)

Ein ”Monoid“ A = (M,∘) ist eine universelle Algebra vom Typ (2) mit

M1: (M,∘) ist eine Halbgruppe (d.h. ∘ ist assoziativ) M2: (M,∘) hat ein neutrales Element

3.11 Definition (Gruppe)

Eine ”Gruppe“ ist eine universelle Algebra vom Typ (2) mit

G1: (M,∘) ist eine Halbgruppe (d.h. ∘ ist assoziativ) G2: (M,∘) hat ein neutrales Element G3: Zu jedem a ∈ M existiert ein inverses Element in M 60 ALGEBRAISCHE STRUKTUREN

3.12 Definition (abelsche Algebren)

Eine Halbgruppe (Moniod, Gruppe, ...) (M,∘) heißt ”abelsch“ falls ∘ kommutativ ist, d.h. wenn ∀a,b ∈ M: a ∘ b = b ∘ a.

3.13 Definition (Ring)

Ein ”Ring“ ist eine universelle Algebra A = (M,⊕,⊙) vom Typ (2,2) mit

R1: (M,⊕) ist eine abelsche Gruppe (das neutrale Element dieser Gruppe wird mit ”0“ bezeichnet). R2: (M,⊙) ist ein Monoid (das neutrale Element dieses Monoids wird mit ”1“ bezeichnet). R3: Es gelten folgende Distributivgesetze:

(b ⊕ c) ⊙ a = (b ⊙ a) ⊕ (c ⊙ a)
a ⊙ (b ⊕ c) = (a ⊙ b) ⊕ (a ⊙ c)

3.14 Definition (Körper)

Ein ”Körper“ ist eine universelle Algebra A = (M,⊕,⊙) vom Typ (2,2) mit

K1: (M,⊕) ist eine abelsche Gruppe (das neutrale Element dieser Gruppe wird mit ”0“ bezeichnet) K2: (M \ {0},⊙) ist eine abelsche Gruppe (das neutrale Element dieser Gruppe wird mit ”1“ be-

zeichnet)

K3: Es gilt das Distributivgesetz a ⊙ (b ⊕ c) = (a ⊙ b) + (a ⊙ c)

Beispiel: (ℚ,+,·), (ℝ,+,·) und (ℂ,+,·) sind Körper.

3.15 Definition (boolsche Algebra)

Eine ”boolsche Algebra“ ist eine universelle Algebra A = (M,⊕,⊙,¬) vom Typ (2,2,1) mit

B1: (M,⊕) ist ein abelsches Monoid (mit neutralem Element 0) B2: (M,⊙) ist eine abelsches Monoid (mit neutralem Element 1) B3: ∀a ∈ M : a ⊕ (¬a) = 1

∀a ∈ M : a ⊙ (¬a) = 0

B4: a ⊙ (b ⊕ c) = (a ⊙ b) ⊕ (a ⊙ c)

a ⊕ (b ⊙ c) = (a ⊕ b) ⊙ (a ⊕ c)

3.16 Beispiel

1) (ℤ,+,·) ist ein kommutativer Ring, d.h. (ℤ,+,·) ist ein Ring und es gilt ∀a,b ∈ ℤ: a · b = b · a 3.2 UNTERALGEBREN, HOMOMORPHISMEN, KONGRUENZEN 61

2) Sei K ein Körper.

• K[x] := {∑ _{k=0}^{n} a_{k}x^{k}|n ∈ ℕ_{0},∀i = 1...n: a_{i} ∈ K} ist ein kommutativer Ring (Polynomring)

• K[[x]] := {∑ _{k=0}^{∞} a_{k}x^{k}|∀i = 1...n: a_{i} ∈ K} ist ein kommutativer Ring (siehe auch Satz 1.32)

• K^{n×n} := \{ ( \begin{matrix}a_{11} & ··· & a_{1n} \\ ⋮ & ... & ⋮ \\ a_{n1} & ··· & a_{nn} \end{matrix} ) |∀1 ≤ i,j ≤ n: a_{ij} ∈ K\} ist ein Ring. Für n > 1 ist dieser Ring nicht

kommutativ.

3) ℚ, ℝ und ℂ sind Körper.

4) Der kleinste Ring besteht lediglich aus der Null. ({0},⊕,⊙) ist ein Ring mit ⊕ = ⊙ und 1 = 0. Der kleinste Körper ist ({0,1},⊕,⊙) definiert durch Tabelle 8. Diese Körper wird mit 𝔽_{2} bezeichnet.

\begin{matrix}x & y & x ⊕ y & x ⊙ y \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{matrix}

Tabelle 8: Multiplikations- und Additionstabelle für ({0,1},⊕,⊙)

Konvention: Sei (K,⊕,⊙) ein Körper.

• Das neutrale Element bezüglich ⊕ wird mit 0 bezeichnet.

• Das neutrale Element bezüglich ⊙ wird mit 1 bezeichnet.

• Das inverse Element von a ∈ K bezüglich ⊕ wird mit −a bezeichnet.

• Das inverse Element von a ∈ K bezüglich ⊙ wird mit a^{−1} bezeichnet.

3.2 Unteralgebren, Homomorphismen, Kongruenzen

Es sei A = (A,(f_{i})_{i∈I}) eine Algebra vom Typ T = (n_{i})_{i∈I} für eine Indexmenge I.

3.17 Definition (Unteralgebra)

U ⊆ A heißt ”Unteralgebra von A“ (geschrieben U ≤ A), falls die Operationen (f_{i})_{i∈I} in U abgeschlossen sind, d.h. ∀i ∈ I : f(U^{n_{i}}) ⊆ U (anders gesagt ∀i ∈ I : ∀u_{1}...u_{n_{i}} ∈ U : f_{i}(u_{1},...,u_{n_{i}}) ∈ U).

3.18 Definition (Untergruppe, Teilring)

• Sei G = (G,⊙) eine Gruppe.

Eine ”Untergruppe von G“ ist eine Unteralgebra von G die eine Gruppe ist.

• Sei R = (R,⊕,⊙) ein Ring.

Ein ”Teilring von R“ ist eine Unteralgebra von R, die ein Ring ist.

62 ALGEBRAISCHE STRUKTUREN

3.19 Beispiel

1)

• (ℤ,+,·) ≤ (ℚ,+,·) ≤ (ℝ,+,·) ≤ (ℂ,+,·) sind Teilringe von (ℂ,+,·)

• (ℤ,+) ≤ (ℚ,+) ≤ (ℝ,+) ≤ (ℂ,+) sind Untergruppen von (ℂ,+)

2) Sei Z_{n}:= {0,...,n − 1} und +_{n}: ℕ × ℕ → Z_{n} eine Operation auf Z_{n} mit a +_{n}b = a + b(mod n). (Z_{n},+_{n}) ist eine Gruppe, jedoch keine Untergruppe von ℤ. Gegenüber (ℤ,+) hat sich die Operation geändert. Beispiel: 3 +_{5}6 = 9(mod5) = 4 aber 3 + 6 = 9.

3.20 Lemma (Abgeschlossenheit von Unteralgebren bezüglich Durchschnitt)

Sei J eine Indexmenge und ∀j ∈ J : U_{j} ≤ A. Dann gilt

⋂_{j∈J} U_{j} ≤ A

3.21 Definition (erzeugte Unteralgebra)

Sei M eine Teilmenge einer Algebra A. Dann heißt

⟨M⟩:= ⋂_{U≤A mit M⊆U} U

die ”von M erzeugte Unteralgebra“.

3.22 Beispiel

1) Sei G = (G,⊙) eine Gruppe und g ∈ G.

⟨g⟩:= ⟨{g}⟩= {g^{i}|i ∈ ℤ}

ist die von g erzeugte Untergruppe. Dabei ist

g^{i} := \{ \begin{matrix}\overbrace{g ⊙ ...⊙ g}^{i mal} & falls i > 0 \\ 1 & falls i = 0 \\ \underbrace{g^{−1} ⊙ ...⊙ g^{−1}}_{−i mal} & falls i < 0 \end{matrix}

2) ⟨{g_{1},...,g_{n}}⟩= {g_{1}⊙ ...⊙ g_{m}|m ∈ ℕ_{0} ∧ g_{i} ∈ {g_{1},...,g_{n},g_{1}^{−1} ,...,g_{n}^{−1} }∀i = 1...m}

3.22 Definition (Homomorphismus)

Seien A = (A,(f_{i})_{i∈I}) und Ã= (Ã,(f̃_{i})_{i∈I}) Algebren vom Typ T = (n_{i})_{i∈I}. Ein ”(Algebra-)Homomorphismus“ ist eine Abbildung φ: A → Ãmit ∀i ∈ I : ∀a_{1}...a_{n_{i}} ∈ A: f̃_{i}(φ(a_{1}),...,φ(a_{n_{i}})) = φ(f_{i}(a_{1}),...,f_{i}(a_{n_{i}})). Die Reihenfolge der Anwendung von f_{i} bzw. f̃_{i} und φ ist also beliebig. Folgende zwei Rechnungen müßen für jede Operation bei beliebigen Operanden das gleiche Ergebnis ergeben:

• Operation auf die Operanden anwenden, anschließend φ auf das Ergebnis anwenden

• φ auf die Operanden anwenden, anschließend die Operation auf den Ergebnissen anwenden

3.23 Beispiel

1) Sei A = (A,(f_{i})_{i∈I}) eine Algebra mit Unteralgebra A′≤ A. Ferner sei id : A′→ A eine Abbildung mit ∀a ∈ A′: id(a) = a.

id ist ein Algebrahomomorphismus. Durch id wird A′in A eingebettet. Zum Beispiel wird so auch (ℕ,+) in (ℤ,+) eingebettet.

2) Seien A = (Σ^{∗},∘) (siehe Beispiel 3.3) und Ã= (ℕ_{0},+). Dann ist φ: Σ^{∗} → ℕ_{0} mit ∀w ∈ Σ^{∗} : φ(w) = \underbrace{|w|}_{Länge von w} ein Homomorphismus.

3) Sei K ein Körper, V und W K-Vektorräume (LA Definition 2.25)

φ: V → W ist Homomorphismus ⇔ φ ist K − linear, d.h. ∀v,w ∈ V : ∀α ∈ K :
φ(v + w) = φ(v) + φ(w)
φ(−v) = −φ(v)
φ(0) = 0
φ(α · v) = α · φ(v)

3.24 Definition (Isomorphismus, Automorphismus)

Seien A = (A,(f_{i})_{i∈I}) und Ã= (Ã,(f̃_{i})_{i∈I}) Algebren

• Ein ”Isomorphismus“ φ: A → Ãist ein bijektiver Homomorphismus.

• A und Ã heißen ”isomorph“ (in Zeichen A ≅ Ã) genau dann wenn ein Isomorphismus φ : A → Ã existiert.

• Ein ”Automorphismus“ ist ein Isomorphismus φ: A → A.

3.25 Beispiel

1) A:= (ℕ,+), Ã:= ({2n|n ∈ ℕ},+), dann ist φ: ℕ → {2n|n ∈ ℕ}, n ↦ 2n ein Isomorphismus.

2) A:= (\underbrace{\{x ∈ ℝ|x > 0\}}_{=:ℝ^{+}},·), Ã= (ℝ,·), dann ist φ: ℝ^{+} → ℝ, x ↦ logx ein Isomorphismus: ∀x,y ∈ ℝ^{+} :

log(x · y) = logx + logy.

3) Sei A = ({1,2,3},∘) eine Algebra mit ∀x,y ∈ {1,2,3}: x ∘ y = 3 und φ: 1 ↦ 2,2 ↦ 1,3 ↦ 3 ist ein Automorphismus.

3.26 Lemma (Strukturerhaltung durch Isomorphismen)

Ein Isomorphismus bildet neutrale Elemente auf neutrale Elemente ab und inverse Elemente auf inverse Elemente

3.27 Lemma (Umkehrabbildung von Isomorphismen)

Ist φ: A → Ãein Isomorphismus, so existiert die Umkehrabbildung φ^{−1} : Ã→ A. Die Umkehrabbildung ist ebenfalls ein Isomorphismus.

64 ALGEBRAISCHE STRUKTUREN

Literaturverzeichnis

[1] A. Steger: ”Diskrete Mathematik I“, Springer 2001

[2] R. Graham, D.Knuth, O. Patashmik: ”Concrete Mathematics“, Addison Wesley, Auflage 2000

Index

abelsch, 60 Ableitung

formale, 25 adjazent, 38 Adjazenzliste, 49 Adjazenzmatrix, 40 Algebra

abelsche, 60 boolsche, 60 universelle, 57

Automorphismus, 63

balanciert, 46 Baum, 45

balancierter, 46 binärer, 47 geordneter, 46 spannender, 47

Baumfaktor, 47 benachbart, 38 Bezierkurve, 12 Binomialkoeffizient, 11

verallgemeinerter, 26 bipartit, 50 Brücke, 42 Breadth-First-Search, 48

Catalan-Zahlen, 32 Cauchy-Produkt, 22 Cayley

Tree Formula, 49

Depth-First-Search, 48 disjunkte Vereinigung, 9 doppeltes Abzählen, 12

Ecke, 35 Eckengrad, 38 Elemente

inverse, 59 neutrale, 58

Endecke, 38 erzeugende Funktion, 21 Exklusion, 15

Faltung, 22 Fibonacci-Zahlen, 28 formale Ableitung, 25 formale Potenzreihe, 21

geometrische Reihe, 23 Gerüst, 47 Gittergraph, 37 goldener Schnitt, 29 Graph, 35

benannter, 40 hamiltonscher, 52 leerer, 38 markierter, 40 regulärer, 38 schlichter, 38 vollständiger, 35

Graphen

bipartite, 50 Gruppe, 59

Halbgruppe, 59 Hamilton-Weg, 52 Hamiltonkreis, 52 hamiltonscher Graph, 52 semi-, 52 Hyperwürfel, 37

injektive Abbildung, 18 Inklusion, 15 Invertierbarkeit

geometrische Reihe, 23 in Ringen, 23 Potenzreihen, 24

Invertieren, 24 Inzidenzmatrix, 40 inzidieren, 38 Isomorphie

zwischen Graphen, 40 Isomorphismus, 63

Körper, 60 Kante, 35 kartesisches Produkt, 9 Knoten, 35 Komponente, 42 Konvolution, 22 Kreis, 36

Hamilton-, 52 Kronecker-Symbol, 21

Matching, 49 maximales, 49 Maximum-, 49 perfektes, 49

Maximum-Matching, 49 Mehrfachkanten, 38 Monoid, 59 Multigraph, 38

Nachbarschaft, 38 Nachfolger, 46

unmittelbarer, 46 Nullgraph, 38

Operation, 57 Operator, 57

Partition, 16 Pascal-Dreieck, 11 Permutation, 10 Potenzmenge, 10 Potenzreihe, 21 Produktregel, 14

formaler Ableitungen, 25

regulär, 38 Rekursionsgleichung

lineare, 27 Ring, 60

Schlingen, 38 Schnittecke, 42 Schubfachprinzip, 13

verallgemeinertes, 14 Siebformel, 15 Signatur, 57 Stelligkeit, 57 Stirling-Dreieck

erster Art, 20 zweiter Art, 16

Stirlingzahlen erster Art, 20 zweiter Art, 16

Summenregel, 14 surjektive Abbildung, 18 symmetrische Gruppe, 10

Teilgraph, 42

induzierter, 42 Teilring, 61 Tiefe, 46 Travelling Salesman Problem, 53 TSP, 53

Unteralgebra, 61 Untergruppe, 61

Vandermonde’sche Identität, 11 Verknüpfung, 57 Vorgänger, 46

unmittelbarer, 46

Wald, 45 Weg, 36

Hamilton-, 52 Wurzelbaum, 46

balanciert, 46

zusammenhängend, 42

Zusammenhangskomponente, 42 Zyklus, 19