首页 新闻 聚焦 科技 财经 创业 综合 图片 视频

IT界

旗下栏目: 行业 生态 IT界 创新

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

来源:互联网 发布时间:2020-07-31
代写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
  免责声明:珠穆朗玛网对于有关本网站的任何内容、信息或广告,不声明或保证其正确性或可靠性,用户自行承担使用网站信息发布内容的真假风险。
责任编辑:珠穆朗玛网