数学建模提高班第六讲-网络优化模型及案例分析ppt课件

1、网络优化模型及案例分析网络优化模型及案例分析赵承业赵承业 2019/4/24 2019/4/24本专题学习目的本专题学习目的掌握把实践问题转化为图或网络问题的方法了解图的根本概念和矩阵表示方法掌握最短路问题、最小生成树问题的算法了解游览商问题主要内容主要内容主要内容主要内容图论的来源：七桥问题图论的来源：七桥问题 c a b d c a b d 图论的来源：七桥问题图论的来源：七桥问题图1图2欧拉图论之父 定理1：一个图存在经过每边正好一次回到出发点的道路的充要条件是： 1图要是连通的2与图中每一顶点相连的边必需是偶数条。于是得出结论：七桥问题无解。图论的来源：七桥问题图论的来源：七桥问题无向

2、图，普通用大写字母G,H表示。一种表示工具一种表示工具图图顶点顶点边边 d c a b 图3 无向图：G=(V,E)， 顶点集：V；边集：E。 e与顶点u, v相关联。 u与v相邻。 两边相邻。 重边 c a b d 一种表示工具一种表示工具图图图4两种特殊图： 简单图 完全图，记为Knb d c a b d c a 一种表示工具一种表示工具图图图6图5有向图：V1V2V3V5V4他能给出一个可用有向图描画的实践例子吗？一种表示工具一种表示工具图图图7网络网络这些数字可以代表间隔，费用，可靠性或其他的相关参数。12345869157103一种表示工具一种表示工具图图图8(G)和(G)分别表示图

3、G的顶点数和边数在无向图中，v的度数，记为d (v)；在有向图中，v的出度，记为d+(v); v的入度，记为d-(v)。一种表示工具一种表示工具图图一个时间安排问题一个时间安排问题 学校要为一年级的研讨生开设六门根底数学课：统计(S)，数值分析(N)，图论(G)，矩阵论(M)，随机过程(R)和数理方程(P)。按培育方案，注册的学生必需选修其中的一门以上，他作为教务管理人员，要设法安排一个课表，使每个学生所选的课程，在时间上不会发生冲突。 S N G M R P李春兰郑文国姚南陈奇峰王润惠邹文燕万华李祖军黄大度史武军刘昆欧阳金郭志伟陈奇峰刘云刘元元黄大度董舟邹鑫赵云王凯李白彤甄军李欣陈俊于洪化范

4、文李出荣张惠赵云曹林军胡志强张敏陈修建欧阳金李晓李白彤万华曾光伟张星夏雯邵桂芳王学权单富民董舟杨欣吴军查小辉王坚程静波邹文燕卫迎新赵小民息志强陈修建邹鑫刘元兵杨成宝邱吉洲许茂陈俊周清武樊雪峰刘伟甄军姜永东一个时间安排问题一个时间安排问题表1SNGRPM完成上述表示课程冲突关系的图直观、明晰地表达知信息的方式一个时间安排问题一个时间安排问题图9人狼羊菜渡河问题人狼羊菜渡河问题摆渡人F狼W羊G菜C图10 南岸形状： 16种，其中WG,GC,WGC，从而FC,FW,F为不允许形状，FWGCFWGFWCFGCFGOCGWWC10个允许形状：人狼羊菜渡河问题人狼羊菜渡河问题FWGCFWG FWC FGC

5、FGOCGWWC寻求图中从顶点“FWGC到顶点“O的最短途径，这样的途径有几条？求出最优的渡河方案。言语描画时未显示的关系跃然纸上人狼羊菜渡河问题人狼羊菜渡河问题图11FWGCFWG FWC FGCFGOCGWWCFWGCFWGFWCFGCFGOCGWWC人狼羊菜渡河问题人狼羊菜渡河问题图12图的矩阵表示方法图的矩阵表示方法邻接矩阵关联矩阵边矩阵邻接顺序表v1v2v5v6v7v4v3abjkcghidfe010100010111100100010110010101010100110101000101076543217654321邻接矩阵图13 无向图的邻接矩阵：A=(aij)nn，其中不相邻与

6、当，相邻与当jijiijvv0vv1a无向图的邻接矩阵有何特点？由邻接矩阵能否能作出原图？邻接矩阵001010000000011011100000010000100100011000101100001000001000001101000000000117654321kjihgfedcba关联矩阵v1v2v5v6v7v4v3abjkcghidfe图13 无 向 图 的 关 联 矩 阵 ：M=(mij)nm, 其中 不相关联与若相关联，与若jijiijev0ev1m无向图的关联矩阵有哪些特征？由关联矩阵能否作出原图？关联矩阵4376766654232654432211Ekjihgfedcba边矩阵

7、v1v2v5v6v7v4v3abjkcghidfe图13最短路问题及算法最短路问题及算法 最短路问题是图论运用的根本问题，很多实践最短路问题是图论运用的根本问题，很多实践问题，如线路的布设、运输安排、运输网络最小费问题，如线路的布设、运输安排、运输网络最小费用流等问题用流等问题,都可经过建立最短路问题模型来求解都可经过建立最短路问题模型来求解.最短路的定义最短路的定义最短路问题的两种方法：最短路问题的两种方法：Dijkstra和和Floyd算算法法 .2) 求赋权图中恣意两点间的最短路求赋权图中恣意两点间的最短路. 2) 在赋权图在赋权图G中，从顶点中，从顶点u到顶点到顶点v的具有最小权的具有

8、最小权定义定义1 1) 假设假设H是赋权图是赋权图G的一个子图，那么称的一个子图，那么称H的各的各边的权和边的权和 为为H的权的权. 类似地，假类似地，假设设)()()(HEeewHw称为路称为路P的权的权假设假设P(u,v)是赋权图是赋权图G中从中从u到到v的路的路,称称)()()(PEeewPw 的路的路P*(u,v)，称为，称为u到到v的最短路的最短路 3) 把赋权图把赋权图G中一条路的权称为它的长，把中一条路的权称为它的长，把(u,v)路的最小权称为路的最小权称为u和和v之间的间隔，并记作之间的间隔，并记作 d(u,v). 1) 赋权图中从给定点到其他顶点的最短路赋权图中从给定点到其他

9、顶点的最短路 假设假设G为赋权有向图或无向图，为赋权有向图或无向图，G边上的权均非边上的权均非负假设负假设 ，那么规定，那么规定 )(),(GEvu.),(vuw最短路是一条路，且最短路的任一节也是最短路最短路是一条路，且最短路的任一节也是最短路例例 求下面赋权图中顶点求下面赋权图中顶点u0到其他顶点的最短路到其他顶点的最短路图14Dijkstra算法算法: 求求G中从顶点中从顶点u0到其他顶点的最短路到其他顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii替代替代 ，计算

10、，计算 ，并把到达这个最小值的，并把到达这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 假设假设 ，那么停顿；假设，那么停顿；假设 ，那么，那么用用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj01Su 10 ,min)(1ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其他顶点的最短路到其他顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii替代替代 ，计算，计

11、算 ，并把到达这个最小值的，并把到达这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 假设假设 ，那么停顿；假设，那么停顿；假设 ，那么，那么用用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj01Su 1)(1ul02Su Dijkstra算法算法: 求求G中从顶点中从顶点u0到其他顶点的最短路到其他顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii替代替代 ，计算，计算 ，

12、并把到达这个最小值的，并把到达这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 假设假设 ，那么停顿；假设，那么停顿；假设 ，那么，那么用用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul03Su )(3ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其他顶点的最短路到其他顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii替代替代 ，计算，计

13、算 ，并把到达这个最小值的，并把到达这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 假设假设 ，那么停顿；假设，那么停顿；假设 ，那么，那么用用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul04Su )(3ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其他顶点的最短路到其他顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii替代替代 ，计

14、算，计算 ，并把到达这个最小值的，并把到达这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 假设假设 ，那么停顿；假设，那么停顿；假设 ，那么，那么用用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul05Su )(3ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其他顶点的最短路到其他顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvl

15、ii替代替代 ，计算，计算 ，并把到达这个最小值的，并把到达这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 假设假设 ，那么停顿；假设，那么停顿；假设 ，那么，那么用用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul)(5ul06Su )(3ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其他顶点的最短路到其他顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()

16、(),(minvuwulvlii替代替代 ，计算，计算 ，并把到达这个最小值的，并把到达这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 假设假设 ，那么停顿；假设，那么停顿；假设 ，那么，那么用用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul)(5ul4)(6ul07Su Dijkstra算法算法: 求求G中从顶点中从顶点u0到其他顶点的最短路到其他顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个

17、对每个 ，用，用iSv),()(),(minvuwulvlii替代替代 ，计算，计算 ，并把到达这个最小值的，并把到达这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 假设假设 ，那么停顿；假设，那么停顿；假设 ，那么，那么用用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其他顶点的最短路到其他顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0

18、uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii替代替代 ，计算，计算 ，并把到达这个最小值的，并把到达这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 假设假设 ，那么停顿；假设，那么停顿；假设 ，那么，那么用用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul)()(min10ulvlSv8)(7ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其他顶点的最短路到

19、其他顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii替代替代 ，计算，计算 ，并把到达这个最小值的，并把到达这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 假设假设 ，那么停顿；假设，那么停顿；假设 ，那么，那么用用 i+1 代代1i1i替替i，并转，并转2).,101uuS 1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ul12Su 21 , 2min)(2ul2)(2ulDijks

20、tra算法算法: 求求G中从顶点中从顶点u0到其他顶点的最短路到其他顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii替代替代 ，计算，计算 ，并把到达这个最小值的，并把到达这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 假设假设 ，那么停顿；假设，那么停顿；假设 ，那么，那么用用 i+1 代代1i1i替替i，并转，并转2).,101uuS 1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7

21、ul12Su 21 , 2min)(2ul2)(2ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其他顶点的最短路到其他顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii替代替代 ，计算，计算 ，并把到达这个最小值的，并把到达这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 假设假设 ，那么停顿；假设，那么停顿；假设 ，那么，那么用用 i+1 代代1i1i替替i，并转，并转2).定义2 根据顶点v的标号l(

22、v)的取值途径，使 到v0u的最短路中与的最短路中与v相邻的前一个顶点相邻的前一个顶点w，称为，称为v的先的先驱驱点，记为点，记为z(v), 即即z(v)=w.先驱点可用于追踪最短途径先驱点可用于追踪最短途径. 例例5的标号过程也的标号过程也可按如下方式进展：可按如下方式进展： 首先写出左图带权邻接矩阵首先写出左图带权邻接矩阵024782063446046340357630135102273201847210W因因G是无向图，故是无向图，故W是对称阵是对称阵表21u0u6u7u2u4u3u5u续表2图82) 求赋权图中恣意两顶点间的求赋权图中恣意两顶点间的最短路最短路算法的根本思想 I求间隔矩

23、阵的方法求间隔矩阵的方法.II求途径矩阵的方法求途径矩阵的方法.III查找最短路途径的方法查找最短路途径的方法. Floyd算法：求恣意两顶点间的最短路算法：求恣意两顶点间的最短路. 举例阐明举例阐明算法的根本思想算法的根本思想I求间隔矩阵的方法求间隔矩阵的方法.II求途径矩阵的方法求途径矩阵的方法.在建立间隔矩阵的同时可建立途径矩阵在建立间隔矩阵的同时可建立途径矩阵R ivjvIII查找最短路途径的方法查找最短路途径的方法.然后用同样的方法再分头查找假设：然后用同样的方法再分头查找假设：1av2av3avkav1bv2bvmbv图16IVFloyd算法：求恣意两顶点间的最短路算法：求恣意两顶

24、点间的最短路.例例 2求以下图中加权图的恣意两点间的间隔与途求以下图中加权图的恣意两点间的间隔与途径径. ,053142503330212044401210 )0(D,654321654321654321654321654321654321 )0(R图17,053142503330212044401210 )0(D,min) 1() 1() 1()(kkjkikkijkijdddd插入点插入点 v1，得：，得：,053132503330212043401210)1(D,654311654321654321654321154321654321 )1(R矩阵中带矩阵中带“=的项为经迭代比较以后有变

25、化的元素的项为经迭代比较以后有变化的元素.,min) 1() 1() 1()(kkjkikkijkijdddd插入点插入点 v2，得：，得：,053132503330212043401210)1(D矩阵中带矩阵中带“=的项为经迭代比较以后有变化的元素的项为经迭代比较以后有变化的元素.,05313250333021204534012510)2(D,654311654321654321654322154321654221 )2(R,min) 1() 1() 1()(kkjkikkijkijdddd,053132503330267120453640127510)3(D,654311654321654

26、333654322153321653221 )3(R插入点插入点 v3，得：，得：,05313250333021204534012510)2(D,min) 1() 1() 1()(kkjkikkijkijdddd,053132503330267120453640127510)3(D插入点插入点 v4，得：，得：,05313250359103302671520453964012107510)4(D,654311654444654333644322143321643221 )4(R,)4()5(DD插入点插入点 v5，得：，得：,)4()5(RR,min) 1() 1() 1()(kkjkikki

27、jkijdddd插入点插入点 v6，得：，得：,05313250359103302671520453964012107510)5(D,053132503587330265152043386401275310)6(D.654311654466654336644326163321666621 )6(R,053132503587330265152043386401275310)6(D.654311654466654336644326163321666621 )6(R8)6(52d8)6(52d故从故从v5到到v2的最短路为的最短路为8 6)6(52R由由v6向向v5追追溯溯: . 6)6(56R由由

28、v6向向v2追溯追溯: , 1)6(62R. 2)6(12R所以从到的最短途径为：所以从到的最短途径为： .2165vvvv最小生成树及算法最小生成树及算法许多运用问题都是一个求无向连通图的最小生成树问题。例如：要在n个城市之间铺设光缆，主要目的是要使这 n 个城市的恣意两个之间都可以通讯，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目的是要使铺设光缆的总费用最低。这就需求找到带权的最小生成树。1) 树的定义与树的特征1v定义定义3 连通且不含圈的无向图称为树常用连通且不含圈的无向图称为树常用T表示表示. 树中的边称为树枝树中的边称为树枝. 树中度为树中度为1的顶点称为树叶的

29、顶点称为树叶.孤立顶点称为平凡树孤立顶点称为平凡树.2v3v4v5v平凡树平凡树图18定理定理2 设设G是具有是具有n个顶点的图，那么下述命题个顶点的图，那么下述命题等价：等价：1) G是树是树 G无圈且连通；无圈且连通；2) G无圈，且有无圈，且有n-1条边；条边；3) G连通，且有连通，且有n-1条边；条边；4) G无圈，但添加任一条新边恰好产生一个圈无圈，但添加任一条新边恰好产生一个圈; 5) G连通，且删去一条边就不连通了即连通，且删去一条边就不连通了即G为最为最最小连通图；最小连通图；6) G中恣意两顶点间有独一一条路中恣意两顶点间有独一一条路.2图的生成树图的生成树定义定义4 假设

30、假设T是包含图是包含图G的全部顶点的子图的全部顶点的子图,它又是它又是树树,那么称那么称T是是G的生成树的生成树. 图图G中不在生成树的边叫做中不在生成树的边叫做弦弦.定理定理3 图图G=(V,E)有生成树的充要条件是图有生成树的充要条件是图G是连是连 通的通的.证明证明 必要性是显然的必要性是显然的.II找图中生成树的方法找图中生成树的方法可分为两种：避圈法和破圈法可分为两种：避圈法和破圈法 A 避圈法避圈法 : 深探法和广探法深探法和广探法 B 破圈法破圈法 A 避圈法避圈法 定理定理3的充分性的证明提供了一种构造图的生的充分性的证明提供了一种构造图的生成树的方法成树的方法. 这种方法就是

31、在已给的图这种方法就是在已给的图G中，每步选出一中，每步选出一条边使它与已选边不构成圈，直到选够条边使它与已选边不构成圈，直到选够n-1条边为条边为止止. 这种方法可称为这种方法可称为“避圈法或避圈法或“加边法加边法 在避圈法中，按照边的选法不同，找图中生在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：深探法和广探法成树的方法可分为两种：深探法和广探法.a) 深探法深探法 假设这样的边的另一端均已有标号，就退到标号假设这样的边的另一端均已有标号，就退到标号为为步骤如下：步骤如下：i) 在点集在点集V中任取一点中任取一点u,ii) 假设某点假设某点v已得标号，已得标号，检检端能否均已

32、标号端能否均已标号. 假设有边假设有边vw之之w未标号未标号,那那么给么给w代代v，反复，反复ii).i-1的的r点点,以以r代代v,反复反复ii),直到全部点得到标号为止直到全部点得到标号为止.给以标号给以标号0.查一端点为查一端点为v的各边，另一的各边，另一w以标号以标号i+1，记下边，记下边vw.令令例例3用深探法求出以下图用深探法求出以下图10的一棵生的一棵生成树成树 图19012345678910111213图203b)广探法广探法步骤如下：步骤如下：i) 在点集在点集V中任取一点中任取一点u,ii) 令一切标号令一切标号i的点集为的点集为能否均已标号能否均已标号. 对一切未标对一切

33、未标号之点均标以号之点均标以i+1,记下这些记下这些 iii) 对标号对标号i+1的点反复步的点反复步步骤步骤ii)，直到全部点得到，直到全部点得到给给u以标号以标号0.Vi,检查检查Vi,VVi中的边端点中的边端点边边.例例4用广探法求出以下图用广探法求出以下图10的一棵生的一棵生成树成树 图191012213212234标号为止标号为止.图21B 破圈法破圈法 相对于避圈法，还有一种求生成树的方法叫做相对于避圈法，还有一种求生成树的方法叫做“破圈法破圈法. 这种方法就是在图这种方法就是在图G中任取一个圈，中任取一个圈，恣意舍弃一条边，将这个圈破掉，反复这个步骤恣意舍弃一条边，将这个圈破掉，

34、反复这个步骤直到图直到图G中没有圈为止中没有圈为止.例例5 用破圈法求出用破圈法求出以下图的一棵生成以下图的一棵生成树树.图22例例6 用破圈法求出以下图的另一棵生成树用破圈法求出以下图的另一棵生成树.不难发现，图不难发现，图的生成树不是的生成树不是独一的独一的 .图233) 最小生成树与算法最小生成树与算法 引见最小树的两种算法：引见最小树的两种算法：Kruskal算法或避圈法和破圈法算法或避圈法和破圈法. 5A Kruskal算法或避圈法算法或避圈法步骤如下：步骤如下： 1) 选择边选择边e1，使得，使得w(e1)尽能够小；尽能够小；2) 假设已选定边假设已选定边 ，那么从，那么从ieee

35、,.,21,.,21ieeeE中选取中选取 ，使得，使得:1iei) 为无圈图，为无圈图，,.,121ieeeG ii) 是满足是满足i)的尽能够小的权，的尽能够小的权，)(1iew 3) 当第当第2)步不能继续执行时，那么停顿步不能继续执行时，那么停顿.定理定理4 由由Kruskal算法构作的任何生成树算法构作的任何生成树,.,121*eeeGT都是最小树都是最小树.,876432eeeeee例例7用用Kruskal算法求以下图的最小树算法求以下图的最小树.在左图中在左图中 权值权值,.,821eee最小的边有最小的边有 任取一条任取一条 ,51ee,1e 在在 中选取权值中选取权值,.,8

36、32eee,5e最小的边最小的边 中权值最小边有中权值最小边有 , 从中选从中选：73,ee;3e任取一条边任取一条边,87642eeeee会与已选边构成圈会与已选边构成圈,故停顿故停顿,得得中选取在中选取中选取在中选取,7e,42ee在 中选取中选取 . 但但 与与 都都,86ee84,ee4e8e图24B破圈法破圈法算法算法2 步骤如下：步骤如下： 1) 从图从图G中任选一棵树中任选一棵树T1.2) 加上一条弦加上一条弦e1，T1+e1中中 立刻生成一个圈立刻生成一个圈. 去掉此去掉此 圈中最大权边，得到新圈中最大权边，得到新树树T2,以以T2代代T1,反复反复2)再再检查剩余的弦，直到全

37、检查剩余的弦，直到全部弦检查终了为止部弦检查终了为止.例例8 用破圈法求以下图的最小树用破圈法求以下图的最小树.先求出上图的一棵生成树先求出上图的一棵生成树. 加以弦加以弦 e2,得到的圈得到的圈v1v3v2v1,去掉最大的权边去掉最大的权边e2,得到一棵新得到一棵新树仍是原来的树；树仍是原来的树；2e 再加上弦再加上弦e7，得到圈，得到圈 v4v5v2v4,27e去掉最大的权边去掉最大的权边e6，得到一，得到一棵棵 新树；如此反复进展，直到全新树；如此反复进展，直到全全部的弦均已试过全部的弦均已试过,得最小树得最小树.图25游览售货员问题游览售货员问题 定义定义6设设G=(V,E)是连通无向

38、图，包含图是连通无向图，包含图G的每个的每个顶点的路称为顶点的路称为G的哈密尔顿路的哈密尔顿路(Hamilton路或路或H路路). 包含图包含图G的每个顶点的圈，称为的每个顶点的圈，称为G的哈密尔顿圈的哈密尔顿圈(或或Hamilton圈或圈或H圈圈). 含含Hamilton圈的图称为哈密尔顿图圈的图称为哈密尔顿图(或或Hamilton图或图或H图图). 游览售货员问题或货郎担问题游览售货员问题或货郎担问题 一个游览售货员想去访问假设干城镇，然后一个游览售货员想去访问假设干城镇，然后回回到出发地到出发地.给定各城镇之间的间隔后，应怎样方案给定各城镇之间的间隔后，应怎样方案他的游览道路，使他能对每

39、个城镇恰好经过一次他的游览道路，使他能对每个城镇恰好经过一次而总间隔最小？而总间隔最小？ 它可归结为这样的图论问题：在一个赋权完它可归结为这样的图论问题：在一个赋权完全图中全图中,找出一个最小权的找出一个最小权的H圈圈,称这种圈为最优圈称这种圈为最优圈. 但这个问题是但这个问题是NP-hard问题，即不存在多项式问题，即不存在多项式时间算法时间算法.也就是说也就是说,对于大型网络对于大型网络(赋权图赋权图),目前还目前还没有一个求解游览售货员问题的有效算法，因此没有一个求解游览售货员问题的有效算法，因此只能找一种求出相当好不一定最优的解只能找一种求出相当好不一定最优的解.一个可行的方法一个可行

40、的方法 : 是先求一个是先求一个H圈圈,然后适当然后适当修正修正,以得到具有较小权的另以得到具有较小权的另一个一个H圈圈.图26定义7 假设对于某一对i和j，有)()()()(1111jjiijijivvwvvwvvwvvw那么圈那么圈Cij将是圈将是圈C的一个改良的一个改良.定义定义8 二边逐次修正法二边逐次修正法: 在接连进展一系列修正之后在接连进展一系列修正之后,最后得一个圈最后得一个圈,不能不能再用此方法改良了，这个最后的圈能够不是最优的再用此方法改良了，这个最后的圈能够不是最优的,但是它是比较好的，为了得到更高的精度，这个但是它是比较好的，为了得到更高的精度，这个程序可以反复几次，每

41、次都以不同的圈开场程序可以反复几次，每次都以不同的圈开场. 这种这种方法叫做二边逐次修正法方法叫做二边逐次修正法.例例9 对以下图对以下图,用二边逐次修正法求较优用二边逐次修正法求较优H圈圈.较优较优H圈圈:其权为其权为W(C3)=19213265413vvvvvvvC 图27 分析分析: 找出的这个解的好坏可用最优找出的这个解的好坏可用最优H圈的权圈的权的下界与其比较而得出的下界与其比较而得出.即利用最小生成树可得最即利用最小生成树可得最优优H圈的一个下界，方法如下：圈的一个下界，方法如下： 设设C是是G的一个最优的一个最优H圈，那么对圈，那么对G的任一顶点的任一顶点v, C-v是是G-v的

42、路，也的路，也G-v是的生成树是的生成树.假设假设T是是G-v的的最小生成树最小生成树,且且e1是是e2与与v关联的边中权最小的两条关联的边中权最小的两条边边,那么那么w(T)+w(e1)+w(e2)将是将是w(C)的一个下界的一个下界.取取v=v3,得得G-v3的的一一最小生成树最小生成树(实线实线),其其权权w(T)=122,与与v3关关联联的权最小的两条边为的权最小的两条边为w(T)+w(v1v3)+w(v2v3)=178.故最优故最优H圈的权圈的权v1v3和和v2v3,故故w(C)应满足应满足178 w(C) 192.1. 1. 设某校的田径选拔赛共设六个工设某校的田径选拔赛共设六个工

43、程的竞赛，即跳高，跳远，标枪，铅程的竞赛，即跳高，跳远，标枪，铅球，球，100100米和米和200200米短跑，规定每个选米短跑，规定每个选手至多参与三个工程的竞赛。现有七手至多参与三个工程的竞赛。现有七名选手报名，选手所选工程如表名选手报名，选手所选工程如表1 1所示。所示。如今要求设计一个竞赛日程安排表，如今要求设计一个竞赛日程安排表，使得在尽能够短的时间内完成竞赛。使得在尽能够短的时间内完成竞赛。练习题练习题姓 名 项 目 1 项 目 2 项 目 3 赵 宁 跳 高 跳 远 铅 球 钱 虎 跳 远 100 米 孙 正 跳 高 200 米 李 江 200 米 标 枪 铅 球 杨 众 跳 远

44、 铅 球 跳 高 刘 平 铅 球 跳 高 200 米 王 跃 标 枪 跳 远 100 米 表1 参赛选手竞赛工程表 附录：图论算法的附录：图论算法的matlab实现实现最短路问题最短路问题例 某公司在六个城市中有分公司，从ci到cj的直接航程票价记在下述矩阵的位置上。表示无直接航路，请协助该公司设计一张城市c1到其它城市间的票价最廉价的道路图。055252510550102025251001020402010015252015050102540500用矩阵 为顶点个数存放各边权的邻接矩阵，行向量pb、index1、index2、d分别用来存放标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量 index2(i)存放始点到第点最短通路中第顶点前一顶点的序号； d(i)存放由始点到第点最短通路的值。nna顶点未标号当第顶点已标号当第iiipb01)(Dijkstra 的Matlab程序如下：M=10000;a(1,:)=0,50,M,40,25,10;