Skip to main content
1 of 4

Push relabel algorithms in flow networks

In the CLRS book Chapter 26 (Maximum Flow) page 744 (third edition), there is the following equation -

$ \sum\limits_{u \in U}e(u) = \sum\limits_{u \in U}\sum\limits_{v \in U}f(v, u) + \sum\limits_{u \in U}\sum\limits_{v \in \bar{U}}f(v, u) - \sum\limits_{u \in U}\sum\limits_{v \in U}f(u, v) - \sum\limits_{u \in U}\sum\limits_{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 vertex $x$, 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.