Tiefensuche erzeugt Baum < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 16:35 Sa 19.05.2007 | | Autor: | quest |
| Aufgabe | Betrachte den folgenden Tiefensuche Algorithmus:
Alle Knoten seien unmarkiert.
Setze T := {}, B := {}.
Für alle v aus V führe aus
Ist v unmarkiert, dann CALL SEARCH(v).
Gib T und B aus, wobei T [mm] \cap [/mm] B = [mm] \emptyset [/mm] und T [mm] \cup [/mm] B = E
Funktion SEARCH(v)
Markiere v.
Für alle Knoten w aus N(v) führe aus: (N(v) sind alle Nachbarknoten von v)
Ist w markiert und vw nicht in T, setze B := B [mm] \cup [/mm] {vw}.
Ist w unmarkiert, setze T := T [mm] \cup [/mm] {vw} und CALL SEARCH(w).
Nehmen wir, dass der Graph G = (V, E), den der Algorithmus als Input erhält, zusammenhängend ist. Zeigen Sie, dass die im Algorithmus konstruierte Menge T ein aufspannender Baum für G ist. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Meine Frage ist nun, wie ich denn mit so einem Algorithmus generell argumentieren kann um das zu beweisen. Es ist ja:
DFS funktioniert => T* ist aufspannender Baum
T* ist ein aufspannender Baum wenn T*=(V',T) mit T [mm] \subseteq [/mm] E, V' = V und T* kreisfrei und zusammenhängend ist.
D.h ich kann auch zeigen
[mm] \neg [/mm] T* ist aufspannender Baum => [mm] \neg [/mm] DFS funktioniert
[mm] \neg [/mm] T* ist aufspannender Baum ist doch dann
[mm] \gdw [/mm] (V' [mm] \not= [/mm] V) [mm] \vee [/mm] (T* nicht kreisfrei) [mm] \vee [/mm] (T nicht zusammenhängend)
D.h. ich muss jetzt so den Widerspruch herbeiführen.
Wenn V' [mm] \not= [/mm] V wäre, dann würde der Algorithmus nicht jeden Knoten besuchen [mm] \Rightarrow [/mm] DFS funktioniert nicht.
Aber wie kann ich die anderen Sachen zeigen, bzw widerlegen?
Vielen dank für eure Hilfe
quest
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Mo 21.05.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
