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?



1 Answer 1


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).

  • $\begingroup$ Thanks! (1) "these edges may be reduced, to a single, oriented edge, with non-negative flow", do you mean to combine multiple edges between two vertices into one edge by summing the signed flows on the multiple edges, and decide its direction so that its flow is nonnegative? (2) "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." Does Wikipedia say that when you do the collapse of multiple edges into one, the flow on that one edge is zero? If yes, it is not an interesting case, is it? $\endgroup$
    – Tim
    Commented Oct 28, 2012 at 20:05
  • $\begingroup$ (1) Yes. (2) This statement is about a single edge, which has already been collapsed; it cannot be collapsed further. f(u,v)=-f(v,u) is rather a statement on how edge direction and sign of flow are connected. $\endgroup$ Commented Oct 29, 2012 at 7:04
  • $\begingroup$ @PerAlexandersson Can we use the in-flow = out-flow constraints to replace the Skew symmetry and Flow conservation? $\endgroup$
    – Mr. Ree
    Commented Mar 10, 2017 at 13:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .