《数学建模--图论模型(2).ppt》由会员分享，可在线阅读，更多相关《数学建模--图论模型(2).ppt（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学建模 图论模型(2)数学与统计学院 李书选 2012/07/18下下下下回回回回停停停停 4.最小生成树及算法最小生成树及算法 5.旅行售货员问题旅行售货员问题数学建模 图论模型(2)6.中国邮递员问题中国邮递员问题4 4最小生成树及算法最小生成树及算法最小生成树及算法最小生成树及算法1)树的定义与树的特征树的定义与树的特征定义定义 连通且不含圈的无向图称为连通且不含圈的无向图称为树树常用常用T表示表示.树中的边称为树中的边称为树枝树枝.树中度为树中度为1的顶点称为的顶点称为树叶树叶.孤立顶点称为孤立顶点称为平凡树平凡树.平凡树平凡树定理定理定理定理2 2 设设设设G G是具有是具有是具有
2、是具有n n个顶点的图，则下述命题等价：个顶点的图，则下述命题等价：个顶点的图，则下述命题等价：个顶点的图，则下述命题等价：1)G是树（是树（G无圈且连通）；无圈且连通）；2)G无圈，且有无圈，且有n-1条边；条边；3)G连通，且有连通，且有n-1条边；条边；4)G无圈，但添加任一条新边恰好产生一个圈无圈，但添加任一条新边恰好产生一个圈;5)G连通，且删去一条边就不连通了（即连通，且删去一条边就不连通了（即G为为最最最小连通图最小连通图）；）；6)G中任意两顶点间有唯一一条路中任意两顶点间有唯一一条路.2 2）图的生成树）图的生成树）图的生成树）图的生成树定义定义 若若T是包含图是包含图G的全
3、部顶点的子图的全部顶点的子图,它又是树它又是树,则称则称T是是G的的生成树生成树.图图G中不在生成树的边叫做中不在生成树的边叫做弦弦.定理定理3 图图G=(V,E)有生成树的充要条件是图有生成树的充要条件是图G是连是连 通的通的.证明证明 必要性必要性是显然的是显然的.（IIII）找图中生成树的方法）找图中生成树的方法）找图中生成树的方法）找图中生成树的方法可分为两种：避圈法和破圈法可分为两种：避圈法和破圈法 A 避圈法避圈法:深探法和广探法深探法和广探法 B 破圈法破圈法 A A 避圈法避圈法避圈法避圈法 定理定理3的充分性的证明提供了一种构造图的生的充分性的证明提供了一种构造图的生成树的方
4、法成树的方法.这种方法就是在已给的图这种方法就是在已给的图G中，每步选出一中，每步选出一条边使它与已选边不构成圈，直到选够条边使它与已选边不构成圈，直到选够n-1条边为条边为止止.这种方法可称为这种方法可称为“避圈法避圈法”或或“加边法加边法”在避圈法中，按照边的选法不同，找图中生在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：成树的方法可分为两种：深探法深探法和和广探法广探法.a)深探法深探法 若这样的边的另一端均已有标号，就退到标号为若这样的边的另一端均已有标号，就退到标号为步骤如下：步骤如下：i)在点集在点集V中任取一点中任取一点u,ii)若某点若某点v已得标号，检已得标号，
5、检端是否均已标号端是否均已标号.若有边若有边vw之之w未标号未标号,则给则给w代代v，重复，重复ii).i-1的的r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止.给以标号给以标号0.查一端点为查一端点为v的各边，另一的各边，另一w以标号以标号i+1，记下边，记下边vw.令令例例用深探法求出下图用深探法求出下图10的一棵生成树的一棵生成树 图1001234567891011121313a)深探法深探法图100123456789101112步骤如下：步骤如下：若这样的边的另一端均已有标号，就退到标号为若这样的边的另一端均已有标号，就退到标号为i)在点集在点集V中
6、任取一点中任取一点u,ii)若某点若某点v已得标号，检已得标号，检端是否均已标号端是否均已标号.若有边若有边vw之之w未标号未标号,则给则给w代代v，重复，重复ii).i-1的的r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止.给给u以标号以标号0.查一端点为查一端点为v的各边，另一的各边，另一w以标号以标号i+1，记下边，记下边vw.令令例例用深探法求出下图用深探法求出下图10的一棵生成树的一棵生成树 3b)广探法广探法步骤如下：步骤如下：i)在点集在点集V中任取一点中任取一点u,ii)令所有标号令所有标号i的点集为的点集为是否均已标号是否均已标号.对所有未
7、对所有未标标号之点均标以号之点均标以i+1,记下这些记下这些 iii)对标号对标号i+1的点重复步的点重复步步骤步骤ii)，直到全部点得到，直到全部点得到给给u以标号以标号0.Vi,检查检查Vi,VVi中的边端中的边端点点边边.例例用广探法求出下图用广探法求出下图10的一棵生成树的一棵生成树 图101012213212234标号为止标号为止.图103b)广探法广探法步骤如下：步骤如下：i)在点集在点集V中任取一点中任取一点u,ii)令所有标号令所有标号i的点集为的点集为是否均已标号是否均已标号.对所有未对所有未标标号之点均标以号之点均标以i+1,记下这些记下这些 iii)对标号对标号i+1的点
8、重复步的点重复步步骤步骤ii)，直到全部点得到，直到全部点得到给给u以标号以标号0.Vi,检查检查Vi,VVi中的边端中的边端点点边边.例例用广探法求出下图用广探法求出下图10的一棵生成树的一棵生成树 图101012213212234标号为止标号为止.显然图显然图10的生成树的生成树不唯一不唯一.B B 破圈法破圈法 相对于避圈法，还有一种求生成树的方法叫做相对于避圈法，还有一种求生成树的方法叫做“破圈法破圈法”.这种方法就是在图这种方法就是在图G中任取一个圈，中任取一个圈，任意舍弃一条边，将这个圈破掉，重复这个步骤任意舍弃一条边，将这个圈破掉，重复这个步骤直到图直到图G中没有圈为止中没有圈为
9、止.例例 用破圈法求出用破圈法求出下图的一棵生成树下图的一棵生成树.B B 破圈法破圈法例例 用破圈法求出下图的另一棵生成树用破圈法求出下图的另一棵生成树.不难发现，图不难发现，图的生成树不是的生成树不是唯一的唯一的.3)3)最小生成树与算法最小生成树与算法最小生成树与算法最小生成树与算法 介绍最小树的两种算法：介绍最小树的两种算法：Kruskal算法算法（或（或避圈法避圈法）和）和破圈法破圈法.A A KruskalKruskal算法（或避圈法）算法（或避圈法）算法（或避圈法）算法（或避圈法）步骤如下：步骤如下：1)选择边选择边e1，使得，使得w(e1)尽可能小；尽可能小；2)若已选定边若已
10、选定边 ，则从，则从中选取中选取 ，使得，使得:i)为无圈图，为无圈图，ii)是满足是满足i)的尽可能小的权，的尽可能小的权，3)当第当第2)步不能继续执行时，则停止步不能继续执行时，则停止.定理定理4 由由Kruskal算法构作的任何生成树算法构作的任何生成树都是最小树都是最小树.例例10用用Kruskal算法求下图的最小树算法求下图的最小树.在左图中在左图中 权值权值最小的边有最小的边有 任取一条任取一条 在在 中选取权值中选取权值最小的边最小的边 中权值最小边有中权值最小边有 ,从中选从中选任取一条边任取一条边会与已选边构成圈会与已选边构成圈,故停止故停止,得得中选取在中选取中选取在中选
11、取 中选取中选取 .但但 与与 都都B B破圈法破圈法算法算法2 步骤如下：步骤如下：1)从图从图G中任选一棵树中任选一棵树T1.2)加上一条弦加上一条弦e1，T1+e1中中 立即生成一个圈立即生成一个圈.去掉此去掉此 圈中最大权边，得到新圈中最大权边，得到新树树T2,以以T2代代T1,重复重复2)再再检查剩余的弦，直到全检查剩余的弦，直到全部弦检查完毕为止部弦检查完毕为止.例例11用破圈法求下图的最小树用破圈法求下图的最小树.先求出上图的一棵生成树先求出上图的一棵生成树.加以弦加以弦 e2,得到的圈得到的圈v1v3v2v1,去掉最大的权边去掉最大的权边e2,得到一棵新得到一棵新树仍是原来的树
12、；树仍是原来的树；再加上弦再加上弦e7，得到圈，得到圈 v4v5v2v4,去掉最大的权边去掉最大的权边e6，得到一棵，得到一棵新树；如此重复进行，直到全新树；如此重复进行，直到全全部的弦均已试过全部的弦均已试过,得得最小树最小树.如如如如图图图图的的的的交交交交通通通通网网网网络络络络，每每每每条条条条弧弧弧弧上上上上的的的的数数数数字字字字代代代代表表表表车车车车辆辆辆辆在在在在该该该该路路路路段段段段行行行行驶驶驶驶所所所所需需需需的的的的时时时时间间间间，有有有有向向向向边边边边表表表表示示示示单单单单行行行行道道道道，无无无无向向向向边边边边表表表表示示示示可可可可双双双双向向向向行行
13、行行驶驶驶驶。若若若若有有有有一一一一批批批批货货货货物物物物要要要要从从从从1 1 1 1号号号号顶顶顶顶点点点点运运运运往往往往11111111号号号号顶顶顶顶点点点点，问问问问运运运运货车应沿哪条线路行驶，才能最快地到达目的地？货车应沿哪条线路行驶，才能最快地到达目的地？货车应沿哪条线路行驶，才能最快地到达目的地？货车应沿哪条线路行驶，才能最快地到达目的地？例：例：最短运输路线问题最短运输路线问题 10237411659813 35 512122 210106 61 15 58 88 87 79 99 93 32 22 27 7 某某某某公公公公司司司司在在在在六六六六个个个个城城城城市
14、市市市C C C C1 1 1 1,C,C,C,C2 2 2 2,C,C,C,C3 3 3 3,C,C,C,C4 4 4 4,C,C,C,C5 5 5 5,C,C,C,C6 6 6 6都都都都有有有有分分分分公公公公司司司司，公公公公司司司司成成成成员员员员经经经经常常常常往往往往来来来来于于于于它它它它们们们们之之之之间间间间，已已已已知知知知从从从从CiCiCiCi到到到到C C C Cj j j j的的的的直直直直达达达达航航航航班班班班票票票票价价价价由由由由下下下下述述述述矩矩矩矩阵阵阵阵的的的的第第第第i i行行行行，第第第第j j列列列列元元元元素素素素给给给给出出出出（表表表表
15、示示示示无无无无直直直直达达达达航航航航班班班班），该该该该公公公公司司司司想想想想算算算算出出出出一一一一张张张张任任任任意意意意两两两两个个个个城城城城市市市市之之之之间间间间的的的的最最最最廉价路线航费表。廉价路线航费表。廉价路线航费表。廉价路线航费表。例：例：最廉价航费表的制定最廉价航费表的制定 练习练习 求图中任意两点间的最短路及最小生成树.5.5.旅行售货员问题旅行售货员问题旅行售货员问题旅行售货员问题 定义定义设设G=(V,E)是连通无向图，包含图是连通无向图，包含图G的每个的每个顶点的路称为顶点的路称为G的的哈密尔顿路哈密尔顿路(Hamilton路路或或H路路).包含图包含图G
16、的每个顶点的圈，称为的每个顶点的圈，称为G的的哈密尔顿圈哈密尔顿圈(或或Hamilton圈圈或或H圈圈).含含Hamilton圈的图称为圈的图称为哈密尔顿图哈密尔顿图(或或Hamilton图图或或H图图).旅行售货员问题或货郎担问题旅行售货员问题或货郎担问题旅行售货员问题或货郎担问题旅行售货员问题或货郎担问题.一个旅行售货员想去访问若干城镇，然后回一个旅行售货员想去访问若干城镇，然后回到出发地到出发地.给定各城镇之间的距离后，应怎样计划给定各城镇之间的距离后，应怎样计划他的旅行路线，使他能对每个城镇恰好经过一次他的旅行路线，使他能对每个城镇恰好经过一次而总距离最小？而总距离最小？它可归结为这样
17、的它可归结为这样的图论问题：图论问题：在一个赋权完在一个赋权完全图中全图中,找出一个最小权的找出一个最小权的H圈圈,称这种圈为称这种圈为最优最优圈圈.但这个问题是但这个问题是NP-hard问题，即不存在多项式问题，即不存在多项式时间算法时间算法.也就是说也就是说,对于大型网络对于大型网络(赋权图赋权图),目前目前还还没有一个求解旅行售货员问题的有效算法，因此没有一个求解旅行售货员问题的有效算法，因此只能找一种求出相当好（不一定最优）的解只能找一种求出相当好（不一定最优）的解.一个可行的办法一个可行的办法一个可行的办法一个可行的办法 :是先求一个是先求一个H圈圈,然后适当然后适当修改修改,以得到
18、具有较小权的以得到具有较小权的另另一个一个H圈圈.定义 若对于某一对若对于某一对i和和j，有，有则圈则圈Cij将是圈将是圈C的一个的一个改进改进.二边逐次修正法二边逐次修正法:在接连进行一系列修改之后在接连进行一系列修改之后,最后得一个圈最后得一个圈,不不能能再用此方法改进了，这个最后的圈可能不是最优的再用此方法改进了，这个最后的圈可能不是最优的,但是它是比较好的，为了得到更高的精度，这个但是它是比较好的，为了得到更高的精度，这个程序可以重复几次，每次都以不同的圈开始程序可以重复几次，每次都以不同的圈开始.这种这种方法叫做方法叫做二边逐次修正法二边逐次修正法.例例例例对下图对下图对下图对下图1
19、616的的的的KK6 6,用二边逐次修正法求较优用二边逐次修正法求较优用二边逐次修正法求较优用二边逐次修正法求较优HH圈圈圈圈.较优较优H圈圈:其权为其权为W(C3)=192 分析分析:找出的这个解的好坏可用最优找出的这个解的好坏可用最优H圈的权圈的权的下界与其比较而得出的下界与其比较而得出.即利用最小生成树可得最即利用最小生成树可得最优优H圈的一个下界，圈的一个下界，方法如下方法如下：设设C是是G的一个最优的一个最优H圈，则对圈，则对G的任一顶点的任一顶点v,C-v是是G-v的路，也的路，也G-v是的生成树是的生成树.如果如果T是是G-v的的最小生成树最小生成树,且且e1是是e2与与v关联的
20、边中权最小的两条关联的边中权最小的两条边边,则则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.6.6.中国邮递员问题中国邮递员问题中国邮递员问题中国邮递员问题七桥问题七桥问题 Seven Bridges Problem1818世纪著名古典数学问题之一。在世纪著名古典数学问题之一。在哥
21、尼斯堡哥尼斯堡的的一个公园里，有七座桥将普雷格尔河中两个岛一个公园里，有七座桥将普雷格尔河中两个岛以及岛与河岸连接起来以及岛与河岸连接起来(如图如图)。问是否可能从。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？次，再回到起点？欧拉于欧拉于17361736年研究并解决了此问题，年研究并解决了此问题，他用点表示他用点表示岛和陆地，两点之间的连线表示连接它们的桥，岛和陆地，两点之间的连线表示连接它们的桥，将河流、小岛和将河流、小岛和桥桥简化为一个简化为一个网络网络，把七桥问题，把七桥问题化成判断连通网络能否化成判断连通网络能否一笔画一笔
22、画的的问题。之后他发问题。之后他发表一篇论文，证明了上述走法是不可能的。并且表一篇论文，证明了上述走法是不可能的。并且给出了连通网络可一笔画的充要条件这一著名的给出了连通网络可一笔画的充要条件这一著名的结论。结论。一笔画问题一笔画问题一笔画问题一笔画问题一笔画问题：一笔画问题：从某一点开始画画，笔不离纸，各从某一点开始画画，笔不离纸，各条线路仅画一次，最后回到原来的出发点。条线路仅画一次，最后回到原来的出发点。想一想：想一想：想一想：想一想：bca图图1v2v3v1v4图图2 图图1和图和图2当中哪一个图满足：当中哪一个图满足：从图中任何一点出发，从图中任何一点出发，途径每条边，最终还能回到出
23、发点？途径每条边，最终还能回到出发点？由此试想一下：一个图应该满足什么条件才能达到由此试想一下：一个图应该满足什么条件才能达到上面要求呢？上面要求呢？一笔画问题一笔画问题一笔画问题一笔画问题凡是能一笔画出的图，奇点的个数最多有凡是能一笔画出的图，奇点的个数最多有两个两个。始点与终点始点与终点重合重合的一笔画问题，奇点的个数必是的一笔画问题，奇点的个数必是0。在一个多重边的连通图中，从某个顶点出发，经在一个多重边的连通图中，从某个顶点出发，经过不同的线路，又回到原出发点，这样的线路必过不同的线路，又回到原出发点，这样的线路必是是尤拉图尤拉图，即，即能一笔画出的图必是尤拉图。能一笔画出的图必是尤拉
24、图。中国邮递员问题中国邮递员问题中国邮递员问题中国邮递员问题 一个邮递员送信，要走完他负责投递的全部街道，一个邮递员送信，要走完他负责投递的全部街道，投完后回到邮局，应该怎样走，使所走的路程最投完后回到邮局，应该怎样走，使所走的路程最短？短？这个问题是我国管梅谷同志这个问题是我国管梅谷同志19621962年首先求出来的，年首先求出来的，因此在国际上通称为中国邮递员问题。在物流活因此在国际上通称为中国邮递员问题。在物流活动中，经常会遇到这样的问题，如：每天在大街动中，经常会遇到这样的问题，如：每天在大街小巷行驶的垃圾车、洒水车、各售货点的送货车小巷行驶的垃圾车、洒水车、各售货点的送货车等都需要解
25、决一个行走的最短路程问题。等都需要解决一个行走的最短路程问题。这个问题就是一笔画问题。这个问题就是一笔画问题。解决这样的问题，可以采用解决这样的问题，可以采用奇偶点图上作业法：奇偶点图上作业法：如果在配送范围内，街道中没有如果在配送范围内，街道中没有奇点奇点，那么他，那么他就可以从配送中心出发，走过每条街道一次，就可以从配送中心出发，走过每条街道一次，且仅一次，最后回到配送中心，这样他所走的且仅一次，最后回到配送中心，这样他所走的路程也就是最短的路程。路程也就是最短的路程。对于有奇点的街道图，该怎么办呢？对于有奇点的街道图，该怎么办呢？这时就必须在每条街道上重复走一次或多次。这时就必须在每条街
26、道上重复走一次或多次。如果在某条路线中，边如果在某条路线中，边 v vi i,v,vj j 上重复走几次，我们就在上重复走几次，我们就在图中图中v vi i,v,vj j之间增加几条边，令每条边的权和原来的权相之间增加几条边，令每条边的权和原来的权相等，并把所增加的边，称为等，并把所增加的边，称为重复边重复边，于是这条路线就是，于是这条路线就是相应的新图中的相应的新图中的尤拉图尤拉图。原来的问题可以叙述为在一个有奇点的图中，要求增加原来的问题可以叙述为在一个有奇点的图中，要求增加一些重复边，使新图不含奇点，并且重复边的总权为最一些重复边，使新图不含奇点，并且重复边的总权为最小。小。我们把使新图
27、不含奇点而增加的重复边简称为我们把使新图不含奇点而增加的重复边简称为可行（重可行（重复边）方案复边）方案，使总权最小的可行方案为，使总权最小的可行方案为最优方案最优方案。现在的问题是现在的问题是第一个可行方案如何确定？第一个可行方案如何确定？在确定一个可行方案后，在确定一个可行方案后，怎么判断这个方案是否怎么判断这个方案是否为最优方案？为最优方案？若不是最优方案，若不是最优方案，如何调整这个方案？如何调整这个方案？车辆从某配送中心（车辆从某配送中心（v v1 1）出发，给街道边上的）出发，给街道边上的超市超市（v v2 2,v,v3 3,v,v4 4,v,v5 5,v,v6 6,v,v7 7,
28、v,v8 8,v,v9 9）送货，如图）送货，如图4-84-8所所示。示。案例案例v1v3v2v4v8v7v6v5v9254339546444图图1显然街区图上有奇点（显然街区图上有奇点（4 4个个），不满足），不满足“一一笔画笔画”的条件，则必然有一些街道要被重复的条件，则必然有一些街道要被重复走过（走过（添加重复边添加重复边）才能回到原出发点。此）才能回到原出发点。此时得到的图就无奇点。时得到的图就无奇点。那么该怎样添加重复边，使得图中全为偶点那么该怎样添加重复边，使得图中全为偶点呢？呢？其实可以通过连接匹配的奇点得到！其实可以通过连接匹配的奇点得到！第一步：确定初始可行方案第一步：确定初
29、始可行方案第一步：确定初始可行方案第一步：确定初始可行方案v1v3v2v4v8v7v6v5v9254339546444图图2这样就得到初始方案这样就得到初始方案.在这个图中，没有奇点，故在这个图中，没有奇点，故称它为欧拉图。对应于这个可行方案，重复边总称它为欧拉图。对应于这个可行方案，重复边总权为权为5151。想一想想一想想一想想一想这样的可行方案是不是只有一种呢？这样的可行方案是不是只有一种呢？在确定一个可行方案后，怎么判断这个方案是否在确定一个可行方案后，怎么判断这个方案是否为最优方案？为最优方案？若不是最优方案，如何调整这个方案？若不是最优方案，如何调整这个方案？第二步：调整可行方案第二
30、步：调整可行方案第二步：调整可行方案第二步：调整可行方案 最优方案必须满足以下（最优方案必须满足以下（1 1）（）（2 2）两个条件：）两个条件：（1 1）在最优方案中）在最优方案中,图的每一边最多有一条重图的每一边最多有一条重复边复边（2 2）在最优方案中）在最优方案中,图中每个圈上的重复边的图中每个圈上的重复边的总权不大于该圈总权的一半。总权不大于该圈总权的一半。为什么为什么?第二步：调整可行方案第二步：调整可行方案第二步：调整可行方案第二步：调整可行方案首先，去掉多余的重复边，使图中每一边首先，去掉多余的重复边，使图中每一边最多有一条重复边。见图最多有一条重复边。见图3 3v1v2v3v
31、4v5v6v7v8v9444342346955图图3第二步：调整可行方案第二步：调整可行方案第二步：调整可行方案第二步：调整可行方案其次，如果把图中某个圈上的重复边去掉，而给其次，如果把图中某个圈上的重复边去掉，而给原来没有重复边的边上加上重复边，图中仍然没原来没有重复边的边上加上重复边，图中仍然没有奇点。因而如果在某个圈上重复边的总权数大有奇点。因而如果在某个圈上重复边的总权数大于这个圈的总权数的一半，像上面所说的那样做于这个圈的总权数的一半，像上面所说的那样做一次调整，将会得到一个总权下降的可行方案。一次调整，将会得到一个总权下降的可行方案。第二步：调整可行方案第二步：调整可行方案第二步：
32、调整可行方案第二步：调整可行方案在图在图4-104-10中，圈（中，圈（v v2 2,v,v3 3,v,v4 4,v,v9 9,v,v2 2）的总长度为）的总长度为2424，但圈上重复边总权为，但圈上重复边总权为1414，大于该圈总长度的一，大于该圈总长度的一半，因此可以做一次调整，以半，因此可以做一次调整，以vv2 2,v,v9 9，vv9 9,v,v4 4 上上的重复边代的重复边代vv2 2,v,v3 3，vv3 3,v,v4 4 上的重复边，使重复上的重复边，使重复边总长度下降为边总长度下降为1717。见图。见图4 4v1v2v3v4v5v6v7v8v9444342346955图图4检查
33、图检查图4 4中圈（中圈（v v1 1,v,v2 2,v,v9 9,v,v6 6,v,v7 7,v,v8 8,v,v1 1）的总长）的总长度为度为2424，但圈上重复边总权为，但圈上重复边总权为1313，大于该圈总长，大于该圈总长度的一半，因此可以做一次调整，使重复边总长度的一半，因此可以做一次调整，使重复边总长度下降为度下降为1515。见图。见图5 5。图图5检查图检查图5 5，均满足条件（，均满足条件（1 1）和（）和（2 2），于是得到最），于是得到最优方案。图优方案。图5 5中的任一欧拉圈都是汽车的最优配送中的任一欧拉圈都是汽车的最优配送路线。路线。如：如：v v1 1-v-v2 2-v-v9 9-v-v8 8-v-v1 1-v-v8 8-v-v7 7-v-v6 6-v-v5 5-v-v4 4-v-v9 9-v-v6 6-v-v9 9-v-v4 4-v v3 3-v-v2 2-v-v1 1是汽车的一条最优配送路线。是汽车的一条最优配送路线。