質問

I have a directed graph G=(V,E) with a source s$\in V$ and a sink t$\in V$. There is a minimum capacity (lower bound) l $_{e}$ for each edge in G. There are no upper bounds on the edges.

In a course that I took, the professor told that to find a minimum flow -

1) We need to assign a large capacity to all edges and find flow f
2) Construct G $_{1}$ where all edges are reversed and each edge has capacity f$_{e}$ - l$_{e}$
3) We need to then find the max flow from t to s in G$_{1}$ that is f$_{1}$
4) Then, the minimum flow in G is f-f$_{1}$

My question is- Why can't we find a s to t path in G with the least value of l$_{e}$. The least value of l$_{e}$ would be the minimum flow that could be pushed through the network?

役に立ちましたか?

解決

Imagine you have the following graph (in red are the minimum capacities):

enter image description here

The $(s,t)$-path with the lowest flow demand needs $1$ unit of flow, but the minimum flow is $4$. And the $(s,t)$-path with minimum sums of capacities has a sum of $2$, so this also doesn't work.

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top