Kapitel 3: Suche in Graphen
Suche in Graphen ist eine grundlegende Fragestellung. Die zugehörigen Strukturen und Methoden bieten zugleich einen Einstieg in weiterführende Themen.
Vorlesung 5
- Datum: Dienstag, 14.11.2017
- Inhalt: Verbindungen und Zusammenhang in Graphen
- Folien: HIER (PDF, 36MB)
- Notizen: HIER (PDF, 1.0MB)
- Weitere Links:
Wikipedia-Seite: Erdös-Zahl
Digital Bibliography & Library Project: Paul Erdös
The Erdös Number Project
Erdös-Zahlen einiger berühmter Leute
Can I give you my number?
Kennzeichen mit Erdös-Zahl
Erdös-Zahlen-Rechner (Auf "Collaboration Distance" klickens; dann am besten Nachnamen eingeben und aus Liste auswählen. Benutzt nur Artikel in MathSciNet, also eine eingeschränkte Datenbasis)
Imaginary Erdös numbers (youtube-Video)
Wikipedia-Seite: Kevin Bacon
Wikipedia-Seite: Kevin-Bacon-Zahl
Internet Movie Database: Kevin Bacon
Das Orakel von Kevin Bacon
Wikipedia-Seite: Kleine-Welt-Netzwerke
Ein bisschen mehr dazu
Der xkcd-Comic zu Erdös - man beachte den Text, wenn man den Mauszeiger über das Bild schiebt.
Kickstarter-Projekt - ein Film über Erdös und Bacon.
Music Map - eine visuelle Darstellung, bei der die Kanten im Graphen unterschiedliche Länge haben, die dem Abstand entspricht.
Vorlesung 6
- Datum: Mittwoch, 15.11.2017
- Inhalt: Graphenscanalgorithmus; Zusammenhangskomponenten; Warteschlange und Stapel; Breiten- und Tiefensuche
- Folien:
Folien (PDF, 6 MB; ACHTUNG! Ohne Animationen.)
Folien mit Animationen der BFS- und DFS-Beispiele (PDF, 24 MB)
- Weitere Links:
Wikipedia-Seite: Zusammenhang von Graphen
Wikipedia-Seite: Aufspannende Bäume
Das Problem aus "Good Will Hunting: Bäume zählen
Wikipedia-Seite: Breitensuche
Wikipedia-Seite: Tiefensuche
Wikipedia-Seite: Warteschlangen
Wikipedia-Seite: Stapelspeicher (Stack)
Der verteilte "Welle"-Algorithmus aus der Vorlesung
Eine technische Version des Verfahrens im Netzwerkkontext: Flooding
Allgemeiner: Verteilte Algorithmen
Vorlesung 7
- Datum: Dienstag, 21.11.2017
- Inhalt: Datenstrukturen für die Codierung von Graphen
- Notizen: HIER (PDF, 1.0MB)
- Weitere Links:
Wikipedia-Seite: Inzidenzmatrix
(Die englischen Seiten sind auch einen Blick wert!)
Wikipedia-Seite: Adjazenzmatrix ( Englisch)
Wikipedia-Seite: Adjazenzliste (Englisch)
Vorlesung 8
- Datum: Mittwoch, 22.11.2017
- Inhalt: Adjazenzliste; Wachstum von Funktionen
- Notizen: HIER (PDF, 1.8MB)
- Folien: HIER (PDF, 2.1MB)
- Weitere Links:
(Für Tonspur auf Bild klicken - und über den Unterschied von t^2 und 2^t nachdenken: Der Aufwand vervierfacht sich nicht nur, sondern quadriert sich!) Wikipedia zur asymptotischen Notation
Sehr detaillierte Skriptnotizen zu Landau-Symbolen (Das ist *viel* detaillierter und tiefer als wir es brauchen)
Noch ein anderer Zugang: Grenzwert des Verhältnisses der Funktionen zum Vergleich (Auch hier die Warnung: Das dient nur der Vertiefung, lieber ignorieren als davon verwirren lassen!)
Theta für Dummies: Ein Forumthread, der gar nicht so schlecht ist (wenn man bewusst darüber nachdenkt)
Große Übung 3
- Datum: Donnerstag, 23.11.2017
- Inhalt: Tiefen-/Breitensuche, O-Notation
- Notizen: HIER
Vorlesung 9
- Datum: Dienstag, 28.11.2017
- Inhalt: Laufzeit von Breiten- und Tiefensuche
- Notizen:
HIER (PDF, 1.0MB)
Vorlesung 10
- Datum: Mittwoch, 29.11.2017
- Inhalt: Eigenschaften von Breiten- und Tiefensuche; Kapitelzusammenfassung
- Notizen: HIER (PDF, 2.5MB)
- Folien: HIER (PDF, 8.5MB)
- Weitere Links:
IDEA-Projekt
Wikipedia zu Online-Algorithmen
Ski Rental: ein besonders eingängiges Online-Problem
Liedtext
Das Lied im Original
Ein bisschen zu vollständiger Induktion
Weiterfürende Themen zu Graphenalgorithmen
- Algorithmus der Woche aus dem Informatikjahr 2006:
Kürzeste Wege
- Algorithmus der Woche aus dem Informatikjahr 2006:
Minimale zusammenhängende Netzwerke
- Algorithmus der Woche aus dem Informatikjahr 2006:
Maximale Flüsse
- Wikipedia zu Flüssen und Schnitten in Graphen