Inhalt

Vorwort

1. Abschnitt Elementare Zahlentheorie

1. Teilbarkeit und Kongruenzen

Die ganzen Zahlen

Teiler und Vielfache

Die Kongruenzrelation

Teilbarkeitsregeln

Übungen

2. Primzahlen

Primzahlen und zusammengesetzte Zahlen

Der Unendlichkeitssatz

Die Primfaktorzerlegung

Fragen über Primzahlen

Übungen

3. Der größte gemeinsame Teiler

ggT und kgV

Der Euklidische Algorithmus

Kettenbrüche

Linearkombinationen

Der Chinesische Restsatz

Übungen

4. Die Eulersche φ-Funktion

Die Kürzungsregel für Kongruenzen

Die φ-Funktion

Vollständige und reduzierte Restsysteme

Multiplikativität und Berechnungsformel

Multiplikative zahlentheoretische Funktionen

Übungen

5. Kongruenzen ersten Grades

Die Sätze von Euler und Fermat

Lösen von Kongruenzen ersten Grades

Einsatz des Euklidischen Algorithmus

Primzahlen modulo vier

Übungen

6. Exkurs:  Das RSA-Verfahren

Zielsetzung

Beschreibung des Verfahrens

Übungen

2. Abschnitt Graphentheorie

1. Graphen

Der allgemeine Begriff eines Graphen

Einfache Graphen

Darstellungen für Graphen

Grundbegriffe der Graphentheorie

Vollständige Graphen

Bipartite Graphen

Kreise

Teilgraphen und Untergraphen

Übungen

2. Kantenzüge und Wege

Wanderungen in einem Graphen

Erreichbarkeit und Zusammenhang

Brücken

Der Abstand zweier Ecken

Übungen

3. Isomorphe Graphen

Motivation

Der Isomorphiebegriff

Eigenschaften von isomorphen Graphen

Die Frage nach der Isomorphie

Einteilung in Isomorphieklassen

Übungen

4. Euler-Züge und Hamilton-Kreise

Eulersche Graphen

Der Algorithmus von Hierholzer

Kreiszerlegungen

Weitere Ergebnisse

Hamilton-Kreise

Entscheidungsprobleme und Komplexitätsklassen

Übungen

5. Bäume

Bäume und Wälder

Aufspannende Bäume und Breitensuche

Anwendungen der Breitensuche

Die Tiefensuche

Optimale Grenzkanten

Übungen

6. Gewichtete Graphen

Kantengewichte

Der Algorithmus von Dijkstra

Der Algorithmus von Floyd

Der Algorithmus von Kruskal

Greedy-Algorithmen

Übungen

7. Planare Graphen

Planare Graphen und ihre Darstellungen

Polyedergraphen und Platonische Körper

Die Eulersche Polyederformel

Anwendungen der Polyederformel

Der Vierfarbensatz

Prismen und Archimedische Körper

Verletzungen der Polyederformel

Übungen

Anhänge

1. Logik

Logische Zeichen im Überblick

Aussagenlogische Formeln und Tautologien

Prädikatenlogische Formeln

Quantorenregeln

Zur Bedeutung der Formalisierung

2. Mengen

Teilmengen

Komprehensionen

Boolesche Mengenoperationen

Allgemeine Mengenoperationen

3. Relationen

4. Funktionen

Abbildungseigenschaften von Funktionen

Monotonie-Eigenschaften

Bild und Urbild

Umkehrfunktion, Verknüpfung, Einschränkung

Die Folgennotation einer Funktion

Transformationen und Operationen

Mächtigkeiten

5. Varianten der Induktion

Die vollständige Induktion

Starke Induktion oder Wertverlaufsinduktion

Das Prinzip vom kleinsten Element

Das Prinzip vom unendlichen Abstieg

Rekursives Definieren

Übungen zur Induktion

6. Symbolverzeichnis

7. Index