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

IT界

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

代做CIS 413/513编程、Python,Java编程

来源:珠穆朗玛网 发布时间:2020-02-10

代做CIS 413/513作业、Python,Java编程语言作业调试、C++实验作业代做、代写Data Structures作业
CIS 413/513 Advanced Data Structures
Winter 2020
Assignment 3
due Wednesday, February 12, 2020
1. (question 4 from chap 10 of Er) Let G be a flow network that contains an opposing pair of
edges u → v and v → u, both with positive capacity. Let G0 be the flow network obtained
from G by decreasing the capacities of both these edges by min{c(u → v), c(v → u)}. In
other words:
• if c(u → v) > c(v → u), change the capacity of u → v to c(u → v)−c(v → u) and delete
v → u.
• if c(u → v) < c(v → u), change the capacity of v → u to c(v → u)−c(u → v) and delete
u → v.
• if c(u → v) = c(v → u), delete both u → v and v → u.
(a) Prove that every maximum (s, t)-flow in G0
is also a maximum (s, t)-flow in G. (Thus,
by simplifying every opposing pair of edges in G, we obtain a new reduced flow network
with the same maximum flow value as G.)
(b) Prove that every minimum (s, t)-cut in G is also a minimum (s, t)-cut in G0 and vice
versa.
(c) (for 513) Prove that there is at least one maximum (s, t)-flow in G that is not a
maximum (s, t)-flow in G0
.
1

如有需要,请加QQ:99515681 或邮箱:99515681@qq.com 微信:codehelp

责任编辑:珠穆朗玛网

最火资讯