Materialien im LK Informatik der Stufe Q2/13

Themenbereich Graphentheorie

Literaturliste (*) ist besonders zu empfehlen

Wichtiger Hinweis: Falls Inhalte von Verweisen (Links) nicht angezeigt werden, könnte das an einer falschen Konfigurierung des Zielservers liegen. Versuchen Sie dann mit Rechtsklick und Öffnen im neuen Fenster bzw. Register dort in der Adresszeile zu Beginn das angegebene Protokoll (https://) in die unsichere Variante (http://) zu ändern und den Link so aufzurufen.

Graphentheorie allgemein:
[1] [Kurze Einführung in die Graphen-Theorie] (FH Köln) oder [als PDF]
[2] [Ausführliche Einführung in die Graphen-Theorie] (Uni Würzburg) oder [als PDF]
Grundlagen: Adjazenzmatrix, Adjazenzliste, Graphendurchlauf:
[1] Abschnitte 5.2 und 5.3 in Güting / Dieker: Datenstrukturen und Algorithmen, Teubner 2003
[2] [Expansion, Tiefen- und Breitendurchlauf] (Uni Linz, AU) oder [als PDF]
[3] [Graphen-Algorithmen] (z. B. Kürzester Weg, Minimaler Spannbaum; Uni Osnabrück)
Kürzeste Wege (Dijkstra- bzw. Bellman-Ford-Algorithmus):
[1] Abschnitt 5.4 in Güting / Dieker: Datenstrukturen und Algorithmen, Teubner 2003
[2] Unterrichtsskript zum Projekt Routenplaner
Kapitel [1] / [2] / [3] / [4] / [5] / Infos / Aufgaben und Lösungen [1] / [2] / [3] / [4] / [5] / [6]
(von Gymnasium Wertingen in Bayern)
[3] Kürzeste Wege - der Algorithmus der Woche #7 im Rahmen des Informatikjahres 2006
[4] Bellman-Ford-Algorithmus interaktiv (TU München)
(Minimaler) Spannbaum (Algorithmus von Kruskal bzw. Prim):
[1] Abschnitt 5.9 in Güting / Dieker: Datenstrukturen und Algorithmen, Teubner 2003
[2] Abschnitt 9.5 im Vorlesungsskript Graphentheorie der Uni Osnabrück
[3] [Brückenproblem der Algolaner] (RWTH Aachen, Informatikjahr 2006) oder [als PDF]
Rundwege:
[1] Die Euler-Tour Algorithmus der Woche #9 zum Informatikjahr 2006
[2] Travelling Salesman Algorithmus der Woche #40 zum Informatikjahr 2006

Interaktiv

Anwendungen zur Graphentheorie (*) (MathePrisma, Uni Wuppertal)
[Königsberger Brückenproblem] [Lagerhaltung] [Wege auf Graphen]

Projekte (z. T. nicht frei zugänglich)

Rund um Opladen (Fahrt mit Bus oder Fahrrad; LK-Projekt 2017)
1. Datenmaterial
2. Haltestellen bzw. Orte im Übersichtsplan
3. Java-Projekt-Dateien

Download (*) z. T. nicht öffentlich

Einfache Deutschlandkarte und Adjazenzmatrix
Download der Lösung zum kürzesten Weg nach Dijkstra (*)
Download Graphendemo (167 kB; Quelle: Gymnasium Odenthal) als zip-Datei einschl. Importdateien
Download der Hilfsklasse GraphInit: [ConGraphInit v2.1] (16 kB) [GuiGraphInit v3.0] (22 kB) (Quelle: Eigenprodukt) als zip-Datei
einschl. Importdateien und Konsolen-Demo und mit JavaDoc-Klassen-Dokumentation auch als zip-Datei