Let G=(V,E) be a flow network, i.e., a weighted directed graph with distinguished source vertex s, a sink vertex t and n

[answerhappygod]

Let G V E Be A Flow Network I E A Weighted Directed Graph With Distinguished Source Vertex S A Sink Vertex T And N 1 (96.92 KiB) Viewed 43 times

Let G=(V,E) be a flow network, i.e., a weighted directed graph with distinguished source vertex s, a sink vertex t and non-negative capacity c(u, v) for every edge (u, v) in E. Suppose you find an s-t cut C which has edges e1,e2, ... ek and a capacity f. Suppose the value of the maximum s-t flow in G is f. What do we call the cut C? A. Augmented Flow B. Maximum Cut C. Augmented Cut a D. Minimum Cut E. Residual Cut What is the value of the maximum flow across C described in the previous question? |

Now let H be the flow network obtained by adding 1 to the capacity of each of the k edges in C. (Notice that the capacities of edges not in C are not changed.) Proposition: the value of the maximum s-t flow in H is necessarily equal to f+k. True False If we found two valid flows fy and f2 in a flow graph G without using the residual graph, and tried to add them together, which constraint(s), if any, might we violate? A. capacity constraint B. conservation constraint C. both capacity and conservation constraints D. neither of the above