Die ungarische Methode - ein Algorithmus für Bipartite Matchings

Inhaltsverzeichnis

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

1. Verzeichnis der verwendeten Symbole und Abkürzungen

Abbildung in dieser Leseprobe nicht enthalten

2. Einleitung

Diese Bachelorarbeit beschäftigt sich mit der ungarischen Methode, bzw. dem un­garischen Algorithmus. Dieser Algorithmus stammt aus dem Bereich der Graphen­theorie. Genauer gesagt lässt er sich der linearen Optimierung zuordnen. Der un­garische Algorithmus ist eine Methode zur Lösung von ungewichteten und gewich­teten 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 Al­gorithmus. Er liefert in einem ungewichteten Graphen die größtmögliche Zuord­nung und in einem gewichteten Graphen die Zuordnung mit der besten Bewer­tung.

Ein Beispiel für eine solche Art von Zuordnung ist, die Paarung von Arbeitssu­chenden 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 an­gestrebt, 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 heiratswilli­gen 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 Graphen­theorie ü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 un­garische Algorithmus Matchings in bipartiten Graphen liefert. Danach werde ich die Definition des Matchings und die verschiedenen Arten von Matchings erläu­tern, 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 eingegan­gen. 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 Na­mensgebung, sowie Grundlagen, auf denen der Algorithmus beruht, geklärt wer­den. Die grundlegenden Sätze werden dann erklärt und bewiesen. Zuletzt werde ich den ungarischen Algorithmus beweisen und anhand einer praktischen Durch­führung zeigen, wie die Lösung eines alltäglichen Problems aussehen könnte.

3. Mathematische Grundlagen

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 ei­nem darauffolgenden erklärt wird. Im Verlauf der Arbeit werde ich die hier geklär­ten Begriffe verwenden.

3.1 Graphen

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.¹

Die Anzahl der Elemente, die eine Menge V enthält, heißt Mächtigkeit |V| der Menge.² 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 Graph³

Ecken werden im Folgenden immer durch Kleinbuchstaben i,j,... mit i,j g V be­zeichnet. Kanten werden durch die sie begrenzenden Ecken bezeichnet. Die Kan­te 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 Gra­phen 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].⁴

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.⁵ Die Anzahl der Kanten, die eine Ecke verlassen oder in dieser enden, heißt Grad einer Ecke.⁶

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. ⁷

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.⁸

Folglich wird in einem ungewichteten Graphen den Kanten e von G kein Kanten­gewicht 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.⁹

Abbildung in dieser Leseprobe nicht enthalten

3.2 Matchings

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 kei­ne Kante aus M mit einer anderen aus M inzidiert.¹⁰ Jede Ecke eines Matchings hat höchstens den Grad 1.¹¹ 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.¹²

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.¹³

3.3 Wege

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.¹⁴

Es sei G ein Graph und M ein Matching von G. Ein Weg heißt alternierend bezüg­lich M, wenn er abwechselnd aus Kanten des Matchings und Kanten von G be­steht 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.¹⁵

[...]

¹ Vgl. Förster, Frank: GT-Gesamt_20090927, Wintersemester 2009/2010, Kapitel 1: Grundlegende Begriffe der Graphentheorie, S.1.

² Vgl. Schubert, Matthias: Mathematik für Informatiker, Vieweg + Teubner Verlag Wiesbaden 2009, S.50.

³ Vgl. Förster: Kapitel 1: S.4.

⁴ Vgl. Diestel, Reinhard: Graphentheorie, Springer-Verlag Berlin 2006, S. 2

⁵ Vgl. Volkmann, Lutz: Fundamente der Graphentheorie, Springer-Verlag Wien 1996, S. 1.

⁶ Vgl. Schubert (2009, 329).

⁷ Vgl. Volkmann (1996, 192).

⁸ Verfügbar über: http://math-www.uni-paderborn.de/~chris/Index41/V/par7.pdf Datum des Zugriffs: 20.05.2010.

⁹ Vgl. Volkmann (1996, 82).

¹⁰ Vgl. Volkmann (1996, 113).

¹¹ Vgl. Schubert (2009, 465).

¹² Vgl. Volkmann (1996, 113).

¹³ Vgl. Diestel (2006, 38).

¹⁴ Vgl. Förster: Kapitel 1, S. 5.

¹⁵ Vgl. Tittmann, Peter: Graphentheorie, Fachbuchverlag Leipzig im Carl Hanser Verlag 2003, S. 65.