一、运输网络1.运输网络的定义定义8.7：一个带权有向图G=(V,E)若满足如下条件：(1)G是连通无自环的；(2)每条弧(i,j)的权cij为非负整数，称为弧的容量，cij全体所构成的集合记为C；(3)存在2个不同的顶点s和t。则称该有向图为运输网络,简称网络，记为N(V,E,C)。称s为发点,t为收点,除s和t以外其它顶点称为中间点。C称为容量函数。2.运输网络N中的流定义8.8：在网络N(V,E,C)的弧集E上定义了一个非负整值函数f={fij},称f为网络N上的流,fij称为弧(i,j)上的流量。若无弧(i,j),则fij定义为0。设流f满足下列条件:(1)容量限制条件：对每一条弧(i,j),有fij≤cij。(2)平衡条件：除s和t外的每个中间点k,有即流出和等于流入和。对于s和t有则称f为网络N的一个可行流,Vf为流f的值,或称f的流量。若N中无可行流f',使Vf'>Vf,则称f为最大流。定义8.9：若fij=cij,则称弧(i,j)是饱和的;若fij<cij,则称弧(i,j)是未饱和的。若fij=0,则称弧(i,j)是f-0的;若fij>0,则称弧(i,j)是f-正的.现在的关键是如何求最大流的值。二、最大流最小割定理引理：对于给定的网络N=(V,E,C),若可行流f和割(P,V-P),成立Vf=C(P,V-P)，则Vfmax=Vf，Cmin(P,V-P)=C(P,V-P)。因此求最大流的一个想法就是构造流和割，使得流量和割容量相等。福特,富克逊(Frod,Falkerson)于1956年给出的最大流最小割定理基本思想：1）对任意网络构造初始流。零流,或其他可行流。2）在初始流基础上寻找可增加流的路，这样的路称为增广路。并在寻找增广路的同时，计算在该路上可增加多少流。3）若找到了从s到t的可增加流的路，则修改流，得到新的可行流。然后转回2）(1)怎样找增广路(2)如果找不到这样的增广路，是否此时的流就是最大流？1.寻找增广路的方法设u为s到t的路（不考虑弧的方向）(1)先考察该路上与路方向一致的弧(称为向前弧)。若路上所有弧均为向前弧，且每条弧的流量<相应弧的容量，则可增加流的路。对于向前弧(i,j)，fij是否<cij。可增加流的通路，采用标号法。1)对源点s标号(-)2)设点i已经标号，j点没有标，对于向前弧(i,j)，若fij<cij，则点j标号i+；若fij=cij，则点j不标号。3)若收点t最后被标号，如t点被标号c+，则找到了从s到t的增广路。还需要知道这条路可增加多少流量，以便修改流。1)对源点s标号(-),令Δs=+∞。2)设点i已经标号，增量为Δi，j点没有标，对于向前弧(i,j)，若fij<cij，则点j标号i+，Δj=min{Δi，cij-fij}若fij=cij，则点j不标号。3)若收点t最后被标号，如t点被标号c+，Δt=min{Δc，cct-fct}，这就找到了从s到t的增广路，可增加的流量是Δt。修改流时，为满足平衡条件，对该路上所有弧流量+Δt。若按此方法找不到增广路，是否就结束？否还可采用下面的方法(2)如果u中部分弧的方向与路的方向相反(称这样的弧为向后弧)。如下图所示。0)对任意网络构造初始流。1)对源点s标号(-，+∞)。2)设点i已经标号，增量为Δi，j点没有标，i)对于向前弧(i,j)，若fij<cij，则点j标号(i+,Δj)，这里Δj=min{Δi，cij-fij}若fij=cij，则点j不标号。ii)对于向后弧(i,j)，若fji>0，则j点标号(i-,Δj)，这里Δj=min{Δi,fji}。若fij=0，则点j不标号。(3)重复第2步，直到i)若收点t最后被标号(x+,Δt)，这就找到了从s到t的增广路，可增加的流量是Δt。修改流时，对该路上所有向前弧流量+Δt，向后弧上的流量减少Δt，并以此结果作为新的流，转向1)。ii)若不再有新的顶点被标号，且t仍没有被标号，则说明网络中的流为最大流定理：用上述标号法在算法停止时得到的一定是最大流。证明：算法停止时,已经标号的点构成集合P，没有标号的构成V-P，则(P,V-P)构成割。然后证明网络中的流的值就等于该割的容量。关于算法有2点要说明：1)在某点有多种标号选择时，可任意选择1种进行标号。2)初始流不一定是零流，只要是可行流即可。8.3图与二分图的匹配完美匹配不一定唯一.定理:无自环的图G,若它有完美匹配,则|V(G)|为偶数.定义：若G中不存在匹配M',使|M'|>|M|,则称M为G的最大匹配。二、匹配的基本定理首先引进2个定义。定义8.12：设M是G的一个匹配,(1)若在G中有一条路,它的边