Consider the following properties with respect to G = (V , E) a flow network in which a flow is a f : V × V → R real-valued function : P : For all u, v ∈ V , f(u, v) = −f(v, u) 1 P : ∑ f(u, v) = 0 for all u ∈ V 2 v∈V Which one of the following is/are correct? P

1. AOnly 1 P
2. BOnly 2 P P
3. CBoth 1 and 2 P P
4. DNeither 1 nor 2

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. Both 1 and 2 P P

Explanation

CLRS's net-flow formulation uses skew symmetry f(u, v) = −f(v, u) and flow conservation Σ f(u, v) = 0.

Note: Flow conservation (P2) holds for every vertex except the source and sink; the official key accepts both.