[Eff Alg.]Das duale LP vom Max-Flow

[hingiswiss]

Guten Tag zusammen,

ich versuche gerade, das primale LP vom Max-Flow-Min-Cut zu verstehen. Vielleicht kann mir der eine oder andere ja helfen. Vielen Dank im Voraus.

sei eine Menge ALLER einfachen Pfade von der Quelle zur Senke.
Für jeden Pfad p haben wir eine Variable

Das primale LP lautet:
Miximiere
unter den Nebenbedingungen:
für alle
für alle

Zum Verständis:
Wie ist denn hier gemeint, dass wir zu jedem Pfad von Quelle zur Senke eine Variable haben?
Ich stelle mir vor, ein Pfad von Quelle zur Senke hat unter Umständen mehrere Kanten. Der eine Pfad hat vielleicht weniger Kanten, der Anderere ein bisschen mehr. Wie soll so ein Pfad denn durch eine Variable "dargestellt" werden?

Gruss aus Stolberg

[TheStranger]

So wie ich das sehe, entspricht dem Fluss entlang von einem Pfad. Es ist nun egal, wieviele Kanten in dem Pfad sind und es können auch unterschiedliche Pfade dieselben Kanten nutzen. Deshalb gibt es die Nebenbedingungen, dass die Flüsse der Pfade (sprich alle ), die über eine bestimmte Kante gehn, zusammen nicht größer als die Kapazität dieser sein sollten.