# Push relabel algorithms in flow networks

In the CLRS book (http://en.wikipedia.org/wiki/Introduction_to_Algorithms) Chapter 26 (Maximum Flow) page 744 (third edition), there is the following equation -

$$\sum_{u \in U}e(u) \;=\; \sum_{u \in U}\;\sum_{v \in U}f(v, u) \;+\; \sum_{u \in U}\;\sum_{v \in \bar{U}}f(v, u) \;-\; \sum_{u \in U}\;\sum_{v \in U}f(u, v) \;-\; \sum_{u \in U}\;\sum_{v \in \bar{U}}f(u, v)$$

where $f(u, v)$ is the flow between vertices $u$ and $v$, $e(u)$ is the excess flow at a particular vertex, $U$ is the set of vertices which are reachable from the source, and $\bar{U}$ is the set of remaining vertices.

In the next line, the first and third terms disappear. I don't understand why that holds. I do realize that those are flow values from vertex $u$ to vertex $v$ where both of them are in the same set $U$, but I don't understand why they cancel out to zero.

-
 Please be more specific, I don't know the CLRS book you mention. – vonbrand Jan 25 at 18:37 en.wikipedia.org/wiki/Introduction_to_Algorithms. I've updated my question with the link. Thanks for pointing out. – Siddhant Jan 26 at 9:16

You just have to reorder the elements of $U\times U$, because the double sum contains each edge $(u,v) \in U\times U$ exactly once:
$$\sum_{u \in U}\sum\limits_{v \in U}f(v, u) = \sum_{(u,v) \in U\times U}f(v, u) = \sum_{(u,v) \in U\times U}f(u, v) = \sum_{u \in U}\sum\limits_{v \in U}f(u, v)$$
You have that $\sum\limits_{u \in U}\sum\limits_{v \in U}f(v, u)=0$ due to the skew symmetry of the flow. In particular $$\sum\limits_{u \in U}\sum\limits_{v \in U}f(v, u)= \sum_{u,v \in U} (f(u,v)+f(v,u))=0.$$
 But if edge $(u,v)$ belongs to the flow network, then we don't allow $(v, u)$ to exist, don't we? In that case, shouldn't $f(v, u)$ be 0? – Siddhant Jan 26 at 9:17