Robert Sedgewick: Algorithmen

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


34. Paarung



Übungen

  1. Finden Sie alle Paarungen mit fünf Kanten für den bipartiten Graph in Abbildung 34.2.
  2. Verwenden Sie den in diesem Kapitel angegebenen Algorithmus zur Bestimmung von maximalen Paarungen für zufällige bipartite Graphen mit 50 Knoten und 100 Kanten. Wie viele Kanten umfassen die Paarungen ungefähr?
  3. Konstruieren Sie einen bipartiten Graph mit sechs Knoten und acht Kanten, der eine drei Kanten umfassende Paarung aufweist, oder beweisen Sie, daß keiner existiert.
  4. Angenommen, die Knoten in einem bipartiten Graph stellen Arbeiten und Personen dar, und jeder Person sollen zwei Arbeiten zugewiesen werden. Würde die Zurückführung auf den Fluß in einem Netzwerk einen Algorithmus für dieses Problem liefern? Beweisen Sie Ihre Antwort.
  5. Modifizieren Sie das Programm des Flusses in einem Netzwerk aus Kapitel 33 dahingehend, daß die spezielle Struktur der 0-1 Netzwerke ausgenutzt wird, die bei der bipartiten Paarung entstehen.
  6. Erstellen Sie ein effizientes Programm, mit dem bestimmt werden kann, ob eine Zuordnung für das Problem der stabilen Ehe stabil ist.
  7. Ist es möglich, daß bei dem Algorithmus der stabilen Ehe zwei Herren ihre jeweils letzte Wahl bekommen? Beweisen Sie Ihre Antwort.
  8. Konstruieren Sie eine Menge von Präferenzlisten für N = 4 für das Problem der stabilen Ehe, bei der jede Person ihre zweite Wahl bekommt, oder beweisen Sie, daß eine solche Menge nicht existiert.
  9. Geben Sie eine stabile Konfiguration für das Problem der stabilen Ehe für den Fall an, daß die Präferenzlisten für Herren und Damen alle gleich sind: in aufsteigender Reihenfolge.
  10. Lassen Sie das Programm für das Problem der stabilen Ehe für N = 50 ablaufen, unter Verwendung von zufälligen Permutationen für die Präferenzlisten. Wie viele Anträge werden während der Ausführung des Algorithmus ungefähr gemacht?


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