运筹学(第6章图与网络分析).ppt

运筹学基础及应用(Operations Research)主讲：杨启明图的基本概念与模型图的基本概念与模型1 1树图和图的最小部分树树图和图的最小部分树2 2最短路问题最短路问题3 3第6章 图与网络分析邮路问题邮路问题4 4网络的最大流网络的最大流5 5近代图论的历史可追溯到18世纪的七桥问题穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡 7 桥”难题。Euler1736年证明了不可能存在这样的路线。KnigsbergKnigsberg桥对应的图桥对应的图6.1 图的基本概念与模型岛北区东区南区l 图论中图是由图论中图是由点点和和边边构成，可以反映一些对象之间的关系。构成，可以反映一些对象之间的关系。l 一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈e2e1e3e4e5例如：在一个人群中，例如：在一个人群中，对相互认识这个关系我对相互认识这个关系我们可以用图来表示，图们可以用图来表示，图6-16-1就是一个表示这种就是一个表示这种关系的图。关系的图。图的定义：图的定义：若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合，记作：其中:V点集 E边集 当然图论不仅仅是要描述对象之间关系，还要研究特定关当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵陈等七人的相互认识关系我们也可以用图的，如对赵陈等七人的相互认识关系我们也可以用图6-26-2来表来表示，可见图论中的图与几何图、工程图是不一样的。示，可见图论中的图与几何图、工程图是不一样的。(v1)赵赵(v2)钱钱孙孙(v3)李李(v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5图图6-2图与网络的基本概念图与网络的基本概念图与网络的基本概念图与网络的基本概念a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈图图6-3 如果我们把上面例子中的如果我们把上面例子中的“相互认识相互认识”关系改为关系改为“认识认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图系了，这是我们引入一个带箭头的联线，称为弧。图6-36-3就是就是一个反映这七人一个反映这七人“认识认识”关系的图。相互认识用两条反向的关系的图。相互认识用两条反向的弧表示。弧表示。图的基本概念与模型的基本概念与模型定义:图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=v1,v1;e2=v1,v2;v3e7e4e8e5e6e1e2e3v1v2v4v5 端点,关联边,相邻若有边e可表示为e=vi,vj，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。图的基本概念与模型的基本概念与模型 环,多重边,简单图如果边e的两个端点相重，称该边为环。如右图中边e1为环。如果两个点之间多于一条，称为多重边，如右图中的e4和e5，对无环、无多重边的图称作简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5图的基本概念与模型的基本概念与模型 次，奇点，偶点，孤立点与某一个点vi相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。右图中d(v1),d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次:一个图的次等于各点的次之和。图的基本概念与模型的基本概念与模型 链，圈，连通图图中某些点和边的交替序列，若其中各边互不相同，且对任意vi,t-1和vit均相邻称为链。用表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称图不连通。图的基本概念与模型的基本概念与模型 二部图（偶图）图G=(V,E)的点集V可以分为两各非空子集X，Y，集XY=V,XY=,使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二部图，(b)也是二部图，但不明显，改画为(c)时可以清楚看出。图的基本概念与模型的基本概念与模型 子图，部分图(支撑子图)图G1=V1、E1和图G2=V2，E2如果有 称G1是G2的一个子图。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G图）若有 ，则称G1是G2的一个部分图(支撑子图)。图的基本概念与模型的基本概念与模型 网络（赋权图）设图G（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权,赋予权的图G称为网络(或赋权图）。权可以代表距离、费用、通过能力(容量)等等。910201571419256端点无序的赋权图称为无向网络端点有序的赋权图称为有向网络。图的基本概念与模型的基本概念与模型 出次与入次 有向图中，以vi为始点的边数称为点vi的出次，用d+(vi)表示；以vi为终点的边数称为点vi 的入次，用表示d-(vi)；vi 点的出次和入次之和就是该点的次。有向图中，所有顶点的入次之和等于所有顶点的出次之和。图的基本概念与模型的基本概念与模型 图图的模型的模型应应用用例6.1 有甲,乙,丙,丁,戊,己6名运动员报名参加A,B,C,D,E,F 6个项目的比赛。下表中打的是各运动员报告参加的比赛项目。问6个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。ABCDEF甲甲乙乙丙丙丁丁戊戊己己图的基本概念与模型的基本概念与模型解：用图来建模。把比赛项目作为研究对象，用点表示。如果2个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。ABCDEF在图中找到一个点序列，使得依次排列的两点不相邻，即能满足要求。如：1)A,C,B,F,E,D2)D,E,F,B,C,A图的基本概念与模型的基本概念与模型一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。思考题思考题图的基本概念与模型的基本概念与模型 思考思考题题解答：解答：以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿道路，如C CE EA AF FD DB B，就是一个符合要求的考试课程表。图的基本概念与模型的基本概念与模型A AF FE EDDC CB B图的基本概念与模型的基本概念与模型A AF FE EDDC CB B图的基本概念与模型的基本概念与模型 图图的基本性的基本性质质：定理1 任何图中，顶点次数之和等于所有边数的2倍。定理2 任何图中，次为奇数的顶点必为偶数个。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的2倍。证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得：2m为偶数，且偶点的次之和 也为偶数，所以 必为偶数，即奇数点的个数必为偶数。图的基本概念与模型的基本概念与模型图的矩阵描述：如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等。1.邻接矩阵对于图G=（V，E），|V|=n，|E|=m，有nn阶方矩阵A=(aij)nn，其中v5v1v2v3v4v64332256437例6.2 下图所表示的图可以构造邻接矩阵A如下对于赋权图G=(V,E),其中边 有权 ,构造矩阵B=(bij)nn 其中：图的基本概念与模型的基本概念与模型 2.2.关关联联矩矩阵阵对于图G=(V,E),|V|=n,|E|=m,有mn阶矩阵M=(mij)mn，其中:3.3.权矩阵权矩阵1 0 1 0 0 0 0 0 0 0 0 01 1 0 0 1 0 0 0 0 0 0 00 1 0 0 0 1 1 1 0 0 0 00 0 0 0 0 0 0 0 1 0 0 10 0 1 1 1 1 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 00 0 0 0 0 0 0 0 0 1 1 10 0 0 1 0 0 1 1 0 0 0 0v1v2v3v4v5v6v7v8e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4例6.3 下图所表示的图可以构造邻接矩阵M如下:M=（mij）=v5v1v2v3v4v64332256437例6.4 下图所表示的图可以构造权矩阵B如下:无向图：由点和边构成的图，记作无向图：由点和边构成的图，记作G=G=（V V，E E）。）。有向图：由点和弧构成的图，记作有向图：由点和弧构成的图，记作D=D=（V V，A A）。）。连通图：对无向图连通图：对无向图G G，若任何两个不同的点之间，至少存在一条，若任何两个不同的点之间，至少存在一条链，则链，则G G为连通图。为连通图。回路：若路的第一个点和最后一个点相同，则该路为回路。回路：若路的第一个点和最后一个点相同，则该路为回路。赋权图：对一个无向图赋权图：对一个无向图G G的每一条边的每一条边(v(vi i,v,vj j)，相应地有一个数，相应地有一个数w wijij，则称图，则称图G G为赋权图，为赋权图，w wijij称为边称为边(v(vi i,v,vj j)上的权。上的权。网络：在赋权的有向图网络：在赋权的有向图D D中指定一点，称为发点，指定另一点称中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把为收点，其它点称为中间点，并把D D中的每一条弧的赋权数称为中的每一条弧的赋权数称为弧的容量，弧的容量，D D就称为网络。就称为网络。图与网络的基本概念图与网络的基本概念树是图论中的重要概念，所谓树就是一个无圈的连通图。树是图论中的重要概念，所谓树就是一个无圈的连通图。图图6-116-11中，中，(a)(a)就是一个树，而就是一个树，而(b)(b)因为图中有圈所以就不是树，因为图中有圈所以就不是树，(c)(c)因为因为不连通所以也不是树。不连通所以也不是树。图图6-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)6.2 树图和图的最小部分树6.2 树图和图的最小部分树树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。例6.2 乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。ABCDEFGH运动员树与与图的最小的最小树例6.3 某企业的组织机构图也可用树图表示。厂长厂长人事科人事科财务科财务科总工总工程师程师生产副生产副厂长厂长经营副经营副厂长厂长开发科开发科技术科技术科生产科生产科设备科设备科供应科供应科销售科销售科检验科检验科动力科动力科树与与图的最小的最小树 树：无圈的连通图即为树性质1：任何树中必存在次为1的点。性质2：n 个顶点的树必有n-1 条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。v1v2v3v4v5v6树与与图的最小的最小树 图的最小部分树(支撑树)如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝，一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G2树与与图的最小的最小树a ab bc cf fe ed dh hg gb bf fe ed d树与与图的最小的最小树a ab bc cf fe ed dh hg gb bf fd dg g树与与图的最小的最小树b bc ce ed da ab bc cf fe ed dh hg g树与与图的最小的最小树a ab bc ch ha ab bc cf fe ed dh hg g树与与图的最小的最小树a af fd dg ga ab bc cf fe ed dh hg g树与与图的最小的最小树 求求树树的方法：破圈法和避圈法的方法：破圈法和避圈法破圈法破圈法树与与图的最小的最小树部分树树与与图的最小的最小树避圈法避圈法v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5树与与图的最小的最小树 赋权图赋权图中求最小中求最小树树的方法：破圈法和避圈的方法：破圈法和避圈法法破圈法：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数n-1=5树与与图的最小的最小树v1v2v3v4v5v643521得到最小树：Min C(T)=15避圈法避圈法（KruskalKruskal）思想：思想：在图中在图中取一条最小权的边，取一条最小权的边，以后每一步中，以后每一步中，总总从未被选取的边中选一条权最小的边，并使之 与已选取的边不构成圈（每一步中，如果有两条或两条以上的边都是最小权的边，则从中任选一条）。5v1v2v3v4v5v6843752618树与与图的最小的最小树v1v2v3v4v5v6435215v1v2v3v4v5v6843752618Min C(T)=15树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636练习：练习：应用破圈法求最小树应用破圈法求最小树树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 317174 41 12323min=1+4+9+3+17+23=57树与与图的最小的最小树练习：练习：应用避圈法求最小树应用避圈法求最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636树与与图的最小的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636min=1+4+9+3+17+23=57min=1+4+9+3+17+23=57树与与图的最小的最小树课课堂堂练习练习：3749346321Min C(T)=12Min C(T)=15254173314475答案：树与与图的最小的最小树34122323242Min C(T)=12213638534567454321Min C(T)=186.3 最短路问题如何用最短的线路将三部电话连起来？此问题可抽象为设ABC为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如ABAC）。ABCABCPl但若增加一个周转站（新点P）l连接4点的新网络的最短路线为PAPBPC。最短新路径之长N比原来只连三点的最短路径O要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。最短路最短路问题问题描述：就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路.有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。最短路最短路问题例例6.4 6.4 渡河游渡河游戏戏一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。最短路最短路问题定义：1）人M（Man），狼W（Wolf），羊G（Goat），草H（Hay）2）点 vi 表示河岸的状态3）边 ek 表示由状态 vi 经一次渡河到状态 vj 4）权边 ek 上的权定为 1我们可以得到下面的加权有向图状态说明：v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=(M,W,H);v4,u4=(M,G,H);v5,u5=(M,G)此游戏转化为在下面的二部图中求从 v1 到 u1 的最短路问题。v1v2v3v4v5u5u4u3u2u1求最短路有两种算法:狄克斯屈拉(Dijkstra)标号算法 逐次逼近算法最短路最短路问题 狄克斯屈拉狄克斯屈拉(Dijkstra)(Dijkstra)标标号算法的基本思路：号算法的基本思路：若序列 vs,v1.vn-1,vn 是从vs到vt间的最短路，则序列 vs,v1.vn-1 必为从vs 到vn-1的最短路。假定v1v2 v3 v4是v1 v4的最短路，则v1 v2 v3一定是v1 v3的最短路，v2 v3 v4也一定是v2 v4的最短路。v1v2v3v4v5最短路最短路问题求网络图的最短路，设图的起点是vs,终点是vt ,以vi为起点vj为终点的弧记为(i,j)距离为dijP P标号标号(点标号点标号)：b(j)起点vs到点vj的最短路长；T T标号标号(边标号边标号)：k(i,j)=b(i)+dij，步骤：1.令起点的标号；b(s)0。2.找出所有已标号vi到未标号vj的弧集合 B=(i,j)如果这样的弧不存在或vt已标号则计算结束；3.计算集合B中弧k(i，j)=b(i)+dij的标号4.选一个点标号 在终点vl处标号b(l),返回到第2步。例6.5 求下图v1到v7的最短路长及最短路线86252353421057086225441114751071211v7已标号，计算结束。从v1到v7的最短路长是 11,最短路线：v1 v4 v6 v7P标号T标号已标号点未标号点 （，），（，），（，）0+8 0+6 0+2 （，），（，），（，），（，）0+8 0+6 2+3 2+2 （，）（，）（，）（，）（，）（，）0+8 0+6 2+3 4+3 4+10 4+7 (,)(,)(,)（,)(,)(,)(,)(,)0+8 0+6 5+2 5+10 5+4 4+3 4+10 4+7 12最短路问题最短路问题例例 求下图中求下图中v v1 1到到v v6 6的最短路的最短路v23527531512v1v6v5v3v4（0,s)解：采用解：采用DijkstraDijkstra算法，算法，最短路径为最短路径为v v1 1 v v3 3 v v4 4 v v6 6(3,3)(2,1)(3,1)(8,4)点v5不能标号，说明vs不可达v5最短路最短路问题从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，注：无向图最短路的求法只将上述步骤2将弧改成边即可。因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj。例6.6 求下图v1到各点的最短距离及最短路线。4526178393261216180452231039612641166188122482418所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。课堂练习：1.用Dijkstra算法求下图从v1到v6的最短距离及路线。v3v54v1v2v4v635222421v1到v6的最短路为：最短路最短路问题2.求从v1到v8的最短路径237184566134105275934682最短路最短路问题237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到v8的最短路径为v1v4v7v5v8，最短距离为10最短路最短路问题3.求下图中v1点到另外任意一点的最短路径v1v2v3v4v6v5322762133最短路最短路问题v1V2V3V4 V6V5322762133024714最短路最短路问题v1V2V3V4 V6V5322762133024714最短路最短路问题算法适用条件：Dijkstra算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近算法。例6.7 如右图所示中按dijkstra算法可得P(v1)=5为从vsv1的最短路长显然是错误的，从vsv2v1路长只有3。v2vsv15-58最短路问题的应用：例6.7 电信公司准备准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。v1（甲地）1517624431065v2v7(乙地)v3v4v5v6解：这是一个求无向图的最短路的问题。直接在无向图中用直接在无向图中用DijkstraDijkstra算法来求解。只要在算法中算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。点到未标号的点的边的集合即可。最短路径最短路径v v1 1 v v3 3 v v5 5 v v6 6 v v7 7 V1（甲地）（甲地）1517624431065 v2V7（乙地）（乙地）V5V6 V3 V4（0,s)（10,1)（13,3)（14,3)（16,5)（18,5)（22,6)最短路最短路问题例6.8 设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表年份年份12345年初价格年初价格1111121213最短路最短路问题设备维修费如下表使用年数使用年数0-11-22-33-44-5每年维修费用每年维修费用5681118解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。v1v2v3v4v5v6把所有弧的权数计算如下表，把权数赋到图中，再用Dijkstra算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723 最终得到下图，可知，v1到v6的距离是53，最短路径有两条：v1v3v6和 v1v4v6 V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723 V2（16,1）16(30,1)(53,3)(53,4)邮递员的工作是每天在邮局里选出邮件，然后送到他所管辖的客户中，再返回邮局。自然地，若他要完成当天的投递任务，则他必须要走过他所投递邮件的每一条街道至少一次。问怎样的走法使他的投递总行程为最短？这个问题就称为中国邮中国邮路问题路问题。1、提出问题上图表示从R1-R15个街道交叉点，街道上的数字表示该街道的长度，单位为米。6.4 中国邮路问题 首先把这个实际问题转换成一个非负赋权图G，G的顶点代表街与街之间的交叉路口和终端，两个顶点相邻当且仅当这两点所对应的路口有直通街道而中间不通过其他路口，每条边的权是这条边所对应街道的长度。G的通过每条边至少一次的闭途径称为G G的环游的环游。具有最小权的环游称为G的最优环游最优环游，则中国邮路问题就是要在赋权图G中找一条最优环游。2、分析问题 街道结构图 由上构造右图3、解决问题返回 结束寻找Euler图的最优环游的基本思路：（1）用双倍边方法求 的一个Euler赋权母图 ，使 达到最小。（2）用Fleury算法求得 的Euler环游 ,就是 图 的环游；定理定理（管梅谷，1960）设 是一个连通的赋权图，是 的一个Euler赋权生成母图，则当且仅当 没有重复数大于2的边。并且 的每一个长度至少是3的回路中多重边的权和不超过此回路权和的一半。返回 结束奇偶点图上作业法（求最优环游算法）：奇偶点图上作业法（求最优环游算法）：(1)把 中度为奇数的顶点两两配对，记为 。对每个 ，中取一条 路 ，将 上的每一条边都添加一条边，从而得到 的一个赋权Euler生成母图 。(2)去掉 中关于 的某一对相邻顶点有多于2条边连接它们，则去掉其中的偶数条边，留下1条或2条边连接这两个顶点。直到每一对相邻顶点至多由2条边连接。(4)用Fleury算法求 的Euler环游。(3)检查 的每一个回路，如果某个回路 上多重边 的权和超过此回路权和的一半，则将 进行调整：删除 ，的边重数增加 1。例例1 1 下图(a)给出赋权图 ，是 的四个奇点。根据上述算法,求下图的最优环游。解：根据上述算法(1)，把 和 配对，和 配对，取 ，并对 中每条边各添加一条边；又取 ，并对 中每条 边各添加一条边。得图(b).依次按算法，得到图(c),(d),(e)奇偶点图上作业法缺陷：奇偶点图上作业法缺陷：奇偶点图上作业法需要检查图中的每个回路。随着顶点个数和边数增加，回路个数增加。如下图一，图二。图一回路超过150个，图二回路至少有上千个。思考：如何求恰好有两个奇点的思考：如何求恰好有两个奇点的赋权图的赋权图的最优环游？最优环游？设 恰好有两个奇点 和 ，则可以利用2.2节求出 的一条最短 路 ，在 中只要把 中的每一条边中再添加一条边，加上权就可得Eluer图 。可以证明 的Eluer环游就是 的最优环游。下左图的最优环游即为右图。如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。6.5 网络的最大流网网络的最大流的最大流基本概念：1.1.容量网容量网络络：队网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量容量，简记为cij。容量网络中通常规定一个发发点点(也称源点，记为s)和一个收点收点(也称汇点，记为t)，网络中其他点称为中中间间点点。st48441226792.网络的最大流是指网络中从发点到收点之间允许通过的最大流量。3.流与可行流 流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的负载量记为fij。若fij=0，称为零流。满足以下条件的一组流称为可行流。容量限制条件。容量网络上所有的弧满足：0fijcij 中间点平衡条件。若以v(f)表示网络中从st的流量，则有：网网络的最大流的最大流结论：任何网络上一定存在可行流。（零流即是可行流）网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使v(f)值达到最大。割与割集割是指容量网络中的发点和收点分割开，并使st的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用 表示。左图中，AA将网络上的点分割成 两个集合。stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(3)7(6)AABB现有 ，称弧的集合(v1,v3),(v2,v4)是一个割，且 的流量为18。定理定理1 1 设网络N中一个从 s 到 t 的流 f 的流量为v(f)，(V,V)为任意一个割集，则 v(f)=f(V,V)f(V,V)推论推论1 1 对网络 N中任意流量v(f)和割集(V,V)，有v(f)c(V,V)证明 w=f(V,V)f(V,V)f(V,V)c(V,V)推论推论2 2 最大流量v(f)不大于最小割集的容量，即：v(f)minc(V,V)定理定理2 2 在网络中st的最大流量等于它的最小割集的容量，即：v(f)=c(V,V)增广增广链链在网络的发点和收点之间能找到一条链，在该链上所有指向为st的弧，称为前向弧，记作+,存在f0，则称这样的链为增广链。例如下图中，sv2v1v3v4t。定理定理3 3 网络N中的流f 是最大流当且仅当N中不包含任何增广链stv3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)求网络最大流的标号算法：基本思想基本思想 由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。基本方法基本方法(1)找出第一个可行流，（例如所有弧的流量fij=0。）(2)用标号的方法找一条增广链 首先给发点s标号(),标号中的数字表示允许的最大调整量。选择一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查：如果弧的起点为vi，并且有fij0，则vj标号(fji)(3)重复第(2)步，可能出现两种结局：标号过程中断，t无法标号，说明网络中不存在增广链，目前流量为最大流。同时可以确定最小割集，记已标号的点集为V,未标号的点集合为V,(V,V)为网络的最小割。t得到标号，反向追踪在网络中找到一条从s到t得由标号点及相应的弧连接而成的增广链。继续第(4)步(4)修改流量。设原图可行流为f，令得到网络上一个新的可行流f。(5)擦除图上所有标号，重复(1)-(4)步，直到图中找不到任何增广链，计算结束。网网络的最大流的最大流例6.10 用标号算法求下图中st的最大流量，并找出最小割。stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)解：(1)先给s标号()stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(0，)(2)检查与s点相邻的未标号的点，因fs1cs1，故对v1标号 =min,cs1-fs1=1,(s，1)stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(6)(0，)(s，1)(2)检查与v1点相邻的未标号的点，因f13c13，故对v3标号 =min1,c13-f13=min1,6=1(v1，1)stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(0，)(s，1)(v1，1)(3)检查与v3点相邻的未标号的点，因f3tc3t，故对vt标号=min1,c3t-f3t=min1,1=1(v3，1)找到一条增广链sv1v3t(4)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)(0，)(s，1)(v1，1)(v3，1)(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。stv1v3v2v48(8)9(4)5(5)10(8)6(0)2(0)9(9)5(3)7(5)(0，)(s，1)(v1，1)(v3，1)(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)(0，)(s，2)(2)=min,2=2(v2，2)(1)=min(v2),f12=min2,3=2(3)=min2,5=2(v1，2)(v3，1)(4)=min2,1=1(v4，1)(t)=min1,2=1(6)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)(0，)(s，2)(v2，2)(v1，2)(v3，1)(v4，1)stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)(7)擦除所有标号，重复上述标号过程，寻找另外的增广链。(0，)(s，2)(v2，2)(v1，2)(v3，1)(v4，1)stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)(s，1)(v2，1)(v1，1)(7)擦除所有标号，重复上述标号过程，寻找另外的增广链。(2)=min,1=1(1)=min1,2=1(3)=min1,4=1(0，)例6.9 求下图st的最大流，并找出最小割stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)