Graphentheorie (GRA)
6/7. Semester
5 ECTS | 4 SWS
Continuous Assessment (CA)
Netzwerke verstehen und nutzen: Du arbeitest mit Verbindungen und Strukturen, entwickelst Algorithmen und löst damit praktische Probleme.
Inhalte
- Grundbegriffe der Graphentheorie,
- Wege, Eulersche Kreise und offene Linien,
- Hamiltonkreise, bewertete Graphen, das Problem des Handlungsreisenden, kürzeste Wege,
- Algorithmen zur Suche kürzester Wege (u.a. der Dijkstra-Algorithmus)
- Bäume, Gerüste, Minimalgerüste, Algorithmen zur Suche Minimalgerüste (u.a. die Kruskal- und Prim-Algorithmen)
- Planare Graphen
- Matchingtheorie, Heiratsproblem
- Färbungen, Färbungsalgorithmen, Ramsey-Theory
- Gerichtete Graphen, Turniere
- Netzwerke
- Maximale Flüsse, minimale Schnitte, der Ford-Fulkerson-Algorithmus
Lernziele/Kompetenzen
Die Studierenden sind in der Lage,
- die Einsatzgebiete und Grenzen der erlernten Verfahren zu erkennen und zu erläutern,
- einige graphentheoretische Algorithmen zu verstehen und ggf. zu implementieren und
- das erhaltene Ergebnis einem nicht eingearbeiteten Fachkollegen zu erklären und zu präsentieren.
Literatur
- A. Steger: Diskrete Strukturen, Band 1, Springer
- Peter Hartmann: Mathematik für Informatiker, Vieweg
- J.Clark, D.A. Holton: Graphentheorie, Spektrum Verlag
Dozentinnen / Dozenten
Empfohlene Vorkenntnisse
Daten zum Modul
| Semester |
6/7 |
| Unterrichtssprache |
Deutsch |
|
Häufigkeit
|
Unregelmäßig
|
| Kreditpunkte |
5 |
| Modulverantwortlich |
Prof. Dr. Elena Fimmel |
| Dauer |
1 Semester |
| Studienleistung |
Keine |
| Prüfungsvorleistung |
Keine |
| Prüfungsleistung |
Continuous Assessment (CA) |
Semesterwochenstunden
| Vorlesung |
2 SWS |
| Übung |
2 SWS |
| Summe |
4 SWS |
Arbeitsaufwand (work load)
| Vorlesung |
30 h |
| Selbststudium |
90 h |
| Aufgaben |
30 h |
| Summe |
150 h |