From Wikipedia:
$G(V,E)$ is a finite directed graph in which every edge $\ (u,v) \in
E$ has a non-negative, real-valued capacity $\ c(u,v)$. A flow network
is a real function $\ f:V \times V \rightarrow \mathbb{R}$ with the
following three properties for all nodes $\ u$ and $\ v$:Capacity constraints: …
Skew symmetry: $\ f(u,v) = – f(v,u)$. The net flow from $\ u$ to $\ v$ must be the opposite of the net flow from $\ v$ to $\ u$.
Flow conservation:…
For any two vertices $v$ and $u$, the two edges $(v,u)$ and $(u,v)$ may not both exist.
Even if they both exist, I don't understand why skew symmetry may be required.
Also I didn't see "Skew symmetry" is required in the definition in books such as Introduction to graph theory by West, and Combinatorial optimization by Korte and Vygen).
So I wonder if skew symmetry is or may be required for a flow network?
Thanks!
Best Answer
Usually, one represents flow like this in a matrix, where entry at position $(u,v)$ is the flow from $u$ to $v.$ If there is no such edge, then we consider the flow to be 0.
You can of course have flow between two nodes along multiple edges, in different directions, but these edges may be reduced, to a single, oriented edge, with non-negative flow.
So, the assumption above you seem to get stuck on, is just an assumption that we've already made this simplification. If you do not like this simplification, you may instead add an extra node on the middle of each multi-edge. For example, if there are three edges between node A and B, add an extra edge in the middle of each such edge, and adjust flow in the obvious manner.
Both these adjustments makes the model simpler, since we only need to store half of the matrix, for example (as it is skew-symmetric).