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. Shortest s-t path in graph with negative edge weights.
(a) What are the subproblems?
(b) What is the recurrence? Do you understand the recurrence?
(c) What are the base cases?
(d) In what order should we evaluate the subproblems?
(e) Which part of the proof of correctness for Dijkstra’s relies on edge weights being non-negative? 2. 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? 3. MinCut(A,B)ofG.
(a) What is a cut (A,B) of G? (b) What is the capacity of a cut?
4. 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?
5. 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?
1
Tutorial
Problem 1
Run the Bellman-Ford algorithm on the directed graph below. Use vertex z as the destination and illustrate how first changes throughout the execution.
t
72 y9z
5 -2
x
6
8
-4 s7
-3
Problem 2
Let G = (V, E) be a connected undirected graph. Given two vertices s and t we can compute the shortest path (shortest in terms of number of edges) in linear time using BFS. It is easy to come up with examples where the there could be multiple shortest paths going from s to t. Design a dynamic programming algorithm to compute the number of shortest paths connecting s and t. Notice that the number of shortest paths connecting s and t may be exponentially large, so we don’t want to list them, just count them.
Problem 3
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ˆ.
Problem 4
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.)
2
4
2
w
10 2
s 7 x 10 y 7 t 10 2 2 6
z
4
7
7
7
6
6
Problem 5
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 6
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 7
Let G be a flow network such that, for every edge e in the network, c(e) is an even integer.
1. Argue that the maximum value of a flow is an even integer.
2. Show that there is a maximum flow f such that, for every edge e, the flow over e is an even integer.
Problem 8
[COMP3927 only] Consider the following simplest-possible randomized algorithm for global min cut: Given an undirected and unweighted graph G = (V, E), choose a random subset A of vertices and if ∅ A V , returnthecut(A,V \A);otherwiseresampleAuntilwegetanAsuchthat∅AV. Yourtaskistogive an example of an n-vertex graph such that the probability that the algorithm returns a global min cut is at most c/2n for some constant c.
3