Text erkannt:
Sei \( G=(V, E) \) ein gerichteter Graph. Wir betrachten eine Tiefensuche auf \( G \). Zeigen oder widerlegen Sie die folgenden Aussagen:
(a) Für alle Knoten \( u, v \in V \) gilt: Gibt es einen Weg von \( u \) nach \( v \) in \( G \), dann gilt \( v . d \leq u . f \).
(b) Für jeden Knoten \( u \in V \) mit In- und Outgrad mindestens 1 gibt es einen Knoten \( v \in V \), sodass \( (u, v) \) oder \( (v, u) \) eine T-Kante ist.
Hallo Zusammen,
unzwar habe ich im folgenden diese Aufgaben zu lösen und habe keinen Ansatz wie ich diese beweisen bzw. widerlegen soll. Bei der (a) meine ich, dass dies nicht sein kann, da v.d = u.f meines Wissens nie möglich ist. Theoretisch könnte man das mit einem einfachen Gegenbeispiel zeigen, aber ob das dann für alle Fälle gilt, steht offen im Raum. Bei der (b) bin ich leider komplett überfragt, wie man das zeigen kann.
Ich wäre sehr dankbar für eine Antwort!
LG :)