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
Übersicht:
- Einführung:
Entwicklung der Graphentheorie, Definition von Graphen und
Motivationsbeispiele, Probleme des Operations Research
- Graphen:
Darstellung von Graphen, Grundbegriffe der Graphentheorie,
spezielle Graphen, Charakterisierung zusammenhängender und bipartiter
Graphen
- Euler- und Hamiltontouren:
Charakterisierung von Eulergraphen,
Konstruktion von Euler- und Hamiltontouren,
- Komplexität:
Komplexität von Algorithmen und Problemen,
polynomiale Algorithmen
- Bäume und Gerüste:
Charakterisierung von Bäumen, Breadth-First-Suche und Depth-First-Suche
- Abstandsprobleme in bewerteten Graphen:
Problemstellung, Minimalgerüste,
Algorithmus von Kruskal, kürzeste Wege, Dijkstra-Algorithmus,
Traveling-Salesman-Problem mit Heuristiken
- Stromprobleme:
Strom und Spannung, Maximale Flüsse, Ford-Fulkerson-Algorithmus,
Kostenminimale Flüsse, Anwendungen
empfohlene Literatur:
- Aigner, M., Diskrete Mathematik, Vieweg, Braunschweig-Wiesbaden 1993.
- Brandstädt, A.: Graphen und Algorithmen. Teubner, Stuttgart 1994.
- Clark, J., Holton, D.A.: Graphentheorie. Spektrum Akademischer
Verlag, Heidelberg-Berlin-Oxford 1994.
- Nägler, G., Stopp, F.: Graphen und Anwendung. Teubner, Leipzig 1996 .
- Skiena, S., Implementing Discrete Mathematics, Combinatorics
and Graph Theory with Mathematica, Addison-Wesley, Redwood City, 1990.
erwartete Vorkenntnisse: Algebra
Einschreibmodalitäten: keine
besondere Hinweise: keine
Wolfram Koepf
Thu May 28 15:30:50 MET DST 1998