数学建模-图论讲稿.ppt
《数学建模-图论讲稿.ppt》由会员分享,可在线阅读,更多相关《数学建模-图论讲稿.ppt(122页珍藏版)》请在三一文库上搜索。
1、数学建模,图论方法专题,图论方法专题,最短路问题及其算法,四,最小生成树问题,图的矩阵表示,哥尼斯堡七桥示意图,问题1:七桥问题 能否从任一陆地出发通过每座桥恰好一次而 回到出发点?,数学建模-图论,七桥问题模拟图:,欧拉指出:如果每块陆地所连接的桥都是偶数座,则从任一陆地出发,必能通过每座桥恰好一次而回到出发地。,数学建模-图论,问题2:哈密顿圈(环球旅行游戏) 十二面体的20个顶点代表世界上20个城市,能 否从某个城市出发在十二面体上依次经过每个 城市恰好一次最后回到出发点?,数学建模-图论,问题3:四色问题,对任何一张地图进行着色,两个共同边界的 国家染不同的颜色,则只需要四种颜色就够了
2、。,德摩尔根致哈密顿的信(1852年10月23日) 我的一位学生今天请我解释一个我过去不知道,现在仍不甚 了了的事实。他说如果任意划分一 个图形并给各部分着上颜色,使任 何具有公共边界的部分颜色不同, 那么需要且仅需要四种颜色就够了 。下图是需要四种颜色的例子 (图1)。 ,数学建模-图论,1847年德国的克希霍夫(G.R.Kirchoff)将树的概念和实践利用于工程技巧的电网络方程组的研究; 1857年英国的凯莱(A.Cayley)也提出了树的概念,并运用于有机化合物的分子构造的研究中; 1936年匈牙利的数学家哥尼格(D.Konig)写出了第一本图论专著有限图与无穷图的理论,使图论成为一门
3、独立的学科。,图论的应用,数学建模-图论,由于管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现,大大增进了图论的发展。特别是电子计算机的大量应用,使大规模问题的求解成为可能。实际问题如电网络、交通网络、电路设计、数据结构以及社会科学中的问题所涉及到的图形都是很复杂的,需要计算机的辅助才有可能进行分析和解决。目前图论在物理、化学、运筹学、计算机科学、电子学、信息论、经济治理等几乎所有学科领域都有应用。,数学建模-图论,数学建模-图论,9,2019年9月8日,一、图的基本概念,10,2019年9月8日,一、图的基本概念,数学建模-图论,例:什么是匹配:把上图想象成3男4女搞对象(无同性
4、吸引),连线代表彼此有好感,但最终只能1夫1妻,最终的配对结果连线就就是一个匹配。 什么是最大匹配:在有好感的基础上,能够最多发展几对。,一、图的基本概念,次数为奇数顶点称为奇点,否则称为偶点。,11,2019年9月8日,数学建模-图论,常用d(v)表示图G中与顶点v关联的边的数目, d(v)称为顶点v的度数. 与顶点v出关联的边的数目称为出度,记作d +(v), 与顶点v入关联的边的数目称为入度,记作d -(v)。,用N(v)表示图G中所有与顶点v相邻的顶点的集合.,一、图的基本概念,数学建模-图论,几个基本定理:,一、图的基本概念,数学建模-图论,若将图G的每一条边e都对应一个实数F(e)
5、, 则称F(e)为该边的权, 并称图G为赋权图, 记为G = (V, E , F ).,设G = (V, E )是一个图, v0, v1, , vkV, 且“1ik, vi1 viE, 则称v0 v1 vk是G的一条通路.,如果通路中没有相同的顶点, 则称此通路为路径, 简称路.,始点和终点相同的路称为圈或回路.,一、图的基本概念,数学建模-图论,顶点u与v称为连通的,如果存在u到v通路,任二顶点都连通的图称为连通图,否则,称为非连通图。极大连通子图称为连通分图。,连通而无圈的图称为树, 常用T 表示树.,树中最长路的边数称为树的高,度数为1的顶点称为树叶。其余的顶点称为分枝点。树的边称为树枝
6、。,设G是有向图,如果G的底图是树,则称G是 有向树,也简称树。,一、图的基本概念,数学建模-图论,邻接矩阵(结点与结点的关系) 关联矩阵(结点与边的关系) 路径矩阵(任意两结点之间是否有路径) 可达性矩阵 直达矩阵 等等,二、图的矩阵表示,数学建模-图论,1 有向图的邻接矩阵 A = (aij )nn (n为结点数),例1:写出右图的邻接矩阵:,解:,二、图的矩阵表示,数学建模-图论,2 有向图的权矩阵A = (aij ) nn (n为结点数),例2:写出右图的权矩阵:,解:,二、图的矩阵表示,数学建模-图论,3 有向图的关联矩阵A =(aij )nm (n为结点数m为边数),有向图:,无向
7、图:,二、图的矩阵表示,数学建模-图论,例3:分别写出右边两图的关联矩阵,解:分别为:,二、图的矩阵表示,数学建模-图论,二、图的矩阵表示,4 应用实例,某厂生产一种弹子锁具,每个锁具的钥匙有5个槽,每个槽的高度从1,2,3,4,5,6)中任取一数由于工艺及其它原因,制造锁具时对5个槽的高度有两个限制: (1)至少有3个不同的数; (2)相邻两槽的高度之差不能为5 满足以上条件制造出来的所有互不相同的锁具称为一批我们的问题是如何确定每一批锁具的个数?,1994年全国大学生数学建模竞赛B题(锁具装箱)中关于锁具总数的问题可叙述如下:,数学建模-图论,该问题用图论中的邻接矩阵解决较为简单易见,令
8、x=t-s,其中,t代表相邻两槽高度之差不为5的锁具数,即:满足限制条件(2)的锁具数,s代表相邻两槽高度之差不为5且槽高仅有1个或2个的锁具数,即:满足限制条件(2)但不满足限制条件(1)的锁具数 我们用图论方法计算t和s.,二、图的矩阵表示(应用实例及解法分析),数学建模-图论,二、图的矩阵表示(应用实例及解法分析),在G中每一条长度为4的道路对应于一个相邻两槽高度之差不超过5的锁具,即满足限制条件(2)的锁具,反之亦然,于是可以通过G的邻接矩阵A来计算t的值,具体步骤如下:,数学建模-图论,二、图的矩阵表示(应用实例及解法分析),因此,,数学建模-图论,又令,二、图的矩阵表示(应用实例及
9、解法分析),其中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计算得到,数学建模-图论,二、图的矩阵表示(应用实例解法分析),事实上,因为,其中i=2,3,4,5,显然y1=1+(4+4+4+4-1) 4=61. 同理,计算y2时应考虑槽高只有2,21,23,24,
10、25, 26时的情形,类似计算可得 y2=1+(4+4+4+4-1)5=76 于是,s=612+764=426,x=6306-426=5880. 该算法既易理解又易操作并且又可扩展,数学建模-图论,二、图的矩阵表示(应用实例及解法分析),公交线路选择问题:在给定某城市公交线路的公交网信息后,求任意两个站点之间的最佳出行路线,包括换乘次数最少、出行时间最短、出行费用最低等。以下图的简化公交网为例来说明。,图中由两条公交线路组成,实线表示第一条线路,依次经过站点1,3,4,5,虚线表示第二条线路,依次经过站点2,3,5。,首先考虑换乘次数最少的线路选择模型,首先建立直达矩阵如下:,数学建模-图论,
11、二、图的矩阵表示(应用实例及解法分析),计算A2得到:,由于A2为非零矩阵,所以任意两站点经过换乘一次都可到达,由于问题较简单,结果显然正确。 一般地,比较A=(aij),A2=(a(2)ij), Ak=(a(k)ij)中的(i,j)元够成的向量中第一个非零向量的上标即为出行换乘的最少次数。,数学建模-图论,二、图的矩阵表示(应用实例及解法分析),接下来考虑出行时间最短的模型,建立直达距离矩阵:,下面利用Floyd矩阵算法可计算出出行时间最短的路线。定义T*T=(t(2)ij), t(2)ij=minmin1=k=5tik+tkj,tij, t(2)ij表示从站点i到站点j的至多换乘一次的最短
12、时间。,数学建模-图论,二、图的矩阵表示(应用实例及解法分析),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,计算结果为:T2 = 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,数学建模-图论,二、图的矩阵表示(应用实例及解法分析),类似
13、可计算出T3,T4,实际上T2的值已为出行路线的最短时间,例如T2(2,5)=2,说明站点2到站点5的最短时间为2站路时间。,数学建模-图论,二、图的矩阵表示(应用实例及解法分析),商人过河问题:假如有三个商人各带一名随从要过河,只有一条船,每次最多只能坐两个人。为安全起见,商人数不能少于随从数,否则随从会杀人越货。船过一次河需要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
14、, 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=(0,3,r), v17=(0,2,r), v18=(0,1,r).,数学建模-图论,二、图的矩阵表示(应用实例及解法分析),渡河可以理解为上面状态的转移,例如状态v1渡河一次可以转化为其他状态v15 v17 v18,其他状态也易列出。以V=v1, v2,. v18为顶点集,当两种状态可以互相转化时,就
15、在相应的来那个顶点间连一边,从而建立一个二分图G=,如右图所示。,G=的邻接矩阵为:,数学建模-图论,二、图的矩阵表示(应用实例及解法分析),其中,矩阵B为:,记a(k)ij为Ak中的(i,j)元,目标是使a(k)1,10不等于0的最小的 自然数k. 利用matlab容易计算出k=11,且a(11)1,10 =4,即小船至少11次才 能把所有人全部运到右岸,说明共有4种不同的过河方案。继续计 算可得出a(19)1,10 =45060,如果允许小船过河19次的话,共有 45060中不同的方案。,数学建模-图论,若将图G的每一条边e都对应一个实数F(e), 则称F(e)为该边的权, 并称图G为赋权
16、图, 记为G = (V, E , F ).,设G = (V, E )是一个图, v0, v1, , vkV, 且“1ik, vi1 viE, 则称v0 v1 vk是G的一条通路.如果通路中没有相同的顶点, 则称此通路为路径,简称路.,对于赋权图,路的长度(即路的权)通常指路上所有边 的权之和。,最短路问题:求赋权图上指定点之间的权最小的路。,三、最短路问题及其算法,数学建模-图论,重要性质:,若v0 v1 vm 是G 中从v0到vm的最短路, 则 对1km, v0v1 vk 必为G 中从v0到vk的 最短路.,即:最短路是一条路,且最短路的任一段 也是最短路。,三、最短路问题及其算法,数学建模
17、-图论,设有给定连接若干城市的公路网,寻求从指定城市到各城市的最短路线。,2、应用实例:最短路问题,问题的数学模型:,三、最短路问题及其算法,37,2019年9月8日,数学建模-图论,38,2019年9月8日,三、最短路问题及其算法,数学建模-图论,39,2019年9月8日,三、最短路问题及其算法,数学建模-图论,40,2019年9月8日,三、最短路问题及其算法,数学建模-图论,41,2019年9月8日,三、最短路问题及其算法,数学建模-图论,42,2019年9月8日,三、最短路问题及其算法,数学建模-图论,43,2019年9月8日,三、最短路问题及其算法,数学建模-图论,44,2019年9月
18、8日,三、最短路问题及其算法,数学建模-图论,45,2019年9月8日,三、最短路问题及其算法,数学建模-图论,46,2019年9月8日,三、最短路问题及其算法,数学建模-图论,Floyd算法,三、最短路问题及其算法,数学建模-图论,三、最短路问题及其算法,数学建模-图论,插入点 v1,得:,矩阵中带“=”的项为经迭代比较以后有变化的元素.,插入点 v2,得:,矩阵中带“=”的项为经迭代比较以后有变化的元素.,插入点 v3,得:,插入点 v4,得:,插入点 v5,得:,插入点 v6,得:,故从v5到v2的最短路为8,由v6向v5追溯:,由v6向v2追溯:,所以从到的最短路径为:,见Matlab
19、程序-Floyd.doc,55,2019年9月8日,三、最短路问题及其算法,数学建模-图论,56,2019年9月8日,三、最短路问题及其算法,数学建模-图论,57,2019年9月8日,三、最短路问题及其算法,数学建模-图论,58,2019年9月8日,三、最短路问题及其算法,数学建模-图论,59,2019年9月8日,三、最短路问题及其算法,数学建模-图论,60,2019年9月8日,求v1到v6的最短路问题.,三、最短路问题及其算法,数学建模-图论,61,2019年9月8日,从上图中容易得到v1到v6只有两条路:,v1v3v6和v1v4v6.,而这两条路都是v1到v6的最短路.,三、最短路问题及其
20、算法,数学建模-图论,62,2019年9月8日,三、最短路问题及其算法,数学建模-图论,(2)答案:由于T=2小时,t=1小时,V=35公里/小时,需访问,的乡镇共有17个,村共有35个. 计算出在乡(镇)及,村的总停留时间为17 2+35=69小时,要在24小时,内完成巡回,若不考虑行走时间,有: 69/i24(i为,分的组数). 得i最小为4,故至少要分4组.,由于该网络的乡(镇)、村分布较为均匀,故有可,能找出停留时间尽量均衡的分组,当分4组时各组停,停留时间大约为69/4=17.25小时,则每组分配在,路途上的时间大约为24-17.25=6.75小时.而前面讨,论过,分三组时有个总路程
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 讲稿
链接地址:https://www.31doc.com/p-3539058.html