Übungsblatt 7: Graphenexploration

Aufgabe 1

Betrachten Sie folgenden gerichteten Graphen:

Wenn bei den folgenden Aufgaben ein Knoten mehrere Nachfolger hat, die Sie besuchen können, dann wählen Sie jeweils den Knoten mit dem kleinsten Schlüssel.

• Welche Knoten besucht die Tiefensuche von Knoten 0? Geben Sie die Knoten in Preorder- und in Postorderreihenfolge und den induzierten Suchbaum an (Liste der Kanten oder gezeichnet).
• Welche Knoten besucht die Breitensuche von Knoten 0 aus und in welcher Reihenfolge? Geben Sie auch den induzierten Suchbaum an (Liste der Kanten oder gezeichnet).
• Eine Eigenschaft der Breitensuche ist, dass die (eindeutigen) Pfade im induzierten Suchbaum kürzesten Pfaden im ursprünglichen Graphen entsprechen. Um einen kürzesten Pfad zu extrahieren, läuft man im induzierten Suchbaum vom Zielknoten rückwärts zum Startknoten und sammelt den Pfad von hinten nach vorne auf. Welchen kürzesten Pfad erhalten Sie mit ihrem induziertem Suchbaum aus Teilaufgabe b) von Knoten 0 zu Knoten 3?

Aufgabe 2

• Geben Sie einen azyklischen, gerichteten Graphen mit 3 Knoten und drei Kanten an, bei dem die Preorder-Reihenfolge der Tiefensuche von Knoten 0 aus nicht der umgekehrten Postorder-Reihenfolge entspricht. Nehmen Sie dabei wieder an, dass bei mehreren Möglichkeiten immer der Knoten mit dem kleinsten Schlüssel besucht wird.

Geben Sie in Ihrer Lösung den Graphen sowie beide Reihenfolgen an.