Consider the following properties with respect to a flow network…
2019
Consider the following properties with respect to a flow network \(𝐺=(𝑉,𝐸)\) in which a flow is a real-valued function \(𝑓:𝑉×𝑉→𝑅\):
\(𝑃_1\): For all \(𝑢,𝑣,∈𝑉,𝑓(𝑢,𝑣)=−𝑓(𝑣,𝑢)\)
\(𝑃_2\): \(\underset{v \in V}{\Sigma} f(u,v)=0\) for all \(𝑢∈𝑉\)
Which one of the following is/are correct?
- A.
Only
\(𝑃_1\) - B.
Only
\(𝑃_2\) - C.
Both
\(𝑃_1\)and\(𝑃_2\) - D.
Neither
\(𝑃_1\)nor\(𝑃_2\)
Attempted by 9 students.
Show answer & explanation
Correct answer: A
Answer: Only P1 is correct.
P1: f(u,v) = -f(v,u) is the skew-symmetry property of a flow. This holds for every pair of vertices and is a standard requirement for flow functions.
P2: Sum over all v of f(u,v) = 0 for all u in V is incorrect as stated. Conservation of flow applies to intermediate vertices only; the source has net outflow equal to the flow value and the sink has net inflow equal to the flow value. Requiring net flow zero at every vertex would force the flow value to be zero.
Counterexample: consider a network with source s and sink t and a single nonzero flow f(s,t)=3. Then f(t,s)=-3, so the skew-symmetry property holds, but the sum over v of f(s,v)=3≠0, so P2 fails.
Conclusion: Only the skew-symmetry property (P1) is valid for flows as stated; P2 is false because it omits the usual source/sink exceptions.
A video solution is available for this question — log in and enroll to watch it.