CLRS - Maxflow Augmented Flow Lemma 26.1 - Verstehe die Verwendung von def nicht. Im Beweis

In Cormen et. al., Einführung in Algorithmen (3. Aufl.), bekomme ich im Beweis von Lemma 26.1 keine Zeile, die besagt, dass der erweiterte Fluss ein Fluss in und st(Dies ist S. 717-718).$f\uparrow f'$$G$$|f\uparrow f'| =|f|+|f'|$

Meine Verwirrung: Wenn sie über die Erhaltung des Flusses streiten , verwenden sie die Definition von in der ersten Zeile, um zu sagen, dass für jedes$f\uparrow f'$$u\in V\setminus\{s,t\}$

$$\sum_{v\in V} (f\uparrow f')(u,v) = \sum_{v\in V} (f(u,v)+f'(u,v) - f'(v,u)),$$

wobei der erweiterte Pfad definiert ist als

$$(f\uparrow f')(u,v) = \begin{cases} f(u,v)+f'(u,v) - f'(v,u) & \text{if $(u,v)\in E$}, \\ 0 & \text{otherwise}. \end{cases}$$

Warum können sie die "sonst" -Klausel in der Summe ignorieren? Ich glaube nicht, dass die erste Klausel in all diesen Fällen Null ergibt. Verwenden sie in irgendeiner Weise die Flusserhaltung von und ?$f$$f'$

Hinweis: Die unten verwendeten Notationen und Definitionen stammen aus der dritten Ausgabe des Buches.

Um diese Frage zu beantworten, beachten Sie zunächst, dass wenn , dann per Flussdefinition,$(u,v) \notin E$

$$f(u,v) = f'(u,v) = (f \uparrow f')(u,v) = 0 \, .$$

Da außerdem , wird erhalten, dass . Dies impliziert einfach, dass ,$f'(v,u) \le c_f(u,v) = f(u,v)$$f'(v,u) = 0$$\forall (u,v) \notin E$

$$(f \uparrow f')(u,v) = f(u,v) + f'(u,v) - f'(v,u) = 0 \, .$$

Daher kann die Definition des erweiterten Flusses für alle wie folgt verallgemeinert werden:$(u,v) \in V \times V$

$$(f \uparrow f')(u,v) = f(u,v) + f'(u,v) - f'(v,u) \, .$$

Der Rest des Beweises ergibt sich aus dieser Beobachtung, die im Text natürlich nicht explizit erläutert wird.

PS Bitte beachten Sie, dass sich die formale Definition des Flusses in der dritten Ausgabe des Buches erheblich von der in der zweiten Ausgabe unterscheidet. Insbesondere gibt es in der zweiten Ausgabe eine Flusseigenschaft namens Skew Symmetry , die erfordert . Diese Eigenschaft wurde in der dritten Ausgabe aufgrund der Annahme entfernt, dass wenn und wenn$f(u,v) = - f(v,u), \forall u,v \in V$$(v,u) \notin E$$(u,v) \in E$$f(v,u) = 0$$(v,u) \notin E$. Aus diesem Grund unterscheiden sich auch die Definitionen der Flusserhaltung in zwei Ausgaben. Viele solcher Verwirrungen sind in der Tat auf diese Änderung der Definition zurückzuführen, die vermutlich die Beweise vereinfachen soll, sich jedoch als verwirrender herausstellte. Ich persönlich würde mich lieber an die zweite Ausgabe des Buches für dieses spezielle Kapitel halten.