0 Daumen
421 Aufrufe

blob.png

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

Avatar von

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community