Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


34. Paarung



Bipartite Graphen

Das oben erwähnte Beispiel, das die Zuordnung von Medizinstudenten zu Arbeitsplätzen betraf, kann sicher stellvertretend für viele andere Anwendungen der Paarung stehen. Zum Beispiel könnten in einem Eheanbahnungsinstitut Herren und Damen einander zugeordnet werden, Anwärter auf eine Stellung könnten freien Stellen zugeordnet werden, oder Abgeordnete zu Ausschüssen. Die Graphen, die in solchen Fällen auftreten, werden bipartite Graphen genannt. Dies sind Graphen, bei denen alle Kanten zwischen zwei Mengen von Knoten verlaufen. Das bedeutet, daß sich die Knoten in zwei Mengen einteilen lassen und keine Kanten zwei Knoten der gleichen Menge verbinden. (Offenbar beabsichtigen wir nicht, einen Stellenanwärter mit einem anderen oder eine Funktion in einem Ausschuß mit einer anderen zu »paaren«.) Abbildung 34.2 zeigt ein Beispiel eines bipartiten Graphen. Der Leser kann versuchen, eine maximale Paarung in diesem Graph zu suchen.

Abbildung 34.2
Abbildung 34.2 Ein bipartiter Graph.

Bei einer Darstellung bipartiter Graphen mittels Adjazenzmatrix kann man offensichtliche Einsparungen erzielen, indem man für eine Menge nur Zeilen und für die andere Menge nur Spalten verwendet. Bei einer Darstellung mittels Adjazenzliste bieten sich keine besonderen Einsparungen an, abgesehen von einer geschickten Bezeichnung der Knoten, so daß einfach zu erkennen ist, welcher Menge ein Knoten angehört.

In unseren Beispielen verwenden wir Buchstaben für die Knoten der einen Menge und Zahlen für die der anderen. Das Problem der maximalen Paarung für bipartite Graphen kann bei dieser Darstellungsweise einfach ausgedrückt werden: »Finde die größte Teilmenge einer Menge aus Buchstaben und Zahlen bestehender Paare mit der Eigenschaft, daß keine zwei Paare den gleichen Buchstaben oder die gleiche Zahl enthalten.« Die Bestimmung der maximalen Paarung für den bipartiten Graph in Abbildung 34.2 entspricht der Lösung dieses Puzzles für die Paare E5 A2 A1 C1 B4 C3 D3 B2 A4 D5 E3 B1 C6 E6 F2 F5 F6.

Es ist ein interessanter Versuch, eine direkte Lösung für das Problem der Paarung für bipartite Graphen zu finden. Das Problem scheint auf den ersten Blick einfach zu sein, doch Schwierigkeiten werden schnell sichtbar. Mit Sicherheit gibt es viel zu viele Paarungen, als daß alle Möglichkeiten ausprobiert werden könnten; eine Lösung für das Problem muß genügend geschickt sein, so daß nur einige wenige der möglichen Varianten der Zusammenstellung der Knoten zu Paaren ausprobiert werden.

Die Lösung, die wir betrachten wollen, ist von indirekter Art: Um ein spezielles Paarungsproblem zu lösen, konstruieren wir ein Beispiel des Problems des Flusses in einem Netzwerk, benutzen den Algorithmus aus dem vorangegangenen Kapitel und verwenden dann die Lösung des Problems des Flusses in einem Netzwerk, um das Paarungsproblem zu lösen. Das heißt, wir führen das Paarungsproblem auf das Problem des Flusses in einem Netzwerk zurück. Das Zurückführen (Reduktion) ist eine Methode zur Algorithmenentwicklung, die in gewisser Hinsicht der Verwendung eines Unterprogramms aus einer Bibliothek entspricht. Es ist in der Theorie der höherentwickelten kombinatorischen Algorithmen von grundlegender Bedeutung (siehe Kapitel 40). Einstweilen wird uns die Methode des Zurückführens eine effiziente Lösung für das Problem der bipartiten Paarung liefern.

Zu einem gegebenen Problem der bipartiten Paarung erstellen wir ein entsprechendes Problem für den Fluß in einem Netzwerk, indem wir zunächst einen neuen Knoten als Quelle erzeugen. Von diesem aus führen Kanten zu allen Knoten der einen Menge im bipartiten Graphen. Dann führen alle Kanten von Knoten dieser ersten Menge zu den Knoten der zweiten Menge abwärts; die letzteren erhalten zusätzlich eine weitere Kante, die zu einem ebenfalls neu erstellten Senken-Knoten führt. Alle Kanten in dem resultierenden Graph erhalten die Kapazität 1.

Abbildung 34.3 zeigt, ausgehend von dem bipartiten Graph aus Abbildung 34.2, die Konstruktion eines Problems des Flusses in einem Netzwerk, gefolgt von der Anwendung des Algorithmus des Flusses in einem Netzwerk aus dem vorangegangenen Kapitel. Beachten Sie, daß die bipartite Eigenschaft des Graphen, die Richtung des Flusses und die Tatsache, daß alle Kapazitäten den Wert eins haben, dazu führen, daß jeder Pfad durch das Netzwerk einer Kante in einer Paarung entsprechen muß: Im Beispiel entsprechen die in den ersten vier Schritten gefundenen Pfade der partiellen Paarung A1 B2 C3 D5. Jedesmal, wenn der Algorithmus des Flusses in einem Netzwerk pfs aufruft, findet er entweder einen Pfad, der den Fluß um eins erhöht, oder er bricht ab.

Abbildung 34.3
Abbildung 34.3 Benutzung des Flusses in einem Netzwerk zur Bestimmung einer maximalen Paarung in einem bipartiten Graph.

Im fünften Schritt sind alle vorwärts durch das Netzwerk führenden Pfade voll, und der Algorithmus muß Rückwärts-Kanten benutzen. Der in diesem Schritt gefundene Pfad ist der Pfad 4B2F. Dieser Pfad erhöht eindeutig den Fluß in dem Netzwerk, wie im vorangegangenen Kapitel beschrieben wurde. Im Zusammenhang mit der jetzigen Anwendung können wir uns den Pfad als eine Folge von Anweisungen vorstellen, wie aus der aktuellen partiellen Paarung eine neue (mit einer Kante mehr) erzeugt werden kann. Diese Konstruktion ergibt sich in natürlicher Weise, wenn man den Verlauf des Pfades verfolgt: »4B« bedeutet das Hinzufügen von B4 zur Paarung, »B2« bedeutet das Entfernen von B2, und »2F« bedeutet das Hinzufügen von F2 zur Paarung. Somit liegt, nachdem dieser Pfad verarbeitet worden ist, die Paarung A1 B4 C3 D5 E6 F2 vor; äquivalent dazu ist die Aussage, daß der Fluß in dem Netzwerk durch volle Leitungen in den diese Knoten verbindenden Kanten gegeben ist. Der Algorithmus endet mit der Realisierung der Paarung F6; alle Leitungen, die aus der Quelle hinausführen und in die Senke hineinführen, sind voll, so daß eine maximale Paarung vorliegt.

Der Beweis, daß die Paarung genau jenen Kanten entspricht, die im Ergebnis des Algorithmus des maximalen Flusses bis an die Grenze ihrer Kapazität gefüllt werden, ist sehr einfach. Erstens ergibt der Fluß in einem Netzwerk stets eine zulässige Paarung: Da jeder Knoten entweder eine hineinführende Kante (von der Senke) oder eine hinausführende Kante (zur Quelle) mit der Kapazität eins hat, kann durch jeden Knoten höchstens eine Einheit des Flusses gehen. Dies führt dazu, daß jeder Knoten höchstens einmal in die Paarung einbezogen wird. Zweitens kann keine Paarung mehr Kanten enthalten, da jede derartige Paarung sofort zu einem Fluß führen würde, der besser ist als der mit dem Algorithmus des maximalen Flusses erzeugte Fluß.

Um die maximale Paarung für einen bipartiten Graph zu berechnen, geben wir somit dem Graph einfach eine solche Form, daß er für die Eingabe in den Algorithmus für den Fluß in einem Netzwerk aus dem vorangegangenen Kapitel geeignet ist. Natürlich sind die Graphen, auf die der Algorithmus für den Fluß in einem Netzwerk in diesem Falle angewandt wird, viel einfacher als die allgemeinen Graphen, für deren Verarbeitung der Algorithmus bestimmt ist, und es erweist sich, daß der Algorithmus für diesen Fall etwas effizienter ist.

Eigenschaft 34.1 Eine maximale Paarung in einem bipartiten Graph kann in O(V3) Schritten gefunden werden, falls der Graph dicht ist, oder in O(V(E + V) log V) Schritten, wenn der Graph licht ist.

Die Konstruktion gewährleistet, daß jeder Aufruf von pfs der Paarung eine Kante hinzufügt, so daß wir wissen, daß während der Ausführung des Algorithmus höchstens V/2 Aufrufe von pfs erfolgen. Daher ist die benötigte Zeit zu einer Größe proportional, die um den Faktor V größer ist als die Zeit für einen einzelnen Suchvorgang, die in Kapitel 31 betrachtet wurde. w.z.b.w.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]