ADM I: Graphen und Netzwerkalgorithmen
	Sommersemester 2001

Inhalt

Viele praxisrelevante Fragestellungen führen auf Optimierungsprobleme in Graphen oder Netzwerken. Beispiele sind kürzeste Wege in Verkehrsnetzen, Optimierung von Verkehrsflüssen, ausfallsichere Telekommunikationsnetze, Steuerung von Produktionsabläufen u.v.a.

Die Vorlesung behandelt grundlegende Graphen- und Netzwerkalgorithmen (kürzeste Wege, maximale und kostenminimale Flüsse, Zuordnungsprobleme ...) und die dazu benötigten mathematischen Grundlagen der Graphentheorie, Komplexitätstheorie und Optimierung. Insbesondere werden auch Problemklassen gemäß ihrer Komplexität klassifiziert (effizient lösbar, NP-schwer) und Techniken zur Lösung NP-schwerer Probleme (zu denen die meisten Praxisprobleme gehören) behandelt.

Diese VL ist die Einführungsveranstaltung und Grundvorlesung für den Schwerpunk "Algorithmische Diskrete Mathematik" in den Studiengängen Mathematik und Techno- und Wirtschaftsmathematik. Im nächsten Semester wird die Reihe durch die VL "Lineare Optimierung" fortgesetzt.

Voraussetzungen:

Übungsblätter

• 1. Übungsblatt  [ Postscript, TeX, PDF ] 
• 2. Übungsblatt  [ Postscript, TeX, PDF ] 
• 3. Übungsblatt  [ Postscript, TeX, PDF ] 
• 4. Übungsblatt  [ Postscript, TeX, PDF ] 
• 5. Übungsblatt  [ Postscript, TeX, PDF ] 
• 6. Übungsblatt  [ Postscript, TeX, PDF ] 
• 7. Übungsblatt  [ Postscript, TeX, PDF ] 
• 8. Übungsblatt  [ Postscript, TeX, PDF ] 
• 9. Übungsblatt  [ Postscript, TeX, PDF ] 
• 10. Übungsblatt  [ Postscript, TeX, PDF ] 
• 11. Übungsblatt  [ Postscript, TeX, PDF ] 
• 12. Übungsblatt  [ Postscript, TeX, PDF ] 
  
  

Lösungen und Sonstiges

• Und hier gibt's ein nettes Spiel zu Aufgabe 3 ("sich (nicht) kennende Menschen")
  
  
• Mehr Hintergrund und die Lösung von Aufgabe 20 gibt es in dem folgenden Artikel:
  
  
  • Cycle time and slack optimization for VLSI-chips
    von Albrecht, Christoph ; Korte, Bernhard ; Schietke, Jürgen ; Vygen, Jens
    
    
  Es ist online erhältlich auf der Seite von Jürgen Schietke.
  
  

Programmieraufgaben:

Es waren Programmieraufgaben zu lösen, welche auf einer Graphenklasse jGABL basieren, die in Java geschrieben ist.

Beispielprogramme

• Das Beispielprogramm aus der 1. Übung (Anzeigen der Adjazenzliste)
  
  
• 1. Version von IndependentSet berechnen von unabhängigen Mengen
  
  
• 2. Version von IndependentSet berechnen von unabhängigen Mengen
  
  

Beispiele für animierte Programme

• animierte Tiefensuche
  
  
• animierter Kruskal-Algorithmus
  
  
• animierter Prim-Algorithmus
  
  
• animierter Dijkstra-Algorithmus
  
  
• animierter Minimum Mean-Cycle - Algorithmus
  
  
• animierter Edmonds-Karp - Algorithmus
  
  
• animierter Goldberg-Tarjan - Algorithmus
  
  

Beispielgraphen

• Aufgabe 1: Zusammenhangsberechnung
  • graph_comp.1.gml
  • graph_comp.2.gml
  • graph_comp.3.gml
  • graph_comp.4.gml
  
  
  
• Aufgabe 2: MST-Berechnung
  • mst_graph.1.gml
  • mst_graph.2.gml
  • mst_graph.3.gml
  • mst_graph.4.gml
  • mst_graph.5.gml
  
  
  
• Aufgabe 3: Berechnen eines Zykels minimaler mittlerer Länge
  • digraph.1.gml
  • digraph.2.gml
  • digraph.3.gml
  • digraph.4.gml
  • digraph.5.gml
  • digraph.6.gml
  
  
  
• Aufgabe 4: Max-Fluss-Berechnung
  • maxflow.1.gml     (Max. Fluß: 4)
  • maxflow.2.gml     (Max. Fluß: 5)
  • maxflow.3.gml     (Max. Fluß: 31)
  • maxflow.4.gml     (Max. Fluß: 2)
  
  
  
• Aufgabe 5: Kostenminimale Flüsse
  • mincostflow.1.gml     (Min. Kosten: 12)
  • mincostflow.2.gml     (Min. Kosten: 28)
  • mincostflow.3.gml     (Min. Kosten: 24)

Die Graphen liegen auch unter "/net/guna/jGABL/Graphen/Aufgabe?"

Graphen ansehen und editieren kann man mit dem Programm graphlet. Die Dokumentation ist etwas rudimentär, es gibt aber eine Graphlet Web-Seite. Außerdem erklährt sich das meiste selbst (oder ist durch ein Experiment herauszufinden). Natürlich kann graphlet das GML-Graphenformat lesen und schreiben. Außerdem gibt es unter Layout verschiede Methoden Graphen automatisch zeichnen zu lassen. Am besten man probiert es aus (vielleicht mit einem Spring Embedder anfangen).

Literatur

• Grundlage für die VL:
  B. Korte, J. Vygen:
  Combinatorial Optimization: Theory and Algorithms,
  Springer, 2000
  
  
• R.K. Ahuja, T.L. Magnanti, J.B. Orlin:
  Network Flows: Theory, Algorithms, and Applications,
  Prentice-Hall, 1993
  
  
• W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver:
  Combinatorial Optimization,
  Wiley, 1998
  
  
• Dieter Jungnickel:
  Graphs, Networks and Algorithms,
  Springer, 1999
  (englische Übersetzung der deutschen Version aus dem Jahre 1994)

Sonstige Daten

• GIDEN - Bibliothek zur Animation von Graphen- und Netzwerkalgorithmen, unter anderem mit Applet.
  
  
• Tagebauproblem - Open-Pit Mining Problem, siehe auch die Homepage von Prof. Dorit Hochbaum.
  
  
• A New Approach to the Minimum Cut Problem
  David Karger und Clifford Stein
  Journal of the ACM, 43:4, pp. 601-640, 1996
  
  
• Seiten der Arbeitsgruppe Algorithmen und Datenstrukturen in Wien. Dort finden sich Hintergrundinformationen zum Graphenzeichnen.
  
  Der Artikel zum Zeichen eines Graphen im Gitter ist:
  
  On embedding a graph in the grid with the minimum number of bends.
  R. Tamassia
  SIAM Journal on Computing 16 (1987) 421 - 444
  
  Leider gibt's den Artikel nicht in der Mathe-Bibliothek (aber vielleicht in der Informatik).