Graphen und Anwendungen

Dieses Lehrbuch wendet sich an Studierende der Natur-, Ingenieur-und Wirtschafts­ wissenschaften, deren Studienplan Graphentheorie vorsieht, sowie insbesondere auch an Mathematiker und Informatiker. Zu Beginn werden typische Motivbeispiele fur Graphen angegeben und einige mathematische Grundlagen zusammengestellt. Anschließend werden Graphen definiert, Grundbegriffe eingefuhrt und verschiedene Darstellungen von und Operationen auf Graphen erörtert. Insbesondere wird auf die Realisierung von Graphen auf Computern eingegangen. Dazu dient die Daten­ struktur Graph. Ein Abschnitt befaßt sich ausfuhrlieh mit der speziellen und wichtigen Klasse der Bäume und ihrer Anwendung als Suchstruktur. Im weiteren werden Optimierungsprobleme auf bewerteten Graphen formuliert, mit Anwendungsbeispielen illustriert und Algorithmen zu ihrer Lösung angegeben. Diese Optimierungsprobleme nennt man üblicherweise Abstands- und Stromprobleme. Stromprobleme mit einem freien Parameter und ein erweitertes Netzplanmodell sollen hier besonders erwähnt werden. Einige Standardprobleme des Operations Research werden graphentheoretisch eingeordnet und behandelt. Abschließend wird eine Methode dargestellt, um auf Computern Graphen mit vor­ gegebenen Eigenschaften zu erzeugen. Dazu sind vorbereitend einige Anzahl­ formeln und weitere Darstellungen von Graphen angegeben, die auch ohne die vor­ gesehene Anwendung interessant und nützlich sind. Die meisten Algorithmen werden nach ihrer Beschreibung auch als Pascal­ Prozeduren notiert, so daß der Leser nach dem Hinzufugen eigener Ein- und Ausgabe-Prozeduren Rechnungen anstellen kann. Etwa 140 Beispiele und Aufgaben ermöglichen ein selbständiges Weiterarbeiten. Lösungshinweise und Lösungen komplettieren das Buch. Leipzig, Februar 1996 Günter Nägler Friedmar Stopp Inhalt 1 Einflihrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 . . . . . . . . . . . . . . . 1.1 Zur Entwicklung der Graphentheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2 Einführende Beispiele. . . . . . . . . . . . . . . . . . . . . . . . . . . 10 . . . . . . . . . . . . 1.3 Aufgaben: Modeliierung mit Graphen...... . . . . . . . . . . . . . . . 14 . . . . . . 2 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 . . . . . . . . . . . . . . .