Sample Problems: Network Flow Chapter 7

· COMP 482 Sample Problems: Network Flow Problem 1. (10 points) For each of the following statements determine whether it is true of false. (+1 for a correct answer, -0.5 for an incorrect answer, 0 for a blank). A network could have a cut larger than its maximum flow. A network could have a cut smaller than its maximum flow. Every problem which can be solved using network flow involves water. Brute force is the fastest way to find the Maximum Network Flow. There are polynomial time network flow algorithms. If an edge has capacity c then f (the amount of water moving through that edge) must satisfy 0  f  c. If we exit the loop in the Augmenting Path algorithm early, the result is still a flow (which may not be optimal). If we exit the loop in the Preflow Push algorithm early, the result is still a flow (which may not be optimal). There are networks where Augmenting Path runs faster than Preflow-Push. Every version of PreflowPush is polynomial time. Every version of AugmentingPath is polynomial time. Many assignment problems can be solved using a NetworkFlow algorithm. If an edge has f = 3 and c = 5 then the residual graph will have a forward edge with capacity 2 and a backward edge with capacity 3. Problem 2. (10 points) Someone started to perform the Augmenting Path algorithm on the network below. Finish running the algorithm. Show enough work to convince me that you are using the algorithm. 4/5 A 6/8 S 6+6 = C 7 T 3/3 4/4 2/5 6/6 12 D - = odd 12 7/7 3/4 2/2 4+ 2+ 6 B cut total but E 2/3 from total Flow should we eve 6+ 6 is be = 12 12 gotta find full Problem 3. (10 points) The diagram below is the same diagram as in the previous problem. Find the Minimum Cut in this network and convince me that it is the Minimum Cut. 4/5 A , B 2 6/8 O ⑧ 2/2 S in 7/7 3/4 C 3/3 + 2 7 + 3 = 12 + 4 O O 4/4 2/5 6/6 O T D E 3 n+ 2 + 2 = - 12 2/3 I Problem 4. (10 points) Run the PreflowPush algorithm on the graph below (show enough work that I am convinced you used the algorithm and didn’t find a solution another way). T T T T T T T T T T T T F F F F F F F F F F F F T F 7 6 4 9 5 8 5 4 4 6 8 5 9 4 7 6 Problem 5. (10 points) Solve the following instance of NetworkFlow using the Augmenting Path algorithm. - i n · C 15 8 SACFT = 5 10 25 A F 5 SADGT = 5 5 5 S D 15 30 70 12 B T SBDEGT = 40 G 30 25 E Problem 6. (10 points) Let N be an instance of NetworkFlow (ie N is a weighted, directed graph). Let N 0 be another instance of NetworkFlow which has the same directed graph, but the weight on every edge has been increased by 1. Give an example where the maximum flow on N 0 is exactly 1 greater than the maximum flow on N . Give an example where the maximum flow on N 0 is more than 1 greater than the maximum flow on N . Problem 7. (10 points) Assume that you are trying to create a matching between people and jobs. The following table shows which people are suitable for which jobs (an X in row i, column j means person i can do job j). Currently, you have a (partial) matching consisting of {(P1 , J2 ), (P2 , J1 ), (P4 , J3 ), (P5 , J5 )}. Using the technique shown in class (and in the book) draw the derived network and if possible find an augmenting path. J1 J2 J3 J4 J5 P1 X X P2 X X P3 X X P4 X X X P5 X X . A ⑤ E C - F ↓ I Min Prof Tax cut : consider residual augmented ⑪ Y E SACF value reachable , YET BDET graph Path & nodes in after running unreachable Breachate cut xE y flow cut of nodes