Graphentheorie

verantwortlich:W. Koepf

• Anzahl der SWS: 4, davon 2 V, 2 Ü
• Einordnung der Veranstaltung: Pflichtfach, 4. Semester
• Zugehörigkeit zur Studienrichtung: Operations Research
• Art des Abschlusses: Klausur

1. Einführung:
   Entwicklung der Graphentheorie, Definition von Graphen und Motivationsbeispiele, Probleme des Operations Research
2. Graphen:
   Darstellung von Graphen, Grundbegriffe der Graphentheorie, spezielle Graphen, Charakterisierung zusammenhängender und bipartiter Graphen
3. Euler- und Hamiltontouren:
   Charakterisierung von Eulergraphen, Konstruktion von Euler- und Hamiltontouren,
4. Komplexität:
   Komplexität von Algorithmen und Problemen, polynomiale Algorithmen
5. Bäume und Gerüste:
   Charakterisierung von Bäumen, Breadth-First-Suche und Depth-First-Suche
6. Abstandsprobleme in bewerteten Graphen:
   Problemstellung, Minimalgerüste, Algorithmus von Kruskal, kürzeste Wege, Dijkstra-Algorithmus, Traveling-Salesman-Problem mit Heuristiken
7. Stromprobleme:
   Strom und Spannung, Maximale Flüsse, Ford-Fulkerson-Algorithmus, Kostenminimale Flüsse, Anwendungen

1. Aigner, M., Diskrete Mathematik, Vieweg, Braunschweig-Wiesbaden 1993.
2. Brandstädt, A.: Graphen und Algorithmen. Teubner, Stuttgart 1994.
3. Clark, J., Holton, D.A.: Graphentheorie. Spektrum Akademischer Verlag, Heidelberg-Berlin-Oxford 1994.
4. Nägler, G., Stopp, F.: Graphen und Anwendung. Teubner, Leipzig 1996 .
5. Skiena, S., Implementing Discrete Mathematics, Combinatorics and Graph Theory with Mathematica, Addison-Wesley, Redwood City, 1990.