运筹学中中的数学问题及模型

《运筹学中中的数学问题及模型》由会员分享，可在线阅读，更多相关《运筹学中中的数学问题及模型（86页珍藏版）》请在金锄头文库上搜索。

1、第一章第一章 运筹学中的几个数学问运筹学中的几个数学问题及模型题及模型 本章主要介绍运筹学中的几个数学问题及模型，即本章主要介绍运筹学中的几个数学问题及模型，即线性规划问题、运输问题、图与网络优化技术等。学习线性规划问题、运输问题、图与网络优化技术等。学习的重点是基本概念。的重点是基本概念。1.线性规划问题及其数学模型问题线性规划问题及其数学模型问题2.运输问题运输问题3.树和最小支撑树问题树和最小支撑树问题4.最短路径问题最短路径问题5.网络最大流问题网络最大流问题6.最小费用最大流问题最小费用最大流问题7.中国邮递员问题中国邮递员问题8. NP-完备性完备性2021/6/71数学预备知识：

2、矩阵的基本概念及初等运算数学预备知识：矩阵的基本概念及初等运算参考文献参考文献1.1.运筹学教材编写组编，运筹学，清华大运筹学教材编写组编，运筹学，清华大学出版社，学出版社，20052005年年6 6月第月第3 3版版2. 2. 田丰、马仲番编著，图与网络流理论，科学出版田丰、马仲番编著，图与网络流理论，科学出版社，社，19871987年年3. 3. 刘振宏、刘振宏、 蔡茂城蔡茂城( (译译) )，组合最优化：算法和，组合最优化：算法和复杂性，清华大学出版社复杂性，清华大学出版社,1988 ,1988 年第年第1 1版版4. 4. C.H. Papadimitriou and K. Steig

3、litz, Combinatorial Optimization: Algorithms and Complexity, Printice-Hall, 19822021/6/72 运筹学的性质和特点运筹学的性质和特点 运筹学是一门应用科学，至今还没有统一且确运筹学是一门应用科学，至今还没有统一且确切的定义。在此提出以下几个定义来说明运筹学的切的定义。在此提出以下几个定义来说明运筹学的性质和特点：性质和特点： 定义定义1: 为决策机构在对其控制下的业务活动进为决策机构在对其控制下的业务活动进行决策时行决策时, 提供以数量化为依据的科学方法提供以数量化为依据的科学方法. 特点特点1: 该定义强调的

4、是科学方法该定义强调的是科学方法,以定量化为基以定量化为基础础,利用数学工具利用数学工具.但任何决策都包含定量和定性两个但任何决策都包含定量和定性两个方面方面,而定性方面又不能简单地用数学表示而定性方面又不能简单地用数学表示,如政治、如政治、社会等因素，只有综合多种因素的决策才是全面的。社会等因素，只有综合多种因素的决策才是全面的。运筹学工作者的职责是为决策者提供可以量化方面运筹学工作者的职责是为决策者提供可以量化方面的分析，并指出那些是定性因素。的分析，并指出那些是定性因素。2021/6/73 定义定义2：运筹学是一门应用科学，它广泛应用现：运筹学是一门应用科学，它广泛应用现有的科学技术知识

5、和数学方法，解决实际中提出的有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。专门问题，为决策者选择最优决策提供定量依据。 特点特点2：该定义表明运筹学具有多学科交叉的特：该定义表明运筹学具有多学科交叉的特点，如综合应用经济学、心理学、物理学和化学中点，如综合应用经济学、心理学、物理学和化学中的一些方法。的一些方法。 特点特点3：由系统的观点研究功能关系。：由系统的观点研究功能关系。 综上所述，运筹学的定义可以提炼为：综上所述，运筹学的定义可以提炼为： 定义定义3：运筹学就是利用计划的方法和多学科专：运筹学就是利用计划的方法和多学科专家组成的队伍，把复杂的

6、功能关系表示成数学模型家组成的队伍，把复杂的功能关系表示成数学模型，其目的是通过定量分析为决策和揭露新问题提供，其目的是通过定量分析为决策和揭露新问题提供数量依据。数量依据。2021/6/74运筹学与计算机运筹学与计算机 计算机是运筹学发展的基本因素，对任何实际问计算机是运筹学发展的基本因素，对任何实际问题，没有现代计算机用来产生最终结果，大多数运筹题，没有现代计算机用来产生最终结果，大多数运筹学技术是完全不能实现的。许多大规模运筹技术的应学技术是完全不能实现的。许多大规模运筹技术的应用只需计算机几分钟的时间，而用人工则需要很长时用只需计算机几分钟的时间，而用人工则需要很长时间。更为重要的是计

7、算机能快速利用某些类型的管理间。更为重要的是计算机能快速利用某些类型的管理信息，而没有这些信息，许多运筹设计是没有意义。信息，而没有这些信息，许多运筹设计是没有意义。 计算机是运筹学不可分割的部分和不可缺少的工计算机是运筹学不可分割的部分和不可缺少的工具，而且计算机方法和运筹学方法是并行发展的。预具，而且计算机方法和运筹学方法是并行发展的。预计今后运筹学和计算机方法的分界线将会消失，并将计今后运筹学和计算机方法的分界线将会消失，并将组成更通用、更广泛的管理科学的形式。组成更通用、更广泛的管理科学的形式。2021/6/75运筹学的工作步骤运筹学的工作步骤1. 提出和形成问题：要弄清问题的目标，可

8、能的约束，提出和形成问题：要弄清问题的目标，可能的约束，问题的可控变量以及有关参数。问题的可控变量以及有关参数。2. 建立模型：把问题中可控变量、参数和目标与约束之建立模型：把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来。间的关系用一定的模型表示出来。3. 求解：用数学方法将模型求解。解可以是最优解、次求解：用数学方法将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机优解、满意解。复杂模型的求解需用计算机,解的精度解的精度要求由决策者提出。要求由决策者提出。4. 解的检验：先检验求解步骤和程序有无错误，然后检解的检验：先检验求解步骤和程序有无错误，然后检查解

9、是否反映现实问题。查解是否反映现实问题。5. 解的控制：通过控制解的变化过程决定对解是否要作解的控制：通过控制解的变化过程决定对解是否要作一定的修改。一定的修改。6. 解的实施：将解用到实际中去，必须考虑到实际的问解的实施：将解用到实际中去，必须考虑到实际的问题，如向实际部门讲清楚解的用法，在实施中可能产题，如向实际部门讲清楚解的用法，在实施中可能产生的问题等。生的问题等。 以上过程应反复进行。以上过程应反复进行。2021/6/761.线性规划问题及其数学模型问题 例例1：某工厂在计划期内安排生产：某工厂在计划期内安排生产、两两种产品，已知生产单位产品所需的设备台种产品，已知生产单位产品所需的

10、设备台时、时、A、B两种原材料的消耗及两种产品每两种原材料的消耗及两种产品每件可获利润见如下表件可获利润见如下表1-1所示：问如何安所示：问如何安排计划使该工厂获利最多？排计划使该工厂获利最多？2021/6/77表表1111产品产品I产品产品II 资源总量资源总量 设设 备备 1台时台时 2台时台时 8 台时台时 原材料原材料A 4公斤公斤 0公斤公斤 16公斤公斤 原材料原材料B 0公斤公斤 4公斤公斤 12公斤公斤 利利 润润 2元元/件件 3元元/件件2021/6/78解：假设解：假设 x1、x2分别表示在计划期内生产产品分别表示在计划期内生产产品I、II的数量，则该计划问题可用如下数学

11、模型表的数量，则该计划问题可用如下数学模型表示为：示为： 目标函数目标函数 Max Z = 2x1 +3x2 约束条件约束条件其最优解为其最优解为x1=4, x2=2, 最优值为最优值为z=14。2021/6/79例例2:（营养问题）某养鸡场所用的混合饲料是由营养问题）某养鸡场所用的混合饲料是由 n 种配料组成。要求这种混合饲料必须含有种配料组成。要求这种混合饲料必须含有 m 种不同的营养成份，而且要求每单位混合饲料种不同的营养成份，而且要求每单位混合饲料中第中第i种营养成份的含量不能低于种营养成份的含量不能低于bi(i= 1,2,m）。已知第。已知第i种营养成份在每单位的第种营养成份在每单位

12、的第 j 种配料中种配料中的含量为的含量为 aij , j = 1,2, , n，每单位的第，每单位的第 j 种配种配料的价格为料的价格为 cj 。现在要求在保证营养条件的前。现在要求在保证营养条件的前提下，应采用何种配方，使混合饲料的成本最提下，应采用何种配方，使混合饲料的成本最小。小。2021/6/710解：设解：设 xj 表示在单位混合饲料中，第表示在单位混合饲料中，第 j 种配料种配料的含量（的含量（j = 1,2, , n）, 则有如下的数学模型：则有如下的数学模型： Min Z = c1x1 + c2x2 + + cnxn 2021/6/711 以上两个例子，从数学上来讲以上两个例

13、子，从数学上来讲,它们的共同它们的共同特征是特征是:(1) 每个问题都用一组决策变量每个问题都用一组决策变量(x1 , x2 , , xn)表表示某一方案示某一方案 ,这组未知数的值就代表一个具体这组未知数的值就代表一个具体的方案的方案,通常要求这些未知数取值是非负的。通常要求这些未知数取值是非负的。(2) 存在一定的限制条件存在一定的限制条件(称为约束条件称为约束条件)，这些条，这些条 件都可以用关于决策变量的一组线性等式或件都可以用关于决策变量的一组线性等式或 不等式来表示。不等式来表示。 (3) 都有一个目标要求都有一个目标要求,并且这个目标可表示为这并且这个目标可表示为这 组决策变量的

14、线性函数组决策变量的线性函数(称为目标函数称为目标函数),按研按研 究问题的不同，要求目标函数实现最大化或究问题的不同，要求目标函数实现最大化或 最小化。最小化。2021/6/712 满足以上三个条件的数学模型称为线性规划满足以上三个条件的数学模型称为线性规划数学模型。其一般形式为数学模型。其一般形式为(1.1)和和(1.2)形式。形式。 在该模型中，方程在该模型中，方程(1.1)称为目标函数，称为目标函数， (1.2)称为约束条件。称为约束条件。2021/6/713线性规划问题的解法线性规划问题的解法1. 对于简单的线性规划问题对于简单的线性规划问题(只有两个决策变量只有两个决策变量或等价于

15、两个决策变量的线性规划问题或等价于两个决策变量的线性规划问题)，我，我们通过图解法可以对它进行求解。们通过图解法可以对它进行求解。2. 图解法虽然有直观、简便等优点图解法虽然有直观、简便等优点,但是在变量但是在变量个数较多（如大于等于个数较多（如大于等于3）时，一般就无能为）时，一般就无能为力了。美国数学家丹捷格（力了。美国数学家丹捷格（G.B.Dantzig）提）提出了求解线性规划问题的方法：单纯形算法出了求解线性规划问题的方法：单纯形算法 （一种代数的方法）。（一种代数的方法）。2021/6/714例例3. 求解线性规划求解线性规划 min z=x1+2x2+x3-x4 s.t. 2x1+

16、4x2+x3+x4 = 6 2x1 +x4+x5 = 3 x1-x2 +x5 = 1 x1, x2, x3, x4, x5 0解：对原问题进行初等变换，得到解：对原问题进行初等变换，得到2021/6/715 min z=x1+2x2+x3-x4 s.t. x1+3x2+x3 = 4 x1+x2 +x4 = 2 x1-x2 +x5 = 1 x1, x2, x3, x4, x5 0 即即 min z=2 + x1 s.t. x1+3x2 4 x1+x2 2 x1-x2 1 x1, x2 0 然后用图解法求解。求出然后用图解法求解。求出x1，x2最优解后，最优解后，再求出再求出x3, x4, x5

17、，就得到了原问题的最优解。，就得到了原问题的最优解。2021/6/716线性规划问题的标准型线性规划问题的标准型 这里我们假设这里我们假设 bi 0 , i = 1,2,m, 否则两端否则两端同时乘以同时乘以“-1”。用矩阵向量描述就是：。用矩阵向量描述就是：2021/6/717其中：其中：c = ( c1, c2, , cn )T ，X = ( x1, x2, , xn )T ，b = ( b1, b2, , bm )T , A = ( P1, P2, , Pn ) ，Pj = ( a1j, a2j, , amj )T ，0 = ( 0, 0, , 0 )T , ( j = 1, 2, ,

18、n ) 。 我们称我们称 A 为约束方程组的系数矩阵为约束方程组的系数矩阵( mn阶阶),一般情况下一般情况下 m n , m 和和n 为正整数为正整数,分别表示分别表示约束条件的个数和决策变量的个数约束条件的个数和决策变量的个数, C 为价值向为价值向量量, X 为决策向量为决策向量, 通常通常aij , bi , cj为已知常数，这为已知常数，这里里 i = 1, 2, , m , j = 1, 2, , n。2021/6/718对偶问题的提出对偶问题的提出 我们将简单叙述对偶线性规划。这里的对偶我们将简单叙述对偶线性规划。这里的对偶是指对同以事物（或问题）从不同的角度观察，是指对同以事物

19、（或问题）从不同的角度观察，有两种不同的表述。有两种不同的表述。例如：例如：“平面中矩形的面积与周长的关系平面中矩形的面积与周长的关系”有下面有下面两种表述两种表述 周长一定时，面积最大的矩形式正方形；周长一定时，面积最大的矩形式正方形； 面积一定时，周长最小的矩形式正方形。面积一定时，周长最小的矩形式正方形。2021/6/719 在前面例在前面例1中，我们讨论了工厂生产计划模中，我们讨论了工厂生产计划模型及其解法，现从另一个角度来讨论这个问题型及其解法，现从另一个角度来讨论这个问题。 假设该工厂的决策者决定不生产产品假设该工厂的决策者决定不生产产品I、II，而将其所有资源出租或出售。这时，工

20、厂的决而将其所有资源出租或出售。这时，工厂的决策者就要考虑给每种资源进行定价的问题。策者就要考虑给每种资源进行定价的问题。 设用设用 y1、 y2、 y3 分别表示出租单位设备台分别表示出租单位设备台时的租金和出让单位原材料时的租金和出让单位原材料 A、B 的附加费。的附加费。2021/6/720 作决策时，需要如下的比较：若一个单位作决策时，需要如下的比较：若一个单位设备台时和四个单位原材料设备台时和四个单位原材料 A可以生产一件产可以生产一件产品品I，可获利，可获利2元，那么生产每件产品元，那么生产每件产品I的设备台的设备台时和原材料出租和出让的所有收入应不低于生时和原材料出租和出让的所有

21、收入应不低于生产一件产品产一件产品I的利润。这就有：的利润。这就有： y1 + 4y2 2 ； 对于产品对于产品II同理有：同理有： 2 y2 + 4y3 3； 把工厂所有设备台时和资源都出租和出让把工厂所有设备台时和资源都出租和出让，其收入应为：，其收入应为：w = 8y1 + 16y2 + 12y3 。2021/6/721 从工厂的决策者来看，当然希望从工厂的决策者来看，当然希望 w 的值越大的值越大越好；但从接受者的角度来看，他支付的越少越越好；但从接受者的角度来看，他支付的越少越好。所以工厂决策者只能在满足好。所以工厂决策者只能在满足 所有产品的单所有产品的单位利润条件下，使其总收入尽

22、可能地小，才能实位利润条件下，使其总收入尽可能地小，才能实现工厂决策者的意愿。为此需要解如下的线性规现工厂决策者的意愿。为此需要解如下的线性规划问题：划问题： 我们称这个线性规划问题为例我们称这个线性规划问题为例1线性规划问线性规划问题（称之为原问题）的对偶问题。题（称之为原问题）的对偶问题。2021/6/722 根据上述例题可见，对于形如如下形式的线性规根据上述例题可见，对于形如如下形式的线性规划问题：划问题：我们可以马上得出我们可以马上得出它的对偶问题：它的对偶问题： 从以上的线性规划问题和其对偶问题中，我们从以上的线性规划问题和其对偶问题中，我们可以得出：原问题的约束条件的个数可以得出：

23、原问题的约束条件的个数 m 就是对偶问就是对偶问题的变量的个数；原问题的变量的个数题的变量的个数；原问题的变量的个数 n 就是对偶就是对偶问题的约束条件的个数；若原问题的目标函数是问题的约束条件的个数；若原问题的目标函数是 Max 型，则对偶问题的目标函数必是型，则对偶问题的目标函数必是 Min 型。它们型。它们二者的最优目标函数值相等。二者的最优目标函数值相等。2021/6/723例例4 4 某工厂拟用用集装箱托运甲乙两种货物，每某工厂拟用用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润及托运所受限制如箱的体积、重量、可获利润及托运所受限制如下表所示。问两种货物各托运多少，可使获得下表所

24、示。问两种货物各托运多少，可使获得利润最大？利润最大？ 表表1-21-2货物货物体积体积（米（米3/箱）箱）重量（百公斤重量（百公斤/箱）箱）利润利润（百元（百元/箱）箱）甲甲5220乙乙4510托运限制托运限制24米米313百公斤百公斤2021/6/724解：设解：设x1、x2分别为甲、乙两种货物的托运箱分别为甲、乙两种货物的托运箱数，则得到整数线性规划：数，则得到整数线性规划： Max Z=20x1+10x2 5x1+4x2 24 2x1+5x2 13 x1, x2 0 x1,x2 为整数为整数 解决此整数线性规划的松驰线性规划，解决此整数线性规划的松驰线性规划，得到得到x1=4.8, x

25、2=0, 目标值为目标值为Z=96。（用图象。（用图象法来说明）但是整数最优解为法来说明）但是整数最优解为x1=4, x2=1, 目目标值为标值为Z*=90。2021/6/7252 2.运输问题运输问题例例1：(运输问题）假设有运输问题）假设有 m 个生产地点个生产地点,可以可以供应某种物资供应某种物资(以后称为产地以后称为产地)，用，用 Ai 表示，表示，i = 1,2, ,m；有；有 n 个销售地，用个销售地，用 Bj 表示，表示，j = 1,2, ,n；产地的产量和销售地的销售量分别；产地的产量和销售地的销售量分别为为 ai 和和 bj , i = 1,2, ,m, j = 1,2, ,

26、n，从，从 Ai 到到 Bj 运输单位物资的运价为运输单位物资的运价为 cij ，这些数据可汇，这些数据可汇总于如总于如下表下表2-1。2021/6/726在假设产销平衡的条件下，即在假设产销平衡的条件下，即要求得总运费最小的调运方案。要求得总运费最小的调运方案。 表表2-1 2-1 产销平衡表与单位运价表产销平衡表与单位运价表 销地销地产地产地 B1 B2 Bn 产量产量 A1 c11 c12 c1n a1 A2 c21 c22 c2n a2 . . . . . . Am cm1 cm2 cmn am 销量销量 b1 b2 bn2021/6/727解解:假设假设 xij 表示从表示从 Ai

27、到到 Bj 的运量的运量,则所求的数学则所求的数学模型为模型为: 2021/6/728指派问题的数学模型指派问题的数学模型 在生活中经常会遇到这样的问题，如某单在生活中经常会遇到这样的问题，如某单位需要指派位需要指派 n 个人去完成个人去完成 n 项任务，每个人只项任务，每个人只做一项工作，同时，每项工作只由一个人完成做一项工作，同时，每项工作只由一个人完成。由于各人的专长不同，每个人完成各项任务。由于各人的专长不同，每个人完成各项任务的效率也不同。于是产生了应指派哪一个人去的效率也不同。于是产生了应指派哪一个人去完成哪一项任务，使完成完成哪一项任务，使完成 n 项任务的总效率最项任务的总效率

28、最高（如所用的时间为最少）。我们把这类问题高（如所用的时间为最少）。我们把这类问题称之为指派问题或分派问题（称之为指派问题或分派问题（Assignment Problem）。）。2021/6/729例例2 :有一份中文说明书有一份中文说明书,需要译成英、日、德、需要译成英、日、德、俄四俄四 种文字，分别记作种文字，分别记作 E、J、G、R 。现有。现有甲、乙、丙、丁四人，他们将中文说明书翻译甲、乙、丙、丁四人，他们将中文说明书翻译成不同文字说明书所成不同文字说明书所 需要的时间如表需要的时间如表2-2所示。所示。问应指派何人去完成哪一项工作，使所需的总问应指派何人去完成哪一项工作，使所需的总时

29、间最少？时间最少？2021/6/730表表2-2 任务任务人员人员EJGR甲甲215134乙乙1041415丙丙9141613丁丁781192021/6/731 类似的有：类似的有：n 项加工任务，怎样指派到项加工任务，怎样指派到 n 台机台机床上分别完成的问题；床上分别完成的问题；n 条航线，怎样指定条航线，怎样指定 n 艘船艘船去航行的问题，等等。对应每个指派问题去航行的问题，等等。对应每个指派问题, 都有类都有类似表似表2-1那样的表格，我们称之为效率矩阵或系数矩那样的表格，我们称之为效率矩阵或系数矩阵，某元素阵，某元素 cij (i,j = 1,2, n ) 表示指派第表示指派第 i

30、个人去个人去完成第完成第j项任务时的效率项任务时的效率(或时间、成本等或时间、成本等)。解题时。解题时需要引入变量需要引入变量 xij ,其取值只能是其取值只能是 1 或或 0，并令，并令 ：2021/6/732 当问题是要求极小化时的数学模型是：当问题是要求极小化时的数学模型是：2021/6/733 指派问题的解矩阵应当是每行或每列只能有指派问题的解矩阵应当是每行或每列只能有一个元素为一个元素为1、其余均为、其余均为 0 的的 n 阶方阵。如下就阶方阵。如下就是例是例 2 的一个解矩阵：的一个解矩阵： 指派问题是指派问题是0-1规划的特例，也是运输问题规划的特例，也是运输问题的特例；即的特例

31、；即 m = n ，ai = bj = 1。我们利用指派问。我们利用指派问题的特点可以有更为简便的题的特点可以有更为简便的匈牙利算法匈牙利算法。2021/6/734 以上讨论仅限于求极小化目标的指派问题。以上讨论仅限于求极小化目标的指派问题。对于求极大化的问题，只要经如下变换，仍可利对于求极大化的问题，只要经如下变换，仍可利用匈牙利算法进行求解。用匈牙利算法进行求解。2021/6/7353. 3. 树和最小支撑树树和最小支撑树3.1图的基本概念图的基本概念 定义定义3.1 图论中的图是由点及点与点之间的图论中的图是由点及点与点之间的线所组成的。我们把点与点之间不带箭头的线线所组成的。我们把点与

32、点之间不带箭头的线称为边，带箭头的线称为弧。称为边，带箭头的线称为弧。 定义定义3.2 如果一个图是由点和边所构成的，如果一个图是由点和边所构成的，那么，称它为无向图，记作那么，称它为无向图，记作G =(V，E)，V表示表示图图G的点集合，的点集合，E表示图表示图G的边集合。连接点的边集合。连接点vi,vj V的边记为的边记为vivj或或vjvi。2021/6/736 定义定义3.3如果一个图是由点和弧所构成的，如果一个图是由点和弧所构成的，称它为有向图，记作称它为有向图，记作D =(V,A)，其中，其中V 表示有向表示有向图图D的点集合，的点集合，A表示有向图表示有向图D的弧集合。一条方的弧

33、集合。一条方向从向从vi指向指向vj的弧，记作的弧，记作(vi,vj)。 如果边如果边vivjE，称称vi,vj是边的端点，或者是边的端点，或者vi,vj是相邻的。如果一个图是相邻的。如果一个图G中，一条边的两个端点中，一条边的两个端点是相同的是相同的,那么称为这条边是环。如果两个端点那么称为这条边是环。如果两个端点之间有两条以上的边，那么称它们为多重边。之间有两条以上的边，那么称它们为多重边。 一个无环、无多重边的图标为简单图。一个无环、无多重边的图标为简单图。 一个无环，有多重边的图标图称为多重图。一个无环，有多重边的图标图称为多重图。2021/6/737 端点的度端点的度 d(v)：点：

34、点 v 作为边端点的个数；作为边端点的个数； 奇度点奇度点v：d(v)=奇数；奇数； 偶度点偶度点v：d(v)=偶数；偶数； 类似地，可以定义有向图中的出度类似地，可以定义有向图中的出度d+(v) 、入度入度d-(v)等。等。 定理定理 3.1（握手定理）所有顶点次数之和（握手定理）所有顶点次数之和等于所有边数的等于所有边数的2倍。倍。 定理定理 3.2 在任一图中，奇点的个数必为偶在任一图中，奇点的个数必为偶数。数。2021/6/7383.2 图的连通性图的连通性 定义定义3.4（路）：给定一个图（路）：给定一个图G=(V,E)，一个，一个点、边交错的由序列点、边交错的由序列P=(v0 ,e

35、1 ,v1 , e2 , v2 ，e3 , v3 , , vk-1,ek,vk), 如果满足如果满足ei=vi-1vi, i=1,2,k,则称则称P为一条联结为一条联结v0和和 vk，记为，记为P=v0 v1v2v3vk-1vk；称；称v0 ，vk分别为分别为路路的起点和终点的起点和终点,其余为中间点。其余为中间点。 特别，当路的起点和终点相同时，称该路为特别，当路的起点和终点相同时，称该路为圈或回路。圈或回路。 定义定义3.5（连通图连通图）：）：图中任意两点之间均图中任意两点之间均至少有一条路，否则称之为不连通图。至少有一条路，否则称之为不连通图。2021/6/7393.3 子图与支撑子图

36、子图与支撑子图 设有图设有图G1=（V1,E1）和）和G2=（V2 ,E2） 定义定义3.6（子图）：如果（子图）：如果 V2 V1 , E2 E1，且且E2中每条边的两个端点均属于中每条边的两个端点均属于V2，称，称 G2 是是 G1 的子图。的子图。 定义定义3.7（支撑子图）：如果（支撑子图）：如果 V2 = V1 , E2 E1 ， 称称 G2 是是 G1 的支撑子图（或生成子图）。的支撑子图（或生成子图）。 定义定义3.8（导出子图）：（导出子图）： 如果如果V2 V1, E2=vi,vj vi,vj V2,称称 G2 是是 G1 中由中由V2 导出导出的的导出子图。导出子图。202

37、1/6/7403.4 树及其性质树及其性质 定义定义3.9：一个无圈的连通图称为树。：一个无圈的连通图称为树。 树有一些重要性质：树有一些重要性质： 定理定理3.3 设图设图G=（V，E）是一个树，其顶点）是一个树，其顶点数数2，那么图，那么图G中至少有两个度为中至少有两个度为1的顶点。的顶点。 定理定理3.4 图图G=（V，E）是一个树的充要条件）是一个树的充要条件是是G不含圈，并且有且仅有不含圈，并且有且仅有n-1条边。条边。 定理定理3.5 图图G=（V，E）是一个树的充要条件）是一个树的充要条件是是G是连通图，并且有且仅有是连通图，并且有且仅有n-1条边。条边。 定理定理3.6 图图G

38、是一个树的充分必要条件是任意是一个树的充分必要条件是任意两个顶点之间有且仅有一条路。两个顶点之间有且仅有一条路。2021/6/741 从以上定理，不难得出以下结论：从以上定理，不难得出以下结论： （1）从一个树中任意去掉一条边，那么剩下）从一个树中任意去掉一条边，那么剩下的图不是连通图，亦即，在点集合相同的图中的图不是连通图，亦即，在点集合相同的图中，树是含边数最少的连通图。，树是含边数最少的连通图。 （2）在树中不相邻的两个点之间加上一条边）在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。，那么恰好得到一个圈。2021/6/7423.5 最小支撑树模型最小支撑树模型 定义定义3.10

39、（支撑树）：设图（支撑树）：设图T=(V,E)是图是图G=(V,E)的一支撑子图的一支撑子图,如果图如果图T=(V,E)是一个树是一个树,那么称那么称T是是G的一棵支撑树。的一棵支撑树。 定理定理3.7 一个图一个图G有支撑树有支撑树T的充要条件是的充要条件是G是连通图。是连通图。 问题问题3.1 给定一个图给定一个图G，如何求图，如何求图G的一棵的一棵支撑树？支撑树？ 问题问题3.2 给定一个图给定一个图G，如何判断图，如何判断图G是连是连通的？通的？2021/6/743 反圈算法求解支撑树：反圈算法求解支撑树： 设设G=(V,E)为一个图为一个图,取取X0=u1,u1为为V中的中的任意一点

40、任意一点,E0=. 若已知有若已知有Xk及及Ek(k0)，(Xk)为为Xk的反圈的反圈集合集合,在在(Xk)中选取一条或多条边中选取一条或多条边,使得所选使得所选边在边在V-Xk中具有不同的端点中具有不同的端点,记所选边的集合记所选边的集合为为Fk,所选顶点的集合为所选顶点的集合为Yk,取取Xk+1=XkYk, Ek+1=EkFk. 当当Xk=V时时,停止停止,有支撑树有支撑树(V,Ek)；在某步，在某步，当当 ，但，但 ，表明，表明G是不连通是不连通的，没有支撑树。的，没有支撑树。2021/6/744 利用反圈法来求一些优化问题的步骤：利用反圈法来求一些优化问题的步骤： 取取 (下面已存在下

41、面已存在 )，按下面方式构造，按下面方式构造 。在。在 中，按所中，按所需条件选边，使得所选边在需条件选边，使得所选边在 中具有不同端中具有不同端点，记这些边组成集合点，记这些边组成集合 ，这些被选端点为，这些被选端点为 。取。取 ，重，重复上述过程或停止。复上述过程或停止。 该算法有三个因素要确定：（该算法有三个因素要确定：（1）初值；（）初值；（2）选边条件；（选边条件；（3）算法停止条件。）算法停止条件。2021/6/745 定义定义3.11（赋权图）：如果图（赋权图）：如果图G =（V，E），对于，对于G中的每一条边中的每一条边vivj，相应地有一个数，相应地有一个数wij，那么称这样

42、的图那么称这样的图G为赋权图，为赋权图，wij称为边称为边vivj的权。的权。这里所指的权，是具有广义的数量值。根据实际这里所指的权，是具有广义的数量值。根据实际研究问题的不同，可以具有不同的含义。例如长研究问题的不同，可以具有不同的含义。例如长度，费用、流量等等。度，费用、流量等等。 赋权图在图论及实际应用方面有着重要的地赋权图在图论及实际应用方面有着重要的地位，被广泛应用于现代科学管理和工程技术等领位，被广泛应用于现代科学管理和工程技术等领域，最小支撑树问题就是赋权图的最优化问题之域，最小支撑树问题就是赋权图的最优化问题之一。一。2021/6/746 定义定义3.12 如果图如果图T =（

43、V，E）是图是图G 的一的一个支撑树，那么称个支撑树，那么称E中所有边的权重之和为支中所有边的权重之和为支撑树撑树T 的权重，记作的权重，记作w(T)。如果图。如果图G 的支撑树的支撑树T* 的权重的权重w(T*)在在G的所有支撑树的所有支撑树T中的权重达到最中的权重达到最小，即小，即w(T*) = min w(T) ，那么称，那么称T*是是G 的一棵的一棵最小支撑树。最小支撑树。 在已知的几个城市之间联结电话线网，要在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，这个问题的求总长度最短和总建设费用最少，这个问题的解决可以归结为最小支撑树问题。城市间交通解决可以归结为最小支撑

44、树问题。城市间交通线的建造等，都可以归结为这一类问题。线的建造等，都可以归结为这一类问题。2021/6/747 常用的方法有破圈法、生长法（避常用的方法有破圈法、生长法（避圈法）和反圈法三种方法：圈法）和反圈法三种方法：1. 破圈法破圈法 在图中寻找一个圈。若不存在圈，在图中寻找一个圈。若不存在圈，则已经得到最短树或该图不存在最短树；则已经得到最短树或该图不存在最短树； 去掉该圈中权数最大的边；去掉该圈中权数最大的边； 反复重复反复重复 两步，直到最小支撑树两步，直到最小支撑树或判断图或判断图G不是连通图。不是连通图。2021/6/7482.避圈法避圈法 从图中依次寻找权数较小的边，寻找过程从

45、图中依次寻找权数较小的边，寻找过程中，节点不得重复，即不得构成圈。注意在找中，节点不得重复，即不得构成圈。注意在找较小权数边时不考虑已选过的边和可能造成圈较小权数边时不考虑已选过的边和可能造成圈的边。如此反复进行，直到得到最小支撑树或的边。如此反复进行，直到得到最小支撑树或证明图不存在最小支撑树。证明图不存在最小支撑树。2021/6/7493.反圈法反圈法 设设G=(V,E)为一个图为一个图,取取X(0)=u1,u1为为V中中的任意一点的任意一点,E(0)=. 若已知有若已知有X(k)及及E(k)(k0)，(X(k)为为X(k)的的反圈集合反圈集合,在在(X(k)中选取一条权重最小的边中选取一

46、条权重最小的边,记记所选边的集合为所选边的集合为F(k),所选顶点的集合为所选顶点的集合为Y(k),取取X(k+1)=X(k)Y(k), E(k+1)=E(k)F(k). 当当X(k)=V时时,停止停止,有最小支撑树有最小支撑树(V,E(k)；在在某步，当某步，当 ，但，但 ，表明，表明G是不连通是不连通的，没有支撑树，则没有的，没有支撑树，则没有最小支撑树最小支撑树。2021/6/7504.4.最短路径问题最短路径问题 一般意义下的最短路问题：设一个赋权有一般意义下的最短路问题：设一个赋权有向图向图D=（V，A），对于每一个弧），对于每一个弧a=（vi,vj），），相应地有一个权相应地有一个

47、权wij。vs,vt是是D中的两个顶点，中的两个顶点，P是是D中从中从vs到到vt的任意一条路，定义路的权是的任意一条路，定义路的权是P中所中所有弧的权重之和，记作有弧的权重之和，记作w(P)。 最短路问题就是要在所有从最短路问题就是要在所有从vs到到vt的路中，的路中，寻找一个权重最小的路寻找一个权重最小的路P0，亦即，亦即w(P0)=minw(P)。P0叫做从叫做从vs到到vt的最短路。的最短路。P0的权重的权重w(P0)称为从称为从vs到到vt的距离，记作的距离，记作d（vs，vt）。由于）。由于D是有向是有向图，显然图，显然d（vs，vt）与）与d（vt，vs）一般不相等。）一般不相等

48、。2021/6/751 反圈算法反圈算法 利用反圈法来求利用反圈法来求vs到到vt的最短路：的最短路：（1）初值：）初值： ，给，给vs一个标号一个标号 ( 从从vs到到v的距离，从的距离，从vs到到v的最短长度）的最短长度）（2）选边条件：在）选边条件：在 中选边中选边e=uv，满足：满足： 达到最小达到最小, i.e. 取取2021/6/752 (3) 停止条件：当停止条件：当 ，则存在从，则存在从vs到到vt的的最短路，其长度为最短路，其长度为 当当 ，但，但 ，说明从，说明从vs到到vt没有路，当然亦无最短路。没有路，当然亦无最短路。（当（当 时，说明存在时，说明存在vs到所有点的最短

49、到所有点的最短路路;当当 ，但，但 ，说明图，说明图G是不连通的。）是不连通的。） 2021/6/753 最短路径问题还有其他算法：最短路径问题还有其他算法：1. Dijkstra算法算法2. Bell-Ford算法算法3. Floyd-Warshall算法算法2021/6/7545.5.网络最大流问题网络最大流问题 定义定义5.1 设一个赋权有向图设一个赋权有向图D =（V,A）,在在V中指定一个发点中指定一个发点vs和一个收点和一个收点vt,其他的点称其他的点称为中间点。对于为中间点。对于D中的每一个弧（中的每一个弧（vi,vj）A,都都有一个权有一个权cij称为弧的容量。我们把这样的图称

50、为弧的容量。我们把这样的图D 称为一个网络系统，简称网络，记做称为一个网络系统，简称网络，记做D =（V，A;c）。）。 网络网络D上的流，是指定义在弧集合上的流，是指定义在弧集合A上的上的一个函数一个函数f=f(vi,vj)=fij, fij =f(vi,vj)称为弧称为弧(vi,vj)上的流量。上的流量。2021/6/755 网络系统上流的特点：网络系统上流的特点：(1)发点的总流出量和收点的总流入量必相等；发点的总流出量和收点的总流入量必相等；(2)每每一一个个中中间间点点的的流流入入量量与与流流出出量量的的代代数数和和等于零；等于零；(3)每每一一个个弧弧上上的的流流量量不不能能超超过

51、过它它的的最最大大通通过过能力（即容量）。能力（即容量）。 对于不满足上述条件的网络暂时不考虑。对于不满足上述条件的网络暂时不考虑。2021/6/756 定义定义5.2 网络上的一个流网络上的一个流 f 叫做可行流，如叫做可行流，如果果 f 满足以下条件满足以下条件 （1）容量条件：对于每一个弧（）容量条件：对于每一个弧（vi,vj）A,有有 0 fij cij. （2）平衡条件：）平衡条件： 对于发点对于发点vs，有，有fsj-fjs=v(f) 对于收点对于收点vt，有，有ftj-fjt=-v(f) 对于中间点，有对于中间点，有fij-fji=0 其中发点的总流量（或收点的总流量）其中发点的

52、总流量（或收点的总流量）v(f)称称 为这个可行流为这个可行流f的流量。的流量。2021/6/757 任意一个网络上的可行流总是存在的。例任意一个网络上的可行流总是存在的。例如零流如零流v(f)=0,就是满足以上条件的可行流。就是满足以上条件的可行流。 网络系统中最大流问题就是在给定的网络网络系统中最大流问题就是在给定的网络上寻求一个可行流上寻求一个可行流f，其流量其流量v(f)达到最大值。达到最大值。 设流设流f=fij是网络是网络D上的一个可行流，我们上的一个可行流，我们把把D中中fij=cij的弧称为饱和弧，的弧称为饱和弧，fij0的弧称为非零流弧，的弧称为非零流弧，fij=0的弧称为零

53、的弧称为零流弧。流弧。2021/6/758 设设是网络是网络D中连接发点中连接发点s和收点和收点vt的一的一条路。定义路的方向是从条路。定义路的方向是从vs到到vt，于是路，于是路上上的弧被分为两类：一些弧的方向与路的方向的弧被分为两类：一些弧的方向与路的方向相同，称为前向弧，前向弧的集合记做相同，称为前向弧，前向弧的集合记做+。二些弧的方向与路的方向相反，称为后向弧二些弧的方向与路的方向相反，称为后向弧，后向弧的集合记做，后向弧的集合记做-。2021/6/759 定义定义5.3（增广路）（增广路）: 如果路如果路是连结是连结vs到到vt的一条路，满足以下条件：的一条路，满足以下条件： 1在弧

54、（在弧（vi,vj）+上，有上，有0fijcij，即，即+中的每一条弧是非饱和弧。中的每一条弧是非饱和弧。 2在弧（在弧（vi,vj）-上，有上，有0fij cij，即，即-中的每一条弧是非零流弧。中的每一条弧是非零流弧。2021/6/760 定义定义5.4 设一个网络设一个网络D=（V，A；c），如），如果点集果点集V被剖分为两个非空集合被剖分为两个非空集合V1和和V-V1，发点发点vsV1,收点收点vtV-V1,那么将弧集那么将弧集（V1, V-V1）称为是分离）称为是分离vs和和vt的截集。的截集。 定义定义5.5 设一个截集（设一个截集（V1, V-V1），将截），将截集（集（V1,

55、V-V1）中所有弧的容量之和称为截集）中所有弧的容量之和称为截集的截量，记做的截量，记做c(V1, V-V1)，亦即，亦即c(V1, V-V1)=cij，这里对所有，这里对所有 (vi,vj)(V1, V-V1)求和。求和。2021/6/761 下面的事实是显然的：下面的事实是显然的： 一个网络一个网络D中，任何一个可行流中，任何一个可行流f的流量的流量v(f)都小于或等于这个网络中任何一个截集都小于或等于这个网络中任何一个截集(V1,V-V1)的截量。并且，如果网络上的一个的截量。并且，如果网络上的一个可行流可行流f*和网络中的一个截集（和网络中的一个截集（V1*,V-V1*），满足条件，满

56、足条件v*(f*)=c(V1*,V-V1*),那么那么f*一定是一定是D上的最大流，而（上的最大流，而（V1*,V-V1*）一定是）一定是D的所的所有的截集中截量最小的一个（即最小截集）有的截集中截量最小的一个（即最小截集）。2021/6/762 定理定理5.1 网络中的一个可行流网络中的一个可行流f*是最大流是最大流的充分必要条件是，不存在关于的充分必要条件是，不存在关于f*的增广链的增广链。 定理定理5.2 在一个网络在一个网络D中，最大流的流量中，最大流的流量等于分离等于分离vs和和vt的最小截集的截量。的最小截集的截量。2021/6/763 如果存在一条从如果存在一条从vs到到vt的增

57、广路的增广路，这时，这时，取调整量取调整量= minmincij-fij| (vi,vj) +, minfij|(vi,vj)- fij +， 当当(vi,vj)+ 令令fij= fij -， 当当(vi,vj)- 其它不变其它不变 再去掉所有的标号，对新的可行流再去掉所有的标号，对新的可行流f=fij,重新进行标号过程，直到找到网络重新进行标号过程，直到找到网络D的最大流为的最大流为止。止。2021/6/7646.6.最小费用最大流问题最小费用最大流问题 在实际的网络系统中，当涉及到有关流的在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，问题的时候，我们往往不仅仅

58、考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。就是要解决这一类问题。2021/6/765 定义定义6.1设一个网络设一个网络D=（V，A；c），对），对于每一个弧于每一个弧(vi,vj)A,给定一个单位流量的费给定一个单位流量的费用用bij0，网络系统的最小费用最大流问题，网络系统的最小费用最大流问题，是指要寻求一个最大流是指要寻求一个最大流f，并且流的总费用，并且流

59、的总费用b(f)=bij fij达到最小，这里对所有弧（达到最小，这里对所有弧（vi,vj）A求和。求和。2021/6/766 在一个网络在一个网络D中，当沿可行流中，当沿可行流f的一条增的一条增广路广路，以调整量，以调整量=1改进改进f，得到的新可行流，得到的新可行流f的流量，有的流量，有v(f)= v(f)+1，而此时总费用，而此时总费用b(f)比比b(f)增加了增加了 b(f)-b(f)=bij(fij-fij)- bij(fij-fij) + - = bij-bij + - 将将bij-bij称为这条增广链的费用。称为这条增广链的费用。 + -2021/6/767 如果可行流在流量为如

60、果可行流在流量为v(f)的所有可行流中的的所有可行流中的费用最小，并且是费用最小，并且是 关于关于f的所有增广链中的费用的所有增广链中的费用最小的增广链。那么沿增广链最小的增广链。那么沿增广链调整可行流调整可行流f，得到的新可行流得到的新可行流f，也是流量为，也是流量为v(f)的所有可行的所有可行流中的最小费用流。流中的最小费用流。 依次类推，当依次类推，当f是最大流时，就是所要求的是最大流时，就是所要求的最小费用最大流。最小费用最大流。 求解最小费用流的算法有迭加算法和求解最小费用流的算法有迭加算法和Klein圈算法（省略）。圈算法（省略）。2021/6/7687.7.中国邮递员问题中国邮递

61、员问题7.1 欧拉问题欧拉问题(Euler Problem) 1736年瑞士科学家欧拉发表了关于图年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如的两岸和岛屿之间有七座桥相互连接，如图图7.1所示。所示。2021/6/769AB图图7.1CD2021/6/770 当地的居民热衷于这样一个问题，一个漫当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每

62、座桥只能步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。多，但是都没有成功。 为了寻找答案，欧拉为了寻找答案，欧拉1736年将这个问题抽年将这个问题抽象成图象成图7.2所示图形的一笔画问题所示图形的一笔画问题,即能否从某即能否从某一点开始不重复地一笔画出这个图形，最终回一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典

63、图相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。论中的第一个著名问题。2021/6/771图图7.2ACDB2021/6/772 定义定义7.1（欧拉回路）设有一个连通图（欧拉回路）设有一个连通图G=（V，E），并且），并且 是是G中存在一条回路中存在一条回路, 称为图称为图G的欧拉回路的欧拉回路, 如果如果 经过经过(包含包含)图图G中的每条边，并且仅包含一次。此时，也称中的每条边，并且仅包含一次。此时，也称图图G是欧拉图。是欧拉图。 问题问题7.1 ：给定一个连通图：给定一个连通图G=（V，E），），如何判断如何判断G是一个欧拉图？是一个欧拉图？ 定理定理7.1(Euler

64、定理定理) 设设G=（V，E）是连通）是连通图，则图，则G是欧拉图是欧拉图iff图图G中不含有次为奇数的顶中不含有次为奇数的顶点。点。2021/6/773 算法算法 用用 表示在第表示在第k步得到的一条路步得到的一条路（其中有的顶点可能相同），记（其中有的顶点可能相同），记 （初始时，取）。按下面方式进行第（初始时，取）。按下面方式进行第k+1步：在步：在 中选一条与中选一条与 相关联的边相关联的边 , 使得使得 不是割边，除非此时不是割边，除非此时 ，令，令 ，取，重复上述过，取，重复上述过程，直到无边可选为止。程，直到无边可选为止。2021/6/774 定义定义7.2（一笔划问题）：给定一

65、个图（一笔划问题）：给定一个图G，能否找到一条路能否找到一条路 ，使得该图中的每条边恰，使得该图中的每条边恰好在好在 中出现一次如果图中出现一次如果图G满足上述要求，满足上述要求，称称G是是M图图问题问题7.2 ：如何判定一个图：如何判定一个图G是是M图？图？定理定理7.2 设设G是一个连通图，则是一个连通图，则G是是M图图iff图图G中奇次的顶点的个数中奇次的顶点的个数22021/6/775 定义定义7.3（有向欧拉回路）设有一个强连（有向欧拉回路）设有一个强连通有向图通有向图D=（V，A）,并且并且 是是D中存在一中存在一条有向回路条有向回路, 称称 为图为图D的有向欧拉回路的有向欧拉回路

66、, 如果如果 经过经过(包含包含)图图D中的每条弧中的每条弧,并且并且仅包含一次。此时，也称图仅包含一次。此时，也称图D是有向欧拉图。是有向欧拉图。 问题问题7.3：给定一个强连通有向图：给定一个强连通有向图D=（V，A），如何判断），如何判断D是一个有向欧拉图？是一个有向欧拉图？ 定理定理7.3(Euler定理定理) 设设D=（V，A）是强）是强连通有向图连通有向图,则则D是有向欧拉图是有向欧拉图iff图图D中每个中每个顶点的出度等于入度，顶点的出度等于入度，d-(u)=d+(u),uV。2021/6/7767.中国邮递员问题中国邮递员问题(Chinese Postman Problem)

67、定义定义7.4（中国邮递员问题）设（中国邮递员问题）设G=(V,E;w)是是赋权图，赋权图， ，能否在图，能否在图G中寻找一条回中寻找一条回路路 ，使得，使得G的每一条边在的每一条边在 中至少出现中至少出现一次，并且使得一次，并且使得 达到最小，称该达到最小，称该问题是中国邮递员问题（问题是中国邮递员问题（CPP）。）。 中国邮递员问题也叙述为图论问题：设中国邮递员问题也叙述为图论问题：设G=(V,E;w)是赋权图，寻找是赋权图，寻找 ，使得，使得GE1是是欧拉图，其目标是使得欧拉图，其目标是使得 达到最小。达到最小。2021/6/777 称上述达到最小的称上述达到最小的E1为为CPP问题的最

68、优集。问题的最优集。 当图当图G是欧拉图时，则利用是欧拉图时，则利用 算法能够算法能够找到一条欧拉回路（这也是最优的回路）。找到一条欧拉回路（这也是最优的回路）。 定理定理7.4（管梅谷，（管梅谷，1960）设）设G=（V，E;w)是一个赋权连通图，则是一个赋权连通图，则E1是最优集是最优集iff对于每个简对于每个简单圈单圈C，均有，均有2021/6/778 当图当图G不是欧拉图，利用不是欧拉图，利用Edmonds算法求解算法求解:1 在在G中找到的所有中找到的所有2k个奇数次顶点，个奇数次顶点，2 在在G中寻找这个顶点之间的最短路及路径，构造中寻找这个顶点之间的最短路及路径，构造一个图一个图

69、 ，这里，这里 定义为定义为G中中 与与 之之间的最短路长度。间的最短路长度。3 在图在图H中寻找最小的完美匹配中寻找最小的完美匹配M。2021/6/7794 利用利用M中的每个元素中的每个元素 对应于图对应于图G中的最中的最短路短路 ，把相应的所有最短路，把相应的所有最短路 叠加到图叠加到图G上，即把最短路上的边使用两次，得上，即把最短路上的边使用两次，得到一个图到一个图G*（此时（此时G*就是一个欧拉图）。就是一个欧拉图）。5 再利用再利用 算法在欧拉图算法在欧拉图G*上，所得到的上，所得到的欧拉回路就是中国邮递员问题的最回路，即最优欧拉回路就是中国邮递员问题的最回路，即最优解。解。 定理

70、定理7.5 Edmonds算法能够得到算法能够得到CPP的最优解。的最优解。2021/6/780 定义定义7.5（有向中国邮递员问题）设（有向中国邮递员问题）设D=(V,A; w)是赋权有向图，是赋权有向图， ，能否在有向图，能否在有向图D中中寻找一条有向回路寻找一条有向回路 ，使得，使得D的每一条弧在的每一条弧在 中至少出现一次，并且使得中至少出现一次，并且使得 达到最达到最小，称该问题是有向中国邮递员问题小，称该问题是有向中国邮递员问题(DCPP)。 有向中国邮递员问题也叙述为图论问题：设有向中国邮递员问题也叙述为图论问题：设D=(V,A;w)是有向赋权图，寻找是有向赋权图，寻找 ，使得，

71、使得DA1是有向欧拉图，其目标是使得是有向欧拉图，其目标是使得 达到最小。达到最小。2021/6/781 注意到有向连通图不一定存在有向邮路注意到有向连通图不一定存在有向邮路。 我们总是假设所讨论的赋权有向图是强我们总是假设所讨论的赋权有向图是强连通的。连通的。如果如果讨论的图讨论的图是有向欧拉图，则该是有向欧拉图，则该图的有向欧拉回路就是最优有向邮路。图的有向欧拉回路就是最优有向邮路。 例图：例图： 图图7.3 7.3 不存在有向邮路的例子不存在有向邮路的例子2021/6/782 当连通赋权有向图不是有向欧拉图，算法：当连通赋权有向图不是有向欧拉图，算法：1 1 设设 为连通赋权有向图。为连

72、通赋权有向图。 ，计，计 算算 。若所有。若所有 ，令，令 ，转第，转第2 2步，否则转第步，否则转第3 3步。步。 2 2 求出求出 的有向欧拉回路的有向欧拉回路 ，结束，结束， 是是 的最优的最优有向路。有向路。3 3 构造集合构造集合 和和 求出求出 中从中从 到到 最短路。最短路。4 4 构造集合构造集合 和和2021/6/7835 构造赋权网络构造赋权网络N=（V*，A*；b* ，c* ）,这里这里V*=s,t ， 对对 和和 ， 表示在表示在D中中 从从x到到y的最短路长度，其余费用为的最短路长度，其余费用为0，容量，容量 全为全为1。6 求出求出N中最小费用最大流中最小费用最大流f。7 8 找出找出M中每条边中每条边(x,y)对应的对应的N中的从中的从x到到y的的 最短路。把这些最短路上的每条弧都作为添最短路。把这些最短路上的每条弧都作为添加弧加到加弧加到D中去，得到有向欧拉图中去，得到有向欧拉图 ，转第，转第2步。步。2021/6/784 定理定理7.6 Edmonds-Johnson算法能够得到有算法能够得到有向中国邮递员问题向中国邮递员问题(DCPP)的最优解。的最优解。 也可以把构造网络的步骤由也可以把构造网络的步骤由LP表示：表示：2021/6/785部分资料从网络收集整理而来，供大家参考，感谢您的关注！