Robert Sedgewick: Algorithmen

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


33. Fluß in einem Netzwerk



Übungen

  1. Geben Sie einen Algorithmus zur Lösung des Problems des Flusses in einem Netzwerk für den Fall an, daß das Netzwerk einen Baum bildet, wenn die Senke entfernt wird.
  2. Welche Pfade werden durch den in Eigenschaft 33.3 genannten Algorithmus verfolgt, wenn der maximale Fluß in dem Netzwerk gefunden werden soll, das man erhält, wenn Kanten von B zu C und von E zu D, beide mit dem Gewicht 3, hinzugefügt werden?
  3. Skizzieren Sie für das in diesem Kapitel betrachtete Beispiel die Prioritätssuchbäume, die bei jedem Aufruf von matrixpfs berechnet werden.
  4. Geben Sie für das in diesem Kapitel betrachtete Beispiel den Inhalt der Matrix flow nach jedem Aufruf von matrixpfs an.
  5. Ist folgende Aussage wahr oder unwahr: Kein Algorithmus kann den maximalen Fluß ermitteln, ohne jede Kante im Netzwerk zu betrachten.
  6. Was geschieht mit dem Verfahren von Ford-Fulkerson, wenn das Netzwerk einen gerichteten Zyklus enthält?
  7. Geben Sie eine vereinfachte Variante der Schranke von Edmonds-Karp für den Fall an, daß alle Kapazitäten O(1) sind.
  8. Geben Sie ein Gegenbeispiel an, welches zeigt, warum die Tiefensuche für das Problem des Flusses in einem Netzwerk nicht geeignet ist.
  9. Implementieren Sie die Lösung der Breitensuche für das Problem des Flusses in einem Netzwerk unter Benutzung von sparsepfs.
  10. Erstellen Sie ein Programm zur Bestimmung des maximalen Flusses in zufälligen Netzwerken mit V Knoten und ungefähr 10V Kanten. Wie viele Aufrufe von sparsepfs erfolgen für V = 25, 50, 100?


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