Exercises 26.2-10

For one edge pair (u,v) and (v,u), we can eliminate one of them. Suppose that c(u,v) > c(v,u), we can set c’(u,v) = c(u,v) – c(v,u), c’(v,u) = 0. In this way, the number of edges becomes |E|/2 and by the theorem 26.9, the iterations needed by the algorithm is |V||E|/4.

Exercises 26.2-9

Let each edge with capacity 1, we select a node u. Let be the maximum flow in G with source u and sink v. The edge connectivity is .

Exercises 26.2-8

Each augment can fulfill at least one edge. Hence there are |E| edge, we can find a way to augment at most |E| times.

Exercises 26.2-7

Obviously, will not violate the capacity constraint and skew symmetry. The flow conservation is still valid because for any vertex the increaseing value of in-flow is always equal to the increasing value of out-flow.

Exercises 26.2-6

Let the capacity from supersource to source is , and capacity from sink to supersink is .

Exercises 26.2-5

By the maximum flow min cut theorem, the value must be finite.

Exercises 26.2-4

= = .

Exercises 26.2-3

X={s,v1,v2,v4}, Y={v3,t}.

Exercises 26.2-2

Exercises 26.2-1