算法代写 | CMPT307 Assignment 4
这个作业案例是完成图相关的数据结构与算法代写
CMPT307 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(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)