Tiefensuche Graph: Widerlegen oder Beweisen

Question

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 :)

Comments

Was ist \(v.d\) und \(u.f\)?

---

... und was ist eine T-Kante? Wie ist die definiert?

---

v.d ist die Entdeckungszeit vom Knoten v und u.f ist die Finishzeit des Knotens u. Jeder Knoten hat bei einer Tiefensuche eine Entdeckungs-/Finishzeit. Sprich jeder Knoten in einem Graphen wird bei der Tiefensuche zu einer gewissen Zeit entdeckt und zu einer gewissen Zeit beendet. Die T-Kante ist die Baumkante, dh. falls ein Knoten v entdeckt wurde und der eine Kante auf einen Knoten u hat, der nicht entdeckt wurde, heißt die Kante T-Kante.  Es gibt bei der Tiefensuche noch weitere Kanten-Arten bei einen Gerichteten Graphen, z.B Rückwärtskanten-Kanten, Cross-Kanten und Vorwärts-Kanten. Diese sind für die Aufgabe meines Erachtens irrelevant.