Algorithmische Graphentheorie

Graphentheorie: eine Theorie, oder einfach eine Methode, um Sachverhalte an schaulich darzustellen, die auch in anderer Weise erfassbar waren? Beides trifft zu: Tatsachlich ist die Graphentheorie heute bereits ein recht weit entwickelter Zweig der diskreten Mathematik, mit dem sich Spezialisten befassen. Auf der anderen Seite bietet die Abstraktion von Problemstellungen aus der "rea len" Welt auf die beiden urspriinglich der Geometrie entliehenen Elemente "Punkt" und "Kante" eine reizvolle Gelegenheit, auch fUr die Losung von Aufgaben eher kombinatorischer Natur an die bildliche Vorstellung zu appellieren. Dieses Buch ist aus dem Manuskript einer einsemestrigen Vorlesung entstan den, die ich mehrere Male an der Eidgenossischen Technischen Hochschule Ziirich (ETH) fUr Studenten der Informatik und der Mathematik in mittleren Semestern gehalten habe. Der Text richtet sich - ausser an dies en Kreis - durchaus auch an Studenten von Hoheren Technischen Lehranstalten (bzw. Fachhochschulen), sowie an Gymnasiallehrer. Die letzteren werden zwar den Stoff kaum als geschlos senen Lehrgang beniitzen, konnen jedoch eventuell einzelne herausgegriffene Teile im Unterricht der oberen Klassen einbringen. Das Buch solI zunachst eine erste EinfUhrung in die Graphentheorie vermitteln - wer nur diese sucht, kann im Extremfall die Kapitel 3 und 4, sowie in den folgenden Kapiteln alles, was sich auf Algorithmen bezieht, weglassen.

Klappentext

Graphentheorie: eine Theorie, oder einfach eine Methode, um Sachverhalte an­ schaulich darzustellen, die auch in anderer Weise erfassbar waren? Beides trifft zu: Tatsachlich ist die Graphentheorie heute bereits ein recht weit entwickelter Zweig der diskreten Mathematik, mit dem sich Spezialisten befassen. Auf der anderen Seite bietet die Abstraktion von Problemstellungen aus der "rea­ len" Welt auf die beiden urspriinglich der Geometrie entliehenen Elemente "Punkt" und "Kante" eine reizvolle Gelegenheit, auch fUr die Losung von Aufgaben eher kombinatorischer Natur an die bildliche Vorstellung zu appellieren. Dieses Buch ist aus dem Manuskript einer einsemestrigen Vorlesung entstan­ den, die ich mehrere Male an der Eidgenossischen Technischen Hochschule Ziirich (ETH) fUr Studenten der Informatik und der Mathematik in mittleren Semestern gehalten habe. Der Text richtet sich - ausser an dies en Kreis - durchaus auch an Studenten von Hoheren Technischen Lehranstalten (bzw. Fachhochschulen), sowie an Gymnasiallehrer. Die letzteren werden zwar den Stoff kaum als geschlos­ senen Lehrgang beniitzen, konnen jedoch eventuell einzelne herausgegriffene Teile im Unterricht der oberen Klassen einbringen. Das Buch solI zunachst eine erste EinfUhrung in die Graphentheorie vermitteln - wer nur diese sucht, kann im Extremfall die Kapitel 3 und 4, sowie in den folgenden Kapiteln alles, was sich auf Algorithmen bezieht, weglassen.

Inhalt
Grundlagen der Graphentheorie.- Computerbezogene Aspekte.- Komplexität.- Färbbarkeit.- Wege.- Transitive Hülle.- Bäume.- Depth-First-Search.- Flussprobleme.- Planarität.