Anwendungen der Graphentheorie
- PDF / 34,159,719 Bytes
- 239 Pages / 481.89 x 691.654 pts Page_size
- 3 Downloads / 335 Views
H. Walther
Anwendungen der Graphentheorie Mit 102 Ahbildungen
Friedr. Vieweg & Sohn Braunschweig/Wiesbaden
CIP-Kurztitelaufnahme der Deutschen Bibliothek Walther, Hansjoachim Anwendungen der Graphentheorie. -1. Auf!. - Braunschweig: Vieweg, 1979
1979 ABe Rechte vorbehalten ® VEB Deutscher Verlag der Wissenschaften, Berlin 1978 Softcover reprint of the hardcover 1st edition 1978 Lizenzausgabe fur Friedr. Vieweg & Sohn Verlagsgesellschaft mbH, Braunschweig, mit Genehmigung des VEB Deutscher Verlag der Wissenschaften, BerlinJDDR ISBN-13: 978-3-528-08418-9 e-ISBN-13: 978-3-322-84013-4 DOl: 10.1007/ 978-3-322-84013-4
Vorwort
Das vorgelegte Buch setzt die von Professor HORST SACHS geschriebenen Bucher "Einfuhrung in die Theorie der endlichen Graphen" I (1970), II (1972) fort und rundet sie durch seinen Anwendungscharakter abo Es wendet sich an Studierende aller Fachrichtungen, die sich mit mathematischen Methoden der Operationsforschung beschaftigen, aber auch an Absolventen und Praktiker, um ihnen ein Handwerkszeug zu vermitteln, das ihnen bei der Modellierung und Losung von Organisations- und Optimierungsproblemen mit vornehmlich kombinatorischer Komponente helfen wird. Anwendung der Graphentheorie hat zwei Aspekte: Sie iet einerseits angewandte Graphentheorie, wobei im Vordergrund die numerische Ermittlung charakteristischer GroJ3en eines vorgegebenen Graphen steht (z. B. die Frage, wie man in einem Graphen eine minimale Bogenmenge finden kann, nach deren Entfernung der Graph kreisfrei ist; vgl. Kap. 9); sie ist andererseits Anwendung von Satzen und Algorithmen der Graphentheorie in anderen Wissensgebieten (bei der Festlegung einer optimalen Berechnungsfolge in einem Algorithmus spielen z. B. Schleifen eine entscheidende Rolle, und man fragt, wie viele Ruckkehrbogen zerschnitten werden mussen, um die Abarbeitung schleifenfrei zu realisieren; vgl. ebenfalls Kap. 9). Beide Aspekte sind voneinander nicht zu trennen und finden im Buch ihren Niederschlag. In der kurz gehaltenen Einleitung werden die notwendigsten Begriffe der Graphentheorie zusammengestellt, die dann standig verwendet werden. Begriffe, die nur in einem Kapitel benotigt werden, werden dort definiert. Kapitel 1 legt die Grundlage fur aIle Kapitel, in denen wir es mit Stromproblemen zu tun haben; alle anderen Kapitel sind im wesentlichen unabhangig voneinander lesbar. Auf der Grundlage bekannter Satze der Graphen- und Netzwerktheorie, auf die auJ3er im erst en Kapitel nicht naher eingegangen wird, werden Satze formuliert und bewiesen, welche zu praktikablen Algorithmen fuhren. Diese Algorithmen werden ausflihrlich dargestellt und an Beispielen erlautert. Auf die Auswahl der Beispiele wurde groJ3er Wert gelegt; sie sind keineswegs simpel, sondern wurden nach Moglichkeit so groJ3 gewahlt, daJ3 aIle Schwierigkeiten, aber auch aIle Feinheiten des Algorithmus deutlich werden. Die angegebenen Algorithmen sind so gehalten, daJ3 sie zwar einer rechentechnischen Realisierung unmittelbar zugangHch sind, jedoch muJ3te davon Abstand genommen werden, die Algorith
