Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In the CLRS book ( 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.

share|cite|improve this question
Please be more specific, I don't know the CLRS book you mention. – vonbrand Jan 25 '13 at 18:37 I've updated my question with the link. Thanks for pointing out. – Siddhant Jan 26 '13 at 9:16
up vote 2 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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