Understanding Flow Network Properties

A flow network is a directed graph $G = (V, E)$ with a source vertex $s \in V$ and a sink vertex $t \in V$, where each edge $(u, v) \in E$ has a non-negative capacity $c(u, v) \ge 0$. A flow in a flow network is a real-valued function $f: V \times V \to \mathbb{R}$ that satisfies certain properties. For edges $(u, v) \notin E$, the capacity $c(u, v)$ is typically considered to be 0, and thus the flow $f(u, v)$ must also be 0.

The standard definition of a flow $f$ typically includes the following properties:

1. Capacity Constraint: For all $u, v \in V$, $f(u, v) \le c(u, v)$. This means the flow through any edge cannot exceed its capacity.
2. Skew Symmetry: For all $u, v \in V$, $f(u, v) = -f(v, u)$. This implies that flow from $u$ to $v$ is the negative of flow from $v$ to $u$. This property is useful for handling residual graphs and flow reversal concepts.
3. Flow Conservation: For all $u \in V \setminus \{s, t\}$, $\sum_{v \in V} f(u, v) = 0$. This means that for any vertex other than the source $s$ or the sink $t$, the total flow entering the vertex must equal the total flow leaving the vertex. The sum $\sum_{v \in V} f(u, v)$ represents the net flow out of vertex $u$.

Now, let's analyze the given properties P1 and P2:

Analyzing Property P1: $f(u, v) = -f(v, u)$

Property P1 states that for all vertices $u, v \in V$, the flow from $u$ to $v$ is the negative of the flow from $v$ to $u$. This is exactly the standard definition of the Skew Symmetry property for a flow function in a flow network. This property holds true for all pairs of vertices in the graph, whether there is an edge between them or not (since flow is 0 if there's no edge, and $0 = -0$).

Therefore, Property P1 is a correct property of a flow function.

Analyzing Property P2: $\sum_{v \in V} f(u, v) = 0$ for all $u \in V$

Property P2 states that for all vertices $u \in V$, the sum of flows from $u$ to all other vertices $v \in V$ is zero. The sum $\sum_{v \in V} f(u, v)$ represents the net flow leaving vertex $u$. Standard flow conservation requires this net flow to be zero only for vertices that are neither the source $s$ nor the sink $t$ (i.e., $u \in V \setminus \{s, t\}$).

• For the source vertex $s$, the net flow out ($\sum_{v \in V} f(s, v)$) is typically equal to the total value of the flow in the network, which is generally a positive value, not zero.
• For the sink vertex $t$, the net flow out ($\sum_{v \in V} f(t, v)$) is typically equal to the negative of the total value of the flow in the network (because flow is coming into the sink), which is generally a negative value, not zero (unless the total flow is zero).

If Property P2 were true for all $u \in V$, including the source and sink, it would imply that the total flow value in the network is zero. This is a special case known as a "circulation," which can be thought of as a flow with no source or sink, where flow circulates within the network. However, P2 is not a requirement for a general flow function in a flow network with distinct source and sink vertices where the total flow value can be positive.

Therefore, Property P2 is not a correct property for a general flow function in a standard flow network.

Conclusion on Flow Properties

Based on the analysis:

• Property P1 ($f(u, v) = -f(v, u)$) is the standard skew symmetry property and is correct.
• Property P2 ($\sum_{v \in V} f(u, v) = 0$ for all $u \in V$) is stricter than standard flow conservation (which excludes source and sink) and is not a correct property for a general flow network with a non-zero flow value.

Thus, only Property P1 is correct.

Revision Table: Flow Network Properties

Additional Information on Flow Networks and Properties

Understanding flow networks and their properties is fundamental in network flow algorithms, such as the Ford-Fulkerson algorithm and Edmonds-Karp algorithm, which are used to find the maximum flow from a source to a sink.

• Source (s): The vertex where flow originates. Net flow out of the source is usually positive.
• Sink (t): The vertex where flow terminates. Net flow into the sink (or negative net flow out) is usually positive and equals the total flow value.
• Capacity Constraint: Ensures that the flow on an edge does not exceed its maximum allowed flow. This is a critical practical limitation in modeling real-world networks.
• Circulation: A flow function where flow conservation holds for *all* vertices, including source and sink (if they are defined, they would effectively have zero net flow). A circulation can be viewed as a flow in a network where the source and sink are the same vertex, or where there's no designated source or sink.
• Residual Capacity: For an edge $(u, v)$ with capacity $c(u, v)$ and flow $f(u, v)$, the residual capacity $c_f(u, v) = c(u, v) - f(u, v)$ is the remaining capacity for flow from $u$ to $v$. Also, there is residual capacity $c_f(v, u) = f(u, v)$ for flow in the reverse direction (from $v$ to $u$), allowing flow to be pushed back. The skew symmetry property $f(u,v) = -f(v,u)$ is crucial for defining residual graphs properly, as it ensures flow pushed back on $(v,u)$ is equivalent to reducing flow on $(u,v)$.