Q1 Ford Fulkerson
Consider the following network:
CSC373 Fall¡¯20 Tutorial 4 Tuesday, Oct. 6, 2020
5 99
s
936 8
b
a
c
4 5
4
7
Figure 1:
d
(a) Compute a maximum flow in this network using the Ford-Fulkerson algorithm. For each iteration, write down the augmenting path, its bottleneck/residual capacity, and the value of the flow at the end of the iteration.
(b) Consider the cut X0 = (S = {s, b, c, d}, T = {a, t}). Identify all forward and all backward edges across X0. Compute the capacity of X0.
(c) Find a cut in the network whose capacity is equal to the value of the flow you computed in part (a). (This provides a guarantee that your flow is indeed maximum.) Use the idea outlined in the proof of correctness of the Ford-Fulkerson algorithm.
Q2 Graph Modifications
In this problem, we will consider what happens to the maximum flow when the flow network G is modified slightly.
(a) TRUE/FALSE: In any network G with integer edge capacities, there always exists an edge e such that increasing the capacity of e increases the maximum flow value in G.
(b) Suppose we are given a network G with n nodes, m edges, and integer edge capacities, and we are also given a flow f in G of maximum value. We now increase the capacity of a specific edge e by one. Give an O(m + n) time algorithm to find a maximum flow in the updated network.
1
t