# 代写CMPT307课程编程、Python，c/c++，Java编程

 代写CMPT307课程编程、Python，c/c++，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)   如有需要，请加QQ：99515681 或邮箱：99515681@qq.com 微信：codehelp
免责声明：珠穆朗玛网对于有关本网站的任何内容、信息或广告，不声明或保证其正确性或可靠性，用户自行承担使用网站信息发布内容的真假风险。