Die Ursprünge der Graphentheorie gehen zurück bis ins Jahr 1736, als Leonhard Euler die erste graphentheoretische Arbeit verfasste. Euler beschäftigte sich in seiner Arbeit mit dem Königsberger Brückenproblem, das in Kapitel 3.2.1 näher erläutert wird.
Im 19. Jahrhundert befassten sich weitere Wissenschaftler mit der Graphentheorie. Gustav Robert Kirchhoff, der Begründer der Netzwerktheorie schrieb im Jahr 1847 seine Abhandlung über elektrische Netze. 1878 veröffentlichte Arthur Cayley eine Arbeit zum Vierfarbenproblem, das er mit Hilfe von Computern löste. Das Vierfarbenproblem erläutert die Fragestellung, ob vier Farben ausreichen um alle Länder einer Landkarte so einzufärben, dass benachbarte Länder nie die gleiche Farbe besitzen [NÄGL96, S. 9, VOLK91, S. viii]. Obwohl ihre Wurzeln also bereits im 18. Jahrhundert liegen, erlangte die Graphentheorie erst ab Mitte des 20. Jahrhunderts größeres Interesse und wissenschaftliche Anerkennung. Als Teilgebiet der Mathematik spielt sie heute in vielen Bereichen, unter anderem auch den Wirtschaftswissenschaften, eine maßgebende Rolle [MAAS93, S. 7].
Zum gesteigerten Ansehen der Graphentheorie trug vor allem das Operations Research bei, welches um 1950 in den USA entstanden und in den 60 Jahren bis nach Deutschland vorgedrungen war. Unter Operations Research versteht man „die Anwendung quantitativer Methoden zur Vorbereitung optimaler Entscheidungen“ [ZIMM01, S. 2]. Zur Entscheidungsfindung bzw. Abbildung von Problemstellungen bedient sich das Operations Research häufig graphentheoretischer Modelle. Modelle, also vereinfachte Darstellungen der Realität, eignen sich besonders gut zur Optimierung und Simulation [DOMS95, S. 2]. Eine der Hauptanwendungen des Operations Research bzw. der Graphentheorie ist die Netzplantechnik. Sie beschäftigt sich vor allem mit der Terminplanung. Projekte, wie z. B. Hausbau o. ä., werden in ihre einzelnen Aktivitäten unterteilt und gemäß ihrer Abarbeitungsreihenfolge zu Graphen zusammengefasst [MÜLL73, S. 254]. Da sich Netzpläne allerdings weder zur Optimierung noch zur Simulation eignen, werden sie hier nicht näher erläutert. Im Rahmen dieser Seminararbeit werden graphentheoretische Modelle in Modelle zur Optimierung und Modelle zur Simulation unterteilt und anhand von Beispielen vorgestellt.
Inhaltsverzeichnis
- Entstehung und Bedeutung der Graphentheorie
- Verfahren von Kruskal
- Verfahren von Dijkstra
- Rundreisen und Touren
- Eulertouren
- Briefträgerprobleme
- Travelling Salesman Probleme
- Transportprobleme
- Klassisches Transportproblem
- Umladeprobleme
- Zuordnungsprobleme
- Flüsse in Graphen
- Graphentheoretische Modelle zur Simulation
- Petrinetze
- Bedingungs-Ereignis-Netze
- Stellen-Transitions-Netze
- Prädikat-Transitions-Netze
Zielsetzung und Themenschwerpunkte
Die Seminararbeit befasst sich mit graphentheoretischen Modellen, die in den Bereichen Optimierung und Simulation Anwendung finden. Ziel ist es, die Entstehung und Bedeutung der Graphentheorie aufzuzeigen und wichtige Anwendungsbeispiele aus dem Logistikbereich zu präsentieren.
- Entstehung und Bedeutung der Graphentheorie
- Anwendungen graphentheoretischer Modelle in der Logistik
- Optimierungsmodelle, insbesondere minimal spannende Bäume, Rundreisen und Touren, Transportprobleme und Flüsse in Graphen
- Simulationsmodelle, vor allem Petrinetze
- Bedeutung graphentheoretischer Modelle für das Operations Research
Zusammenfassung der Kapitel
Das erste Kapitel befasst sich mit der Entstehung und Bedeutung der Graphentheorie. Hier werden die Ursprünge der Graphentheorie und die wichtigsten Entwicklungsschritte beleuchtet. Das zweite Kapitel erläutert die Grundlagen der Graphentheorie und stellt wichtige Begriffe wie Knoten, Kanten, gerichtete Graphen und Bäume vor. Im dritten Kapitel werden graphentheoretische Modelle zur Optimierung vorgestellt, insbesondere minimal spannende Bäume, Rundreisen und Touren, Transportprobleme und Flüsse in Graphen. Dabei werden wichtige Verfahren zur Lösung dieser Probleme, wie z. B. das Verfahren von Kruskal, beschrieben.
Schlüsselwörter
Graphentheorie, Optimierung, Simulation, Logistik, Operations Research, minimal spannende Bäume, Rundreisen, Touren, Transportprobleme, Flüsse in Graphen, Petrinetze, Bedingungs-Ereignis-Netze, Stellen-Transitions-Netze, Prädikat-Transitions-Netze.
- Arbeit zitieren
- Steffi Meier (Autor:in), 2006, Graphentheoretische Modelle zur Optimierung und Simulation, München, GRIN Verlag, https://www.grin.com/document/58679
