代写CMPT307、Python，c/c++，Java编程设计代做、代写data留学生-代写Java编程

Assignment 4

CMPT307

Summer 2020

Assignment 4

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(V2/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)