图411所示的就是一个网络,其中孤上的数值为该孙容量 3 图41.1网络 2021/12/10 重庆邮电大学 理学 6 院
图 4.1.1 所示的就是一个网络，其中弧上的数值为该弧的容量。 图 4.1.1 网络2 4 37 2 61 51 2021/12/10 重庆邮电大学 理学 院 6
·对于任意一个有多个收、发点的网络N,可以在 上添加两个顶点S和t得到新的网N′,其中用容量 为∽的弧把S连接到V中每一个发点,用容量为∞的 弧把V中每一个收点连接到t,这时分别称和为超 级发点或超级源和超级收点或超级汇。 如图4.1.2,其中图(a)表示有三个发点两个收点的网 络,囹(b)表示添加了超级发点和超级收点的网络。 S 6 4 S (a) 图412超级发点与超级收点 021/12/10 理学院 7
2021/12/10 重庆邮电大学 理学院 7 5 5 4 2 6 4 3 3 2 (b) 图 4.1.2 超级发点与超级收点 (a) 4 2 6 4 3 3 2
定义412设N=<V,E,C>是一个网络。称定义在弧集EA非负 函数F为网络N=<V,E,C>上的流 对于弧e=<v,v>∈E,F(e)=F(v,v>)称为弧e=< vn,v>∈E上的流量,记作同,即F(e)=F(<v,n>)=F1 ·称ΣeνF(即ΣvevF,下同)是流入j的流量或j的流入量; ·称Σ ey Fii是流出j的流量或j的流出量; 若Fj=Cj,即弧<vv>的流量已经达到它的容量,则称弧 <;,υ;>在流F下是饱和的,否则称弧<1;,υ;>是不饱和的。 若流F满足 1)Fi≤Cij(称为限制条件或相容条件); (2)对于既不是源也不是汇的每个顶点,Σ ey Fi=∑evF (称为守恒条件或平衡条件,其中除非另有说明,总是对所 有步,而且如果<vv>不是边,则设F=0)。 中网络的一个可行流。 202l/12/10 重庆邮电大学 理学院 8
2021/12/10 重庆邮电大学 理学院 8
定理Ⅰ给定网络N=<V,E,C>的一个流,其 为S,收点为t,则流出发点S流量等于流入收点t的 流量,即∑evFt=∑ i∈ VSi o 定义3给定网络N=<V,E,C>的一个流,其发点 为S,收点为t,称值∑∈vFsi=∑evFt为流F的值, 记作V(F)。如图41.1中V(F)=10 图41.1网络 021/12/10 重 ""、 哩学院
2021/12/10 重庆邮电大学 理学院 9 图 4.1.1 网络 2 4 3 7 2 6 1 5 1
网络流研究中的一个基本问题是求网络N的一个 可行流F,而且还希望使得F达到最大值,即使 行流F成为网络N的最大流 般地,可能存在几个具有相同最大值的流。为 了给出一个求最大流的算法。下面我们再来介绍 网络的截集。 021/12/10 重庆邮电大学 理学院
2021/12/10 重庆邮电大学 理学院 10