运筹学第5章图论课件.ppt

* v1 v2 vs v3 vt (0, 10) (0, 8) (0, 2) (0, 10) (0, 5) (0, 7) (0, 4) 解： （1）取f（0）= 0为初始可行流。如下图所示，弧旁数字为( fij , cij )。 * v1 v2 vs v3 vt 4 1 6 3 2 1 2 构造赋权有向图W（f（0）），用标号法求其最短路。 (vs, 1) (0,0) * v1 v2 vs v3 vt 3 1 (vs, 1) (0, 0) (v2, 3) 2 2 1 4 6 * v1 v2 vs v3 vt 3 1 (vs, 1) (0, 0) (v2, 3) (v2, 4) 4 1 2 2 6 * v1 v2 vs v3 vt 3 1 (vs, 1) (0, 0) (v2, 3) (v2, 4) (v1,4) 6 2 2 1 4 * 由此得到从vs到vt的最短路： v1 v2 vs v3 vt (4, 10) (1, 8) (6, 2) (3, 10) (2, 5) (1, 7) (2, 4) (vs, 1) (v2, 3) (v1,4) * v1 v2 vs v3 vt (0, 10) (0, 8) (0, 2) (0, 10) (0, 5) (0, 7) (0, 4) 与上述最短路相应的增广链为μ＝( vs, v2, v1, vt )。以 ? =5调整该增广链，得到流 f（1），过程如下图所示： (5, 8) (5, 5) (5, 7) * （2）构造赋权有向图W（f（1）），用标号法求出最短路： v1 v2 vs v3 vt 4 1 6 3 1 2 -1 -2 -1 零流弧不变； 饱和弧反向，且权为其相反数； 既非零流弧，也非饱和弧的，添加反向弧，其权为其相反数。 * v1 v2 vs v3 vt (0, 10) (5, 8) (0, 2) (0, 10) (5, 5) (5, 7) (0, 4) 以? =2调整最短路对应的增广链，得到流 f（2）。 (2, 10) (7, 7) * （3）构造赋权有向图W（f（2）），用标号法求出最短路： v1 v2 vs v3 vt 4 1 6 3 -1 2 -1 -2 -4 * 以? =3调整最短路对应的增广链，得到流 f（3）。 v1 v2 vs v3 vt (0, 10) (5, 8) (0, 2) (0, 10) (5, 5) (5, 7) (0, 4) (2, 10) (7, 7) (8, 8) (3, 10) (3, 4) * （4）构造赋权有向图W（f（3）），用标号法求其最短路： v1 v2 vs v3 vt 4 -1 6 3 -1 2 -2 -2 -4 -3 * 以? =1调整最短路对应的增广链，得到流 f（4）。 v1 v2 vs v3 vt (0, 10) (5, 8) (0, 2) (0, 10) (5, 5) (5, 7) (0, 4) (2, 10) (7, 7) (8, 8) (3, 10) (3, 4) (3, 10) (4, 5) (4, 10) (4, 4) * （5）构造赋权有向图W（f（4）），用标号法求其最短路： v1 v2 vs v3 vt 4 -1 6 3 -1 -2 -2 -4 -3 2 此时已不存在从vs到vt的最短路。故流 f（4）即为最小费用最大流。 * v1 v2 vs v3 vt (0, 10) (5, 8) (0; 6, 2) (0, 10) (5, 5) (5, 7) (0, 4) (2, 10) (7; 1,7) (8; 1, 8) (3, 10) (3, 4) (3; 4, 10) (4; 2, 5) (4; 3,10) (4; 2,4) 弧旁数字为( fij ; bij , cij ) * 第六节 中国邮递员问题 一、问题的提出 给定一个连通图，在每条边ei上赋予一个非负的权w(ei )，求一个圈（未必是简单圈），过每条边至少一次，并使圈的总权最小。 (1)概念：欧拉图——一个图若含有欧拉圈，则称为欧拉图。 (2)结论：连通图G能够一笔画 ? G为欧拉图或包含欧拉链。 欧拉（Euler）链—连通多重图G中的链，过每边一次，且仅一次。 (v3, v4,v3,v1,v2,v4) v3 v4 v2 v1 e1 e2 e3 e4 e5 欧拉圈—连通多重图G中的简单圈，过每边一次，