数学建模图论讲稿.pptx

《数学建模图论讲稿.pptx》由会员分享，可在线阅读，更多相关《数学建模图论讲稿.pptx（122页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论方法专题图论方法专题一一图的基本概念二二三三最短路问题及其算法四四最小生成树问题五五E图与H图图的矩阵表示六六网络最大流第1页/共122页ABCD哥尼斯堡七桥示意图问题1:七桥问题能否从任一陆地出发通过每座桥恰好一次而回到出发点？数学建模-图论第2页/共122页七桥问题模拟图:ABDC欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地。数学建模-图论第3页/共122页问题2:哈密顿圈（环球旅行游戏）十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？数学建模-图论第4页/共122页问题

2、3:四色问题 对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了。德摩尔根致哈密顿的信（1852年10月23日）我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分着上颜色，使任何具有公共边界的部分颜色不同，那么需要且仅需要四种颜色就够了。下图是需要四种颜色的例子（图1）。数学建模-图论第5页/共122页1847年德国的克希霍夫(G.R.Kirchoff)将树的概念和实践利用于工程技巧的电网络方程组的研究；1857年英国的凯莱(A.Cayley)也提出了树的概念，并运用于有机化合物的分子构造的研究中；1936年匈牙利的数

3、学家哥尼格(D.Konig)写出了第一本图论专著有限图与无穷图的理论，使图论成为一门独立的学科。图论的应用 数学建模-图论第6页/共122页由于管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现，大大增进了图论的发展。特别是电子计算机的大量应用，使大规模问题的求解成为可能。实际问题如电网络、交通网络、电路设计、数据结构以及社会科学中的问题所涉及到的图形都是很复杂的，需要计算机的辅助才有可能进行分析和解决。目前图论在物理、化学、运筹学、计算机科学、电子学、信息论、经济治理等几乎所有学科领域都有应用。数学建模-图论第7页/共122页 数学建模-图论82023年3月25日 一、图的基本概念

4、一、图的基本概念第8页/共122页92023年3月25日 一、图的基本概念一、图的基本概念 数学建模-图论例：什么是匹配：把上图想象成3男4女搞对象（无同性吸引），连线代表彼此有好感，但最终只能1夫1妻，最终的配对结果连线就就是一个匹配。什么是最大匹配：在有好感的基础上，能够最多发展几对。第9页/共122页 一、图的基本概念一、图的基本概念次数为奇数顶点称为次数为奇数顶点称为奇点奇点，否则称为否则称为偶点偶点。102023年3月25日 数学建模-图论第10页/共122页常用常用d d(v v)表示图表示图G G中与顶点中与顶点v v关联的边的数目关联的边的数目,d d(v v)称为顶点称为顶点

5、v v的度数的度数.与顶点与顶点v v出关联的边的数目称为出关联的边的数目称为出度出度，记作，记作d d +(v v)，与顶点与顶点v v入关联的边的数目称为入关联的边的数目称为入度入度，记作，记作d d -(v v)。用用N N(v v)表示图表示图G G中所有与顶点中所有与顶点v v相邻的顶点的集合相邻的顶点的集合.一、图的基本概念一、图的基本概念数学建模-图论第11页/共122页几个基本定理：几个基本定理：一、图的基本概念一、图的基本概念数学建模-图论第12页/共122页 若将图若将图G G的每一条边的每一条边e e都对应一个实数都对应一个实数F F(e e),则称则称F F(e e)为

6、该边的为该边的权权,并称图并称图G G为为赋权图赋权图,记为记为G G=(=(V V,E E,F F ).设设G G=(=(V V,E E)是一个图是一个图,v v0 0,v v1 1,v vk kV V,且且“11i ik k,v vi i1 1 v vi iE E,则称则称v v0 0 v v1 1 v vk k是是G G的一条的一条通路通路.如果通路中没有相同的顶点如果通路中没有相同的顶点,则称此通路为则称此通路为路径路径,简称简称路路.始点和终点相同的路称为始点和终点相同的路称为圈圈或或回路回路.一、图的基本概念一、图的基本概念数学建模-图论第13页/共122页 顶点顶点u u与与v

7、v称为称为连通连通的，如果存在的，如果存在u u到到v v通路，任二顶通路，任二顶点都连通的图称为点都连通的图称为连通图连通图，否则，称为，否则，称为非连通图非连通图。极大。极大连通子图称为连通子图称为连通分图连通分图。连通而无圈的图称为连通而无圈的图称为树树,常用常用T T 表示树表示树.树中最长路的边数称为树的树中最长路的边数称为树的高，高，度数为度数为1 1的顶点的顶点称为称为树叶树叶。其余的顶点称为。其余的顶点称为分枝点分枝点。树的边称为。树的边称为树树枝枝。设设G G是有向图，如果是有向图，如果G G的底图是树，则称的底图是树，则称G G是是有向树有向树，也简称，也简称树树。一、图的

8、基本概念一、图的基本概念数学建模-图论第14页/共122页邻接矩阵（结点与结点的关系）邻接矩阵（结点与结点的关系）关联矩阵（结点与边的关系）关联矩阵（结点与边的关系）路径矩阵（任意两结点之间是否有路径）路径矩阵（任意两结点之间是否有路径）可达性矩阵可达性矩阵直达矩阵直达矩阵 等等等等二、图的矩阵表示二、图的矩阵表示数学建模-图论第15页/共122页1 1 有向图的邻接矩阵有向图的邻接矩阵A=(aij)nn（n为结点数）例例1 1：写出右图的邻接矩阵：写出右图的邻接矩阵：解：二、图的矩阵表示二、图的矩阵表示数学建模-图论第16页/共122页2 2 有向图的权矩阵有向图的权矩阵A=(aij)nn（

9、n为结点数）例2：写出右图的权矩阵：解：二、图的矩阵表示二、图的矩阵表示数学建模-图论第17页/共122页3 有向图的有向图的关联矩阵关联矩阵A A=(aij)nm（n为结点数m为边数）有向图：有向图：无向图：无向图：二、图的矩阵表示二、图的矩阵表示数学建模-图论第18页/共122页例3：分别写出右边两图的关联矩阵解：分别为：二、图的矩阵表示二、图的矩阵表示数学建模-图论第19页/共122页 二、图的矩阵表示4 4 应用实例应用实例 某厂生产一种弹子锁具，每个锁具的钥匙有5个槽，每个槽的高度从1，2，3，4，5，6)中任取一数由于工艺及其它原因，制造锁具时对5个槽的高度有两个限制：(1)至少有

10、3个不同的数；(2)相邻两槽的高度之差不能为5 满足以上条件制造出来的所有互不相同的锁具称为一批我们的问题是如何确定每一批锁具的个数?19941994年全国大学生数学建模竞赛年全国大学生数学建模竞赛B B题题(锁具装箱锁具装箱)中关于中关于锁具总数的问题可叙述如下：锁具总数的问题可叙述如下：数学建模-图论第20页/共122页 该问题用图论中的邻接矩阵解决较为简单易见，该问题用图论中的邻接矩阵解决较为简单易见，令令 x=t-sx=t-s，其中，其中，t t代表相邻两槽高度之差不为代表相邻两槽高度之差不为5 5的锁的锁具数，即：满足限制条件具数，即：满足限制条件(2)(2)的锁具数，的锁具数，s

11、s代表相邻两代表相邻两槽高度之差不为槽高度之差不为5 5且槽高仅有且槽高仅有1 1个或个或2 2个的锁具数，即：个的锁具数，即：满足限制条件满足限制条件(2)(2)但不满足限制条件但不满足限制条件(1)(1)的锁具数的锁具数 我们用图论方法计算我们用图论方法计算t t和和s.s.二、图的矩阵表示（应用实例及解法分析）数学建模-图论第21页/共122页 二、图的矩阵表示（应用实例及解法分析）在在G G中每一条长度为中每一条长度为4 4的道路对应于一个相的道路对应于一个相邻两槽邻两槽高度之差不超过高度之差不超过5 5的锁具，即满足限制条件（的锁具，即满足限制条件（2 2）的锁）的锁具，反之亦然，于

12、是可以通过具，反之亦然，于是可以通过G G的邻接矩阵的邻接矩阵A A来计算来计算t t的的值，具体步骤如下：值，具体步骤如下：构造无向图构造无向图 124356数学建模-图论第22页/共122页 二、图的矩阵表示（应用实例及解法分析）因此，因此，数学建模-图论第23页/共122页又令又令 二、图的矩阵表示（应用实例及解法分析）其中其中y yi i表示满足限制条件表示满足限制条件(2)(2)但不满足限制条件但不满足限制条件(1)(1)且且首位为首位为i i的锁具数的锁具数,（i=1,2,3,4,5,6),i=1,2,3,4,5,6),显然显然y y1 1=y=y6 6,y y2=2=y y4 4

13、=y=y3 3=y=y5 5,于是我们只需要计算于是我们只需要计算y y1 1和和y y2.2.计算计算y y1 1可分别考虑槽高只有可分别考虑槽高只有1 1，1212，1313，1414，1515的的情形若只有情形若只有1 1，这样的锁具效只有，这样的锁具效只有1 1个，个，若只有若只有1 1和和i(i=2,3,4,5)i(i=2,3,4,5)，这样的锁具数，这样的锁具数=G=G中以中以1 1和和i i为为顶点，长度为顶点，长度为3 3的道路数，此数可通过的道路数，此数可通过A A的子矩阵的子矩阵A A1i1i计计算得到算得到124356数学建模-图论第24页/共122页 二、图的矩阵表示（

14、应用实例解法分析）事实上，因为事实上，因为 其中其中i=2,3,4,5,i=2,3,4,5,显然显然y y1 1=1+(4+4+4+4-1)=1+(4+4+4+4-1)4=61.4=61.同理，计算同理，计算y y2 2时应考虑槽高只有时应考虑槽高只有2,21,23,24,25,2,21,23,24,25,2626时的情形，类似计算可得时的情形，类似计算可得 y y2 2=1+(4+4+4+4-1)5=76=1+(4+4+4+4-1)5=76 于是，于是，s=612+764=426s=612+764=426，x=6306-426=5880.x=6306-426=5880.该算法既易理解又易操作

15、并且又可扩展该算法既易理解又易操作并且又可扩展数学建模-图论第25页/共122页 二、图的矩阵表示（应用实例及解法分析）公交线路选择问题：公交线路选择问题：在给定某城市公交线路的公交网信息后，在给定某城市公交线路的公交网信息后，求任意两个站点之间的最佳出行路线，包括换乘次数最少、出行求任意两个站点之间的最佳出行路线，包括换乘次数最少、出行时间最短、出行费用最低等。以下图的简化公交网为例来说明。时间最短、出行费用最低等。以下图的简化公交网为例来说明。12345 图中由两条公交线路组成，实线表示第图中由两条公交线路组成，实线表示第一条线路，依次经过站点一条线路，依次经过站点1,3,4,51,3,4

16、,5，虚线表，虚线表示第二条线路，依次经过站点示第二条线路，依次经过站点2,3,52,3,5。首先考虑换乘次数最少的线路选择模型，首首先考虑换乘次数最少的线路选择模型，首先建立直达矩阵如下：先建立直达矩阵如下：数学建模-图论第26页/共122页 二、图的矩阵表示（应用实例及解法分析）12345计算计算A A2 2得到：得到：由于由于A A2 2为非零矩阵，所以任意两站点经为非零矩阵，所以任意两站点经过换乘一次都可到达，由于问题较简单，结过换乘一次都可到达，由于问题较简单，结果显然正确。果显然正确。一般地，比较一般地，比较A=(aA=(aijij),A),A2 2=(a=(a(2)(2)ijij

17、),),A,Ak k=(a(a(k)(k)ijij)中的中的(i,j)(i,j)元够成的向量中第一个非元够成的向量中第一个非零向量的上标即为出行换乘的最少次数。零向量的上标即为出行换乘的最少次数。数学建模-图论第27页/共122页 二、图的矩阵表示（应用实例及解法分析）12345接下来考虑出行时间最短的接下来考虑出行时间最短的模型，建立直达距离矩阵：模型，建立直达距离矩阵：下面利用下面利用FloydFloyd矩阵算法可计算出出行时矩阵算法可计算出出行时间最短的路线。定义间最短的路线。定义T*T=(tT*T=(t(2)(2)ijij),),t t(2)(2)ijij=minmin=minmin1

18、=k=51=k=5ttikik+t+tkjkj,t,tijij,t(2)ij表示表示从站点从站点i i到站点到站点j j的至多换乘一次的最短时间。的至多换乘一次的最短时间。数学建模-图论第28页/共122页 二、图的矩阵表示（应用实例及解法分析）41235利用利用matlabmatlab编写程序如下：编写程序如下：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);e

19、ndendT2计算结果为：计算结果为：T2=0212220122110112210122110 数学建模-图论第29页/共122页 二、图的矩阵表示（应用实例及解法分析）12345 类似可计算出类似可计算出T T3 3，T T4 4，实际上实际上T T2 2的值已为的值已为出行路线的最短时间，例如出行路线的最短时间，例如T T2 2（2,52,5）=2=2，说明站点说明站点2 2到站点到站点5 5的最短时间为的最短时间为2 2站路时间。站路时间。数学建模-图论第30页/共122页 二、图的矩阵表示（应用实例及解法分析）商人过河问题：商人过河问题：假如有三个商人各带一名随从要过河，只有一假如有三

20、个商人各带一名随从要过河，只有一条船，每次最多只能坐两个人。为安全起见，商人数不能少于随条船，每次最多只能坐两个人。为安全起见，商人数不能少于随从数，否则随从会杀人越货。船过一次河需要从数，否则随从会杀人越货。船过一次河需要5 5分钟，问最短几分钟，问最短几分钟能使他们都过去？分钟能使他们都过去？用邻接矩阵来解决：用邻接矩阵来解决：设设(m,n,(m,n,l)表示左岸商人表示左岸商人m m人，随从人，随从n n人；设人；设(m,n,r)(m,n,r)表示右岸有商人表示右岸有商人m m人，随从人，随从n n人。从左岸到右岸去，所有可人。从左岸到右岸去，所有可能的状态为：能的状态为：v v1 1=

21、(3,3,=(3,3,l),v),v2 2=(3,2,=(3,2,l),v),v3 3=(3,1,=(3,1,l),v),v4 4=(3,0,=(3,0,l),v),v5 5=(2,2,=(2,2,l),),v v6 6=(1,1,=(1,1,l),v),v7 7=(0,3,=(0,3,l),v),v8 8=(0,2,=(0,2,l),v),v9 9=(0,1,=(0,1,l),v),v1010=(3,3,r),=(3,3,r),v v1111=(3,2,r),v=(3,2,r),v1212=(3,1,r),v=(3,1,r),v1313=(3,0,r),v=(3,0,r),v1414=(2,

22、2,r),=(2,2,r),v v1515=(1,1,r),=(1,1,r),v v1616=(0,3,r),=(0,3,r),v v1717=(0,2,r=(0,2,r),),v v1818=(0,1,r).=(0,1,r).数学建模-图论第31页/共122页 二、图的矩阵表示（应用实例及解法分析）V10 v11 v12 v13 v14 v15 v16 v17 v18v1 v2 v3 v4v5v6v7v8v9 渡河可以理解为上面状态的转移，例如状态渡河可以理解为上面状态的转移，例如状态v v1 1渡河一次可渡河一次可以转化为其他状态以转化为其他状态v v1515 v v1717 v v181

23、8，其他状态也易列出。以其他状态也易列出。以V=vV=v1 1,v v2 2,.v,.v1818 为顶点集，当两种状态可以互相转化时，就在相应为顶点集，当两种状态可以互相转化时，就在相应的来那个顶点间连一边，从而建立一个二分图的来那个顶点间连一边，从而建立一个二分图G=G=，如右，如右图所示。图所示。G=G=的邻接矩阵为：的邻接矩阵为：数学建模-图论第32页/共122页 二、图的矩阵表示（应用实例及解法分析）V10 v11 v12 v13 v14 v15 v16 v17 v18v1 v2 v3 v4v5v6v7v8v9其中，矩阵其中，矩阵B B为：为：记记a a(k)(k)ijij为为A Ak

24、 k中的（中的（i,ji,j）元，目标是使）元，目标是使a(k)1,10不等于不等于0 0的最小的的最小的自然数自然数k.k.利用利用matlabmatlab容易计算出容易计算出k=11k=11，且，且a(11)1,10=4,=4,即小船至少即小船至少1111次才次才能把所有人全部运到右岸，说明共有能把所有人全部运到右岸，说明共有4 4种不同的过河方案。继续计种不同的过河方案。继续计算可得出算可得出a a(19)(19)1,10 1,10=45060=45060，如果允许小船过河，如果允许小船过河1919次的话，共有次的话，共有4506045060中不同的方案。中不同的方案。数学建模-图论第3

25、3页/共122页 若将图若将图G G的每一条边的每一条边e e都对应一个实数都对应一个实数F F(e e),则称则称F F(e e)为该边的为该边的权权,并称图并称图G G为为赋权图赋权图,记为记为G G=(=(V V,E E,F F ).设设G G=(=(V V,E E)是一个图是一个图,v v0 0,v v1 1,v vk kV V,且且“11i ik k,v vi i1 1 v vi iE E,则称则称v v0 0 v v1 1 v vk k是是G G的一条的一条通路通路.如果通路中没有相同的顶点如果通路中没有相同的顶点,则称此通路为则称此通路为路径路径,简称简称路路.对于赋权图，对于赋

26、权图，路的长度（即路的权）路的长度（即路的权）通常指路上所有边通常指路上所有边的权之和。的权之和。最短路问题最短路问题：求赋权图上指定点之间的权最小的路。：求赋权图上指定点之间的权最小的路。三、最短路问题及其算法三、最短路问题及其算法数学建模-图论第34页/共122页重要性质：若若v v0 0 v v1 1 v vm m 是是G G 中从中从v v0 0到到v vm m的最短路的最短路,则则对对11k km m,v v0 0v v1 1 v vk k 必为必为G G 中从中从v v0 0到到v vk k的的最短路最短路.即：最短路是一条路，且最短路的任一段也是最短路。三、最短路问题及其算法三、

27、最短路问题及其算法数学建模-图论第35页/共122页 设有给定连接若干城市的公路网，寻求从指定城设有给定连接若干城市的公路网，寻求从指定城市到各城市的最短路线。市到各城市的最短路线。2、应用实例：最短路问题、应用实例：最短路问题 问题的数学模型问题的数学模型:三、最短路问题及其算法三、最短路问题及其算法362023年3月25日数学建模-图论第36页/共122页372023年3月25日 三、最短路问题及其算法三、最短路问题及其算法254647109137106648数学建模-图论第37页/共122页382023年3月25日 三、最短路问题及其算法三、最短路问题及其算法数学建模-图论第38页/共1

28、22页392023年3月25日 三、最短路问题及其算法三、最短路问题及其算法数学建模-图论第39页/共122页402023年3月25日 三、最短路问题及其算法三、最短路问题及其算法数学建模-图论第40页/共122页412023年3月25日 三、最短路问题及其算法三、最短路问题及其算法254647109137106648数学建模-图论第41页/共122页422023年3月25日 三、最短路问题及其算法三、最短路问题及其算法数学建模-图论第42页/共122页432023年3月25日 三、最短路问题及其算法三、最短路问题及其算法数学建模-图论第43页/共122页442023年3月25日 三、最短路问

29、题及其算法三、最短路问题及其算法数学建模-图论第44页/共122页452023年3月25日 三、最短路问题及其算法三、最短路问题及其算法254647109137106648数学建模-图论第45页/共122页Floyd算法 三、最短路问题及其算法三、最短路问题及其算法数学建模-图论第46页/共122页 三、最短路问题及其算法三、最短路问题及其算法数学建模-图论第47页/共122页插入点v1，得：矩阵中带“=”的项为经迭代比较以后有变化的元素.第48页/共122页插入点v2，得：矩阵中带“=”的项为经迭代比较以后有变化的元素.第49页/共122页插入点v3，得：第50页/共122页插入点v4，得：

30、插入点v5，得：第51页/共122页插入点v6，得：第52页/共122页故从v5到v2的最短路为8由v6向v5追溯:由v6向v2追溯:所以从到的最短路径为：见Matlab程序-Floyd.doc第53页/共122页542023年3月25日 三、最短路问题及其算法三、最短路问题及其算法数学建模-图论第54页/共122页552023年3月25日 三、最短路问题及其算法三、最短路问题及其算法数学建模-图论第55页/共122页562023年3月25日 三、最短路问题及其算法三、最短路问题及其算法254647109137106648数学建模-图论第56页/共122页572023年3月25日 三、最短路问

31、题及其算法三、最短路问题及其算法数学建模-图论第57页/共122页582023年3月25日 三、最短路问题及其算法三、最短路问题及其算法数学建模-图论第58页/共122页592023年3月25日求求v v1 1到到v v6 6的最短路问题的最短路问题.三、最短路问题及其算法三、最短路问题及其算法数学建模-图论第59页/共122页602023年3月25日从上图中容易得到从上图中容易得到v v1 1到到v v6 6只有两条路只有两条路：v v1 1v v3 3v v6 6和和v v1 1v v4 4v v6 6.而这两条路都是而这两条路都是v v1 1到到v v6 6的最短路的最短路.三、最短路问

32、题及其算法三、最短路问题及其算法数学建模-图论第60页/共122页612023年3月25日 三、最短路问题及其算法三、最短路问题及其算法数学建模-图论第61页/共122页（2）答案：由于T=2小时,t=1小时,V=35公里/小时,需访问的乡镇共有17个，村共有35个.计算出在乡(镇)及村的总停留时间为172+35=69小时，要在24小时内完成巡回，若不考虑行走时间，有:69/i24(i为分的组数).得i最小为4，故至少要分4组.由于该网络的乡(镇)、村分布较为均匀,故有可能找出停留时间尽量均衡的分组,当分4组时各组停停留时间大约为69/4=17.25小时，则每组分配在路途上的时间大约为24-1

33、7.25=6.75小时.而前面讨论过,分三组时有个总路程599.8公里的巡视路线，分4组时的总路程不会比599.8公里大太多,不妨以599.8公里来计算.路上约用599.8/35=17小时,若平均分配给4个组,每个组约需17/4=4.25小时6.75小小时,故分成4组是可能办到的.第62页/共122页现在尝试将顶点分为4组.分组的原则：除遵从前面准则1、2、3外，还应遵从以下准则：准则4尽量使各组的停留时间相等.用上述原则在下图上将图分为4组，同时计算各组的停留时间,然后用算法一算出各组的近似最最佳旅行售货员巡回，得出路线长度及行走时间,从而得出完成巡视的近似最佳时间.用算法一计计算时，初始圈

34、的输入与分三组时同样处理.这4组的近似最优解见表3.第63页/共122页第64页/共122页表3符号说明：加有底纹的表示前面经过并停留过,此次只经过不停留;加框的表示此点只经过不停留.可看出,表3分组的均衡度很好,且完全满足24小时完成巡视的要求.该分组实际均衡度4.62%第65页/共122页 顶点顶点u u与与v v称为称为连通连通的，如果存在的，如果存在u-vu-v通路，任二顶点通路，任二顶点都连通的图称为都连通的图称为连通图连通图，否则，称为，否则，称为不连通图不连通图。极大连。极大连通子图称为通子图称为连通分图连通分图。连通而无圈的图称为连通而无圈的图称为树树,常用常用T T 表示树表

35、示树.树中最长路的边数称为树的树中最长路的边数称为树的高高的度为的度为1 1的顶点称的顶点称为为树叶树叶。其余的顶点称为。其余的顶点称为分枝点分枝点。树的边称为。树的边称为树枝树枝。设设G G是有向图，如果是有向图，如果G G的底图是树，则称的底图是树，则称G G是是有向树有向树，也简称，也简称树树。四、最小生成树问题及其算法四、最小生成树问题及其算法数学建模-图论第66页/共122页定理定理 设设GG是具有是具有n n个顶点的图，则下述命题等价：个顶点的图，则下述命题等价：1)G是树（G无圈且连通）；2)G无圈，且有n-1条边；3)G连通，且有n-1条边；4)G无圈，但添加任一条新边恰好产生

36、一个圈;5)G连通，且删去一条边就不连通了（即G为最最小连通图）；6)G中任意两顶点间有唯一一条路.第67页/共122页若若 任任 意意 一一 个个 连连 通通 的的 图图 G=G=的的 生生 成成 子子 图图T=VT=(V(V=V,E=V,E为为E E的的子子集集)为为树树,这这棵棵树树T T称为称为图图G G的生成树的生成树.设设T T是是图图G G的的一一棵棵生生成成树树,用用F F (T T)表表示示树树T T中中所所有有边边的权数之和的权数之和,F F(T T)称为树称为树T T的的权权.一个连通图一个连通图G G的生成树一般不止一棵的生成树一般不止一棵,图图G G的所有生成树中权数

37、最小的生成树称为的所有生成树中权数最小的生成树称为图图G G的的最小生成树最小生成树.四、最小生成树问题及其算法四、最小生成树问题及其算法数学建模-图论第68页/共122页 怎样找出最小生成树？怎样找出最小生成树？G T1 T2 T3 T4 T5 T6 T7 T8 T T1 1至至T T8 8是是 图图G G的生的生成树成树 四、最小生成树问题及其算法四、最小生成树问题及其算法数学建模-图论第69页/共122页Kruskal 算法或避圈法或避圈法思想：在不形成圈得条件下，优先挑选权小的边形成生成思想：在不形成圈得条件下，优先挑选权小的边形成生成树。树。76788334245v1v2v3v4v5

38、v6v7683324v1v2v3v4v5v6v7 四、最小生成树问题及其算法四、最小生成树问题及其算法数学建模-图论第70页/共122页步骤如下：1)选择边e1，使得w(e1)尽可能小；2)若已选定边，则从中选取，使得:i)为无圈图，ii)是满足i)的尽可能小的权，3)当第2)步不能继续执行时，则停止.定理4由Kruskal算法构作的任何生成树都是最小树.数学建模-图论 四、最小生成树问题及其算法四、最小生成树问题及其算法第71页/共122页例用Kruskal算法求下图的最小树.在左图中权值最小的边有任取一条在中选取权值最小的边中权值最小边有,从中选任取一条边会与已选边构成圈,故停止。中选取在

39、中选取中选取.但与都第72页/共122页732023年3月25日 四、最小生成树问题及其算法四、最小生成树问题及其算法数学建模-图论第73页/共122页742023年3月25日 四、最小生成树问题及其算法四、最小生成树问题及其算法数学建模-图论第74页/共122页752023年3月25日 四、最小生成树问题及其算法四、最小生成树问题及其算法运行结果如下：运行结果如下：T=1 3 5 1 6 3 2 6 6 6 7 4c=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

40、8 3 7 6;Krusf(b,1);76788334245v1v2v3v4v5v6v7683324v1v2v3v4v5v6v7数学建模-图论第75页/共122页762023年3月25日 四、最小生成树问题及其算法四、最小生成树问题及其算法数学建模-图论第76页/共122页772023年3月25日 四、最小生成树问题及其算法四、最小生成树问题及其算法数学建模-图论第77页/共122页782023年3月25日 四、最小生成树问题及其算法四、最小生成树问题及其算法数学建模-图论第78页/共122页792023年3月25日 四、最小生成树问题及其算法四、最小生成树问题及其算法运行结果如下：运行结果如

41、下：T=1 1 6 6 6 3 2 6 3 5 7 4c=2 4 3 3 6 876788334245v1v2v3v4v5v6v7数学建模-图论第79页/共122页64686865505061456054例：分别利用例：分别利用KruskalKruskal算法和算法和PrimPrim算法如图算法如图G G的最小生的最小生成树：成树：四、最小生成树问题及其算法四、最小生成树问题及其算法数学建模-图论第80页/共122页称经过图称经过图 G G=(=(V V,E E)的每条边恰好一次的路为的每条边恰好一次的路为 EulerEuler路径路径，经过经过G G 的每条边恰好一次的回路为的每条边恰好一次

42、的回路为 EulerEuler回路回路。称有。称有 Euler Euler 回路的图为回路的图为 EulerEuler图图 五、五、E图与图与H图问题图问题命题：命题：G G 是是 Euler Euler 图当且当图当且当G G 连连通且没有度数为奇数的点；通且没有度数为奇数的点；G G 有有 Euler Euler 路径当且仅当路径当且仅当 G G 连通且没有或只有二个度数为基连通且没有或只有二个度数为基数的点。数的点。ABCD4 个点的度数皆为奇数，不存在 Euler 路数学建模-图论第81页/共122页中国邮递员问题：中国邮递员问题：一个邮递员从邮局取出邮件后，需要到他管辖区域内的每条街

43、道一个邮递员从邮局取出邮件后，需要到他管辖区域内的每条街道进行投递，送完邮件后返回邮局，问如何选择一条总路程最短的进行投递，送完邮件后返回邮局，问如何选择一条总路程最短的投递路线？投递路线？以街道为边，街道的交叉口或端点为点，街道的长度为权，构以街道为边，街道的交叉口或端点为点，街道的长度为权，构造赋权图造赋权图G G=(=(V V,E,wE,w)。投递路线应是一条经过。投递路线应是一条经过G G的每条边至少一的每条边至少一次的回路。次的回路。五、五、E图与图与H图问题图问题数学建模-图论第82页/共122页将将G G的度数为奇数的点（必的度数为奇数的点（必为偶数个）两个一组、两为偶数个）两个

44、一组、两个一组用最短路连结起来。个一组用最短路连结起来。4 3 3 34 3 3 3a 2 b 2 c 2 de 3 f 2 g 2 hi 4 j 2 k 2 l 24 322 如何分组可以使得如何分组可以使得重复路径的总长度最短重复路径的总长度最短？23 2 22 五、五、E图与图与H图问题图问题数学建模-图论第83页/共122页 解中国邮递员问题的奇偶点图上作业法：具体步骤如下：1.通过加重复边，消灭图中的奇点。将奇点两两配对，在每一对奇点的通路上，均加上重复边。2。删除过多的重复边。如果图中某条边的重复边多于一条，则可将它的重复边删除偶数条。3。优化重复边。使所加的重复边的总长度最小。下

45、面通过具体例子来说明具体计算过程：第84页/共122页 例 设有街道图如下：假如邮递员从V1点出发，求他的最优投递路线。4444459655V132V9V4V3V2V8V7V6V5解：第85页/共122页 考虑加边的圈：V1,V2,V9,V8 中，加边的长度是4+6=10，而不加边的长度是4+5=9，故需改进如下。4444459655V132V9V4V3V2V8V7V6V5 考虑加边的圈：v4,v5,v6,v9 中，加边的长度是3+5=8，而不加边的长度是4+2=6，故需改进如下。图中已无奇点，可得最优投递路线：第86页/共122页 五、五、E图与图与H图问题图问题若若G G是是EulerEu

46、ler图，则任何一条图，则任何一条EulerEuler回路是最短投递路线回路是最短投递路线,都满足都满足条件，针对这种情况，条件，针对这种情况，FleuryFleury提出一种算法，能够在提出一种算法，能够在EulerEuler图图中找出中找出EulerEuler路径，解决了邮递员问题；路径，解决了邮递员问题；若若G G 不是不是EulerEuler图，则投递路图，则投递路线将重复经过某些街道，最线将重复经过某些街道，最优投递路线应使得重复经过优投递路线应使得重复经过的街道的总长度最短。的街道的总长度最短。例如，确定右图是否例如，确定右图是否EulerEuler图，若是，图，若是，找出图中的找

47、出图中的EulerEuler回路回路。2 3 6 5 4 1数学建模-图论第87页/共122页882023年3月25日 五、五、E图与图与H图问题图问题数学建模-图论第88页/共122页892023年3月25日 五、五、E图与图与H图问题图问题数学建模-图论第89页/共122页902023年3月25日 五、五、E图与图与H图问题图问题数学建模-图论第90页/共122页912023年3月25日 五、五、E图与图与H图问题图问题数学建模-图论第91页/共122页922023年3月25日 五、五、E图与图与H图问题图问题数学建模-图论第92页/共122页932023年3月25日 五、五、E图与图与H

48、图问题图问题上述例题的上述例题的MatlabMatlab程序如下：程序如下：cleard=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);2 3 6 5 4 1数学建模-图论第93页/共122页例：确定所示的赋权图是否例：确定所示的赋权图是否EulerEuler图，图，若是，找出图中的若是，找出图中的EulerEuler回路。回路。五、五、E图与图与H图问题图问题数学建模-图论第94页/共122页952023年3月25日 五、五、E图与图与H图问题图问题运行结果如下：运行结果

49、如下：T=1 5 4 3 5 5 4 3 2 1c=5d=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数学建模-图论第95页/共122页称经过图称经过图 G G=(=(V V,E E)的每个点恰好一次的路为的每个点恰好一次的路为HamiltonHamilton路路，经过，经过G G的每个点恰好一次的回路为的每个点恰好一次的回路为HamiltonHamilton回路回路。称有。称有HamiltonHamilton回路的回路的图为图为HamiltonHamilton图图。1112345678910121314151617181920十二面体的平

50、面嵌入为 Hamilton 图 Hamilton 图与 Euler 图在定义上很相似，但判断一个图是否 Hamilton 图较判断它是否 Euler 图要困难得多，目前还没有易验证的充要条件。五、五、E图与图与H图问题图问题数学建模-图论第96页/共122页在国际象棋中，马跳动一次只能沿着一个在国际象棋中，马跳动一次只能沿着一个 23 23 的长方形的对角的长方形的对角线从一个角跳到另一个角，问是否存在一串符合规定的着法使得线从一个角跳到另一个角，问是否存在一串符合规定的着法使得马可以从任一格子出发跳遍马可以从任一格子出发跳遍 88 88 的整个棋盘，并只到达每个格的整个棋盘，并只到达每个格子