Die ungarische Methode - ein Algorithmus für Bipartite Matchings

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