Robert Sedgewick: Algorithmen

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


31. Gewichtete Graphen



Übungen

  1. Geben Sie einen weiteren minimalen Spannbaum für den Graph aus dem Beispiel zu Beginn dieses Kapitels an.
  2. Geben Sie einen Algorithmus zur Bestimmung des minimalen aufspannenden Waldes eines zusammenhängenden Graphen an (jeder Knoten muß von irgendeiner Kante berührt werden, doch der resultierende Graph muß nicht zusammenhängend sein).
  3. Existiert ein Graph mit V Knoten und E Kanten, für den die Lösung des Problems des minimalen Spannbaum mit Prioritätssuche eine zu (E + V) log V proportionale Zeit erfordern könnte? Geben Sie ein Beispiel an bzw. begründen Sie Ihre Antwort.
  4. Angenommen, wir führen in den allgemeinen Implementationen der Traversierung von Graphen die Prioritätswarteschlange als eine sortierte Liste. Wie groß wäre die Laufzeit im ungünstigsten Fall, bis auf einen konstanten Faktor genau? Wann wäre dieses Verfahren zweckmäßig, wenn überhaupt?
  5. Geben Sie Gegenbeispiele an, die zeigen, weshalb die folgende »gefräßige« Strategie weder für das Problem des kürzesten Pfades noch für das Problem des minimalen Spannbaumes geeignet ist: »Besuche bei jedem Schritt denjenigen noch nicht besuchten Knoten, der dem soeben besuchten Knoten am nächsten liegt.«
  6. Geben Sie die Bäume der kürzesten Pfade für die anderen Knoten in dem Graph aus dem Beispiel an.
  7. Beschreiben Sie, wie Sie für einen extrem umfangreichen Graph (der zu groß ist, um im Hauptspeicher untergebracht werden zu können) den minimalen Spannbaum finden würden.
  8. Erstellen Sie ein Programm zur Erzeugung von zufälligen zusammenhängenden Graphen mit V Knoten, und finden Sie dann den minimalen Spannbaum und den Baum der kürzesten Pfade für einen bestimmten Knoten. Verwenden Sie zufällige Gewichte zwischen 1 und V. Wie unterscheiden sich die Gewichte der Bäume für verschiedene Werte von V?
  9. Erstellen Sie ein Programm zur Erzeugung von zufälligen vollständigen gewichteten Graphen mit V Knoten durch einfaches Ausfüllen einer Adjazenzmatrix mit zufälligen Zahlen zwischen 1 und V. Führen Sie empirische Testläufe durch, um zu bestimmen, mit welchem Verfahren der minimale Spannbaum für V = 10, 25, 100 schneller gefunden wird: mit dem von Prim oder mit dem von Kruskal.
  10. Geben Sie ein Gegenbeispiel an, das zeigt, warum die folgende Methode zum Auffinden des Euklidischen minimalen Spannbaumes nicht funktioniert: »Sortiere die Punkte nach ihren x-Koordinaten, finde dann die minimalen Spannbäume der ersten Hälfte und der zweiten Hälfte, und finde dann die kürzeste Kante, die sie verbindet.«


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