注:(1)网络顶点分层后,弧有三种可能的情况: 从第i层顶点指向第i+1层顶点 从第i层顶点指向第i层顶点 从第i层顶点指向第j层顶点(<1); (2)不存在从第i层顶点指向第计+k层顶点的弧(k≥2)。 (3)并非所有网络都能分层。例如,下列网络不能分层。 网络顶点分层的算法广探法,广度优先搜索法): 给定N=(V,x,y,A,C 算法描述1 第0步:令V={x},:=0 第1步:令S=UV,若S=V,分层完毕:否则转下步 第2步:令V1=N(S)={S1的所有出邻点}。若V1=中,则停,网络不能继续分层;否则,转 下步。 第3步:令i=i+1,转第1步。 算法描述2: 第0步:给x标上0,令V={x},U6=F-V,T=V,i:=0。 第1步:在T中任取顶点v,找出v的所有尚未标号的出邻点,给它们标上 第2步:令T=T-{v},若T≠Φ,转第1步;否则转下步。 第3步:令Vn1={标号为i+1的所有顶点},U1=U-V1 若l1≠Φ,Ul≠Φ,则令T=Vn1,i:=i+1,转第1步。 若1≠Φ,但Ul4=Φ,则停止,分层完毕。 若V=Φ,但U,1≠Φ,则停止,网络不能继续分层。 注:分层算法的复杂性为O(4)。 三、辅助网络 定义932设∫是网络N(V,x,y,A,c)的可行流,N()是N的关于∫的增量网络,对N(f)的顶点按 最短有向路分层后,删去比y层数高的顶点及与y同层的顶点(保留y);再删去从高层指向低层的弧及 同层顶点间的弧。所剩的各条弧上的容量与N(f)中相同。这样所得的网络是N()的子网络,称为N 1关于流∫的辅助网络,记为AN(f)注：(1) 网络顶点分层后，弧有三种可能的情况： z 从第 i 层顶点指向第 i +1 层顶点； z 从第 i 层顶点指向第 i 层顶点； z 从第 i 层顶点指向第 j 层顶点 (j < i )； (2) 不存在从第 i 层顶点指向第 i+k 层顶点的弧( ) k ≥ 2 。 (3) 并非所有网络都能分层。例如，下列网络不能分层。 网络顶点分层的算法(广探法，广度优先搜索法)： 给定 N = (V, x, y, A, C)， 算法描述 1： 第 0 步：令 { }, : 0 V xi = = 0 . 第 1 步：令 , 0 i i i k S V= = ∪ 若 i S V= ，分层完毕；否则转下步。 第 2 步：令 () { V NS S i ii 1 + + = = 的所有出邻点}。若Vi+1 = φ ，则停，网络不能继续分层；否则，转 下步。 第 3 步：令i i := + 1 ，转第 1 步。 算法描述 2： 第 0 步：给 x 标上 0，令 0 V x = { }， , ,: 0 00 U V VT Vi =− = = 0 。 第 1 步：在 T 中任取顶点 v，找出 v 的所有尚未标号的出邻点，给它们标上 i+1. 第 2 步：令TT v = −{ }，若T ≠ Φ ，转第 1 步；否则转下步。 第 3 步：令 1 { Vi+ = 标号为i +1的所有顶点}，U UV i ii +1 1 = − + . 若 1 1 , V U i i + + ≠Φ ≠Φ ，则令 1,: 1 TV i i = i+ = + ，转第 1 步。 若Vi+1 ≠ Φ ，但Ui+1 = Φ ，则停止，分层完毕。 若Vi+1 = Φ ，但Ui+1 ≠ Φ ，则停止，网络不能继续分层。 注：分层算法的复杂性为 O(A)。 三、辅助网络： 定义 9.3.2 设 f 是网络 NV x y Ac (,,, ,) 的可行流， N f ( ) 是 N 的关于 f 的增量网络，对 N f ( ) 的顶点按 最短有向路分层后，删去比 y 层数高的顶点及与 y 同层的顶点(保留 y)；再删去从高层指向低层的弧及 同层顶点间的弧。所剩的各条弧上的容量与 N f ( ) 中相同。这样所得的网络是 N f ( ) 的子网络，称为 N 的关于流 f 的辅助网络，记为 AN f ( ) 。 x y