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 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 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.
Inhaltsverzeichnis
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
Zielsetzung & Themen
Die vorliegende Arbeit hat zum Ziel, die ungarische Methode als effizienten Algorithmus zur Lösung von Zuordnungsproblemen in bipartiten Graphen vorzustellen und ihre mathematische Funktionsweise sowie Anwendbarkeit anhand praktischer Beispiele zu verdeutlichen.
- Grundlagen der Graphentheorie (Graphen, Matchings, Wege, Bäume)
- Entstehung und theoretische Fundierung des ungarischen Algorithmus
- Beweisführung zentraler Sätze wie der Satz von Berge und der Satz von König
- Praktische Anwendung des Algorithmus an einem Beispiel zur Arbeitsvermittlung
Auszug aus dem Buch
4.1 Die Entstehung des Algorithmus
Der amerikanische Mathematiker Harold William Kuhn veröffentlichte 1955 zu ersten Mal den ungarischen Algorithmus in der Schrift mit dem Titel „The Hungarian Method for the Assignment Problem“. Den Namen für den Algorithmus hat Kuhn gewählt, um die Arbeit der beiden ungarischen Mathematiker Dénes König und Eugene Egerváry zu würdigen, auf deren Arbeiten er sich gestützt hat. Im Folgenden werden der Satz von Berge, der Satz von König und der Heiratssatz von Hall erläutert und bewiesen, da hierbei ein starker Zusammenhang zu dem ungarischen Algorithmus besteht.
Zusammenfassung der Kapitel
2. Einleitung: Einführung in das Thema der Zuordnungsprobleme und Darlegung der Zielsetzung, den ungarischen Algorithmus verständlich zu erklären.
3. Mathematische Grundlagen: Definition grundlegender graphentheoretischer Begriffe wie Graphen, Matchings, Wege und Bäume, die für das Verständnis der Methode essentiell sind.
4. Die ungarische Methode: Erläuterung der historischen Entwicklung, der theoretischen Ansätze inklusive der Beweise der zentralen Sätze sowie die praktische Durchführung des Algorithmus.
5. Fazit: Zusammenfassende Bewertung der Methode als effektives Werkzeug zur Bestimmung maximaler Matchings und Reflexion über den Erkenntnisgewinn durch die Arbeit.
Schlüsselwörter
Ungarische Methode, Algorithmus, Graphentheorie, Bipartite Graphen, Matching, Maximale Zuordnung, Satz von Berge, Satz von König, Heiratssatz, Wurzelbaum, Lineare Optimierung, Arbeitsvermittlung, Augmentierende Wege, Kantenaustauschverfahren, Eckenüberdeckung
Häufig gestellte Fragen
Worum geht es in der Arbeit grundlegend?
Die Arbeit behandelt den sogenannten ungarischen Algorithmus, eine Methode aus der Graphentheorie zur Lösung von Zuordnungsproblemen in bipartiten Graphen.
Was sind die zentralen Themenfelder?
Die zentralen Themen sind graphentheoretische Definitionen, die Herleitung des ungarischen Algorithmus über mathematische Sätze und dessen praktische Anwendung.
Was ist das primäre Ziel der Untersuchung?
Das Ziel ist die Vorstellung der ungarischen Methode und eine so detaillierte Darstellung der Schritte, dass die Funktionsweise und das Erreichen maximaler Zuordnungen für den Leser nachvollziehbar wird.
Welche wissenschaftliche Methode wird verwendet?
Es wird eine theoretische Erörterung der mathematischen Grundlagen sowie eine beweisgestützte Herleitung der Algorithmus-Logik verwendet, ergänzt durch ein Anwendungsbeispiel.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in mathematische Grundlagen, die Entstehung des Algorithmus, die theoretische Herleitung sowie die Anwendung in einem ungewichteten Graphen.
Welche Schlüsselwörter charakterisieren die Arbeit?
Zu den wichtigsten Begriffen zählen ungarische Methode, bipartite Graphen, Matching, Satz von Berge, Satz von König und Heiratssatz.
Warum ist der Satz von Berge wichtig für den Algorithmus?
Der Satz von Berge beweist, dass ein Matching genau dann maximal ist, wenn kein augmentierender Weg existiert, was die Basis für die Effektivität des Algorithmus bildet.
Welchen Zweck erfüllt das Beispiel der Arbeitsvermittlung?
Das Beispiel dient dazu, einen abstrakten graphentheoretischen Prozess anschaulich zu machen und die praktische Anwendbarkeit zur Optimierung von Zuordnungen zu verdeutlichen.
Was besagt der Heiratssatz von Philip Hall?
Er bietet ein Kriterium, um zu bestimmen, ob in einem bipartiten Graphen ein Matching existiert, das alle Ecken einer Teilmenge sättigt.
- Quote paper
- Meike Voß (Author), 2010, Die ungarische Methode - ein Algorithmus für Bipartite Matchings, Munich, GRIN Verlag, https://www.hausarbeiten.de/document/173467
