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
1 Entstehung und Bedeutung der Graphentheorie
2 Grundlagen
3 Graphentheoretische Modelle zur Optimierung
3.1 Minimal spannende Bäume
3.1.1 Verfahren von Kruskal
3.1.2 Verfahren von Dijkstra
3.2 Rundreisen und Touren
3.2.1 Eulertouren
3.2.2 Briefträgerprobleme
3.2.3 Travelling Salesman Probleme
3.3 Transportprobleme
3.3.1 Klassisches Transportproblem
3.3.2 Umladeprobleme
3.3.3 Zuordnungsprobleme
3.4 Flüsse in Graphen
4 Graphentheoretische Modelle zur Simulation
4.1 Petrinetze
4.1.1 Bedingungs-Ereignis-Netze
4.1.2 Stellen-Transitions-Netze
4.1.3 Prädikat-Transitions-Netze
5 Fazit
Zielsetzung & Themen
Diese Arbeit untersucht die Anwendung von graphentheoretischen Modellen zur Lösung komplexer logistischer Optimierungs- und Simulationsprobleme. Ziel ist es, durch die Transformation realer Fragestellungen in mathematische Graphenmodelle effiziente Lösungswege aufzuzeigen und die Anwendbarkeit verschiedener algorithmischer Ansätze zu verdeutlichen.
- Optimierung von Netzwerken mittels minimal spannender Bäume
- Methoden zur Tourenplanung und zum Travelling Salesman Problem
- Modellierung von Transport- und Flussproblemen in der Logistik
- Einsatz von Petrinetzen für die Simulation komplexer dynamischer Abläufe
Auszug aus dem Buch
3.1.1 Verfahren von Kruskal
Die Idee des Kruskal Algorithmus ist es, ausgehend von einzelnen, nicht zusammenhängenden Knoten, diese nach und nach um die Kante mit der kleinsten Bewertung zu erweitern bis ein Baum entsteht. Allerdings muss darauf geachtet werden, dass sich bei Aufnahme einer neuen Kante kein Zyklus ergibt [KATH05, S. 61].
Im ersten Schritt ordnet man die Kanten aufsteigend nach ihren Bewertungen. Bei Kanten gleicher Bewertung kann die Reihenfolge beliebig erfolgen. Für den Graphen aus Abbildung 2 erhält man die Reihenfolge k12 k78 k79 k24 k36 k13 k34 k48 k57 k25 k68 k89 k14 k45.
Auf Grundlage dieser Reihenfolge kann mit dem eigentlichen Verfahren begonnen werden, indem der kantenlose Graph um die erste Kante der Reihenfolge erweitert wird. Danach werden alle weiteren Kanten der Reihenfolge nach und nach hinzugefügt, solange sie keinen Zyklus bilden. Kanten, durch die ein Zyklus entstehen würde, werden übersprungen. Dieses Vorgehen wird solange fortgeführt bis entweder alle vorhandenen Kanten durchgegangen wurden oder der Graph, durch Aufnahme genügender Kanten zum Baum geworden ist. Keiner der Knoten ist dann mehr isoliert [DOMS89, S. 41f.; MAAS93, S. 69].
Für das Beispiel aus Abbildung 2 ergibt sich ein minimal spannender Baum nach Abarbeitung der ersten neun Kanten der Reihenfolge. Allerdings muss Kante k34 übersprungen werden, da durch sie ein Zyklus entstehen würde. Wie Abbildung 3 zeigt, sind nun alle Knoten miteinander verbunden.
Zusammenfassung der Kapitel
Entstehung und Bedeutung der Graphentheorie: Historischer Abriss der Graphentheorie von den Anfängen durch Leonhard Euler bis zur Etablierung im Operations Research.
Grundlagen: Einführung in die zentralen Begriffe und Definitionen der Graphentheorie, wie Knoten, Kanten, gerichtete/ungerichtete Graphen und Bäume.
Graphentheoretische Modelle zur Optimierung: Darstellung mathematischer Verfahren zur Lösung logistischer Optimierungsprobleme, unterteilt in Kürzeste-Wege-Probleme, Tourenplanung, Transportprobleme und Flüsse.
Graphentheoretische Modelle zur Simulation: Einführung in die Simulation komplexer Systeme mittels Petrinetzen, wobei unterschiedliche Netzarten und deren Schaltlogik erläutert werden.
Fazit: Zusammenfassende Bewertung des Nutzens graphentheoretischer Modelle für die Analyse und intuitive Darstellung komplexer Fragestellungen in der Praxis.
Schlüsselwörter
Graphentheorie, Operations Research, Optimierung, Simulation, Petrinetze, Minimal spannender Baum, Travelling Salesman Problem, Transportproblem, Eulerzyklus, Netzplantechnik, Digraphen, Entscheidungsfindung, Knoten, Kanten, Flussmodellierung
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit behandelt die mathematische Modellierung logistischer Probleme mithilfe der Graphentheorie, sowohl zur rechnerischen Optimierung als auch zur Simulation dynamischer Prozesse.
Was sind die zentralen Themenfelder der Arbeit?
Die Schwerpunkte liegen auf Optimierungsmodellen (Wege, Touren, Transport) sowie Simulationsmodellen unter Verwendung verschiedener Petrinetz-Typen.
Was ist das primäre Ziel der Untersuchung?
Das Ziel ist die Vorstellung graphentheoretischer Ansätze, um komplexe logistische Realitätsszenarien effizient abzubilden und Lösungswege für Fragestellungen wie Routenminimierung oder Kapazitätsauslastung zu bieten.
Welche wissenschaftliche Methode wird verwendet?
Die Arbeit nutzt mathematische Graphenmodelle und Algorithmen, wie z.B. den Kruskal- oder Dijkstra-Algorithmus zur Optimierung sowie Petrinetze zur ereignisorientierten Simulation.
Was wird im Hauptteil behandelt?
Der Hauptteil ist in zwei große Bereiche gegliedert: Optimierungsmodelle (minimal spannende Bäume, Transport, Flüsse) und Simulationsmodelle (Petrinetze).
Welche Schlüsselwörter charakterisieren die Arbeit?
Wichtige Begriffe sind Graphentheorie, Operations Research, Optimierung, Simulation, Petrinetze und Transportplanung.
Wie unterscheidet sich der Ansatz des Dijkstra-Algorithmus vom Kruskal-Algorithmus?
Während der Kruskal-Algorithmus schrittweise Kanten zu einem kantenlosen Graphen hinzufügt, startet der Dijkstra-Algorithmus bei einem Graphen und sucht gezielt kürzeste Wege von einem Startknoten aus.
Warum sind Petrinetze für die Simulation von Vorteil?
Petrinetze ermöglichen eine anschauliche, visuelle Abbildung komplexer und nebenläufiger dynamischer Prozesse, ohne dass tiefgreifende formale mathematische Kenntnisse für das Grundverständnis erforderlich sind.
Was besagt das Min-Cut-Max-Flow-Theorem im Kontext von Flussproblemen?
Es besagt, dass der maximale Fluss durch ein Netzwerk dem Wert des kapazitätsminimalen trennenden Schnittes entspricht, der das Netzwerk in zwei Teilgraphen (Quelle und Senke) trennt.
- Quote paper
- Steffi Meier (Author), 2006, Graphentheoretische Modelle zur Optimierung und Simulation, Munich, GRIN Verlag, https://www.grin.com/document/58679
