CLRS - Maxflow Augmented Flow Lemma 26.1 - ne comprend pas l'utilisation de def. en preuve

Dans Cormen et. al., Introduction to Algorithms (3e éd.), je n'ai pas de ligne dans la preuve du lemme 26.1 qui déclare que le flux augmenté$f\uparrow f'$ est un flux $G$ et est st $|f\uparrow f'| =|f|+|f'|$ (c'est pp. 717-718).

Ma confusion: lorsqu'ils discutent de la conservation des flux, ils utilisent la définition de$f\uparrow f'$ dans la première ligne pour dire que pour chaque $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)),$$

où le chemin augmenté est défini comme

$$(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}$$

Pourquoi peuvent-ils ignorer la clause «autrement» dans le résumé? Je ne pense pas que la première clause s'évalue à zéro dans tous ces cas. Utilisent-ils la conservation des flux de$f$ et $f'$ en quelque sorte?

Remarque: Les notations et définitions utilisées ci-dessous sont empruntées à la troisième édition du livre.

Pour répondre à cette question, notez tout d'abord que si $(u,v) \notin E$, puis par définition de flux,

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

En outre, depuis $f'(v,u) \le c_f(u,v) = f(u,v)$, on obtient que $f'(v,u) = 0$. Cela implique simplement que$\forall (u,v) \notin E$,

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

Par conséquent, la définition du débit augmenté peut être généralisée pour tous $(u,v) \in V \times V$ être comme suit:

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

Le reste de la preuve découle de cette observation qui, bien entendu, n'est pas explicitement expliquée dans le texte.

PS Veuillez noter que la définition officielle du flux dans la troisième édition du livre est significativement différente de celle de la deuxième édition. En particulier, dans la deuxième édition, il existe une propriété de flux nommée symétrie de biais qui nécessite$f(u,v) = - f(v,u), \forall u,v \in V$. Cette propriété a été supprimée dans la troisième édition en raison des hypothèses selon lesquelles$(v,u) \notin E$ si $(u,v) \in E$ et $f(v,u) = 0$ si $(v,u) \notin E$. Pour cette raison, les définitions de la conservation des flux dans deux éditions sont également différentes. Beaucoup de ces confusions, en fait, viennent de ce changement de définition qui est vraisemblablement destiné à simplifier les preuves, mais s'est avéré plus perplexe. Personnellement, je préfère m'en tenir à la deuxième édition du livre pour ce chapitre particulier.