Graphentheoretische Konzepte und Algorithmen
Please always quote using this URN: urn:nbn:de:0297-zib-5873
- Das vorliegende Skript bietet eine Einf{ü}hrung in die Graphentheorie und graphentheoretische Algorithmen. Im zweiten Kapitel werden Grundbegriffe der Graphentheorie vorgestellt. Das dritte Kapitel besch{ä}ftigt sich mit der Existenz von Wegen in Graphen. Hier wird auch die L{ö}suung des ber{ü}hmten K{ö}nigsberger Br{ü}ckenproblems aufgezeigt und der Satz von Euler bewiesen. Im vierten Kapitel wird gezeigt, wie man auf einfache Weise die Zusammenhangskomponenten eines Graphen bestimmen kann. Im Kapitel sechs wird dann sp{ä}ter mit der Tiefensuche ein Verfahren vorgestellt, das schneller arbeitet und mit dessen Hilfe man noch mehr Informationen {ü}ber die Struktur eines Graphen gewinnen kann. In den folgenden Kapiteln werden Algorithmen vorgestellt, um minimale aufspannenden B{ä}ume, k{ü}rzeste Wege und maximale Fl{ü}sse in Graphen zu bestimmen. Am Ende des Skripts wird ein kurzer Einblick in die planaren Graphen und Graphhomomorphismen geboten.
Author: | Sven Krumke, Hartmut Noltemeier, Hans-Christoph Wirth |
---|---|
Document Type: | ZIB-Report |
Tag: | Algorithmen; Graphen; Komplexit{ä}t; kombinatorische Optimierung |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization |
Date of first Publication: | 2000/05/17 |
Series (Serial Number): | ZIB-Report (00-19) |
ZIB-Reportnumber: | 00-19 |