In diesem Dokument wird versucht, die (für Informatik) bedeutendesten Erkenntnisse aus dem Gebiet der Graphentheorie, verständlich zu erläutern und mit Beispielen zu veranschaulichen. Viel zu beweisen gibt es dabei nicht, da hauptsächlich Definitionen genannt und durch einfache Beispiele verständlich gemacht werden.

Um weiterführende Algorithmen bearbeiten und verstehen zu können sind fundierte Kenntnisse der Graphensuche bzw. des Graphendurchlaufs unerlässlich. Dabei gibt es grundsätzlich zwei Arten, die Tiefensuche (bzw. der Tiefendurchlauf) und die Breitensuche (bzw. der Breitendurchlauf). Beide Verfahren werden untersucht und erklärt.

Im Einzelnen werden die folgenden Themen behandelt:

• gerichteter Graph, ungerichteter Graph: Definitionen, Kanten (Ecken), Knoten, Anschauung und Objekte aus der Realwelt
• Grad eines Knotens, Pfad als Folge von Knoten, einfachen Pfad, Erreichbarkeit eines Knotens
• Nachfolgermengen und Vorgängermengen: Post(v), Pre(v), Post*(v), Pre*(v), benachbarte Knoten, Beispiele
• (einfacher) Zyklus in gerichteten und ungerichteten Graphen, Beispiele
• Stark verbundene Graphen/Komponenten, Cliquen, Beispiele
• Graphendurchlauf - Traversierungsmethoden, Definition, Schema für eine Graphtraversierung
• Breitensuche (BFS), Tiefensuche (DFS) mit Beispielen, rekursive Formulierung der Tiefensuche
• Expansion eines Graphen, Zusammenhang zum DFS, (minimaler) Spannbaum

Das Suchen, Einfügen und Entfernen eines Schlüssels in einem zufällig erzeugten binären Suchbaum mit N Schlüsseln ist zwar im Mittel O(log(N)) Schritten ausführbar. Im schlechtesten Fall kann jedoch ein Aufwand von der Ordnung (N) zur Ausführung dieser Operation erforderlich sein, weil der gegebene Baum mit N Schlüsseln zu einer Liste degeneriert ist. Es ist daher natürlich, durch zusätzliche Bedingungen an die Struktur der Bäume ein Degenerieren zu verhindern. Die Operationen zum Einfügen und Entfernen werden dann allerdings komplizierter als für natürliche Bäume.

• Kosten für das Einfügen (insert), Löschen (delete) und Suchen (member) in AVL-Bäumen
• Definitionen: AVL-Baum als spezieller binärer Suchbaum, Balancefaktor, bal(v), linker Teilbaum, rechter Teilbaum, Algorithmus isbalanced, Beispiele
• Operationen auf AVL-Bäumen, 4 elementaren Operationen auf AVL-Bäumen, Doppelrotation, einfache Rotation, wann welche Operation?, Schema für die Doppelroation und die einfache Rotation, Doppelrotation = zwei einfache Rotationen
• Löschoperationen

• Suchen nach einem Datensatz,
• Einfügen eines neuen Datensatzes,
• Löschen eines Datensatzes.

Die grundsätzlich Idee ist nun den Speicherplatz eines jeweiligen Datensatzes mit Hilfe des eindeutigen Schlüsselwertes zu berechnen. Dazu benötigen wir natürlich eine Funktion, welche auf einer Teilmenge der natürlichen Zahlen definiert ist - die Hashfunktion. Diese muss um den praktischen Anforderungen zu genügen gewisse Eigenschaften aufweisen.

• Grundlagen des Hashings, Behälter, Array, Datensätze, Datenstrukturen zur Verwaltung von Dictionaries, dynamische Datenmengen - Einfügen, Löschen, Verändern
• Kosten, Platz, Zeit, O(n), Komplexität
• Hashfunktion, Auswahl der Hashfunktionen, totale Abbildung, surjektiv, injektiv, effizient berechenbar, Kollision, Beispiele
• Wahrscheinlichkeit einer Kollision, Beispiel
• Klassifizierung der Hashverfahren, Verkettung der Überläufer, offener Adressierung, offenes Hashing, geschlossenes Hashing
• Sondierfolge, Sondierungsarten, Lineares Sondieren, quadratisches Sondieren, Doppel-Hashing, Beispiel
• Divisionsmethode, Multiplikationsmethode, Mittelquadratmethode

Ein Vektorraum und ein Unterraum wird zur Konstruktion eines Faktorraums benötigt.
Ob man damit elliptischen Funktionen definiert, einen Beweis über nilpotente Endomorphismen erbringt oder aber den Homomorphiesatz beweist - überall erweisen sich diese, zunächst scheinbar schwer zu begreifenden Räume, als überaus gewinnbringend.

Im folgenden Dokument werden Faktorräume prägnant dargestellt, dabei wurde insbesondere auf die Anschaulichkeit Wert gelegt, deshalb findet man auch viele Skizzen und Beispiele.

Im Einzelnen werden behandelt:

• Nebenklassen und Repräsentanten, wohldefiniert
• Unterraumkriterium, Untervektorraum, Beispiele
• Kriterium für die Gleichheit von Nebenklassen, Äquivalenzrelation (Reflexivität, Transitivität, Symmetrie)
• Basen von Faktorräumen, Faktorraum ist ein Vektorraum

Das vorliegende Dokument gibt eine kurze Einführung in die unendlichen Produkte, die wichtigsten Sätze und Eigenschaften werden bewiesen und begründet.

Im Einzelnen werden behandelt:

• Partialprodukt, unendliche Produkte (ab einem Index N)
• Sonderstellung der 0, Nullstellen
• Konvergenz von unendlichen Produkten, Beziehungen zwischen der Konvergenz von Reihen und Produkten
• Notwendige Bedingung zur Konvergenz bei unendlichen Produkten
• Abschätzung der Logarithmus-Funktion
• Konvergenz-Kriterium für unendliche Reihen
• Beispiele