2
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Yes verry smart, what if we consider only flows that dont have these "detached" flow cycles? $\endgroup$
    – leoneu
    Sep 24, 2022 at 16:23
  • $\begingroup$ According to the flow decomposition theorem, that is all that can go wrong. $\endgroup$
    – RobPratt
    Sep 24, 2022 at 17:59

You must log in to answer this question.

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