Robert Sedgewick: Algorithmen

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


30. Zusammenhang



Übungen

  1. Geben Sie die Gelenkpunkte und die zweifach zusammenhängenden Komponenten des Graphen an, der gebildet wird, wenn in dem Graph aus unserem Beispiel GJ gelöscht und IK hinzugefügt wird.
  2. Zeichnen Sie den Tiefensuchbaum für den in Übung 1 beschriebenen Graph.
  3. Welches ist die minimale Anzahl von Kanten, die erforderlich ist, um einen zweifach zusammenhängenden Graph mit V Knoten zu erzeugen?
  4. Erstellen Sie ein Programm zur Ausgabe der zweifach zusammenhängenden Komponenten eines Graphen.
  5. Zeichnen Sie den Wald der Vereinigungs-Suche, der für das Beispiel aus diesem Kapitel erzeugt wird, wobei jedoch angenommen werden soll, daß find dahingehend geändert wird, daß a[i]=j anstatt a[j]=i gesetzt wird.
  6. Lösen Sie die Aufgabe aus der vorangegangenen Übung unter der zusätzlichen Annahme, daß Pfadverdichtung angewandt wird.
  7. Zeichnen Sie die Wälder der Vereinigungs-Suche, die für die Kanten AB BC CD DE EF...YZ erzeugt werden, wenn zuerst angenommen wird, daß Ausgleichen des Gewichts ohne Pfadverdichtung verwendet wird, und dann, daß Pfadverdichtung ohne Ausgleichen des Gewichts verwendet wird.
  8. Lösen Sie die Aufgabe aus der vorangegangenen Übung unter der Annahme, daß sowohl Pfadverdichtung als auch Ausgleichen des Gewichts verwendet werden.
  9. Implementieren Sie die in diesem Kapitel beschriebenen Varianten der Vereinigungs-Suche, und führen Sie empirisch einen Vergleich ihrer Leistungsfähigkeit für 1000 Vereinigungs-Operationen durch, unter Verwendung von zufälligen ganzen Zahlen zwischen 1 und 100 für beide Argumente.
  10. Erstellen Sie ein Programm zur Erzeugung eines zufälligen zusammenhängenden Graphen mit V Knoten, indem Sie zufällige Paare von ganzen Zahlen zwischen 1 und V erzeugen. Schätzen Sie ab, wie viele Kanten benötigt werden, um einen zusammenhängenden Graph herzustellen, in Abhängigkeit von V.


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