Die ungarische Methode - ein Algorithmus fr Bipartite Matchings

Bachelorarbeit aus dem Jahr 2010 im Fachbereich Mathematik - Angewandte Mathematik, Note: 2,3, Technische Universitt Carolo-Wilhelmina zu Braunschweig, Sprache: Deutsch, Abstract: Diese Bachelorarbeit beschftigt sich mit der ungarischen Methode, bzw. dem ungarischen Algorithmus. Dieser Algorithmus stammt aus dem Bereich der Graphentheorie. Genauer gesagt lsst er sich der linearen Optimierung zuordnen. Der ungarische Algorithmus ist eine Methode zur Lsung von ungewichteten und gewichteten Zuordnungsproblemen in bipartiten Graphen. In dieser Arbeit werde ich mich aber ausschlielich mit dem ungarischen Algorithmus fr ungewichtete Graphen beschftigen. Alle genannten Begriffe werden im Laufe dieser Arbeit geklrt.

Da die Optimierungsprozesse mich im Studium sehr interessiert haben, entschied ich mich fr ein Thema aus diesem Bereich. Besonders interessant ist, dass sich die teilweise komplexen Probleme und deren Lsungen sehr gut durch Beispiele aus dem Alltag veranschaulichen lassen. So ist es auch mit dem ungarischen Algorithmus. Er liefert in einem ungewichteten Graphen die grtmgliche Zuordnung und in einem gewichteten Graphen die Zuordnung mit der besten Bewertung.
Ein Beispiel fr eine solche Art von Zuordnung ist, die Paarung von Arbeitssu-chenden zu freien Arbeitspltzen, wobei jeder Arbeitssuchende fr eine bestimmte Anzahl von Arbeitspltzen qualifiziert ist. Auch die Zuordnung von Maschinen zu bestimmten Standorten lsst sich unter diesen Bereich fassen. Hierbei wird angestrebt, die Kosten, die bei dem Transport einer Maschine zu einem Standort entstehen, mglichst 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. mglichst viele, Damen einen Herren heiraten, der ihnen gefllt. Hierauf werde ich spter noch genauer eingehen, wenn ich zu dem sogenannten `Heiratssatz komme, der von dem Englnder Philip Hall entwickelt wurde.