91Ó°ÊÓ

Gibt es Fälle, in denen der vom DFS-Algorithmus berechnete Baum von \(v_{0}\) aus zu jedem Knoten einen kürzesten Weg enthält? Berechnet der DFS-Algorithmus immer einen längsten Weg von \(v_{0}\) zu den anderen Knoten?

Sei \(G=(V, E)\) ein zusammenh?ngender einfacher Graph. Beweisen Sie oder widerlegen Sie durch ein Beispiel: 1\. Sei \(s\) der Knoten, in dem der DFS-Algorithmus startet, und \(T=\left(V, E_{0}\right)\) der konstruierte Baum. Dann ist jede Kante \((s, v) \in E\) auch in \(E_{0}\) 2\. Sei \(s\) der Knoten, in dem der BFS-Algorithmus startet. Dann ist jede Kante \((s, v) \in E\) auch in \(E_{0}\)

Aufgabe 2.7. Seien \(G\) ein Graph, \(T_{\mathrm{BFS}}\) der von der Breitensuche berechnete spannende Baum, und \(T_{\text {DFS }}\) der von der Tiefensuche berechnete Baum. Mit \(d_{G}(v)\) bezeichnen wir den Grad eines Knotens \(v\) im Graphen \(G\), mit \(d_{\mathrm{BFS}}(v)\) den im \(T_{\mathrm{BFS}}\) und mit \(d_{\mathrm{DFS}}(v)\) den in \(T_{\mathrm{DFS}}\). Welche Aussagen sind richtig und welche sind falsch? 1\. Für alle Knoten \(v \in V\) gilt \(d_{G}(v)=d_{\mathrm{BFS}}(v)\). 2\. Es gibt immer einen Knoten mit \(d_{G}(v)=d_{\mathrm{BFS}}(v)\). 3\. Es gibt immer einen Knoten mit \(d_{G}(v)=d_{\text {DFS }}(v)\).

Sei \(T\) ein spannender Baum von \(G=(V, E)\) und \(s \in V .\) Betrachtet \(\operatorname{man} T=\left(V, E_{T}\right)\) als einen gerichteten Graphen, in dem alle Kanten von \(s\) weg orientiert sind, so heißen zwei Knoten \(u, v\) auch \(T\)-verbunden, wenn in \(T\) ein \((u, v)\) Weg oder ein \((v, u)\)-Weg enthalten ist (Abb. 2.20). Sei \(T_{\text {DFS }}\) ein vom Knoten \(s\) aus durch die Tiefensuche berechneter Baum und sei \((x, y)\) eine Kante, die nicht in \(T_{\text {DFS }}\) enthalten ist. Dann sind die Knoten \(x, y\) ebenfalls \(T_{\text {DFS }}\)-verbunden.