代做CIS 413/513、Python，Java编程语言调试、C++代写代做、代写Data Structures

日期：2020-02-09 10:21

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