COMP3027/COMP3927 Tutorial questions The University of Sydney 2019 Semester 1 Tutorial 8 School of Computer Science
Pre-tutorial questions
Do you know the basic concepts of this week’s lecture content? These questions are only to test yourself. They will not be explicitly discussed in the tutorial, and no solutions will be given to them.
1. Flow network G = (V, E).
(a) Is G directed or undirected?
(b) What does it mean that an edge has a capacity?
(c) Whatisaflowf inG?
(d) Why is the flow of an edge bounded by the capacity of an edge?
(e) What are the capacity and conservation constraints? 2. MinCut(A,B)ofG.
(a) What is a cut (A,B) of G? (b) What is the capacity of a cut?
(c) What is the flow of a cut? 3. Min cut vs. max flow
(a) Why is the value of a cut an upper bound on the maximum flow? (b) What does the Min Cut – Max Flow theorem state?
4. Ford-Fulkerson
(a) The Ford-Fulkerson algorithm iteratively increases the flow. How is this done in each iteration? (b) Can you upper bound the number of iterations performed by the Ford-Fulkerson algorithm?
Tutorial
Problem 1
Let G = (V, E) be an arbitrary flow network, with source s, sink t, and edge capacities c : E → Z+. Decide whether each of the following statements are true of false. If it is true, give a short explanation. If it is false, give a counterexample.
1. If f is a maximum s-t flow in G, then f saturates every edge out of s; that is, f(e) = c(e) for each edge e coming out of s.
2. Let (A, B) be a minimum s-t cut with respect to c. Define new capacities cˆ(e) = c(e) + 1 for each e ∈ E. Then (A, B) is a minimum s-t cut with respect cˆ.
1
Problem 2
The figure below shows a flow network on which an s − t flow is shown. The capacity of each edge appears as a label next to the edge, and the numbers in boxes give the amount of flow sent on each edge. (Edges without boxed numbers have no flow being sent on them.)
1. What is the value of this flow?
2. Is this a maximum s−t flow in this graph? If not, find a maximum s−t flow. 3. Find a minimum s − t cut. (Specify which vertices belong to the sets of the cut.)
4
4
2
w
10 2
s 7 x 10 y 7 t 10 2 2 6
z
4
7
7
7
6
6
Problem 3
Find all minimum s − t cuts in the following graph. The capacity of each edge appears as a label next to the edge.
u
22
s2t 2
2
w
Problem 4
Design a linear time algorithm that given a flow f verifies that f is maximum. If the flow is maximum your algorithm should output “yes”, otherwise, it should output “no”. No other action is required.
Problem 5
Consider a generalization of the maximum flow problem where vertices have capacities. An instance is defined by a directed graph G = (V, E), a pair of vertices s and t, and vertex capacities c : V → Z+. A flow f : E → Z+ is feasible if fout(u) ≤ c(u). The objective is to find a maximum feasible s-t flow.
Design an efficient algorithm for this problem.
Problem 6
2
Consider a generalization of the minimum cut problem where we want to separate two sets of vertices. An instance is defined by a graph G = (V, E), a pair of disjoint subsets of vertices S, T ⊆ V , and edge capacities c:E→Z+. Theobjectiveistofindaminimumcapacitycut(A,B)suchthatS⊆AandT ⊆B.
Design an efficient algorithm for this problem.
Problem 7
We want to wirelessly connect a set of mobile computers to a set of stationary base stations. Each computer u has an effective transmission radius ru. Suppose we know the spatial location of each computer and each base station. Our goal is to assign each computer to some station within its transmission radius. Define the load of a station to be the number of computers assigned to it.
Your task is to design a polynomial time algorithm that will produce a feasible computer-station assign- ment minimizing the maximum station load.
3