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?

New contributor
leoneu is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

1 Answer 1

0
$\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
    2 days ago
  • $\begingroup$ According to the flow decomposition theorem, that is all that can go wrong. $\endgroup$
    – RobPratt
    2 days ago

Your Answer

leoneu is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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