图论—最大流及最小费用流

图论

能不能从前门出去穿过每个门恰好一次且从后门出去？？

欲建设一个连接7个城市的光纤通信网络。 各城市间线路的造价如图所示，求一个使总造价最少的线路建设方案。

各线路的造价图

最大流问题：

?

最大流问题是一类应用极为广泛的问题，例如在交通运输网络中有人流、车流、货物流、物流、通信系统中有信息流、油气管流——他们的共同的特点：有发点、收点、中转点、每条弧上有传输能力的限制、传输有方向。

网络流

?

概念： 发点 收点 vs 中间点 容量 cij流量 fijv1 (4.2) (5.2) v4 v5 (3.3) vt

?????

v2 (3.0) v3

(2.2)

v6

通过每条弧的流只允许沿着弧的箭头方向流 动，目标是使得从发点到收点的总流量最大