Algorithmus von Hopcroft und Karp

Der Algorithmus von Hopcroft und Karp (1973 von John E. Hopcroft und Richard M. Karp entwickelt) dient in der Graphentheorie zur Bestimmung einer größten Paarung in einem bipartiten Graphen. Er geht aus von der Paarung, die keine Kanten enthält, und konstruiert dazu „alternierende“ Pfade zwischen noch ungepaarten Knoten. Jeder solche Pfad liefert eine Vergrößerung („Augmentierung“) der Paarung um eine Kante.

Inhaltsverzeichnis

Augmentierende Pfade

Ist zu einem Graphen mit Kantenmenge E eine Paarung P\subset E gegeben, so betrachten wir zusammenhängende Teilgraphen, die keinen Kreis enthalten (sog. Bäume) und die bestehen aus

(a) einem ungepaarten Knoten als Wurzel,
(b) gepaarten Knoten, die sich von der Wurzel aus innerhalb des Baumes erreichen lassen auf alternierenden Pfaden gerader Kantenzahl (alternierend heißt, dass die Kanten des Pfades abwechselnd zu P gehören und nicht zu P gehören; diese Knoten haben also geraden Abstand von der Wurzel) und
(c) allen Knoten und Kanten entlang der Pfade aus (b) (dadurch kommen auch Knoten ungeraden Abstandes von der Wurzel hinzu).

Eine Vereinigung solcher Bäume, die keine gemeinsamen Knoten haben, heißt Wald.

Wenn Knoten x und y aus zwei verschiedenen Bäumen des Waldes, die jeweils geraden Abstand von ihrer Wurzel haben, durch die Kante xy\in E verbunden sind, so kann diese Kante nicht zu P gehören, denn die Knoten sind ja schon durch je eine andere Kante innerhalb des Baumes gepaart (es sei denn, es handelt sich um die Wurzel, die sowieso ungepaart ist). Der Pfad mit Kantenmenge Q von der Wurzel des einen Baumes über xy zur Wurzel des anderen Baumes ist dann ein alternierender Pfad mit ungepaartem Anfangs- und Endpunkt. Ein solcher Pfad wird P-augmentierender Pfad genannt, denn (P\setminus Q)\cup (Q\setminus P) ist eine Paarung, die eine Kante mehr enthält als P.

Umgekehrt gilt, dass eine Paarung R, die mehr Kanten enthält als P, einen Teilgraph mit Kantenmenge (P\setminus R)\cup (R\setminus P) ergibt, in dem alle Pfade zwischen P und R alternieren, und von denen mindestens | R | − | P | Pfade P-augmentierend ohne gemeinsame Knoten sein müssen. P ist also genau dann eine größte Paarung, wenn es keinen P-augmentierenden Pfad gibt.

Ungarische Wälder

Bei der Definition der betrachteten Wälder wurde bisher nicht vorausgesetzt, dass ein bipartiter Graph vorliegt. In einem bipartiten Graphen (U\cup V,E) gilt aber mehr: Dort liegen die Knoten geraden Abstandes von ihrer Wurzel in U oder V, je nachdem wo die Wurzel auch liegt. Wenn es dann im Wald keine zwei Knoten x und y mit xy\in E wie im letzten Abschnitt gibt und der Wald auch nicht mehr unter Einhaltung der Eigenschaften (a) bis (c) vergrößert werden kann, heißt er ein ungarischer Wald. Wegen der Bipartitheit lässt sich dann zeigen, dass die Paarung P genau dann eine größte Paarung ist, wenn es zu ihr einen ungarischen Wald gibt.

Algorithmus

Der folgende Algorithmus ist eine Vorstufe zum Algorithmus von Hopcroft und Karp. Er konstruiert zu einem bipartiten Graphen mit Paarung P einen Wald mit Eigenschaften (a) bis (c), der

  • entweder ein ungarischer Wald ist
  • oder einen P-augmentierenden Pfad liefert.
  1. Beginne mit dem Wald, der alle ungepaarten Knoten als Wurzeln enthält, aber keine Kanten.
  2. Suche eine Kante von einem Knoten x des Waldes mit geradem Abstand von seiner Wurzel zu einem Knoten y, der nicht zum Wald gehört oder geraden Abstand von seiner Wurzel hat. Falls es keinen solchen Knoten mehr gibt, ist der Wald ein ungarischer Wald; beende den Algorithmus.
  3. Falls y geraden Abstand von seiner Wurzel hat, gibt es einen Pfad gerader Länge von einem ungepaarten Knoten z nach y; gib den P-augmentierenden Pfad von x über y nach z zurück und beende den Algorithmus.
  4. Falls y nicht zum Wald gehört, ist y gepaart, etwa yz\in P; füge die Knoten y und z sowie die Kanten xy und yz zum Wald hinzu und gehe zurück zu Schritt 2.
Ermittlung augmentierender Pfade

Zu Beginn wird der Algorithmus wird mit P=\emptyset ausgeführt. Falls er in Schritt 3 mit einem P-augmentierenden Pfad Q endet, wird P durch (P\setminus Q)\cup (Q\setminus P) ersetzt und der Algorithmus erneut durchgeführt. Der Fall, dass der Algorithmus in Schritt 2 mit einem ungarischen Wald endet (wobei dann P eine größte Paarung ist), muss nach spätestens ( | U | + | V | ) / 2 Durchläufen des Algorithmus eintreten, weil die Paarung im anderen Fall jeweils um zwei Knoten vergrößert wird. Die Laufzeit bei einmaliger Durchführung des Algorithmus ist proportional zur Kantenzahl | E | , die Gesamtlaufzeit bei mehrmaliger Durchführung also proportional zum Produkt aus Kanten- und Knotenzahl.

Beispiel

Im rechts abgebildeten Beispiel ist U=\{1,\ldots,6\} und V=\{a,\ldots,g\}. Die animierte Fassung dieser Grafik stellt die wiederholte Ausführung dieses Algorithmus dar, wobei fünfmal ein augmentierender Pfad und dann ein ungarischer Wald ermittelt wird.

Gleichzeitige Augmentierung mehrerer Pfade

Die Gesamtlaufzeit des Algorithmus kann verringert werden, wenn mehrere P-augmentierende Pfade gleichzeitig betrachtet werden. Es sei l(P) die Länge des kürzesten P-augmentierenden Pfades. Wir betrachten P-augmentierende knotendisjunkte Pfade Q_1,\ldots,Q_m der Länge l(P), denen sich kein weiterer P-augmentierender Pfad der Länge l(P) knotendisjunkt hinzufügen lässt. Dann lässt sich zeigen, dass

l\left((P\setminus(Q_1\cup\ldots\cup Q_m)) \cup ((Q_1\cup\ldots\cup Q_m)\setminus P)\right) > l(P).

Der o.g. Algorithmus kann so zum Algorithmus von Hopcroft und Karp erweitert werden, dass er nicht nur einen augmentierenden Pfad zurückgibt, sondern eine Menge augmentierender Pfade wie gerade betrachtet. Dazu müssen Schritt 2 und 3 als Breitensuche durchgeführt werden, wobei die konstruierten Pfade im Wald erst dann verlängert werden, wenn keine neuen Pfade der bisherigen Länge mehr zu finden sind. Sobald ein Pfad zu einem ungepaarten Knoten führt (also ein augmentierender Pfad ist), brauchen keine Pfade noch größerer Länge mehr betrachtet zu werden.

Ist R eine größte Paarung und n = | U | + | V | , so liefert der so erweiterte Algorithmus nach \sqrt n Durchläufen eine Paarung P mit l(P)\ge\sqrt
n und | R | − | P | knotendisjunkte P-augmentierende Pfade, deren Länge mindestens l(P)\ge\sqrt n ist. Weil keiner der n Knoten in zweien dieser Pfade enthalten ist, muss |R|-|P|\le\sqrt n sein, also muss die größte Paarung nach spätestens weiteren \sqrt n Durchläufen erreicht sein. Die Gesamtlaufzeit des Algorithmus von Hopcroft und Karp ist demnach proportional zum Produkt aus Kantenzahl und Quadratwurzel der Knotenzahl.

Literatur

  • Hubertus Th. Jongen: Optimierung B. Skript zur Vorlesung, Aachen: Verlag der Augustinus-Buchhandlung, ISBN 3-925038-19-1

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Hopcroft — John Edward Hopcroft (* 7. Oktober 1939 in Seattle) ist ein amerikanischer Informatiker. Biographie 1961 machte Hopcroft seinen ersten Abschluss als Bachelor an der Universität von Seattle, danach wechselte er an die Stanford University und… …   Deutsch Wikipedia

  • Satz von Hall — Eine Paarung (Matching) ist in der Graphentheorie eine Teilmenge der Kanten eines Graphen, in der keine zwei Kanten einen gemeinsamen Knoten besitzen. Paarungen haben innerhalb der Graphentheorie einen weiten Anwendungsbereich. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Richard M. Karp — Richard Karp 2009 Richard Manning Karp (* 3. Januar 1935 in Boston, Massachusetts) ist ein amerikanischer Informatiker. Er ist verantwortlich für bedeutende Erkenntnisse in der Komplexitätstheorie. 1985 erhielt er für seine Forschungsarbeit auf… …   Deutsch Wikipedia

  • John E. Hopcroft — John E. Hopcroft, 2009 John Edward Hopcroft (* 7. Oktober 1939 in Seattle) ist ein amerikanischer Informatiker. 1986 wurde er zusammen mit Robert Tarjan für das Design und die Analyse von Algorithmen und Datenstrukturen mit dem Turing Award… …   Deutsch Wikipedia

  • John Edward Hopcroft — (* 7. Oktober 1939 in Seattle) ist ein amerikanischer Informatiker. Biographie 1961 machte Hopcroft seinen ersten Abschluss als Bachelor an der Universität von Seattle, danach wechselte er an die Stanford University und erlangte dort 1962 den… …   Deutsch Wikipedia

  • Alternierender Pfad — Eine Paarung (Matching) ist in der Graphentheorie eine Teilmenge der Kanten eines Graphen, in der keine zwei Kanten einen gemeinsamen Knoten besitzen. Paarungen haben innerhalb der Graphentheorie einen weiten Anwendungsbereich. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Augmentierender Pfad — Eine Paarung (Matching) ist in der Graphentheorie eine Teilmenge der Kanten eines Graphen, in der keine zwei Kanten einen gemeinsamen Knoten besitzen. Paarungen haben innerhalb der Graphentheorie einen weiten Anwendungsbereich. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Größte Paarung — Eine Paarung (Matching) ist in der Graphentheorie eine Teilmenge der Kanten eines Graphen, in der keine zwei Kanten einen gemeinsamen Knoten besitzen. Paarungen haben innerhalb der Graphentheorie einen weiten Anwendungsbereich. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Größte gewichtete Paarung — Eine Paarung (Matching) ist in der Graphentheorie eine Teilmenge der Kanten eines Graphen, in der keine zwei Kanten einen gemeinsamen Knoten besitzen. Paarungen haben innerhalb der Graphentheorie einen weiten Anwendungsbereich. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Größtes Matching — Eine Paarung (Matching) ist in der Graphentheorie eine Teilmenge der Kanten eines Graphen, in der keine zwei Kanten einen gemeinsamen Knoten besitzen. Paarungen haben innerhalb der Graphentheorie einen weiten Anwendungsbereich. Inhaltsverzeichnis …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”