公共点集,情形(二)的有向路也不通过情形(一)的公共点集所以可判断出 这两部分是独立的、互补的如果我们在图G中分别去掉点集{(1,2,以=0,1,2}和 (2,1,)z=0,1,2}及与之相关联的入弧,就形成两个新的网络图,如图H1和H2 这两个网络图具有互补性对于一个问题来说,最短路线必存在于它们中的某 个中. 由于调整垂直刀具为3次时,总费用需增加3e,故我们先安排这种情况的权 增加值e,每次转刀时,给其待切弧上的权增加e增加e的情况如图9-14中所示再 来判断是否满足调整垂直刀具为二次、一次时的情况,我们发现所增加的权满足 另外两类切割序列 综合上述分析,我们将原网络图G分解为两个网络图H1和H2,并在指定边 上的权增加e,然后分别求出图H1和H2中从Ⅵl到v27的最短路,最短路的权分 别为:dl,d2则得出整体的最少费用为:d=min(d1,d2),最优切割序列即为其 对应的最短路径 实例:r=15,∈-2时,求得图G与G2的最短路为G2的路ⅤI-Ⅴ4-V5-V14 V17-V26-V27,权为4435,对应的最优切割序列为M-MI-M6-M4-M5 M2,最优费用为4435. u18 图9-14H1 图9-15H2公共点集，情形（二）的有向路也不通过情形（一）的公共点集.所以可判断出 这两部分是独立的、互补的.如果我们在图G中分别去掉点集{(1,2,z)|z=0,1,2}和 {(2,1,z)|z=0,1,2}及与之相关联的入弧，就形成两个新的网络图，如图Ｈ1和Ｈ2. 这两个网络图具有互补性.对于一个问题来说，最短路线必存在于它们中的某一 个中. 由于调整垂直刀具为3次时，总费用需增加3e， 故我们先安排这种情况的权 增加值e，每次转刀时，给其待切弧上的权增加e.增加e的情况如图9-14中所示.再 来判断是否满足调整垂直刀具为二次、一次时的情况，我们发现所增加的权满足 另外两类切割序列. 综合上述分析，我们将原网络图G分解为两个网络图Ｈ1和Ｈ2，并在指定边 上的权增加e，然后分别求出图Ｈ1和Ｈ2中从V1到V27的最短路，最短路的权分 别为：d1,d2.则得出整体的最少费用为：d = min(d1,d2) ，最优切割序列即为其 对应的最短路径. 实例：r=15,e=2时，求得图G1与G2的最短路为G2的路V1－V4－V5－V14－ V17－V26－V27，权为4435，对应的最优切割序列为M3－M1－M6－M4－M5 －M2，最优费用为4435. 图 9-14 H1 图 9-15 H2