Robert Sedgewick: Algorithmen

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


32. Gerichtete Graphen



Übungen

  1. Geben Sie die Adjazenzmatrix für die transitive Hülle des dag in Abbildung 32.8 an.
  2. Welches Ergebnis erhielte man, wenn man die Algorithmen für die transitive Hülle auf einen ungerichteten Graph anwenden würde, der mittels einer Adjazenzmatrix dargestellt ist?
  3. Erstellen Sie ein Programm zur Bestimmung der Anzahl der Kanten in der transitiven Hülle eines gegebenen gerichteten Graphen unter Verwendung einer Darstellung mittels Adjazenzliste.
  4. Stellen Sie einen Vergleich zwischen dem Algorithmus von Warshall und dem in diesem Kapitel beschriebenen, unter Verwendung der Tiefensuche abgeleiteten Algorithmus für die transitive Hülle an, jedoch unter Benutzung der einer Adjazenzmatrix entsprechenden Form von visit und bei Beseitigung der Rekursion.
  5. Geben Sie die topologische Reihenfolge an, die für den in Abbildung 32.8 angegebenen dag erzeugt wird, wenn die vorgeschlagene Methode mit einer Darstellung mittels Adjazenzmatrix angewandt wird, dfs jedoch beim Suchen nach noch nicht besuchten Knoten die Knoten in umgekehrter Reihenfolge (von V bis 1) durchläuft.
  6. Ist der Algorithmus des kürzesten Pfades aus Kapitel 31 auf gerichtete Graphen anwendbar? Erklären Sie, warum, bzw. geben Sie ein Beispiel an, wo er scheitert.
  7. Erstellen Sie ein Programm, mit dem bestimmt werden kann, ob ein gegebener gerichteter Graph ein dag ist oder nicht.
  8. Wie viele streng zusammenhängende Komponenten existieren in einem dag? In einem Graph mit einem gerichteten Zyklus der Größe V?
  9. Benutzen Sie Ihre Programme aus den Kapiteln 29 und 30, um umfangreiche zufällige gerichtete Graphen mit V Knoten zu erzeugen. Wie viele streng zusammenhängende Komponenten haben solche Graphen im allgemeinen etwa?
  10. Erstellen Sie ein Programm, welches von seiner Funktion her zu find aus Kapitel 30 analog ist, jedoch streng zusammenhängende Komponenten des durch die eingegebenen Kanten beschriebenen gerichteten Graphen betrifft. (Dies ist kein leichtes Problem; es wird sicher nicht gelingen, ein Programm zu erhalten, das so effizient ist wie find.)


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