question about flow decomposition theorem

43 Views Asked by At

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:

  1. 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?
  2. 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!

1

There are 1 best solutions below

0
On

After reading the proof of this theorem, I have the answer.

  1. edge weight does not need to be integer.
  2. Yes, there exists a decomposition such that each path or cycle has positive integer weight