Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
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? –  Tim Oct 28 '12 at 20:05
    
(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. –  Per Alexandersson Oct 29 '12 at 7:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.