Problem 26-7

a. The symmetric difference will be in the odd position in P, so it will be a matching. Because the length of P must be odd, the |P∩{E-M}| - |P∩M| = 1, |M⊕P| = |M|+1. If there are k vertex-disjoint augment paths, then we can get a matching cardinality |M| + k.

b. Because the degree in M and M’ is 1, so degree in M⊕M* is at most two. A graph with maximum degree 2 is either path or cycle, and the edge must be alternately to M or M*. If |M|≤ |M*|, we can collect all the path in M⊕M* to form the augment path. Because the number of edge from M or M* in a cycle is the same and the difference of number of edge from M or M* in path is one, so there must be |M*| – |M| paths.

c. If P is vertex-disjoint from P1 to Pk with l edges or fewer, then P will be found prefiously.

d. By the definition, A will be (P1∪ ..∪Pk). Because the operation ⊕ is associated, (M⊕M’)⊕P = M⊕(M’⊕P) and we know that |M’⊕P| – |M| = k+1. Thus, (M⊕M’)⊕P  contains at least k+1 vertex-disjoint paths with lenght at least l. That is, |A|≥(k+1)l.

e. Suppose that there is a maximum matching M*, we know that there are |M*|-|M| vertex-disjoint path in M*⊕M. Because there are at most |V| vertex and the shortest augment path for M has length l, so |M*|-|M| < |V| / l.

f. When l = , the maximum matching is at most |M| +. On the other hand, when we increment l by one, we can increase M by 1. Because there are at most augment path, we can find them in another iteration.

g. Using the BFS from unmatched vertex to find the shortest augmenting path length l, and use the DFS to trace back the paths.

Problem 26-6

a. Because f(u,v) must be smaller than c(u,v)  and c(u,v) is a negative value. That is f(u,v)≥-c(u,v) which means the lower bound.

b. If c(u,v) < 0 and c(v,u) > 0, then it means the upper bound and lower bound exists in the same time. And the upper bound must be greater then the lower bound, otherwise the feasible solution does not exist. The c’(u,t’) means the summation of necessary lower bound flow.

c. If there is a maximum flow f’ in G’ which saturate all the edges into t’, we can conver f’(u,v) to f(u,v) by let f(u,v) = f’(u,v)*2 + lower bound of (u,v).

d. Construct a feasible flow first then augment this flow.

Problem 26-5

a. Minimum cut is equal to maximum flow and the maximum capacity is C for one edge. Hence, the maximum flow is at most C|E|.

b. We can discard edges which  capacity are smaller than K and search for the augmenting path.

c. Because K will be one in the last iteration, it is equal to unconstrainted augmenting path search. By the augmenting path algorithm, the result must be optimal.

d. The capacity of a minimum cut of the residual graph is equal to the difference between the optimal solution and current flow. By the scaling algorithm, the upper bound of difference is at most 2K|E|.

e. Because the residual graph has at most 2K|E| capacity and we increase K a time. The lines 5-6 must be executed at most 2|E| times which is O(|E|).

f. By b and e, we can conclude that the running time is .

Problem 26-4

a. Run one iteration of Ford-Fulkerson algorithm.

b. If f(u,v)>0, then we can use BFS or DFS to check whether there exist another path from u to v can reroute one unit flow.

Problem 26-3

a. If there is a but ∉T, then the cut must not be finite capacity.

b. Because every feasible solution is corresponding to a flow in G. The net revenue is – minimum cut of G.

c. Using the network flow algorithm to find the minimum cut of  G. The vertex number is m + n + 2 and the edge number is r.

Problem 26-2

a. We can use the V’ and E’ with all edges capacity are 1. Find the maximum flow f from to , the minimum path cover will be |V| – f.

b. In general, minimum path cover is NP-Complete problem.

Problem 26-1

a. We can transform a capacity on vertex v by this way. For all node v, we create a new node v’, and a edge from v to v’ which capacity is the capacity of v. All inedges of v are still on v, but all out-edges moved to the v’. Finally all the capacities are one the edge.

b.  We can use the grid as the network graph. Every edge and node in the grid has capacity 1. Using m points as multi-sources, and all the boundary points are multi-sink. The maximum flow on this graph is the solution of escape problem.