@misc{KrumkeNoltemeierWirth2000, author = {Krumke, Sven and Noltemeier, Hartmut and Wirth, Hans-Christoph}, title = {Graphentheoretische Konzepte und Algorithmen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5873}, number = {00-19}, year = {2000}, abstract = {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.}, language = {de} }