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?
Answer: A. Only \(๐_1\) โ 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โฆ
- 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.