Assignment 4
CMPT307
Summer 2020
Assignment 4
Due Wed Aug 5 at 23:59
4 problems, 40 points.
1. Let G = (V, E) be a directed graph with weighted edges, edge weights
can be positive, negative, or zero. Suppose vertices of G are partitioned
into k disjoint subsets V1, V2, . . . , Vk; that is, every vertex of G belongs to
exactly one subset Vi
. For each i and j, let δ(i, j) denote the minimum
shortest-path distance between vertices in Vi and vertices in Vj , that is
δ(i, j) = min{dist(u, v) | u ∈ Vi and v ∈ Vj}
Describe an algorithm to compute δ(i, j) for all i and j. For full credit,
your algorithm should run in O(V E + kV log V ) time. (10 points)
2. Let G = V, E be a flow network in which every edge has capacity 1 and
the shortest-path distance from s to t is at least d. (10 points)
(a) Prove that the value of the maximum (s, t)-flows is at most E/d.
(b) Now suppose that G is simple, meaning that for all vertices u and v,
there is at most one edge from u to v. Prove that the value of the
maximum (s, t)-flow is at most O(V
2/d2
).
3. A cycle cover of a given directed graph G = (V, E) is a set of vertexdisjoint cycles that cover every vertex in G. Describe and analyze an
efficient algorithm to find a cycle cover for a given graph, or correctly
report that no cycle cover exists. (10 points)
Hint: use bipartite matching. But G is not bipartite, so you’ll have to use
a graph derived from G.
4. Solve the equation by using an LUP decomposition. (For full credit, show
your detail steps. ) (10 points)