M051图的模型和基本概念.ppt

《M051图的模型和基本概念.ppt》由会员分享，可在线阅读，更多相关《M051图的模型和基本概念.ppt（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、行行 遍遍 性性 问问 题题一、中一、中 国国 邮邮 递递 员员 问问 题题二、推二、推 销销 员员 问问 题题三、建模案例：最佳灾情巡视路线三、建模案例：最佳灾情巡视路线2.1 哈哈 密密 尔尔 顿顿 图图2.2推推 销销 员员 问问 题题1.1 单源问题单源问题1.2 每对顶点之间的最短路每对顶点之间的最短路哥尼斯堡哥尼斯堡“七桥问题七桥问题” 给出了给出了“一笔画一笔画”成立的一个等价判别条件：成立的一个等价判别条件：欧拉欧拉图中任意两点是连通的图中任意两点是连通的每个点都与偶数条边相连每个点都与偶数条边相连 1 图的模型图的模型19981998年全国大学生年全国大学生 数学模型竞赛数学

2、模型竞赛B B题题最佳灾情巡视路线最佳灾情巡视路线：乡镇、村的公路网示意图乡镇、村的公路网示意图某县组织三路人从某县组织三路人从县政府所在地出发县政府所在地出发巡视全县各受灾乡巡视全县各受灾乡（镇）、村，又回（镇）、村，又回到县政府，设计总到县政府，设计总路程最短且各组尽路程最短且各组尽可能均衡的路线可能均衡的路线返回返回2 图的基本概念图的基本概念 定义定义 图图G是一个有序二元组(V, E)，其中 V=v1，v2，vn是一个有限非空的集合。V 中的元素称为G的结点结点, V 称为图G的结点集, 常记作V(G);E是V 中某些顶点的偶对的集合, E中的元素称为G的边边，E称为图G的边集边集,

3、 常记作E (G). 在图G中，与V 中顶点的有序偶对(vi , vj) 对应的边e, 称为图的有向边有向边(或弧弧), 而与V 中顶点的无序偶对 (vi , vj)对应的边e, 称为图的无向边无向边。每一条边都是无向边的图, 称为无向图无向图; 每一条边都是有向边的图, 称为有向图有向图;既有无向边又有有向边的图称为混合图混合图。 图G中, 如果任意两个不同的顶点都是相邻的, 则称图G是完全图完全图。如果 , ,则称图H为图G 的子图子图，记作 。特别的，如果 ，则称图H为图G 的生成子图。生成子图。 ()()V HV G ()()E HE G HG ()( )V HV G 在无向图G中，若

4、边e=(vi，vj)，则称vi、vj为边e的端端点点，并称顶点vi与vj相邻相邻，称边e与顶点vi、vj关联关联；如果某两条边至少有一个公共端点，则称这两条边在图G中相邻相邻。在有向图G中，若e=(vi，vj)，即箭头由vi指向vj，则称vi相邻到相邻到vj ，vi称为e的起点起点，vj称为e的终点终点。 在无向图G中，与顶点v关联的边的数目称为v的次数次数，记为d(v)。 例题例题 在有向图G中，从顶点v引出的弧的数目称为v的出度出度，记为d +(v)；从顶点v引入的弧的数目称为v的入度入度,记为d -(v) ；d(v)=d +(v)+d -(v)称为v的次数次数。 点边交替序列 l= v0

5、 e1 v1 e2 ek vk，其中vjV（G），），0jk，eiE（G），），0ik ，ei与vi-1,vi 关联，称l是图是图G 的一条路径路径，k为路长路长，顶点v0和vk k分别称为l的起点起点和终点终点，而 v1,v2 vk-1称为它的内部顶点内部顶点。 若路径l 的边不重复，则称 l 为简单路径简单路径（或迹迹）； 若图G 的两个顶点u 、v间存在路径，则称u和v连通连通。若图G的任两个顶点均连通，则称G为连通图连通图。连通而无圈的图称为树树。如果图G的生成子图H是树，则称H为图G的生成树生成树。 例题例题若路径l 的顶点不重复，则称l为基本路径基本路径（或链链）。起点和终点重合的

6、路径称为回路回路；起点和终点重合的简单路径称为简单回路简单回路；起点和终点重合的基本路径称为基本回路基本回路（或圈圈）。 若将图G的每一条边e都对应一个实数w(e)，称w(e)为边e的权权，并称图G为赋权图赋权图。 赋权图G中从顶点u到顶点v的一条路径上所有边的权之和,称为该路径的权权，记作d(u, v). 赋权图G中从顶点 u 到顶点 v 的具有最小权的路径，称为u到v的最短路最短路。返回返回 例例 图G如右图所示，是一个有向图 顶点集Vv1, v2, v3, v4, v5边集E=e1, e2, e3, e4, e5, e6, e7, e8点v2的出度d+(v2)=1，入度d-(v2)=2

7、,度d(v2)= 3图 5.3（b） v1e1v2e2v3e3v4e4v2e2v3e7v5e6v4e5v1是一条回路，不是简单回路 v1e1v2e2v3e7v5e8v3e3v4e5v1是一条简单回路，不是基本回路 v1e1v2e2v3e7v5e6v4e5v1是一条基本回路（圈）（圈）返回返回 图5.3（a）图5.3（b）是图5.3（a）的生成树三、三、 图的矩阵表示图的矩阵表示(1)(1)邻接矩阵邻接矩阵图G =(V,E)的邻接矩阵 C是一个n n 的0-1矩阵, 即()0,1n nijn nCc 1, ( , )0, ( , )iji jEci jE (2)(2)关联矩阵关联矩阵图G =(V

8、,E)的关联矩阵B是一个n m 的矩阵，即() 1,0,1n mikn mBb , , 1,()1,()0jkijikjkjiikvV ev vEbvV ev vEve 与与不不关关联联 例题例题返回返回图 5.3（a） 0100000100000111100000110C1000100011010000011000110011110000000111B返回返回例1 1 单源问题单源问题最短路的性质：最短路中的任一段子路径也是最短路。迪克斯特拉迪克斯特拉（Dijkstra）算法算法的基本思想基本思想： 按距起点u0 0从近到远的顺序，依次求得u0 0到G的各顶点的最短路径和距离，直至G中距起点

9、u0 0最远的顶点。Dijkstra算法的步骤： l(v) ：从顶点u0到v的一条路的权 pri (v) ：v的前驱点，用以逆序查找最短路径 i ：更新次数 v*： 中距离u0最近的顶点Ui：第i 次更新确定其最短路的顶点Si ：第i 次更新时确定的顶点集iS .0000000Step 1()0( )( )0Sul uUuvul vpri vUi 令，对，令， .*111Step 2 ()()()( )( )()()( )() = min ( ) iiiiiiiii*i+i+ii+v SvS SVSl Uw U ,vl vl vl Uw U ,vpri vUl vl vUvSSU 对每个，若，

10、则，否则不变计算得到令， Step 3| 1| 11Step 2iViVii 若，结束；若，令，转例返回返回2 2 每对顶点之间的最短路每对顶点之间的最短路Floyd算法的基本思想： 通过依次插入结点 v1, v2, , vk, , vn，递推产生两个矩阵序列 D0, D1, , Dk, , Dn ，path0, path1, , pathk, , pathn ，其中Dk(i，j) 表示赋权图中从结点vi 出发仅通过v1, v2, , vk 中的某些结点到达 vj的最短路径的长度， pathk(i，j)表示从 vi到vj 的当前最短路径中起点 vi的后继结点的标号。计算时用迭代公式：,111(

11、)min()()()kkkkDi, jDi, jDi,kDk, j Floyd算法的步骤： 00(,)(,)( , )0(,)( , )ijijijw v vv vED i jijv vE path i jj 若若若若若若Step 1 初始化矩阵 D、path ，令Step 2 刷新 D、path 对k=1,2,，n 重复Step 3和和Step 4 Step 3 刷新行 对 i=1,2,，n 重复Step 4 Step 4 刷新D k(i，j)、pathk (i，j)对 j=1,2,，n 111( , )min( , ),( , )( , )kkkkD i jDi jDi kDk j 111

12、1( , )( , )( , )( , )( , )( , )kkkkkkpathi kDi jDi kDk jpath i jpathi j 若 否则 Step 5 结束迭代，得到 Dk即是各点之间的最短路径值矩阵 结束Step 4循环 结束Step 3循环结束Step 2循环 例题例题返回返回例 某公司在六个城市中有分公司，从城市 ci到城市 cj的 直接航程票价如下表所示（表示无直接航路），请帮助该公司设计一张城市间的票价最便宜的路线图。票价票价城市城市1 城市城市 2城市城市3 城市城市 4城市城市 5城市城市6 城市城市 1050402510城市城市2 500152025城市城市 3

13、1501020城市城市4 40201001025城市城市5 252010055城市城市 6102525550 11 0 50 40 25 1050 0 15 20 75 25 15 0 10 20 c40 20 10 0 10 2525 75 20 10 0 3510 25 25 35 0D ，插插入入得得,1 1 2 3 4 5 6 1 2 3 4 1 6 1 2 3 4 5 6 1 2 3 4 5 6 1 1 3 4 5 1 1 2 3 path 4 1 622 0 50 65 40 25 1050 0 15 20 75 2565 15 0 10 20 40c40 20 10 0 10 2

14、525 75 20 10 0 3510 25 40 25 35 D ，插插入入得得2, 1 2 2 4 5 6 1 2 3 4 1 6 2 2 3 4 5 2 1 2 3 4 5 6 1 1 3 4 5 10 1 2 2 path4 1 6 ,000504025101 2 3 4 5 6500152025 1 2 3 4 5 61501020 1 2 3 4 5 640201001025 1 2 252010055102525550Dpath ，初初始始化化得得 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6返回返回33 0 50 65 40 25 1050 0 15 20 3

15、5 2565 15 0 10 20 40c40 20 10 0 10 2525 35 20 10 0 3510 25 40 25 35 D ，插插入入得得3, 1 2 2 4 5 6 1 2 3 4 3 6 2 2 3 4 5 2 1 2 3 4 5 6 1 3 3 4 5 10 1 2 2path 4 1 644 0 50 50 40 25 1050 0 15 20 30 2550 15 0 10 20 3540 20 10 0 10 2525 30 20 10 0 3510 25 35 25 35 D c ，插插入入得得4, 1 2 4 4 5 6 1 2 3 4 4 6 4 2 3 4

16、5 4 1 2 3 4 5 6 1 4 3 4 5 10 1 2 4path 4 1 655 0 50 45 35 25 1050 0 15 20 30 2545 15 0 10 20 35c35 20 10 0 10 2525 30 20 10 0 3510 25 35 25 35 D ，插插入入得得5 1 2 5 5 5 6 1 2 3 4 4 6 5 2 3 4 5 4, 5 2 3 4 5 6 1 4 3 4 5 10 1 2 4path 4 1 666 0 35 45 35 25 1035 0 15 20 30 2545 15 0 10 20 35c35 20 10 0 10 252

17、5 30 20 10 0 3510 25 35 25 35 D ，插插入入得得, 1 6 5 5 5 6 6 2 3 4 4 6 5 2 3 4 5 4 5 2 3 4 5 6 1 4 3 4 5 10 1 2 46path 4 1 6D6(1，2)=35，故从c1 到 c2的最短距离为35 path6(1，2)=6， c1的后继点是c6 ；又 path6(6，2)=2， c6的后继点是c2 ；故 c1 到 c2 的最短路径是c1 c6 c2返回返回1 1 哈密顿路径问题哈密顿路径问题 哈密顿(Hamilton)道路问题是1859年发明的一种游戏：在一个实心的正十二面体，20个顶点标上世界著名

18、大城市的名字，要求游戏者从某一城市出发，遍历所有城市仅一次，最后回到原地。这就是“绕行世界”问题。哈哈 密密 尔尔 顿顿 图图返回返回定义定义在加权图G=(V,E)中，（）权最小的哈密尔顿圈称为最佳最佳H圈圈（）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路最佳推销员回路 一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈H回路，长22最佳推销员回路，长4定定理理加权图 G的最佳推销员回路的权与 G的最佳 H 圈的权相同无向赋权完全图，一种简单的构造H圈算法最邻近算法最邻近算法：初步改进初步改进:Step 1 找一条最短的边ei 。Step 2

19、以关联 ei的两个顶点 vi1、 vi2分别作为起点，用最邻 近算法求最佳H圈。Step 3 再比较这两条回路的长度，以确定最短的一条。 Step 1 从任一顶点出发，记为 v1,找一个与 v1最近的顶点v2 , (v1 , v2 )为两个顶点的基本道路。Step 2 若已找出有p个顶点的基本道路( v1 , v2 , vp ), pn，在道路外找一个离 vp最近的顶点, 记为vp1 ， 将其加入则得到具有p +1个顶点的基本道路。Step 3 若p +1 =n ，转step4，否则转Step2。Step 4 闭合回路：即增加一条边( vn , v1 ), 则( v1 , v2 , vp ,v

20、1 ) 为一条近似的最短H圈。 例题例题返回返回dceab141113812910567d714865cbae最邻近算法所求为：(a，c，e，d，b，a)总长为 768514=40实际最佳H圈： (a，c，e， b， d，a) 总长为769510=37改进: : (b，d)边长为5，是最短边。以b作起点得：(b，d，e，c， a ， b), 总长为40以d作起点得： (d ，b ，e，c， a ， d), 总长为37例返回返回对已构造的Hamilton圈改良的算法二次逐边修正法二次逐边修正法：Step 1 构造初始圈C v1v2 vnv1。Step 2 对于所有 i、j ，1 i+1jn ，构

21、造新的Hamilton圈： Cij v1v2 vivj vj-1vj-2 vi+1vj+1 vj+2 vnv1 它是由 C中删去边 vivi+1和vj vj+1 ，添加边 vivj和vi+1vj+1 而得到的，如图所示。 若 w(vivj)+w(vi+1vj+1) w(vivi+1)+w(vjvj+1) ， 则令 C Cij ，Cij叫做 C的改良圈。Step 3 对更新的C重复步骤2，直至对所有 i、j 都不存在改良圈 Cij ，停止。注意：用二次逐边修正算法得到的结果一般不是最优解。可选择不同的初始圈，重复进行几次算法，再从中选优以求得较精确的结果。返回返回例例对以下完备图，用二边逐次修正法求较优对以下完备图，用二边逐次修正法求较优H圈圈返回返回32 结束语结束语