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
- Verzeichnis der verwendeten Symbole und Abkürzungen
- Einleitung
- Mathematische Grundlagen
- Graphen
- Matchings
- Wege
- Bäume
- Die ungarische Methode
- Die Entstehung des Algorithmus
- Der Satz von Berge
- Der Satz von König
- Der Heiratssatz
- Der theoretische Ansatz des Algorithmus
- Die Suche nach einem augmentierenden Weg in einem Wurzelbaum
- Die Umsetzung des Algorithmus
- In einem ungewichteten Graphen
- Die Entstehung des Algorithmus
- Fazit
- Abbildungsverzeichnis
- Literaturverzeichnis
Zielsetzung und Themenschwerpunkte
Diese Bachelorarbeit befasst sich mit der ungarischen Methode, einem Algorithmus aus der Graphentheorie, genauer der linearen Optimierung. Der Algorithmus dient zur Lösung von Zuordnungsproblemen in bipartiten Graphen, sowohl ungewichteten als auch gewichteten. Der Fokus dieser Arbeit liegt auf dem ungarischen Algorithmus für ungewichtete Graphen. Das Ziel ist die Vorstellung der ungarischen Methode, die Erörterung des Problembereichs und die detaillierte Darstellung der Schritte des Algorithmus, um seine Funktionsweise nachvollziehbar zu machen. Darüber hinaus wird gezeigt, warum der ungarische Algorithmus stets Matchings mit maximalen Zuordnungen liefert.
- Der ungarische Algorithmus für ungewichtete bipartite Graphen
- Die Anwendung des Algorithmus in alltäglichen Problemstellungen
- Die mathematischen Grundlagen von Matchings und Graphen
- Die Funktionsweise des Algorithmus durch die Erklärung seiner Schritte
- Die Beweisführung der Funktionsweise des Algorithmus
Zusammenfassung der Kapitel
- Einleitung: Die Einleitung stellt den ungarischen Algorithmus als eine Methode zur Lösung von Zuordnungsproblemen in bipartiten Graphen vor. Sie beschreibt den Anwendungsbereich des Algorithmus in verschiedenen Bereichen, wie der Zuordnung von Arbeitssuchenden zu Arbeitsplätzen oder von Maschinen zu Standorten. Zudem wird der "Heiratssatz" von Philip Hall erwähnt, ein Beispiel für die Anwendung des Algorithmus in der Zuordnung von Damen zu heiratswilligen Herren.
- Mathematische Grundlagen: Dieses Kapitel erklärt grundlegende Begriffe der Graphentheorie, die für das Verständnis des ungarischen Algorithmus wichtig sind. Dazu gehören Graphen, Matchings, Wege und Bäume.
- Die ungarische Methode: Dieses Kapitel befasst sich mit der Entstehung des Algorithmus und stellt die grundlegenden Sätze vor, auf denen er beruht. Es werden die Sätze von Berge, König und Hall erklärt und bewiesen.
Schlüsselwörter
Die wichtigsten Schlüsselwörter dieser Arbeit sind: ungarische Methode, Algorithmus, bipartiter Graph, Matching, Zuordnungsproblem, lineare Optimierung, ungewichteter Graph, Satz von Berge, Satz von König, Heiratssatz, Wurzelbaum, augmentierender Weg.
- Quote paper
- Meike Voß (Author), 2010, Die ungarische Methode - ein Algorithmus für Bipartite Matchings, Munich, GRIN Verlag, https://www.hausarbeiten.de/document/173467
