Für neue Kunden:
Für bereits registrierte Kunden:
Bachelorarbeit, 2010
33 Seiten, Note: 2,3
1. Verzeichnis der verwendeten Symbole und Abkürzungen
2. Einleitung
3. Mathematische Grundlagen
3.1 Graphen
3.2 Matchings
3.3 Wege
3.4 Bäume
4. Die ungarische Methode
4.1 Die Entstehung des Algorithmus
4.1.1 Der Satz von Berge
4.1.2 Der Satz von König
4.1.3 Der Heiratssatz
4.2 Der theoretische Ansatz des Algorithmus
4.2.1 Die Suche nach einem augmentierenden Weg in einem Wurzelbaum
4.3 Die Umsetzung des Algorithmus
4.3.1 In einem ungewichteten Graphen
5. Fazit
6. Abbildungsverzeichnis
7. Literaturverzeichnis
Abbildung in dieser Leseprobe nicht enthalten
Diese Bachelorarbeit beschäftigt sich mit der ungarischen Methode, bzw. dem ungarischen Algorithmus. Dieser Algorithmus stammt aus dem Bereich der Graphentheorie. Genauer gesagt lässt er sich der linearen Optimierung zuordnen. Der ungarische Algorithmus ist eine Methode zur Lösung von ungewichteten und gewichteten Zuordnungsproblemen in bipartiten Graphen. In dieser Arbeit werde ich mich aber ausschließlich mit dem ungarischen Algorithmus für ungewichtete Graphen beschäftigen. Alle genannten Begriffe werden im Laufe dieser Arbeit geklärt.
Da die Optimierungsprozesse mich im Studium sehr interessiert haben, entschied ich mich für ein Thema aus diesem Bereich. Besonders interessant ist, dass sich die teilweise komplexen Probleme und deren Lösungen sehr gut durch Beispiele aus dem Alltag veranschaulichen lassen. So ist es auch mit dem ungarischen Algorithmus. Er liefert in einem ungewichteten Graphen die größtmögliche Zuordnung und in einem gewichteten Graphen die Zuordnung mit der besten Bewertung.
Ein Beispiel für eine solche Art von Zuordnung ist, die Paarung von Arbeitssuchenden zu freien Arbeitsplätzen, wobei jeder Arbeitssuchende für eine bestimmte Anzahl von Arbeitsplätzen qualifiziert ist. Auch die Zuordnung von Maschinen zu bestimmten Standorten lässt sich unter diesen Bereich fassen. Hierbei wird angestrebt, die Kosten, die bei dem Transport einer Maschine zu einem Standort entstehen, möglichst gering zu halten.
Das wohl bekannteste Beispiel ist aber die Zuordnung von Damen zu heiratswilligen Herren. Dabei soll eine derartige Paarung gefunden werden, sodass alle, bzw. möglichst viele, Damen einen Herren heiraten, der ihnen gefällt. Hierauf werde ich später noch genauer eingehen, wenn ich zu dem sogenannten 'Heiratssatz' komme, der von dem Engländer Philip Hall entwickelt wurde.
Dies alles sind sehr interessante Beispiele für die der ungarische Algorithmus eine Lösung liefert.
Die Zielsetzung dieser Bachelorarbeit ist es, die ungarische Methode vorzustellen,um den Problembereich genauer zu erörtern. Außerdem werde ich die einzelnen Schritte des ungarischen Algorithmus so darstellen, dass nachvollziehbar wird, wie der Algorithmus arbeitet. Anschließend soll deutlich gemacht werden, warum der ungarische Algorithmus funktioniert. Das heißt, dass ich zeigen werde, dass er immer Matchings mit maximalen Zuordnungen liefert.
Es wird also aufgezeigt, dass alltägliche Probleme in den Bereich der Graphentheorie überführt werden können, sodass mithilfe von Algorithmen das Finden von Lösungen ermöglicht wird.
Um eine verständliche Abfolge zu gewährleisten, habe ich mich für den folgenden Aufbau entschieden.
Zu Beginn werde ich einige Begrifflichkeiten in den mathematischen Grundlagen klären. Dabei werde ich näher auf den Begriff des Graphen eingehen, da der ungarische Algorithmus Matchings in bipartiten Graphen liefert. Danach werde ich die Definition des Matchings und die verschiedenen Arten von Matchings erläutern, denn das Finden von Matchings erfasst gerade den Problembereich, für den der ungarische Algorithmus eine Lösung liefert. Anschließend folgt die Klärung des Begriffs 'Weg'. Dies ist notwendig, da der Algorithmus mithilfe von Wegen in Bäumen arbeitet. Daher wird danach auf die Bedeutung von Bäumen eingegangen. Diese Reihenfolge finde ich sinnvoll, da die Begriffsklärungen aufeinander aufbauen.
Als nächstes werde ich dann zu der ungarischen Methode kommen. An dieser Stelle gehe ich zunächst auf die Entstehung des Algorithmus ein, wobei die Namensgebung, sowie Grundlagen, auf denen der Algorithmus beruht, geklärt werden. Die grundlegenden Sätze werden dann erklärt und bewiesen. Zuletzt werde ich den ungarischen Algorithmus beweisen und anhand einer praktischen Durchführung zeigen, wie die Lösung eines alltäglichen Problems aussehen könnte.
Dieses Kapitel ist, wie schon erwähnt, nach einer logischen Abfolge aufgebaut. Das heißt, dass die Unterpunkte so aufeinander folgen, dass kein Begriff mit einem darauffolgenden erklärt wird. Im Verlauf der Arbeit werde ich die hier geklärten Begriffe verwenden.
Ein Graph ist ein Paar [Abbildung in dieser Leseprobe nicht enthalten], wobei V und E disjunkte Mengen sind. V ist eine nichtleere Menge und E besteht aus zweielementigen Teilmengen von V, also [Abbildung in dieser Leseprobe nicht enthalten] oder [Abbildung in dieser Leseprobe nicht enthalten].
Die Elemente der Menge V werden als Ecken und die Elemente der Menge E als Kanten des Graphen bezeichnet.1
Die Anzahl der Elemente, die eine Menge V enthält, heißt Mächtigkeit |V| der Menge.2 Ist die Anzahl der Ecken in einem Graphen G endlich, also [Abbildung in dieser Leseprobe nicht enthalten], so ist G ein endlicher Graph. Andernfalls ist G ein unendlicher Graph3
Ecken werden im Folgenden immer durch Kleinbuchstaben i,j,... mit i,j g V bezeichnet. Kanten werden durch die sie begrenzenden Ecken bezeichnet. Die Kante zwischen den Ecken i und j wird zum Beispiel mit ij oder ji bezeichnet, wobei ij л ji g E gilt. Weiterhin wird mit e g E eine beliebige Kante der Kantenmenge E des Graphen bezeichnet.
Bildlich lassen sich die Ecken als Punkte und die Kanten als Verbindungslinien zwischen den Punkten veranschaulichen. Wie dieses Diagramm von einem Graphen aussieht, kann variieren. Wichtig hierbei ist, dass es keine Abhängigkeit der formalen Definition des Graphen von einem seiner Diagramme gibt.
Beispiel:[Abbildung in dieser Leseprobe nicht enthalten].4
Abbildung in dieser Leseprobe nicht enthalten
Abb.1: Diagramm 1 des Graphen G = (V,E) Abb.2: Diagramm 2 des Graphen G = (V,E)
Ein Graph lässt sich also durch unterschiedliche Diagramme veranschaulichen. Bilden zwei Ecken a und b die Endpunkte einer Kante ab, so inzidiert die Kante ab mit diesen Ecken. Sind a und b durch ab verbunden und es gilt: a ψ b, so heißen die Ecken a und b Nachbarn N. Falls aber gilt: a = b, so heißt die Kante ab Schlinge.5 Die Anzahl der Kanten, die eine Ecke verlassen oder in dieser enden, heißt Grad einer Ecke.6
Eine Eckenmenge U von G wird als Eckenüberdeckung von G bezeichnet, falls alle Kanten aus G mit mindestens einer Ecke aus U inzidieren. Existiert nun keine andere Eckenüberdeckung U* von G, mit |U*| < |tf|, ist U die minimale Eckenüberdeckung von G. Eine Ecke v heißt überdeckt, falls gilt: v£U. 7
Abbildung in dieser Leseprobe nicht enthalten
Abb.3: Graph G mit der Eckenüberdeckung U
In einem gewichteten Graphen wird jeder Kante e von G ein Kantengewicht g(e) £ M+ zugeordnet.8
Folglich wird in einem ungewichteten Graphen den Kanten e von G kein Kantengewicht zugeordnet.
Ein Graph G = (V, E) wird als p-partit, mit p ≥ 2 und pEM, bezeichnet, wenn sich V(G) in p paarweise disjunkte Eckenmengen V-^ ...,VP zerlegen lässt. Innerhalb einer Eckenmenge ...,VP dürfen keine Ecken durch eine Kante miteinander verbunden sein. Vl, ...,VP werden als Partitionen des Graphen bezeichnet.
Ein Graph mit zwei Partitionen, p = 2, wird bipartit genannt. Vl und V2 bilden die Bipartition von G.9
Abbildung in dieser Leseprobe nicht enthalten
Sei G = (V, E) ein Graph. Als Matching (Paarung, Zuordnung) von G lässt sich eine Kantenmenge M von G bezeichnen, in der keine Schlingen enthalten und keine Kante aus M mit einer anderen aus M inzidiert.10 Jede Ecke eines Matchings hat höchstens den Grad 1.11 Ecken, die mit einer Matchingkante inzidieren, und Kanten, die Elemente von M sind, heißen gesättigt oder gematcht.
Gibt es kein Matching M in G, sodass gilt: M0ÇM und es gilt M0 ψ M, so heißt M0 gesättigtes Matching von G.
Existiert in G kein Matching mit einer größeren Anzahl von Kanten als M*, also kein M, sodass gilt: |M*| < |M|, heißt M* maximales Matching von G.
Ein Matching M heißt perfekt, wenn es alle Ecken von G sättigt. Also gilt:
G[M] = (E(M), M) ist ein perfektes Matching.12
Abbildung in dieser Leseprobe nicht enthalten
Abb.6: Gesättigtes Matching Abb.7: Maximales Matching Abb.8: Perfektes Matching
In einem bipartiten Graphen G = (V, E) mit der Bipartition A, B gilt:
Abbildung in dieser Leseprobe nicht enthalten
Das bedeutet, dass eine Kanten e des Matchings immer durch eine Ecke an g A und eine Ecke bn G B begrenzt wird. e = anbn.13
Ein Kantenzug in einem Graphen G = (V,E) wird durch eine Folge ( v0,v1,_,vn), mit n g N, von Ecken gebildet. Zwei Ecken, die aufeinander folgen, müssen durch eine Kante verbunden, also benachbart sein. Somit gilt: ei := {vifVi+1} g E, mit i = 0f1f ...f n — 1.
Ein Kantenzug, dessen Start- und Endecke identisch und alle Kanten verschieden sind, heißt Kreis.
Ein Weg besteht aus einem Kantenzug, dessen Start- und Endecke verschieden sind und in dem jede Kante e nur einmal vorkommt.14
Es sei G ein Graph und M ein Matching von G. Ein Weg heißt alternierend bezüglich M, wenn er abwechselnd aus Kanten des Matchings und Kanten von G besteht und die Startecke ungesättigt ist.
Sind die erste und letzte Kante eines alternierenden Weges keine Matching- kanten, so heißt dieser Weg augmentierend oder erweiternd bezüglich M. Durch das Austauschen der gesättigten und der ungesättigten Kanten des augmentie- renden Weges wird das ursprüngliche Matching um eine Kante vergrößert. Dies wird das Kantenaustauschverfahren genannt.15
[...]
1 Vgl. Förster, Frank: GT-Gesamt_20090927, Wintersemester 2009/2010, Kapitel 1: Grundlegende Begriffe der Graphentheorie, S.1.
2 Vgl. Schubert, Matthias: Mathematik für Informatiker, Vieweg + Teubner Verlag Wiesbaden 2009, S.50.
3 Vgl. Förster: Kapitel 1: S.4.
4 Vgl. Diestel, Reinhard: Graphentheorie, Springer-Verlag Berlin 2006, S. 2
5 Vgl. Volkmann, Lutz: Fundamente der Graphentheorie, Springer-Verlag Wien 1996, S. 1.
6 Vgl. Schubert (2009, 329).
7 Vgl. Volkmann (1996, 192).
8 Verfügbar über: http://math-www.uni-paderborn.de/~chris/Index41/V/par7.pdf Datum des Zugriffs: 20.05.2010.
9 Vgl. Volkmann (1996, 82).
10 Vgl. Volkmann (1996, 113).
11 Vgl. Schubert (2009, 465).
12 Vgl. Volkmann (1996, 113).
13 Vgl. Diestel (2006, 38).
14 Vgl. Förster: Kapitel 1, S. 5.
15 Vgl. Tittmann, Peter: Graphentheorie, Fachbuchverlag Leipzig im Carl Hanser Verlag 2003, S. 65.