Graphentheoretische Methoden Und Ihre Anwendungen

ISBN-13: 9783642951220 / Niemiecki / Miękka / 2012 / 114 str.

W. Knodel

Opis

Im letzten Jahrzehnt hat die Mathematisierung von Fachgebieten, die vorher heuristisch bearbeitet wurden, grosse Fortschritte erzielt. Dies gilt fur das Strassenverkehrswesen ebenso wie fur die Steuerung und uberwachung umfangreicher Projekte. Meist handelt es sich darum, aufgrund eines Modells der Wirklichkeit Entscheidungen zu treffen, die eine Zielfunktion optimieren. Dabei kann die Anzahl der moglichen Entscheidungen endlich sein, wie bei der Frage, in welcher Reihenfolge vier Orte besucht werden sollen, damit die zuruckgelegte Strecke mog lichst klein wird; oder das Modell kann sich der abstrakten Vorstellung unendlich vieler Moglichkeiten bedienen, wie bei der Auswahl eines Zeitpunkts aus einer kontinuierlich ablaufenden Zeit. Die endlichen Modelle konnen bei aller Verschiedenheit wegen ihres kombinatorischen Charakters vorteilhaft mit. graphentheoretischen Methoden behandelt werden. Der vorliegende Band liefert dafur exemplarische Beispiele. Die Aus wahl erfolgte dabei aufgrund meiner personlichen Neigung und Erfah rungen, so dass Probleme der Strassenverkehrstechnik im Vordergrund stehen. Ordnungsgesichtspunkt bei der Gliederung des Stoffes waren jedoch nicht die Anwendungsgebiete, sondern die verwendeten Modelle und Methoden, wie es sich in den Uberschriften der Kapitel 2 - 5 wider spiegelt. Die Methoden sind bis zu rechenfahigen Algorithmen ausge arbeitet. Meine Absicht war verstandliche Darstellung der Zusammen hange und Fassung des Erarbeiteten in Rechenvorschriften, nicht aber eine bloss rezeptmassige Aufzahlung von Techniken. In Kapitell sind die benutzten graphentheoretischen Begriffe fur den Nichtmathematiker zusammengestellt und erklart."

Spis treści

0 Einleitung.- 1 Grundlagen.- 11 Graphentheorie.- 111 Erste Begriffe.- 112 Kantenfolgen.- 113 Zusammenhängende Graphen.- 114 Schnitte.- 115 Bäume.- 116 Gerichtete Graphen.- 117 Basen.- 118 Linien von Euler und Hamilton.- 12 Bewertete Graphen.- 121 Optimale Kantenfolgen.- 122 Numerische Beschreibung von bewerteten Graphen.- 2 Kürzeste Wege.- 21 Wege aus einem Labyrinth.- 22 Der Algorithmus von Moore für kürzeste Wege.- 23 Das Verfahren von Dijkstra.- 24 Zeitverluste durch Abbiegen oder Umsteigen.- 25 k-kürzeste Wege (Alternativrouten).- 26 Kürzeste Wege unter Unsicherheit.- 27 Kürzeste Wege unter Belastung.- 3 Das Rundreiseproblem.- 31 Das Verfahren von Bellman.- 32 Die Methode des Entscheidungsbaumes.- 321 Reduktion.- 322 Exkurs über Zuordnungsprobleme.- 323 Der Entscheidungsbaum.- 324 Der Algorithmus.- 4 Maximaler Fluß.- 41 Definitionen.- 42 Rechenregeln.- 43 Der Hauptsatz.- 44 Ein Beispiel.- 45 Der Algorithmus für den maximalen Fluß.- 46 Lineare Optimierung.- 47 Zurückführung auf kürzeste Wege.- 5 Phasenfolgen an Kreuzungen.- Literatur.- Namen- und Sachverzeichnis.