Question

运筹学最大流问题中没有给出流量，如何简便方法看出流量

Answer 1

就是说如何找出一条初始可行流。书上说可以令所有弧的流量等于0，但是这样太慢了，所以我都是自己配的。

按三个原则

1. 发点发出的总流量等于收点收到的总流量。

2. 每一个中间点进去的总流量等于出去的总流量。

3. 流量小于等于容量

   
   

   
   

   
   

   

   比如上面这个图，括号中给出的是初始流量。

   V1发出6+10=16，V7收到7+3+6=16

   V2收到6+3=9，发出6+3=9

   V3收到10，发出3+0+7=10

   V4/V5/V6亦是如此。

   你也可以自己拿这个题练练，比如把V1→V2的流量改成8，那么就变成了下面这样

   

   加粗倾斜的8、1、2、5就是因为把V1→V2的流量改成8而发生了改变。

   但符合上面三条原则，是初始可行流。

追问

非常感谢，，通过你的提示，豁然开朗！