RWTH Aachen Lehrgebiet Theoretische Informatik Rossmanith–Hensel–Kuinke–Sánchez SS 2016 Blatt 8 13. Juni 2016 Übung zur Vorlesung Datenstrukturen und Algorithmen Aufgabe T23 Entwickeln Sie eine Möglichkeit, die Adjazenzmatrix eines ungerichteten Graphens mit n Knoten in höchstens n(n − 1)/2 Einträgen zu speichern, so daß es trotzdem in O(1) Schritten möglich ist zu entscheiden, ob zwei Knoten i, j adjazent sind. Aufgabe T24 Führen Sie eine Tiefensuche auf dem folgenden Graphen durch. Geben Sie zu jedem Knoten discovery und finish Zeiten an, und geben Sie dann zu jeder Kante an, welchen Typ sie bezüglich des entstandenen Tiefensuchwaldes hat (Baumkante, Vorwärtskante, Rückwärtskante, Querkante). Welche starken Zusammenhangskomponenten hat der Graph? Aufgabe T25 Beweisen oder widerlegen Sie: Ergibt eine Tiefensuche in einem ungerichteten Graphen genau eine Rückwärtskante, so liefert jede Tiefensuche in diesem Graphen genau eine Rückwärtskante. Aufgabe H20 (10 Punkte) Beweisen oder widerlegen Sie: Ergibt eine Tiefensuche in einem gerichteten Graphen genau eine Rückwärtskante, so liefert jede Tiefensuche in diesem Graphen genau eine Rückwärtskante. Aufgabe H21 (5+3 Punkte) Beweisen oder widerlegen Sie: a) Wenn eine Tiefensuche auf einem ungerichteten Graphen durchgeführt wird, erhalten wir keine Querkanten. b) Wenn eine Tiefensuche auf einem gerichteten Graphen durchgeführt wird, erhalten wir keine Querkanten. Aufgabe H22 (10 Punkte) Verwenden Sie den Algorithmus von Kosaraju, um die starken Zusammenhangskomponenten dieses Graphen zu finden.
© Copyright 2024 ExpyDoc
