Q)a)(T/F) Suppose that flow network G contains edge (u, v) and we create a new f
ID: 3712541 • Letter: Q
Question
Q)a)(T/F) Suppose that flow network G contains edge (u, v) and we create a new flow network G0 by creating a new vertex x and replacing (u, v) by new edges (u, x) and (x, v) with c(u, x) = c(x, v) = c(u, v). Then, a maximum flow in G0 has the same value as a maximum flow in G.
b)(T/F) A maximum-flow problem with multiple sources and multiple sinks can be converted to a maximum-flow problem with a single source and a single sink as follows. We add a super-source s and add a directed edge (s, si) with capacity c(s, si) = ? for each source si. We also add a super-sink t and add a directed edge (ti, t) with capacity c(ti, t) ) = ? for each sink ti . Any flow in a multiple-source, multiple-sink flow network corresponds to a flow of identical value in the single-source, single-sink flow network, and vice versa.
Explanation / Answer
a) <True>
splitting an edge in a flow network yields an equivalent network AND HAS THE SAM MAXIMUM FLOW
b) <True>
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.