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.


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)$$

The fist sum sorts the edges by their first vertex, the third sum (of the question's equation) sorts the edges by their second vertex. This is the simplest imaginable form of a double counting argument.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.