Graphentheoretische Konzepte und Algorithmen
Graphentheoretische Konzepte und Algorithmen
复制标题
图形理论概念与算法
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
H. Noltemeier
中科院分区：
文献类型：
--
作者：
S. O. Krumke;H. Noltemeier
Das vorliegende Skript bietet eine Einf{u}hrung in die Graphentheorie und graphentheoretische Algorithmen. Im zweiten Kapitel werden Grundbegriffe der Graphentheorie vorgestellt. Das dritte Kapitel besch{a}ftigt sich mit der Existenz von Wegen in Graphen. Hier wird auch die L{o}suung des ber{u}hmten K{o}nigsberger Br{u}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{a}ter mit der Tiefensuche ein Verfahren vorgestellt, das schneller arbeitet und mit dessen Hilfe man noch mehr Informationen {u}ber die Struktur eines Graphen gewinnen kann. In den folgenden Kapiteln werden Algorithmen vorgestellt, um minimale aufspannenden B{a}ume, k{u}rzeste Wege und maximale Fl{u}sse in Graphen zu bestimmen. Am Ende des Skripts wird ein kurzer Einblick in die planaren Graphen und Graphhomomorphismen geboten.
Das vorliegende Skript bietet eine Einf{u}hrung in die Graphentheorie und graphentheoretische Algorithmen. Im zweiten Kapitel werden Grundbegriffe der Graphentheorie vorgestellt. Das dritte Kapitel besch{a}ftigt sich mit der Existenz von Wegen in Graphen. Hier wird auch die L{o}suung des ber{u}hmten K{o}nigsberger Br{u}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{a}ter mit der Tiefensuche ein Verfahren vorgestellt, das schneller arbeitet und mit dessen Hilfe man noch mehr Informationen {u}ber die Struktur eines Graphen gewinnen kann. In den folgenden Kapiteln werden Algorithmen vorgestellt, um minimale aufspannenden B{a}ume, k{u}rzeste Wege und maximale Fl{u}sse in Graphen zu bestimmen. Am Ende des Skripts wird ein kurzer Einblick in die planaren Graphen und Graphhomomorphismen geboten.