Is a network flow equivalent to a walk?

45 Views Asked by At

Consider a directed graph where each edge has infinite capacity.
Now consider a directed walk on this graph from arbirtary node s to arbitrary node t with $s \neq t$.

Definition (Directed walk): A walk is a sequence of not necessarily distinct edges directed in the same direction which joins a sequence of vertices. It differs from a path because a walk can contain cycles.

With this walk we can build an s,t-flow of size 1 where the following condition holds: the flow on every edge e is equal to how manny times e appears in the walk.

I'm pretty sure the flow we just built is valid because if the walk passes i times from node v with $v \notin$ {$s,t$} then node v sees a flow of size i entering and a flow of size i leaving. It's not a formal proof but I think I can write one down.

What I'm not so sure about is if we can do exactly the reverse: build a directed walk between nodes s and t for every s,t-flow of size 1 such that the same condition as above holds.

My question is: is it possible to build a walk for every flow, and if yes how would I go about prooving it?

1

There are 1 best solutions below

2
On

Consider the sum of a flow of $1$ along a directed path from $s$ to $t$ and a flow of $1$ along a directed cycle that does not share any nodes with the path.