Gerichtete Version des Theorems von Menger zeigen

Question

ich soll folgendes zeigen:
$$\text{Zeigen Sie die folgende gerichtete Version des Theorems von Menger:}\\\text{Seien s und t zwei Knoten in einem gerichteten Graphen. Dann ist die Anzahl der paarweise }\\\text{kantendisjunkten Wegen zwischen s und t gleich}\\min\{|\delta^{out}(S)||S \subseteq V \text{ mit } s \in S \text{ und } t \notin S\}.\\\text{Hier ist ein Weg ein einfacher Pfad und zwei Wege sind kantendisjunkt, wenn sie keine Kante gemeinsam haben.}$$

Ich habe leider keine Ahnung, wie ich das machen soll...

Könnte mir jemand dabei helfen?

Vielen Dank im Voraus :)

Answer 1

Hey!

Denk mal an einen gerichteten Graphen, bei dem alle Kantengewichte = 1 sind und wie da der maximale s-t-Fluss mit der Anzahl der kantendisjunkten Wege zusammenhängt.

LG

Comments

Achso! Na klar, logisch :D

Totalen Denkfehler gehabt. Vielen Dank :)