Problem 2. Complete the proof for the following theorem on flow networks: Theorem: A flow |f|...

Transcribed Image Text:

Problem 2. Complete the proof for the following theorem on flow networks: Theorem: A flow |f| through a network G(V, E, c) is always equal to the flow through any given S-T cut of the same network i.e. |ƒ| = f(S, T) Proof. We know that SUT = V since the cuts are disjoint sets, we can re-write the above statement as follows: ƒ(S,T) = f(S, _) — ƒ(S,_) = f(S, _) = f(_, _) + f($ — _, _) = f(_, _) f(S, T) = |f| where, f(S, T) represents a flow through the given S-T cut and (Note: Feel free to justify the steps as neccessary in the final statement) Problem 2. Complete the proof for the following theorem on flow networks: Theorem: A flow |f| through a network G(V, E, c) is always equal to the flow through any given S-T cut of the same network i.e. |ƒ| = f(S, T) Proof. We know that SUT = V since the cuts are disjoint sets, we can re-write the above statement as follows: ƒ(S,T) = f(S, _) — ƒ(S,_) = f(S, _) = f(_, _) + f($ — _, _) = f(_, _) f(S, T) = |f| where, f(S, T) represents a flow through the given S-T cut and (Note: Feel free to justify the steps as neccessary in the final statement)