Return to Question

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

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.

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\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.

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

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.

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\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.