例2.7.2对例2.7.1的各结点的重新排序如图2.27，其最早启动时间是 π(1')=0，r(2)=15,π(3)=15， π(4)=20，π(5)=20，π(6)=24. 元7)=24，r(8)=20,r(9)=27, π(1Y)-27,π(11)=30。 最晚店动时间是 x11‘）=30,r(10)=27, r(9)=28, x(8)=23,x(7)=24, ·r(6)=25,π(5')=20.r(4')=21, r(3)*26,r(2)=15,x(1')=0。 因而图2.26各工序的允许延误时间是 1=0,t2=0,t3=j1,t4=1,t5=0, 图2.27 16=1,l:=1,8=0,tg=0,l16=3,t11=0。 从中可见，最长路径即关键路径上各工序是不允许延误的，否则必将拖延整个]程的 进度。 2.7.2PERT图 在PERT(Programme evaluation and review technique)图中，采用有向边表示工序， 其权值表示该工序所需时间。如果工序e4完成后，才能开始，则令，是e,的终点，P,的始 点.根据这种约定，例2.7.1的PERT 图如2.28，其中i表示工序i。 同样，PERT图不存在有向回路。 5 而且与PT图类似，PERT图中工程 15 的敏早完工时间是到，的最长路 径长度，这条路径就是关键路径。工序 =(:y)的最早启动时间是π(u), 最晚启动时间是t（,,)=π(v) 图2.28 一π(Uvn)一u(v),其中π(，) 是，到，的最长路径长度，w(,v;)是该工序所需的时间。这样工序e=(,v)的允许 延误时间是t(u,,)=r(,,)一π(）。 出算法1可以求出π(d),为了便于计算t(,),可先作简单变换。由于x()= r(v)一r(y),故t(x,)=r()-w(,),即得t(,)=r()一r()一w(, )。这样可直接使用算法2求x()。以图2.28为例，其计算结果是（设已回到原结点 号)。 x(1)=0、r(2)=15,π(3)=20，π(4)=27，r(5)=24,π(6)=30， r(1)=0,t(2)=15,x(3)=20,t(4)=27,r(5)=24.x(6)=30, t1)=0,(2)=0,t(3)=11,t(4)=1,t(5)=0,t(6)=1, ·31·
t(7)=1t(8)=0,t(9)=0,t(10)=3. 与PT图-一样，采用PERT图计算关键路径的复杂性也是O(n)。 PT图和PERT图各具特色。PERT图包含的结点和边数少些，而PT图的结点数与 PFRT图的边数基本料同，图此出边数m较大时PERT图有其优越性。不过PT图更加 灵活，它能适应一些额外的约束、例如图2.29中 d/2 山，十t 【a tb) (c) 2.29 (a）表示工序i完成一半之后j就可以开始。 (b)表示工序；完成后经过t时刻j才开始， (c)表示在时间b,之后工序j才能开始，其中，表示虚拟结点， 2.8中国邮路 中国邮路问题是我国著名图论学者管梅谷教授首先提出并解决的。它与欧拉回路、最 短路以及最小费用流问题都有密切联系。 邮递员传送报纸和信件，要从邮局出发经过他所管辖的每一条街道最后返回邮局，当 然每个邮递员都希望选择一条最短的传送线路，这就是中国邮路问题。用图论的语言描 述，就是在一个正权连通图G中，求从某结点出发经过每条边至少一次最后返回出发点 的最短回路。 我]分别对G是光向连通图和有向连通图进行讨论，而混合图的求解较为复杂，本 书不再加以分析。 2.8.1无向图的中国邮路 如果C中各结点的度都是偶数，挪么G·一定有欧拉回路。显然任何一条欧拉回路都 是该可题的解，若G中只有2个结点”，，的度是奇数，则一定存在从，到，的一条欧拉 道路，它经过了G的各边-次。在(；中再找一条从，到，的最短道路P,则(G'=C十P。 中存在？拉闻路。这样（中的监拉回路.即对应于G中P的边重复…次而其余边只过… 次的回路是-一条中国邮路，或称般挂邮路。 如果心中度为奇数的结点数多于2个，怎样确定最佳邮路呢？ 定理2.8.1L是尤向连通图G最佳邮路的充要条件是： 1.,的每条边敏多軍复-次 2.在的任意个回路上，重复边的长度之和不超过该回路长度的一半。 证明：必要性，如果一条最佳娜路婴重复经过某些边，我们将G中次重复的边商出 相应的条边，得到G.假定一条最佳邮路L,'使(G中的任·条边重复n(n≥2)次，这时 ·32·
G中有欧拉回路L'。岩使e在G重复n·2次.得到(”，G”各点的度仍是偶数，G"的欧 拉间路1"也是(；的一条中国邮路，Hπ(L”)<π(I')、与L'是最佳邮路矛盾，因此，'中e 最多重复一次。假定G的某个回路C上重复边的总长超过该回路长度的一半，可以令C 中重复边不重复，不重复边重复，得倒(”仍是炊拉图。何π(1")<π()，亦与I,是最佳邮 路矛盾。 充分性。假定红意两个不问的邮路L,L:都满足条件1和2，我们将证明r(I,)= π(L),假定此式成立.因为最佳邮路/也满足1和2，这样(L')=(L1),即L:和L,都 是最佳邮路。于是充分性就能得证：。 设L:=E(G)十Q+Q,L2=k()+Q+Q.其中Q是1，和L2中共同的重复边集合。 Q是只属十L,Q:是只属于1的重复边集合。I:和L2的对称差E(G)=Q十Q是(G 中只属于I和只属于L以的重复边集合。构造(=(V(G),E(G),G是简单图，且各结 点的度都是偶数。若E(G)=本.显见π(I,)一(1)；否则G可以划分成若干个回路，对 G的任意-一个回路C.设C,(C外判是L,和I的重复边集，由已知条件，π(C)≤π(C:), π(C:)≤π(C）。故π(C:)x(.)。因此元(1)=π(2】。 定理2.8.1给出了求C中量生邮路的构造方法。首先找出度为奇数的结点，然后依 据条件1构造邮路，保证计算重以法之后各站点的度都是偶数，再由条件2对所有回路进 行判断，如果发现某个回路不满足条件，则令该回路中原先重复的边不重复，而不重复边 变为重复。待完全满足荣件2时，该图的中国邮路得解。 例2.8.1图2.30(a)中国邮酱的求解过程如1下，其中(d)是最终解。重边表示原图该 边重复、 (a) (b) (e) (d) ”., 这种构造算法中由于问路的数址·般很多，因此计算键庞大。中国邮路问题的一个好 算法是Edmonds提出的最小权匹配算法。最小权匹配属于运筹学范畴，在此我]只介绍 该算法的基本思路。 1.确定G中度为奇数的结点，构成V:(), 2.求V(G)各结，点在G中的最短路径P,及其长度π(0：，）。 3.对V(G)的结点达行最小权匹配，即选出iV'(G)i/2个π(，v,),保证每个结点 ∈V(G)在P中只出现-一次，时满足这些π(x,)的总和最小。 4.在：最小权匹配里各π(x,)断对应的路径P,中的诸边在G中重复一次，得到G。 5.(”是欧拉图，它的一苏：向路即！为解 ·33
2.8.2有向的中国邮路 对于有向图来说.中国邮路问题可能无解。其原因是G中可以含有正度或负度为0 的结点.例如的2.31中就不存在最佳邮路。以下我们将排除 这类情况进行讨论。 如果(：中名结点的正、负度相等，则由推论2.3.2，G中 存在：有向欧拉回路。它过每边一次且仅…次。[因此任一条欧 垃回路都是中国邮路。 知！果图（不对称，即存在-…些结点，d(.)≠d(), 图2.31 不妨设d“(u,)>d(u,),由于邮递员班经过进入的每-一条 边，因此他…定要重复走以，为始点的某条边。设f,表示边(，v,)的重复次数，表示 该边的权，那么中国邮路要选择重复一些边后存在有向欧拉回路并且使 J/。 (1) .已（的 为最小的·个解。显然这时满足 d(,)+∑f=dr(u,)+∑f, u,∈V(G) 将上式整理可得 ∑(fn-f)=d()-d(,)=d'(i). (2) 如巢(i)>0,表示邮路中，要d(i)次经过，所发出的一些边，或者说：可供应 d”(i)个单位其。如果d”()<0,表示邮路中u,要d”()次经过进入的一些边，或者说v 可按收d)个单位薰。d”G)=0则称是中间结点。由于∑d()=d(u,),所以 严d1二)，这样可以逐次保证每个可供应点，经过一些边向某个接收点y,供应1个 前位放，最后达到平衡。或若说这些道路上的边出现重复，最后得到的图G是有向欧拉 图，如烘这些彩复边的总长最小，它即是最佳邮路。 为了便于分析.可以对图G增设两个结点：超发点，超收点，。对每一个供应点， 都打边(u,),f,=d(i),n=0;对每一个接收点，都有边(v,),于=一d(j),w#=0。 :明用d)条币边表示(，，)，d(j)条重边表示(，)，得到多重图G。这样中国邮路问 超导改求过G'中形如，，)，(，心，)每边-一次，总长最短的d(o,)条Pm道路。 综上，非对称有向图的中国邮路算法的基本思路是： 1.让算各结点的正、负度，求出d()。 2.如·个超发点，对满足d(i)>0的结点“，加入d'()条有向边(v,),权均为 :漆加一个超收点，对满是d()<0的结点·加入d'（)|条有向边(，)，权均为 行，得到图(：。 3.在G中求d()条过以，，为两端点的形如(，，)，(u,)每边一次且仅-一次的 丛利最小的P道路。记下G中各边在这些道路中的重复次数。 4.计入各边的重复次数，G中存在有向欧拉间路，其中一条即为解。 例说明下： ·34·
例2.8.2求图2.32的中国邮路。 解：(1)各结.点的d(i)为d(1)=d”(5)=0,(2)=2,d(3)=一1，d(4)=一1。 (2)构造（如图2.33(a)。 (3)得到2条总和最小的P道路P,=(2v4v),π(P1)=5。P2=(,2,4,3, ,),r(P:)上6。x(p,)=1。这样边()重复2次，边(4，a)重复1次。得图 2.33(b),其中虚线边表示重复1次。 (4)2.33(b)是欧拉图。其中一条欧拉回路如(2，v4,3,,04V,5,2v4,5山) 就是最佳邮路。 (a) (b) 图2.32 图2.33 算法的难点是步骤3。它需要找d(,)条P道路，这些道路长度的总和最小。若用 Dijkstra算法一条一条地寻找最短P道路，则计算量比较大，同时结果并不一定最佳。如 果我们把G中每边的权视为通过该边的费用，而容量为∞，对始发点，(，，)形式的边 只有一条，它的费用为0，容量为d(i);同样对超收点v,每条边()的费用为0，容量 为d()1,这样步骤3就可以转化为在G上求从巴，到v:传送∑d(i)个单位量的最小费 州流问题，如式(1)所示。关于最小费用流将在第六章讨论。 习 题二 1.设简单图G有k个连通支，证明 7m≤专(n一+1(nk). 2.证明G和G至少有一个是连通图。 3.证明：连通图有的最长道路必定相交于同结点。 4.在简单图中，证明：若2≥4且m≥2n…3,期G中含有带弦的回路。 5.设G是不存在三角形的简单图，证明： a.≥dr(u,)≤mn。 bms学 ·35·