数学建模-图论讲.ppt

1、数学建模,图论方法专题,图论方法专题,最短路问题及其算法,四,最小生成树问题,图的矩阵表示,数学建模-图论,3,2020年11月12日,一、图的基本概念,数学建模-图论,4,2020年11月12日,一、图的基本概念,一、图的基本概念,次数为奇数顶点称为奇点，否则称为偶点。,5,2020年11月12日,数学建模-图论,常用d(v)表示图G中与顶点v关联的边的数目, d(v)称为顶点v的度数. 与顶点v出关联的边的数目称为出度，记作d +(v)， 与顶点v入关联的边的数目称为入度，记作d -(v)。,用N(v)表示图G中所有与顶点v相邻的顶点的集合.,任意两顶点都相邻的简单图称为完全图. 有n个顶

2、点的完全图记为Kn 。,一、图的基本概念,数学建模-图论,几个基本定理：,一、图的基本概念,数学建模-图论,若将图G的每一条边e都对应一个实数F(e), 则称F(e)为该边的权, 并称图G为赋权图, 记为G = (V, E , F ).,设G = (V, E )是一个图, v0, v1, , vkV, 且“1ik, vi1 viE, 则称v0 v1 vk是G的一条通路.,如果通路中没有相同的顶点, 则称此通路为路径, 简称路.,始点和终点相同的路称为圈或回路.,一、图的基本概念,数学建模-图论,顶点u与v称为连通的，如果存在u到v通路，任二顶点都连通的图称为连通图，否则，称为非连通图。极大连通

3、子图称为连通分图。,连通而无圈的图称为树, 常用T 表示树.,树中最长路的边数称为树的高，度数为1的顶点称为树叶。其余的顶点称为分枝点。树的边称为树枝。,设G是有向图，如果G的底图是树，则称G是 有向树，也简称树。,一、图的基本概念,数学建模-图论,邻接矩阵（结点与结点的关系） 关联矩阵（结点与边的关系） 路径矩阵（任意两结点之间是否有路径） 可达性矩阵 直达矩阵 等等,二、图的矩阵表示,数学建模-图论,1 有向图的邻接矩阵 A = (aij )nn （n为结点数）,例1：写出右图的邻接矩阵：,解：,二、图的矩阵表示,数学建模-图论,2 有向图的权矩阵A = (aij ) nn （n为结点数）

4、,例2：写出右图的权矩阵：,解：,二、图的矩阵表示,数学建模-图论,3 有向图的关联矩阵A =(aij )nm （n为结点数m为边数）,有向图：,无向图：,二、图的矩阵表示,数学建模-图论,例3：分别写出右边两图的关联矩阵,解：分别为：,二、图的矩阵表示,数学建模-图论,二、图的矩阵表示,4 应用实例,某厂生产一种弹子锁具，每个锁具的钥匙有5个槽，每个槽的高度从1，2，3，4，5，6)中任取一数由于工艺及其它原因，制造锁具时对5个槽的高度有两个限制： (1)至少有3个不同的数； (2)相邻两槽的高度之差不能为5 满足以上条件制造出来的所有互不相同的锁具称为一批我们的问题是如何确定每一批锁具的个

5、数?,1994年全国大学生数学建模竞赛B题(锁具装箱)中关于锁具总数的问题可叙述如下：,数学建模-图论,该问题用图论中的邻接矩阵解决较为简单 易见， x=t-s，其中，t代表相邻两槽高度之差不为5的锁具数，即：满足限制条件(2)的锁具数，s代表相邻两槽高度之差不为5且槽高仅有1个或2个的锁具数，即：满足限制条件(2)但不满足限制条件(1)的锁具数 我们用图论方法计算t和s.,数学建模-图论,二、图的矩阵表示（应用实例及解法分析）,在G中t每一条长度为4的道路对应于一个相邻两槽高度之差不超过5的锁具，即满足限制条件（2）的锁具，反之亦然，于是可以通过G的邻接矩阵A来计算t的值，具体步骤如下：,数

6、学建模-图论,二、图的矩阵表示（应用实例及解法分析）,因此，,数学建模-图论,二、图的矩阵表示（应用实例及解法分析）,又令,其中yi表示满足限制条件(2)但不满足限制条件(1)且首位为i的锁具数,（i=1,2,3,4,5,6),显然y1=y6, y2=y4=y3=y5,于是我们只需要计算y1和y2. 计算y1可分别考虑槽高只有1，12，13，14，15的情形若只有1，这样的锁具效只有1个， 若只有1和i(i=2,3,4,5)，这样的锁具数=G中以1和i为顶点，长度为3的道路数，此数可通过A的子矩阵A1i计算得到,数学建模-图论,二、图的矩阵表示（应用实例及解法分析）,二、图的矩阵表示（应用实例

7、解法分析）,事实上，因为,其中i=2,3,4,5,显然y1=1+(4+4+4+4-1) 4=61. 同理，计算y2时应考虑槽高只有2,21,23,24,25, 26时的情形，类似计算可得 y2=1+(4+4+4+4-1)5=76 于是，s=612+764=426，x=6306-426=5880. 该算法既易理解又易操作并且又可扩展,数学建模-图论,二、图的矩阵表示（应用实例及解法分析）,公交线路选择问题：在给定某城市公交线路的公交网信息后，求任意两个站点之间的最佳出行路线，包括换乘次数最少、出行时间最短、出行费用最低等。以下图的简化公交网为例来说明。,数学建模-图论,图中由两条公交线路组成，实

8、线表示第一条线路，依次经过站点1,3,4,5，虚线表示第二条线路，依次经过站点2,3,5。,首先考虑换乘次数最少的线路选择模型，首先建立直达矩阵如下：,二、图的矩阵表示（应用实例及解法分析）,数学建模-图论,计算A2得到：,由于A2为非零矩阵，所以任意两站点经过换乘一次都可到达，由于问题较简单，结果显然正确。 一般地，比较A=(aij),A2=(a(2)ij), Ak=(a(k)ij)中的(i,j)元够成的向量中第一个非零向量的上标即为出行换乘的最少次数。,二、图的矩阵表示（应用实例及解法分析）,数学建模-图论,接下来考虑出行时间最短的模型，建立直达距离矩阵：,下面利用Floyd矩阵算法可计算

9、出出行时间最短的路线。定义T*T=(t(2)ij), t(2)ij=minmin1=k=5tik+tkj,tij, t(2)ij表示从站点i到站点j的至多换乘一次的最短时间。,二、图的矩阵表示（应用实例及解法分析）,数学建模-图论,4,利用matlab编写程序如下： T=0 inf 1 2 3;inf 0 1 inf 2; 1 1 0 1 1; 2 inf 1 0 1; 3 2 1 1 0; n=length(T); T2=zeros(n); for i=1:n for j=1:n T2(i,j)=min(min(T(i,:)+T(:,j),T(i,j); end end T2,计算结果为：T

10、2 = 0 2 1 2 2 2 0 1 2 2 1 1 0 1 1 2 2 1 0 1 2 2 1 1 0,二、图的矩阵表示（应用实例及解法分析）,数学建模-图论,类似可计算出T3，T4，实际上T2的值已为出行路线的最短时间，例如T2（2,5）=2，说明站点2到站点5的最短时间为2站路时间。,思考：最省乘车费用的最佳出行路线该如何考虑呢？（分情况讨论） （1）按路程收费；（出行时间最短） （2）按换乘次数收费。（最少换乘次数）,二、图的矩阵表示（应用实例及解法分析）,数学建模-图论,商人过河问题：假如有三个商人各带一名随从要过河，只有一条船，每次最多只能坐两个人。为安全起见，商人数不能少于随从

11、数，否则随从会杀人越货。船过一次河需要5分钟，问最短几分钟能使他们都过去？,用邻接矩阵来解决：设(m,n,l)表示左岸商人m人，随从n人；设(m,n,r)表示右岸有商人m人，随从n人。从左岸到右岸去，所有可能的状态为： v1=(3,3,l), v2=(3,2,l), v3=(3,1,l), v4=(3,0, l), v5=(2,2,l), v6=(1,1,l), v7=(0,3,l), v8=(0,2,l), v9=(0,1,l), v10=(3,3,r), v11=(3,2,r), v12=(3,1,r), v13=(3,0,r), v14=(2,2,r), v15=(1,1,r), v16

12、=(0,3,r), v17=(0,2,r), v18=(0,1,r).,二、图的矩阵表示（应用实例及解法分析）,数学建模-图论,渡河可以理解为上面状态的转移，例如状态v1渡河一次可以转化为其他状态v15 v17 v18，其他状态也易列出。以V=v1, v2,. v18为顶点集，当两种状态可以互相转化时，就在相应的来那个顶点间连一边，从而建立一个二分图G=，如右图所示。,G=的邻接矩阵为：,二、图的矩阵表示（应用实例及解法分析）,数学建模-图论,其中，矩阵B为：,记a(k)ij为Ak中的（i,j）元，目标是使a(k)1,10不等于0的最小的 自然数k. 利用matlab容易计算出k=11，且a(

13、11)1,10 =4,即小船至少11次才 能把所有人全部运到右岸，说明共有4种不同的过河方案。继续计 算可得出a(19)1,10 =45060，如果允许小船过河19次的话，共有 45060中不同的方案。,若将图G的每一条边e都对应一个实数F(e), 则称F(e)为该边的权, 并称图G为赋权图, 记为G = (V, E , F ).,设G = (V, E )是一个图, v0, v1, , vkV, 且“1ik, vi1 viE, 则称v0 v1 vk是G的一条通路.如果通路中没有相同的顶点, 则称此通路为路径,简称路.,对于赋权图，路的长度（即路的权）通常指路上所有边 的权之和。,最短路问题：求

14、赋权图上指定点之间的权最小的路。,三、最短路问题及其算法,数学建模-图论,重要性质：,若v0 v1 vm 是G 中从v0到vm的最短路, 则 对1km, v0v1 vk 必为G 中从v0到vk的 最短路.,即：最短路是一条路，且最短路的任一段 也是最短路。,数学建模-图论,三、最短路问题及其算法,设有给定连接若干城市的公路网，寻求从指定城市到各城市的最短路线。,2、应用实例：最短路问题,问题的数学模型:,三、最短路问题及其算法,31,2020年11月12日,数学建模-图论,32,2020年11月12日,三、最短路问题及其算法,数学建模-图论,33,2020年11月12日,三、最短路问题及其算法

15、,数学建模-图论,34,2020年11月12日,三、最短路问题及其算法,数学建模-图论,35,2020年11月12日,三、最短路问题及其算法,数学建模-图论,36,2020年11月12日,三、最短路问题及其算法,数学建模-图论,37,2020年11月12日,三、最短路问题及其算法,数学建模-图论,38,2020年11月12日,三、最短路问题及其算法,数学建模-图论,39,2020年11月12日,三、最短路问题及其算法,数学建模-图论,40,2020年11月12日,三、最短路问题及其算法,数学建模-图论,41,2020年11月12日,三、最短路问题及其算法,数学建模-图论,42,2020年11月

16、12日,三、最短路问题及其算法,数学建模-图论,43,2020年11月12日,三、最短路问题及其算法,数学建模-图论,44,2020年11月12日,三、最短路问题及其算法,数学建模-图论,45,2020年11月12日,数学建模-图论,三、最短路问题及其算法,46,2020年11月12日,数学建模-图论,求v1到v6的最短路问题.,三、最短路问题及其算法,47,2020年11月12日,数学建模-图论,从上图中容易得到v1到v6只有两条路：,v1v3v6和v1v4v6.,而这两条路都是v1到v6的最短路.,三、最短路问题及其算法,48,2020年11月12日,三、最短路问题及其算法,数学建模-图论

17、,顶点u与v称为连通的，如果存在u-v通路，任二顶点都连通的图称为连通图，否则，称为不连通图。极大连通子图称为连通分图。,连通而无圈的图称为树, 常用T 表示树.,树中最长路的边数称为树的高的度为1的顶点称为树叶。其余的顶点称为分枝点。树的边称为树枝。,设G是有向图，如果G的底图是树，则称G是 有向树，也简称树。,四、最小生成树问题及其算法,数学建模-图论,若任意一个连通的图G=的生成子图T=(V=V,E为E的子集)为树, 这棵树T称为图G的生成树.,设T是图G的一棵生成树, 用F (T)表示树T中所有边的权数之和, F(T)称为树T的权.,一个连通图G的生成树一般不止一棵, 图 G的所有生成

18、树中权数最小的生成树称为 图G的最小生成树.,数学建模-图论,四、最小生成树问题及其算法,怎样找出最小生成树？,G T1 T2,T3 T4 T5,T6 T7 T8,T1至T8是 图G的生 成树,数学建模-图论,四、最小生成树问题及其算法,Kruskal 算法 思想：在不形成圈得条件下，优先挑选权小的边形成生成树。,数学建模-图论,四、最小生成树问题及其算法,注：算法构造的最小生成树的边集为 E1；标号 l 具有性质：当且仅当 u、v 之间有一条仅由 E1 中的边形成的路时，l(u) = l(v)，因此在步骤 (2) 发现 l(u) = l(v) 时，(u, v) 不能放入 E1，否则会形成一个

19、圈。,数学建模-图论,四、最小生成树问题及其算法,54,2020年11月12日,四、最小生成树问题及其算法,数学建模-图论,55,2020年11月12日,四、最小生成树问题及其算法,数学建模-图论,56,2020年11月12日,四、最小生成树问题及其算法,数学建模-图论,运行结果如下： T = 1 3 5 1 6 3 2 6 6 6 7 4 c = 26,上述例题的matlab程序如下： b=1 1 2 2 3 3 3 4 5 5 6;2 6 3 6 4 6 7 7 6 7 7;2 4 4 5 8 3 7 8 3 7 6; Krusf(b,1);,57,2020年11月12日,四、最小生成树问

20、题及其算法,数学建模-图论,58,2020年11月12日,四、最小生成树问题及其算法,数学建模-图论,59,2020年11月12日,四、最小生成树问题及其算法,数学建模-图论,60,2020年11月12日,四、最小生成树问题及其算法,数学建模-图论,运行结果如下： T = 1 1 6 6 6 3 2 6 3 5 7 4 c = 2 4 3 3 6 8,例：分别利用Kruskal算法和Prim算法如图G的最小生成树：,四、最小生成树问题及其算法,数学建模-图论,称经过图 G = (V , E ) 的每条边恰好一次的路为 Euler路径，经过G 的每条边恰好一次的回路为 Euler回路。称有 Eu

21、ler 回路的图为 Euler图,五、E图与H图问题,数学建模-图论,命题：G 是 Euler 图当且当G 连通且没有度数为奇数的点； G 有 Euler 路径当且仅当 G 连通且没有或只有二个度数为基数的点。,4 个点的度数皆为奇数，不存在 Euler 路,中国邮递员问题： 一个邮递员从邮局取出邮件后，需要到他管辖区域内的每条街道进行投递，送完邮件后返回邮局，问如何选择一条总路程最短的投递路线？,以街道为边，街道的交叉口或端点为点，街道的长度为权，构造赋权图G =(V,E,w)。投递路线应是一条经过G的每条边至少一次的回路。,数学建模-图论,五、E图与H图问题,将G的度数为奇数的点（必为偶数

22、个）两个一组、两个一组用最短路连结起来。,如何分组可以使得重复路径的总长度最短？,数学建模-图论,五、E图与H图问题,数学建模-图论,五、E图与H图问题,若G是Euler图，则任何一条Euler回路是最短投递路线,都满足条件，针对这种情况，Fleury提出一种算法，能够在Euler图中找出Euler路径，解决了邮递员问题；,若G 不是Euler图，则投递路线将重复经过某些街道，最优投递路线应使得重复经过的街道的总长度最短。,例如，确定右图是否Euler图，若是，找出图中的Euler回路。,66,2020年11月12日,数学建模-图论,五、E图与H图问题,67,2020年11月12日,数学建模-

23、图论,五、E图与H图问题,68,2020年11月12日,数学建模-图论,五、E图与H图问题,69,2020年11月12日,数学建模-图论,五、E图与H图问题,70,2020年11月12日,数学建模-图论,五、E图与H图问题,71,2020年11月12日,数学建模-图论,五、E图与H图问题,上述例题的Matlab程序如下： clear d=0 1 1 1 1 1 ;1 0 1 1 1 1;1 1 0 1 1 1;1 1 1 0 1 1;1 1 1 1 0 1;1 1 1 1 1 0; T=Fleuf1(d);,例：确定所示的赋权图是否Euler图，若是，找出图中的Euler回路。,数学建模-图论

24、,五、E图与H图问题,73,2020年11月12日,数学建模-图论,五、E图与H图问题,运行结果如下： T = 1 5 4 3 5 5 4 3 2 1 c = 5 d = 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0,称经过图 G =(V,E)的每个点恰好一次的路为Hamilton路，经过G的每个点恰好一次的回路为Hamilton回路。称有Hamilton回路的图为Hamilton图。,十二面体的平面嵌入为 Hamilton 图,Hamilton 图与 Euler 图在定义上很相似，但判断一个图是否 Hamilton 图较判断它是否 Eul

25、er 图要困难得多，目前还没有易验证的充要条件。,数学建模-图论,五、E图与H图问题,在国际象棋中，马跳动一次只能沿着一个 23 的长方形的对角线从一个角跳到另一个角，问是否存在一串符合规定的着法使得马可以从任一格子出发跳遍 88 的整个棋盘，并只到达每个格子一次？,数学建模-图论,五、E图与H图问题,旅行推销员问题 （货郎担问题）,一个推销员要去一些城市访问他的客户然后返回出发城市，问如何选择旅行路线可以使得总路程最短？,以城市为点，以两个城市之间的旅行距离为权，构造一个赋权完全图 G = (V ,E ,w) 。,推销员的旅行路线应是G 的一条经过每个点至少一次的回路，且回路的长度尽可能短。

26、,数学建模-图论,五、E图与H图问题,与最短路问题相反，至今未找到有求解旅行商问题的有效算法，我们试图寻找一个比较好的方法，但不一定是最优解；首先给出近似最优的改良后的最邻近算法，称为改良圈算法，改良圈算法是一种近似算法，给出的结果不一定是最优的，但是有理由认为它常常是比较好的。 该算法的matlab程序为：,数学建模-图论,五、E图与H图问题,78,2020年11月12日,数学建模-图论,五、E图与H图问题,79,2020年11月12日,数学建模-图论,五、E图与H图问题,例：给定4个点的坐标为(0,0),(100,1000),(0,2),(1000,0),试用改良圈算法求通过这4个点的Hamilton圈。,