Given a flow network on a directed graph, the flow decomposition theorem tells us that it can be composed into a finite set of s-t paths and cycles.
I have two questions about the flow decomposition theorem:
- Do we require that each edge weight in the network be a non-negative integer? if edge weights are non-negative float, is the flow decomposition theorem still correct?
- If each edge weight in the network is a non-negative integer, can we always find a decomposition such that each path or cycle has positive integer weight?
Thanks!
After reading the proof of this theorem, I have the answer.