1、玩具、照片、飞机、火箭模型玩具、照片、飞机、火箭模型 实物模型实物模型地图、电路图、分子结构图地图、电路图、分子结构图 符号模型符号模型模型模型是为了一定目的，对客观事物的一部分是为了一定目的，对客观事物的一部分进行简缩、抽象、提炼出来的进行简缩、抽象、提炼出来的原型原型的替代物的替代物模型模型集中反映了集中反映了原型原型中人们需要的那一部分特征中人们需要的那一部分特征1.2 从现实对象到数学模型从现实对象到数学模型我们常见的模型我们常见的模型你碰到过的数学模型你碰到过的数学模型“航行问题航行问题”用用 x 表示船速，表示船速，y 表示水速，列出方程：表示水速，列出方程：75050)(7503
2、0)(yxyx答：船速每小时答：船速每小时20千米千米/ /小时小时. .甲乙两地相距甲乙两地相距750千米，船从甲到乙顺水航行需千米，船从甲到乙顺水航行需30小时，小时，从乙到甲逆水航行需从乙到甲逆水航行需50小时，问船的速度是多少小时，问船的速度是多少?x =20y =5求解求解航行问题航行问题建立数学模型的基本步骤建立数学模型的基本步骤 作出简化假设（船速、水速为常数）；作出简化假设（船速、水速为常数）； 用符号表示有关量（用符号表示有关量（x, y表示船速和水速）；表示船速和水速）； 用物理定律（匀速运动的距离等于速度乘以用物理定律（匀速运动的距离等于速度乘以 时间）列出数学式子（二元
3、一次方程）；时间）列出数学式子（二元一次方程）； 求解得到数学解答（求解得到数学解答（x=20, y=5）；）； 回答原问题（船速每小时回答原问题（船速每小时20千米千米/小时）。小时）。数学模型数学模型 (Mathematical Model) 和和数学建模（数学建模（Mathematical Modeling)对于一个对于一个现实对象现实对象，为了一个，为了一个特定目的特定目的，根据其根据其内在规律内在规律，作出必要的，作出必要的简化假设简化假设，运用适当的运用适当的数学工具数学工具，得到的一个，得到的一个数学结构数学结构。建立数学模型的全过程建立数学模型的全过程（包括表述、求解、解释、检
4、验等）（包括表述、求解、解释、检验等）数学模型数学模型数学数学建模建模1.3 数学建模的重要意义数学建模的重要意义 电子计算机的出现及飞速发展；电子计算机的出现及飞速发展； 数学以空前的广度和深度向一切领域渗透。数学以空前的广度和深度向一切领域渗透。数学建模作为用数学方法解决实际问题的第一步，数学建模作为用数学方法解决实际问题的第一步，越来越受到人们的重视。越来越受到人们的重视。 在一般工程技术领域数学建模仍然大有用武之地；在一般工程技术领域数学建模仍然大有用武之地； 在高新技术领域数学建模几乎是必不可少的工具；在高新技术领域数学建模几乎是必不可少的工具； 数学进入一些新领域，为数学建模开辟了
5、许多处女地。数学进入一些新领域，为数学建模开辟了许多处女地。数学建模的具体应用数学建模的具体应用 分析与设计分析与设计 预报与决策预报与决策 控制与优化控制与优化 规划与管理规划与管理数学建模计算机技术知识经济知识经济如虎添翼如虎添翼 数学建模的基本方法数学建模的基本方法机理分析机理分析测试分析测试分析根据对客观事物特性的认识，根据对客观事物特性的认识，找出反映内部机理的数量规律找出反映内部机理的数量规律将对象看作将对象看作“黑箱黑箱”,通过对量测数据的通过对量测数据的统计分析，找出与数据拟合最好的模型统计分析，找出与数据拟合最好的模型机理分析没有统一的方法，主要通过实例研究机理分析没有统一的
6、方法，主要通过实例研究 (Case Studies)来学习。以下建模主要指机理分析。来学习。以下建模主要指机理分析。二者结合二者结合用机理分析建立模型结构用机理分析建立模型结构,用测试分析确定模型参数用测试分析确定模型参数1.4 数学建模的方法和步骤数学建模的方法和步骤 数学建模的一般步骤数学建模的一般步骤模型准备模型准备模型假设模型假设模型构成模型构成模型求解模型求解模型分析模型分析模型检验模型检验模型应用模型应用模模型型准准备备了解实际背景了解实际背景明确建模目的明确建模目的搜集有关信息搜集有关信息掌握对象特征掌握对象特征形成一个形成一个比较清晰比较清晰的的问题问题模模型型假假设设针对问题
7、特点和建模目的针对问题特点和建模目的作出合理的、简化的假设作出合理的、简化的假设在合理与简化之间作出折中在合理与简化之间作出折中模模型型构构成成用数学的语言、符号描述问题用数学的语言、符号描述问题发挥想像力发挥想像力使用类比法使用类比法尽量采用简单的数学工具尽量采用简单的数学工具 数学建模的一般步骤数学建模的一般步骤模型模型求解求解各种数学方法、软件和计算机技术各种数学方法、软件和计算机技术如结果的误差分析、统计分析、如结果的误差分析、统计分析、模型对数据的稳定性分析模型对数据的稳定性分析模型模型分析分析模型模型检验检验与实际现象、数据比较，与实际现象、数据比较，检验模型的合理性、适用性检验模
8、型的合理性、适用性模型应用模型应用 数学建模的一般步骤数学建模的一般步骤数学建模的全过程数学建模的全过程现实对象的信息现实对象的信息数学模型数学模型现实对象的解答现实对象的解答数学模型的解答数学模型的解答表述表述求解求解解释解释验证验证(归纳)(演绎)表述表述求解求解解释解释验证验证根据建模目的和信息将实际问题根据建模目的和信息将实际问题“翻译翻译”成数学问成数学问题题选择适当的数学方法求得数学模型的解答选择适当的数学方法求得数学模型的解答将数学语言表述的解答将数学语言表述的解答“翻译翻译”回实际对象回实际对象用现实对象的信息检验得到的解答用现实对象的信息检验得到的解答实践现现实实世世界界数数
9、学学世世界界理论实践 近几年全国大学生数学建模竞赛题近几年全国大学生数学建模竞赛题A 出版社的资源配置出版社的资源配置 2006 B 艾滋病疗法的评价及疗效艾滋病疗法的评价及疗效的预测的预测 A 中国人口增长预测中国人口增长预测 2007 B 乘公交，看奥运乘公交，看奥运 A 数码相机定位数码相机定位 2008 B 高等教育学费标准探讨高等教育学费标准探讨 A 制动器试验台的控制方法制动器试验台的控制方法分析分析 2009 B 眼科病床的合理安排眼科病床的合理安排 2010A储油罐的变位识别与罐容表储油罐的变位识别与罐容表标定标定B20102010年上海世博会影响力的年上海世博会影响力的定量评
10、估定量评估2011A城市表层土壤重金属城市表层土壤重金属污染分析污染分析B交巡警服务平台的设交巡警服务平台的设置与调度置与调度真是月亮惹的祸吗真是月亮惹的祸吗? ?三国人物：谁是天下第一？三国人物：谁是天下第一？图论与网络优化一、最小生成树问题二、最短路问题哥尼斯堡七桥问题哥尼斯堡七桥问题CADB抽象为图的问题：图G(V,E)能经过每条边恰好一次回到原点 每个顶点与偶数条边相关联图G(V,E)Fleury算法网络优化及实例网络优化及实例从某点出发，经过图上每条边从某点出发，经过图上每条边恰好一次回到原点恰好一次回到原点Euler环游环游图图G(V,E)有有Euler环游环游 图图G(V,E)无
11、奇点无奇点例：中国邮递员问题例：中国邮递员问题(CPP-Chinese Postman Problem)一名邮递员负责投递某个街区的邮件一名邮递员负责投递某个街区的邮件. .如何设计一条最短的如何设计一条最短的投递路线投递路线( (从邮局出发，经过投递区内每条街道从邮局出发，经过投递区内每条街道至少一次至少一次，最后返回邮局最后返回邮局) )？由于这一问题是我国学者？由于这一问题是我国学者管梅谷管梅谷教授教授19601960年首先提出的，所以国际上称之为中国邮递员问题年首先提出的，所以国际上称之为中国邮递员问题. . 例：例：1973年，John和 Edmonds结合Fleury算法给出好算法
12、图与网路的基本概念图与网路的基本概念 6.1.1 图与网路图与网路顶点顶点 (Vertex)物理实体、事物、概念物理实体、事物、概念一般用一般用 vi 表示表示边边 (Edge)顶顶点间的连线，表示有关点间的连线，表示有关联联一般用一般用 eij 表示表示图图 (Graph)顶顶点和边的集合点和边的集合一般用一般用 G(V,E) 表示表示顶顶点集点集 V=v1,v2, vn边集边集E=eij 网路网路 (Network)边上具有表示连接强边上具有表示连接强度的权值，如度的权值，如 wij又称加权图又称加权图(Weighted graph)所有边都没有方向的图称为无向图所有边都没有方向的图称为无
13、向图在无向图中在无向图中 eij=eji，或，或 (vi, vj)=(vj, vi)当所有边都有方向时，称为有向图，用当所有边都有方向时，称为有向图，用G(V,A)表示表示在有向图中，有向边又称为弧，用在有向图中，有向边又称为弧，用 aij表示，表示，i, j 的顺序的顺序是不能颠倒的，图中弧的方向用箭头标识是不能颠倒的，图中弧的方向用箭头标识图中既有边又有弧，称为混合图图中既有边又有弧，称为混合图无向图与有向图无向图与有向图返回返回完备图完备图 二元图二元图 完备二元图完备二元图 顶点的次数顶点的次数4)(4vd5)(3)(2)(444vdvdvd定理定理)(2)()(GvdGVv推论推论任
14、何图中奇次顶点的总数必为偶数例例 在一次聚会中，认识奇数个人的人数一定是偶数。返回返回子图子图定定义义设图 G=(V,E,),G1=(V1,E1,1)(1) 若 V1V，E1E,且当 eE1时，1(e)= (e),则称 G1是 G 的子子图图特别的，若 V1=V，则 G1称为 G 的生生成成子子图图(2) 设 V1V，且 V1，以 V1为顶点集、两个端点都在 V1中的图 G 的边为边集的图 G 的子图，称为 G 的由由 V1导导出出的的子子图图，记为 GV1.(3)设 E1E,且 E1,以 E1为边集,E1的端点集为顶点集的图 G 的子图,称为 G 的由由 E1导导出出的的子子图图,记为 GE
15、1. GGv1,v4,v5Ge1,e2,e3返回返回关联矩阵关联矩阵对无向图，其关联矩阵)(ijm，其中：不关联与若相关联与若jijiijevevm01M=43215432110110011000101110001vvvveeeee对有向图，其关联矩阵)(ijm，其中：不关联与若的终点是若的起点是若jijijiijevevevm011注：假设图为简单图返回返回邻接矩阵邻接矩阵对无向图，其邻接矩阵)(ijaA，其中：不相邻与若相邻与若jijiijvvvva01注：假设图为简单图A=432143210111101011011010vvvvvvvv对有向图（，） ，其邻接矩阵)(ijaA，其中：Ev
16、vEvvajijiij），若（），若（01对有向赋权图，其邻接矩阵)(ijaA，其中：EvvjiwEvvwajiijjiijij),(0,),(若若为其权且若无向赋权图的邻接矩阵可类似定义A=4321432105375083802720vvvvvvvv返回返回例 甲、乙、丙、丁、戊五个球队比赛情况。v5v1v3v4v2v1v2v3v4v5v5v1v3v4v2某单位储存八种化学药品，其中某些药品不能存放在同一个仓库，考虑所需最少仓库数v5v1v2v3v4v6v7v8至少四个库房：1，2，5，8任意两个不能同存1，3，4，7258，6 边与顶点均不重复的通路称为路径边与顶点均不重复的通路称为路径
17、路：vi1vi2vin-2vin-1vinvi3vijvik, jk1 41 1 2 54 6223v vTv e v e v e v e v路径1 41 1 2 3 3v vPv ev e v定义定义（）任意两点均有路径的图称为连通图连通图（）起点与终点重合的路径称为圈圈（）连通而无圈的图称为树树定定义义（）设 P(u,v)是赋权图 G 中从 u 到 v的路径， 则称)()()(PEeewPw为路径 P 的权权(2) 在赋权图 G 中，从顶点 u 到顶点 v的具有最小权的路 ),(*vuP，称为 u 到 v的最最短短路路返回返回无圈连通图v1v2v3v4v5v6v7v8v1v2v3v4v5v
18、6v7v8v1v2v3v4v5v6v7v8树：G的生成树(spanning tree): T(V,E)是图 G(V,E)的子图,且是一棵树最小生成树: T(V,E)是图G(V,E)所有生成树中权重最小的一棵树图与最小生成树一般研究无向图树图：倒置的树，根(root)在上，树叶(leaf)在下多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图C1C2C3C4根根叶叶例 在五个村庄之间修路，使任一村庄可到其余各村庄。已知各村庄间修路所需费用如下图，考虑费用最省方案。v5v1v2v3v450153010301025204050(万元)12345150 30 40 25250
19、 15 30 50330 15 10 10440 30 10 20525 50 10 20 问题即为求对应图的最小生成树最小生成树求解方法：避圈法；破圈法避圈法；破圈法避圈法v2v3v4501530103010252040501234v1v5v1v2v3v415101025权重为60最小生成树为：v5Kruskal算法v2v3v450153010301025204050v1v5635421权重为60最小生成树为：破圈法v5v1v2v3v415101025权矩阵v1v2 v3v4v5v1 503040 25v2501530 50v3301510 10v440301020v525501020 (w
20、ij)=第第1列叉列叉,第第1行最行最小圈小圈.圈列圈列叉叉第第1，5行行最小最小圈圈.圈列圈列叉叉v1v2 v3v4v5v1 50304025v250153050v330151010v440301020v525501020第第1,4,5行行最小最小圈圈.圈列圈列叉叉v525v1v525v1v310权矩阵v1v2 v3v4v5v1 50304025v250153050v330151010v440301020v525501020(wij)=第第1列叉列叉,第第1行最行最小圈小圈.圈列圈列叉叉第第1，5行行最小最小圈圈.圈列圈列叉叉v1v2 v3v4v5v1 50304025v250153050v
21、330151010v440301020v525501020第第1,4,5行行最小最小圈圈.圈列圈列叉叉v1v2 v3v4v5v1 50304025v250153050v330151010v440301020v525501020第第1,3,4,5行最行最小圈小圈.圈列圈列叉叉v1v2 v3v4v5v1 50304025v250153050v330151010v440301020v525501020v5v1v2v3v415101025v525v1v525v1v310v5v1v4101025v3 寻求网络中两寻求网络中两点间的最短路就是寻求连接这两个点间的最短路就是寻求连接这两个点的边的点的边的总权
22、数为最小的通路总权数为最小的通路。 管道铺设、线管道铺设、线路安排、厂区布局、设备更新等。路安排、厂区布局、设备更新等。最短路问题(非负权)从始点出发，逐步从始点出发，逐步顺序地向外顺序地向外探寻探寻，每向外延伸一步都要求是每向外延伸一步都要求是网络中网络中所有的弧权所有的弧权均均 ，即，即 。0ijw 最短路问题(非负权)例 有五个位置，其间的路都是单行道。具体方向及距离见下图。求由位置1到其他各个位置怎么走路途最短。v5v1v2v3v4244310121转化为求v1到其他所有顶点的最短路权矩阵v1v2 v3v4v5v1 110 54v2 4v3 3 2v4 2 v5 1(wij)=5v1v
23、2 v3v4v5v1 110 54v2 4v3 3 2v4 2 v5 1(wij)=第第1列叉列叉,第第1行最行最小圈小圈.圈列圈列叉叉1v1v2 v3v4v5v1 110 54v2 5v3 3 2v4 2 v5 11对应对应行加行加1,第第1,2行最行最小圈小圈,圈列圈列叉叉4对应对应行加行加4,第第1,2,5行最行最小圈小圈,圈列圈列叉叉v1v2 v3v4v5v1 110 54v2 5v3 3 2v4 2 v5 5145对应对应行加行加5,第第1,2,4,5行最行最小圈小圈,圈列圈列叉叉v1v2 v3v4v5v1 110 54v2 5v3 3 2v4 7 v5 51457可化为最短路问题的
24、多阶段决策问题可化为最短路问题的多阶段决策问题 例例 1 设备更新问题：企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的.若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用.现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少. 已知该种设备在每年年初的价格为：第一年第二年第三年第四年第五年1111121213 使用不同时间设备所需维修费为：使用年限0112233445维修费5681118（1）顶点集 V=V V V V V V123456,，Vi表第 i 年初购置新设备的决策，V6表第五年底.（2）弧集 E=(,)V Vij，i=1,2
25、,3,4,5; ij6,弧(,)V Vij表第 i 年初购进一台设备一直使用到第 j 年初的决策，其权 W(,)V Vij表由这一决策在第 i 年初到第 j 年初的总费用，如W(,)V V14=11+5+6+8=30.（3）问题转化为求V1到V6的最短路问题，求得两条最短路为VVV146，VVV136，权为 53，与图 G1(V,E)的解相同返回返回 选址问题选址问题-中心问题中心问题例例 2某城市要建立一个消防站，为该市所属的七个区服务，如图所示问应设在那个区，才能使它至最远区的路径最短（3）求出顶点kv，使)(min)(1iikvSvS则kv就是要求的建立消防站的地点此点称为图的中心点中心
26、点05 .15 .55 .86475 .10475 .45 .25 .55 .54032475 .8730571065 .42502545 .24720375 .5710530DS(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5S(v3)=6,故应将消防站设在v3处。 返回返回 选址问题选址问题-重心问题重心问题例例 3某矿区有七个矿点，如图所示已知各矿点每天的产矿量)(jvq（标在图的各顶点上） 现要从这七个矿点选一个来建造矿厂 问应选在哪个矿点，才能使各矿点所产的矿运到选矿厂所在地的总运力（千吨公里）最小（1
27、）求距离阵 D=)(ijd（2） 计算各顶点作为选矿厂的总运力)(ivm ijjjidvqvm)()(1 , 2 , 1i（3） 求kv使)(min)(1iikvmvm，则kv就是选矿厂应设之矿点此点称为图 G 的重心重心或中位点中位点返回返回e3v1v2v3v4e1e2e4e5e6欧欧 拉拉 图图e3v1v2v3v4e1e2e4e5环游 ：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉环游 ：v1e1v2e2v3e5v1e4v4e3v3e6v1图G(V,E)有Euler环游充要条件是图G(V,E)无奇点 Fleury算法算法-基
28、本思想基本思想：从任一点出发，每当访问一条边时，先要进行检查如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边割边作为访问边，直到没有边可选择为止.割边的定义割边的定义：设G连通，e E(G),若从G中删除边e后，图G-e不连通，则称边e为图G的割边V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9割边G的边e是割边的充要条件是e不含在G的圈中V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9e10Fleury 算算法法 算算法法步步骤骤 ：（）任选 一个顶点 v0，令道路 w0=v0（）假定 道路 wi=v0e1v1e2eivi已经选好，则从 E
29、e1,e2, ,ei中选一条边 ei+1，使： a）ei+1与 vi相关联b）除非不能 选择，否 则一定要 使 ei+1不是 Gi=GE-e1,e2, ,ei的割边（）第（ ）步不 能进行时 就停止中国邮递员问题中国邮递员问题- -算法算法 1、G是欧拉图是欧拉图 此时 G 的任何一个欧拉巡回便是最佳巡回问题归结为在欧拉图中确定一个欧拉巡回2、G 不是欧拉图不是欧拉图 若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次 解决这类问题的一般方法是，在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小情形情形G正好有两个奇次顶点
30、正好有两个奇次顶点（）用 Dijkstra 算法求出奇次顶点 u 与 v 之间的最短路径 P（）令 G*=GP，则 G*为欧拉图（）用 Fleury 算法求出 G*的欧拉巡回，这就是 G 的最佳巡回V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9情形情形G有有n个奇次顶点个奇次顶点（n）Edmonds 最小对集算法：最小对集算法：基 本 思 想 ： 先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小再沿点对之间的最短路径添加重复边得欧拉图 G*，G*的欧拉巡回便是原图的最佳巡回算法步骤：算法步骤：（）以 G 的所有奇次顶点为顶点集（个数为偶数） ，作一完备图，边上的权为两端
31、点在原图 G 中的最短距离，将此完备加权图记为 G1（）在 G 中沿配对顶点之间的最短路径添加重复边得欧拉图 G*（）用 Fleury 算法求出 G*的欧拉巡回，这就是 G 的最佳巡回（）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对 定定义义 设图 G =（V，E） ，ME，若 M 的边互不相邻，则称 M 是 G 的一个匹匹配配.若顶点 v与 M 的一条边关联，则称 v是 M饱和的饱和的 设 M 是 G 的一个匹配，若 G 的每个顶点都是 M饱和的，则称 M 是 G 的理理想想匹匹配配.例例求右图所示投递区的一条最佳邮递路线1图中有 v4、v7、v8、v9四个奇次顶点用 Floyd 算法
32、求出它们之间的最短路径和距离：3),(,6),(,9),(,6)(,3),(,5),(,9898979787879,49848484747234989787948474vvdvvPvvdvvPvvdvvPvvdvvvPvvdvvPvvdvvvvPvvvvvvvvvvvv2以 v4、v7、v8、v9为顶点，它们之间的距离为边权构造完备图 G13求出 G1的最小权完美匹配 M=(v4,v7),(v8,v9)4在 G 中沿 v4到 v7的最短路径添加重复边，沿 v8到 v9的最短路径 v8v9添加重复边，得欧拉图 G2G2中一条欧拉巡回就是 G 的一条最佳巡回其权值为返回返回哈哈 密密 尔尔 顿顿
33、图图定定义义设 G=(V,E)是连通无向图（） 经过 G 的每个顶点正好一次的路径，称为 G 的一条 哈哈密密尔尔顿顿路路径径（） 经过 G 的每个顶点正好一次的圈，称为 G 的哈哈密密尔尔 顿顿圈圈或 H 圈（）含 H 圈的图称为哈哈密密尔尔顿顿图图或 H 图返回返回推销员问题推销员问题- -定义定义 流动推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最小这就是推销员问题推销员问题 若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题定义定义在加权图G=(V,E)中，（）
34、权最小的哈密尔顿圈称为最佳最佳H圈圈（）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路最佳推销员回路 一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈H回路，长22最佳推销员回路，长4定定理理在加权图G=(V,E)中，若对任意x,y,zV，zx,zy,都有 w(x,y)w(x,z)+w(z,y)，则图 G 的最佳 H 圈也是最佳推销员回路最佳推销员回路问题可转化为最佳 H 圈问题方法是由给定的图 G=(V,E)构造一个以 V 为顶点集的完备图 G=(V,E)，E的每条边(x,y)的权等于顶点 x 与 y 在图中最短路的权即：x,yE w(x,y
35、)=mindG(x,y)定理定理加权图 G 的最佳推销员回路的权与 G的最佳 H 圈的权相同推销员问题近似算法：推销员问题近似算法：二边逐次修正法二边逐次修正法：（）任取初始 H 圈: C0=v1,v2,vi, ,vj,vn,v1（）对所有的 i ,j，1i+1jn,若w(vi, vj)+w(vi+1,vj+1)w(vi,vi+1)+w(vj,vj+1)则在 C0中删去边(vi,vi+1)和(vj,vj+1)而加入边(vi, vj)和(vi+1,vj+1)，形成新的 H 圈 C，即C= v1,v2,vi,vj , vj-1, ,vi+1,vj+1, ,vn,v1）对 C 重复步骤（） ，直到条件不满足为止，最后得到的C即为所求
