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.
Inhalt
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
Quellenverzeichnis
1 Entstehung und Bedeutung der Graphentheorie
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.
2 Grundlagen
Um in den nächsten Kapiteln mit Graphen arbeiten zu können, müssen vorab einige Grundbegriffe geklärt werden. Weitere Begriffsdefinitionen folgen an späterer Stelle.
Ein Graph G besteht aus einer endlichen Anzahl Knoten E und Kanten K. Dargestellt werden die Knoten als Kreise, welche beispielsweise für verschiedene Orte stehen. Die Kanten verbinden jeweils zwei Knoten miteinander und können somit einen Weg zwischen zwei Orten symbolisieren.
Sind die Kanten eines Graphen gerichtet, d. h. besitzt jede Kante einen Anfangsknoten und einen Endknoten, so spricht man von einem gerichteten Graphen bzw. Digraphen. Gerichtete Kanten werden als Pfeile P dargestellt und ermöglichen die Abbildung von Abläufen [MAAS93, S. 31f.].
Besitzen zwei Kanten den gleichen Anfangs- und Endknoten, so bezeichnet man sie als parallele Kanten und den dazugehörigen Graphen als Multigraph. Besitzt dagegen eine Kante einen identischen Anfangs- und Endknoten, so bezeichnet man diese als Schlinge. Graphen ohne parallele Kanten und Schlingen nennt man schlichte Graphen. Innerhalb dieser Arbeit werden bei fast allen Beispielen schlichte Graphen verwendet [DOMS95, S. 58].
Eine Kantenfolge in einem Graphen ist eine Folge, bei der sich Ecken und Kanten abwechseln. Sind alle Ecken paarweise voneinander verschieden, so spricht man von einem Weg. Diesen Weg bezeichnet man als geschlossen bzw. als Zyklus wenn Anfangs- und Endknoten identisch sind [VOLK91, S. 10].
Wenn ein Graph zusammenhängend und die Anzahl seiner Kanten um eins kleiner ist als die Anzahl seiner Knoten, d. h. wenn der Graph keinen Kreis besitzt, spricht man von einem Baum, wenn die Summe seiner Kantenbewertungen minimal ist von einem minimal spannenden Baum [DOMS95, S. 60].
Beim Zeichnen der Graphen wird Wert auf Übersichtlichkeit gelegt. Die genaue realitätsgetreue Position der Knoten in der Ebene ist jedoch nicht notwendig um mit Graphen arbeiten zu können [MAAS93, S. 31].
Abbildung 1 zeigt einen schlichten Digraphen mit sechs Knoten und neun Kanten. Denkbare wäre z. B. die Kantenfolge e1 k12 e2 k23 e3. Sie beschreibt den Weg von Knoten 1 zu Knoten 3. Wenn man diesen Wege um den Knoten 4 und die Kanten k34 und k41 erweitert erhält man einen Zyklus, der die Knoten 1, 2, 3 und 4 enthält.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 1: Beispiel eines Graphen
3 Graphentheoretische Modelle zur Optimierung
Graphentheoretische Modelle der Optimierung werden in der Praxis sehr häufig, gerade auch im Bereich der Logistik bzw. des Operations Research, angewandt. Durch geeignete Transformation können sehr viele Probleme des Alltags einem bestimmten graphentheoretischen Modell zugeordnet werden [HÄSS79, S. 5].
Bei der Optimierung wird für ein Problem bezüglich eines bestimmten Kriteriums, mit Hilfe von mathematischen Verfahren, die beste Lösung ermittelt. Dazu wird stets eine Zielfunktion benötigt. Da die Optimierung jedoch oft sehr aufwendig ist, muss häufig auf heuristische Verfahren zurückgegriffen werden. Diese liefern jedoch höchstens durch Zufall eine optimale Lösung. Allerdings sind die Lösungen, die durch heuristische Verfahren bestimmt werden zulässig und dienen deshalb Optimierungsverfahren häufig als Ausgangslösung [MÜLL73, S. 22f.].
Im Rahmen dieser Seminararbeit werden die Optimierungsmodelle unterteilt in minimal spannenden Bäumen, Rundreisen und Touren, Transportprobleme und Flüsse in Graphen.
3.1 Minimal spannende Bäume
Kürzeste Wege spielen besonders in der Logistik eine große Rolle. Um sie zu ermitteln bedarf es in vielen Fällen lediglich der Aufstellung sogenannter minimal spannender Bäume. Genau diese Fälle sollen im Kapitel 3.1 vorgestellt werden.
Kürzeste Wege werden z. B. gesucht wenn zwischen n Orten ein Versorgungsnetz aufgebaut werden soll. Für die Versorgungsqualität bzw. -quantität ist es irrelevant, ob zwei Orte direkt durch eine Leitung verbunden werden oder indirekt über einen oder mehrere Orte [DOMS89, S. 41].
Darstellen lässt sich o. g. Beispiel mit Hilfe eines schlichten ungerichteten Graphen, an dessen Kanten die Baukosten für die Direktleitungen abgetragen werden. Um die Gesamtbaukosten zu minimieren muss mit Hilfe geeigneter Verfahren ein minimal spannender Baum aufgestellt werden [MAAS93, S. 69].
Zwei solcher Verfahren zur Bestimmung kürzester Wege, bei denen bewusst auf die Aufstellung minimal spannender Bäume Wert gelegt wird sollen im Folgenden kurz beschrieben werden. Sie sind ohne größere Berechnungen und stark am Graphen orientiert durchführbar.
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.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2: Graph, für den mit Hilfe des Kruskal Verfahrens ein minimal spannender Baum aufgestellt werden soll
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.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 3: Minimal spannender Baum nach Durchführung des Kruskal Verfahrens
[...]
- Quote paper
- Steffi Meier (Author), 2006, Graphentheoretische Modelle zur Optimierung und Simulation, Munich, GRIN Verlag, https://www.grin.com/document/58679
-
-
-
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X.