Network's flow - a couple of issues

Question

There are three requirements for the path to be a flow - capacity constraints, skew symmetry, and the flow conservation ( http://en.wikipedia.org/wiki/Flow_network ).

Ok, but what if the network would have only directed edges?

Green numbers are the flow function values, numbers in the squares are values of c(x, y).

Now, I don't see how the skew symmetry and the flow conservation are complied here...are they? (according to my notes they should be).

---

Another thing is - what actually is the flow? I guess it's not just a path between S and T vertices. I'd owe you a beer if you could explain me this as simply as possible :P

Answer 1

Everything regarding the question should be clear from the Wikipedia entry you referred to. Anyway, flow networks are directed graphs by definiton. For 'skew symmetry' Cormen's Introduction to Algorithms says:

Skew symmetry is a notational convenience that says that the flow from a vertex $u$ to a vertex $v$ is the negative of the flow in the reverse direction.

So nothing to worry about skew symmetry. It is true for the graph by definition.

For 'flow-conservation' Cormen says:

The flow-conservation property says that the total flow out of a vertex other than the source or sink is $0$.

This property obviously holds for the given graph. For example, for vertex $1$: $f(1, s) = -1$ (due to skew symmetry), $f(1, 2) = 0$, $f(1, 4) = 0$, and $f(1, t) = 1$. Adding all of them gives $0$, hence the total flow out of vertex $1$ is indeed $0$. You should be able to prove this for other vertices.

In the given graph the net flow is $1$---that is $1$ unit of flow is leaving source ($s$) and exactly that amount of flow is reaching sink ($t$). Consult the Wikipedia entry or a good graph theory or algorithm textbook to understand what is 'flow' better.