”
写作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
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
