数学建模图论讲ppt课件.ppt

数学建模数学建模 图论方法专题图论方法专题图论方法专题图的基本概念图的基本概念最短路问题及其算法最短路问题及其算法最小生成树问题最小生成树问题E图与图与H图图图的矩阵表示图的矩阵表示 32022年年7月月26日日 一、图的基本概念一、图的基本概念42022年年7月月26日日 一、图的基本概念一、图的基本概念 一、图的基本概念一、图的基本概念次数为奇数顶点称为次数为奇数顶点称为奇点奇点，否则称为否则称为偶点偶点。52022年年7月月26日日常用常用d d( (v v) )表示图表示图G G中与顶点中与顶点v v关联的边的数目关联的边的数目, , d d( (v v) )称为顶点称为顶点v v的度数的度数. .与顶点与顶点v v出关联的边的数目称为出关联的边的数目称为出度出度，记作，记作d d + +( (v v) )，与顶点与顶点v v入关联的边的数目称为入关联的边的数目称为入度入度，记作，记作d d - -( (v v) )。用用N N( (v v) )表示图表示图G G中所有与顶点中所有与顶点v v相邻的顶点的集合相邻的顶点的集合. 任意两顶点都相邻的简单图称为任意两顶点都相邻的简单图称为完全图完全图. .有有n n个顶点的完全图记为个顶点的完全图记为K Kn n 。 一、图的基本概念一、图的基本概念几个基本定理：几个基本定理： .21EvdEVGVv，有，、对图数个。、度为奇数的顶点有偶2 . 3EvdvdEVGVvVv则是有向图，、设 一、图的基本概念一、图的基本概念 若将图若将图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的一条的一条通路通路. . 如果通路中没有相同的顶点如果通路中没有相同的顶点, , 则称此通路为则称此通路为路径路径, , 简称简称路路. . 始点和终点相同的路称为始点和终点相同的路称为圈圈或或回路回路. . 一、图的基本概念一、图的基本概念 顶点顶点u u与与v v称为称为连通连通的，如果存在的，如果存在u u到到v v通路，任二顶通路，任二顶点都连通的图称为点都连通的图称为连通图连通图，否则，称为，否则，称为非连通图非连通图。极大。极大连通子图称为连通子图称为连通分图连通分图。 连通而无圈的图称为连通而无圈的图称为树树, , 常用常用T T 表示树表示树. . 树树中中最长路的边数称为树的最长路的边数称为树的高，高，度数为度数为1 1的顶点的顶点称为称为树叶树叶。其余的顶点称为。其余的顶点称为分枝点分枝点。树的边称为。树的边称为树树枝枝。 设设G G是有向图，如果是有向图，如果G G的底图是树，则称的底图是树，则称G G是是有向树有向树，也简称，也简称树树。 一、图的基本概念一、图的基本概念邻接矩阵（结点与结点的关系）邻接矩阵（结点与结点的关系）关联矩阵（结点与边的关系）关联矩阵（结点与边的关系）路径矩阵（任意两结点之间是否有路径）路径矩阵（任意两结点之间是否有路径）可达性矩阵可达性矩阵直达矩阵直达矩阵 等等等等二、图的矩阵表示二、图的矩阵表示1 1 有向图的邻接矩阵有向图的邻接矩阵 A = (aij )nn （n为结点数）EvvEvvajijiij, 0, 1 例例1 1：写出右图的邻接矩阵：写出右图的邻接矩阵：0101100101001010A解：二、图的矩阵表示二、图的矩阵表示2 2 有向图的权矩阵有向图的权矩阵A = (aij ) nn （n为结点数） EvvjiEvvvvFajijijiij , , 0 ,例2：写出右图的权矩阵：05420370860A解：二、图的矩阵表示二、图的矩阵表示3 有向图的有向图的关联矩阵关联矩阵A A =(aij )nm （n为结点数m为边数） 不关联与若的终点是若的始点是若iiiiiiijeveveva, 0, 1, 1有向有向图：图： 无向图：无向图：不关联与若关联与若jijiijvvvva, 0 , 1 二、图的矩阵表示二、图的矩阵表示例3：分别写出右边两图的关联矩阵解：分别为：1101100011011000000111011001A 二、图的矩阵表示二、图的矩阵表示eabcd1e2e3e4e5e0001101001111000011010000A 二、图的矩阵表示二、图的矩阵表示4 4 应用实例应用实例 某厂生产一种弹子锁具，每个锁具的钥匙有5个槽，每个槽的高度从1，2，3，4，5，6)中任取一数由于工艺及其它原因，制造锁具时对5个槽的高度有两个限制：(1)至少有3个不同的数；(2)相邻两槽的高度之差不能为5 满足以上条件制造出来的所有互不相同的锁具称为一批我们的问题是如何确定每一批锁具的个数?19941994年全国大学生数学建模竞赛年全国大学生数学建模竞赛B B题题( (锁具装箱锁具装箱) )中关于中关于锁具总数的问题可叙述如下：锁具总数的问题可叙述如下： 该问题用图论中的邻接矩阵解决较为简单该问题用图论中的邻接矩阵解决较为简单易见，易见， x=x=t-st-s，其中，其中，t t代表相邻两槽高度之差不为代表相邻两槽高度之差不为5 5的锁具数，即：满足限制条件的锁具数，即：满足限制条件(2)(2)的锁具数，的锁具数，s s代表相代表相邻两槽高度之差不为邻两槽高度之差不为5 5且槽高仅有且槽高仅有1 1个或个或2 2个的锁具数，个的锁具数，即：满足限制条件即：满足限制条件(2)(2)但不满足限制条件但不满足限制条件(1)(1)的锁具的锁具数数 我们用图论方法计算我们用图论方法计算t t和和s.s. 二、图的矩阵表示（应用实例及解法分析）二、图的矩阵表示（应用实例及解法分析）,1,2,3,4,5,6,5GVEVEij i jVij，且 在在G G中中t t每一条长度为每一条长度为4 4的道路对应于一个相的道路对应于一个相邻两槽邻两槽高度之差不超过高度之差不超过5 5的锁具，即满足限制条件（的锁具，即满足限制条件（2 2）的锁）的锁具，反之亦然，于是可以通过具，反之亦然，于是可以通过G G的邻接矩阵的邻接矩阵A A来计算来计算t t的的值，具体步骤如下：值，具体步骤如下： 二、图的矩阵表示（应用实例及解法分析）二、图的矩阵表示（应用实例及解法分析）构造无向图构造无向图 124356111110111111111111111111111111011111A5555545555555555555555555555554555552A1411651651651651401651941941941941651651941941941941651651941941941941651651941941941941651401651651651651414A.63066161)4(ijijat因此，因此， 二二、图的矩阵表示（应用实例及解法分析）、图的矩阵表示（应用实例及解法分析）又令又令 ,654321yyyyyys其中其中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=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(ii(i=2,3,4,5)=2,3,4,5)，这样的锁具数，这样的锁具数=G=G中以中以1 1和和i i为为顶点，长度为顶点，长度为3 3的道路数，此数可通过的道路数，此数可通过A A的子矩阵的子矩阵A A1i1i计计算得到算得到 二、图的矩阵表示（应用实例及解法分析）二、图的矩阵表示（应用实例及解法分析）124356 二、图的矩阵表示（应用实例解法分析）二、图的矩阵表示（应用实例解法分析）事实上，因为事实上，因为 444422221111i131211iiiAAA，行第行第其中其中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=1+(4+4+4+4-1+(4+4+4+4-1) )5=765=76 于是，于是，s=61s=612+762+764=4264=426，x=6306-426=5880.x=6306-426=5880. 该算法既易理解又易操作并且又可扩展该算法既易理解又易操作并且又可扩展 二、图的矩阵表示（应用实例及解法分析）二、图的矩阵表示（应用实例及解法分析）公交线路选择问题：公交线路选择问题：在给定某城市公交线路的公交网信息后，在给定某城市公交线路的公交网信息后，求任意两个站点之间的最佳出行路线，包括换乘次数最少、出行求任意两个站点之间的最佳出行路线，包括换乘次数最少、出行时间最短、出行费用最低等。以下图的简化公交网为例来说明。时间最短、出行费用最低等。以下图的简化公交网为例来说明。 12345 图中由两条公交线路组成，实线表示第图中由两条公交线路组成，实线表示第一条线路，依次经过站点一条线路，依次经过站点1,3,4,51,3,4,5，虚线表，虚线表示第二条线路，依次经过站点示第二条线路，依次经过站点2,3,52,3,5。 首先考虑换乘次数最少的线路选择模型，首首先考虑换乘次数最少的线路选择模型，首先建立直达矩阵如下：先建立直达矩阵如下： 二、图的矩阵表示（应用实例及解法分析）二、图的矩阵表示（应用实例及解法分析）0111110101110111010011100A12345计算计算A A2 2得到：得到：42312232223241212122222232A 由于由于A A2 2为非零矩阵，所以任意两站点经为非零矩阵，所以任意两站点经过换乘一次都可到达，由于问题较简单，结过换乘一次都可到达，由于问题较简单，结果显然正确。果显然正确。 一般地，比较一般地，比较A=(aA=(aijij),A),A2 2=(a=(a(2)(2)ijij),), , A Ak k=(=(a a(k)(k)ijij) )中的中的( (i,ji,j) )元够成的向量中第一个元够成的向量中第一个非零向量的上标即为出行换乘的最少次数。非零向量的上标即为出行换乘的最少次数。 二、图的矩阵表示（应用实例及解法分析）二、图的矩阵表示（应用实例及解法分析）011231012110112103210T12345接下来考虑出行时间最短的接下来考虑出行时间最短的模型，建立直达距离矩阵：模型，建立直达距离矩阵： 下面利用下面利用FloydFloyd矩阵算法可计算出出行时矩阵算法可计算出出行时间最短的路线。定义间最短的路线。定义T T* *T=(tT=(t(2)(2)ijij), ), t t(2)(2)ijij=minmin=minmin1=k=51=k=5ttikik+t+tkjkj,t,tijij, t(2)ij表示表示从站点从站点i i到站点到站点j j的至多换乘一次的最短时间。的至多换乘一次的最短时间。 站点不可直达站点与，站的距离站点共有站点jinjintij, 二、图的矩阵表示（应用实例及解法分析）二、图的矩阵表示（应用实例及解法分析）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); endendT2计算结果为：计算结果为：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 二、图的矩阵表示（应用实例及解法分析）二、图的矩阵表示（应用实例及解法分析）12345 类似可计算出类似可计算出T T3 3，T T4 4，实际上实际上T T2 2的值已为的值已为出行路线的最短时间，例如出行路线的最短时间，例如T T2 2（2,52,5）=2=2，说明站点说明站点2 2到站点到站点5 5的最短时间为的最短时间为2 2站路时间。站路时间。思考：思考：最省乘车费用的最佳出行路线该如何考最省乘车费用的最佳出行路线该如何考虑呢？（分情况讨论）虑呢？（分情况讨论）（1 1）按路程收费；（）按路程收费；（出行时间最短出行时间最短）（2 2）按换乘次数收费）按换乘次数收费。（。（最少换乘次数最少换乘次数） 二、图的矩阵表示（应用实例及解法分析）二、图的矩阵表示（应用实例及解法分析）商人过河问题：商人过河问题：假如有三个商人各带一名随从要过河，只有一假如有三个商人各带一名随从要过河，只有一条船，每次最多只能坐两个人。为安全起见，商人数不能少于随条船，每次最多只能坐两个人。为安全起见，商人数不能少于随从数，否则随从会杀人越货。船过一次河需要从数，否则随从会杀人越货。船过一次河需要5 5分钟，问最短几分钟，问最短几分钟能使他们都过去？分钟能使他们都过去？用邻接矩阵来解决：用邻接矩阵来解决：设设( (m,n,m,n,l) )表示左岸商人表示左岸商人m m人，随从人，随从n n人；设人；设( (m,n,rm,n,r) )表示右岸有商人表示右岸有商人m m人，随从人，随从n n人。从左岸到右岸去，所有可人。从左岸到右岸去，所有可能的状态为：能的状态为：v v1 1=(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,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). 二、图的矩阵表示（应用实例及解法分析）二、图的矩阵表示（应用实例及解法分析）)(00对称阵BBAV10 v11 v12 v13 v14 v15 v16 v17 v18v1 v2 v3 v4 v5 v6 v7 v8 v9 渡河可以理解为上面状态的转移，例如状态渡河可以理解为上面状态的转移，例如状态v v1 1渡河一次可渡河一次可以转化为其他状态以转化为其他状态v v1515 v v1717 v v1818，其他状态也易列出。以其他状态也易列出。以V=vV=v1 1, , v v2 2,. v,. v1818 为顶点集，当两种状态可以互相转化时，就在相应为顶点集，当两种状态可以互相转化时，就在相应的来那个顶点间连一边，从而建立一个二分图的来那个顶点间连一边，从而建立一个二分图G=G=，如右，如右图所示。图所示。G=G=的邻接矩阵为：的邻接矩阵为： 二、图的矩阵表示（应用实例及解法分析）二、图的矩阵表示（应用实例及解法分析）000000001000000011000000110000000011000010100000000000001010000011100000110100000BV10 v11 v12 v13 v14 v15 v16 v17 v18v1 v2 v3 v4 v5 v6 v7 v8 v9其中，矩阵其中，矩阵B B为：为：记记a a(k)(k)ijij为为A Ak 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中不同的方案。中不同的方案。 若将图若将图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的一条的一条通路通路. .如果通路中没有相同的顶点如果通路中没有相同的顶点, , 则称此通路为则称此通路为路径路径, ,简称简称路路. .对于赋权图，对于赋权图，路的长度（即路的权）路的长度（即路的权）通常指路上所有边通常指路上所有边的权之和。的权之和。最短路问题最短路问题：求赋权图上指定点之间的权最小的路。：求赋权图上指定点之间的权最小的路。 三、最短路问题及其算法三、最短路问题及其算法重要性质：重要性质：若若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的的最短路最短路. . 即：最短路是一条路，且最短路的任一段即：最短路是一条路，且最短路的任一段也是最短路。也是最短路。 三、最短路问题及其算法三、最短路问题及其算法 设有给定连接若干城市的公路网，寻求从指定城设有给定连接若干城市的公路网，寻求从指定城市到各城市的最短路线。市到各城市的最短路线。 2、应用实例：最短路问题、应用实例：最短路问题 问题的数学模型问题的数学模型: : 三、最短路问题及其算法三、最短路问题及其算法312022年年7月月26日日322022年年7月月26日日 三、最短路问题及其算法三、最短路问题及其算法0v 3v 1v2v 4v 5v6v7v8v254647109137106648332022年年7月月26日日 三、最短路问题及其算法三、最短路问题及其算法342022年年7月月26日日 三、最短路问题及其算法三、最短路问题及其算法352022年年7月月26日日 三、最短路问题及其算法三、最短路问题及其算法362022年年7月月26日日 三、最短路问题及其算法三、最短路问题及其算法0v 3v 1v2v 4v 5v6v7v8v254647109137106648372022年年7月月26日日 三、最短路问题及其算法三、最短路问题及其算法382022年年7月月26日日 三、最短路问题及其算法三、最短路问题及其算法392022年年7月月26日日 三、最短路问题及其算法三、最短路问题及其算法402022年年7月月26日日 三、最短路问题及其算法三、最短路问题及其算法0v 3v 1v2v 4v5v6v7v8v254647109137106648412022年年7月月26日日 三、最短路问题及其算法三、最短路问题及其算法422022年年7月月26日日 三、最短路问题及其算法三、最短路问题及其算法432022年年7月月26日日 三、最短路问题及其算法三、最短路问题及其算法0v 3v 1v2v 4v 5v6v7v8v254647109137106648442022年年7月月26日日 三、最短路问题及其算法三、最短路问题及其算法452022年年7月月26日日 三、最短路问题及其算法三、最短路问题及其算法462022年年7月月26日日ijkkijicbvvF1)(求求v v1 1到到v v6 6的最短路问题的最短路问题. . 三、最短路问题及其算法三、最短路问题及其算法4 11411()11 568kkF vvbc 472022年年7月月26日日从上图中容易得到从上图中容易得到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的最短路的最短路. . 三、最短路问题及其算法三、最短路问题及其算法482022年年7月月26日日 三、最短路问题及其算法三、最短路问题及其算法 顶点顶点u u与与v v称为称为连通连通的，如果存在的，如果存在u-vu-v通路，任二顶点通路，任二顶点都连通的图称为都连通的图称为连通图连通图，否则，称为，否则，称为不连通图不连通图。极大连。极大连通子图称为通子图称为连通分图连通分图。 连通而无圈的图称为连通而无圈的图称为树树, , 常用常用T T 表示树表示树. . 树树中中最长路的边数称为树的最长路的边数称为树的高高的度为的度为1 1的顶点称的顶点称为为树叶树叶。其余的顶点称为。其余的顶点称为分枝点分枝点。树的边称为。树的边称为树枝树枝。 设设G G是有向图，如果是有向图，如果G G的底图是树，则称的底图是树，则称G G是是有向树有向树，也简称，也简称树树。 四、最小生成树问题及其算法四、最小生成树问题及其算法若 任 意 一 个 连 通 的 图若 任 意 一 个 连 通 的 图 G = G = 的 生 成 子 图的 生 成 子 图T=(V=V,ET=(V=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的所有生成树中权数最小的生成树称为的所有生成树中权数最小的生成树称为图图G G的的最小生成树最小生成树. . 四、最小生成树问题及其算法四、最小生成树问题及其算法 怎样找出最小生成树？怎样找出最小生成树？G T1 T2 T3 T4 T5 T6 T7 T8 T T1 1至至T T8 8是是 图图G G的生的生成树成树 四、最小生成树问题及其算法四、最小生成树问题及其算法Kruskal 算法算法 思想：在不形成圈得条件下，优先挑选权小的边形成生成思想：在不形成圈得条件下，优先挑选权小的边形成生成树。树。76788334245v1v2v3v4v5v6v7683324v1v2v3v4v5v6v7 四、最小生成树问题及其算法四、最小生成树问题及其算法。，取取，成成的的边边按按权权非非减减次次序序排排列列将将图图1|)| , 2 , 1()(,)1(1|21 kVjjvlEeeeGjiiiE 。；否否，取取，转转是是，取取是是否否相相等等？、的的标标号号、连连结结的的二二点点边边)2(1)()()2(11kkiieEEkkvlulvue 。，令令的的对对一一切切满满足足)(, )(min)()(, )(max)()3(vlulvlvvlulvljjj 。，转转取取算算法法终终止止；否否是是)2(1,?1|)4(1 kkVE注：算法构造的最小生成树的边集为注：算法构造的最小生成树的边集为 E E1 1；标号；标号 l l 具有性质：具有性质：当且仅当当且仅当 u u、v v 之间有一条仅由之间有一条仅由 E E1 1 中的边形成的路时，中的边形成的路时，l l( (u u) ) = = l l( (v v) )，因此在步骤，因此在步骤 (2) (2) 发现发现 l l( (u u) =) = l l( (v v) ) 时，时，( (u u, , v v) ) 不不能放入能放入 E E1 1，否则会形成一个圈。，否则会形成一个圈。 四、最小生成树问题及其算法四、最小生成树问题及其算法542022年年7月月26日日 四、最小生成树问题及其算法四、最小生成树问题及其算法552022年年7月月26日日 四、最小生成树问题及其算法四、最小生成树问题及其算法562022年年7月月26日日 四、最小生成树问题及其算法四、最小生成树问题及其算法运行结果如下：运行结果如下：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 8 3 7 6;Krusf(b,1);112233345562636467767724458378376b76788334245v1v2v3v4v5v6v7683324v1v2v3v4v5v6v7572022年年7月月26日日 四、最小生成树问题及其算法四、最小生成树问题及其算法 582022年年7月月26日日 四、最小生成树问题及其算法四、最小生成树问题及其算法592022年年7月月26日日 四、最小生成树问题及其算法四、最小生成树问题及其算法602022年年7月月26日日 四、最小生成树问题及其算法四、最小生成树问题及其算法 运行结果如下：运行结果如下：T = 1 1 6 6 6 3 2 6 3 5 7 4c = 2 4 3 3 6 806787603354730808738045402420A76788334245v1v2v3v4v5v6v71v2v3v4v5v64686865505061456054例：分别利用例：分别利用KruskalKruskal算法和算法和PrimPrim算法如图算法如图G G的最小生的最小生成树：成树： 四、最小生成树问题及其算法四、最小生成树问题及其算法称经过图称经过图 G G = ( = (V V , , E E ) ) 的每条边恰好一次的路为的每条边恰好一次的路为 EulerEuler路路径径，经过，经过G G 的每条边恰好一次的回路为的每条边恰好一次的回路为 EulerEuler回路回路。称有。称有 Euler Euler 回路的图为回路的图为 EulerEuler图图 五、五、E图与图与H图问题图问题命题：命题：G G 是是 Euler Euler 图当且当图当且当G G 连连通且没有度数为奇数的点；通且没有度数为奇数的点； G G 有有 Euler Euler 路径当且仅当路径当且仅当 G G 连通且没有或只有二个度数为基连通且没有或只有二个度数为基数的点。数的点。ABCD4 个点的度数皆为奇个点的度数皆为奇数，不存在数，不存在 Euler 路路中国邮递员问题：中国邮递员问题： 一个邮递员从邮局取出邮件后，需要到他管辖区域内的每条街一个邮递员从邮局取出邮件后，需要到他管辖区域内的每条街道进行投递，送完邮件后返回邮局，问如何选择一条总路程最道进行投递，送完邮件后返回邮局，问如何选择一条总路程最短的投递路线？短的投递路线？以街道为边，街道的交叉口或端点为点，街道的长度为权，构以街道为边，街道的交叉口或端点为点，街道的长度为权，构造赋权图造赋权图G G =( =(V V, ,E,wE,w) )。投递路线应是一条经过。投递路线应是一条经过G G的每条边至少的每条边至少一次的回路。一次的回路。 五、五、E图与图与H图问题图问题将将G G的度数为奇数的点（必的度数为奇数的点（必为偶数个）两个一组、两为偶数个）两个一组、两个一组用最短路连结起来。个一组用最短路连结起来。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图问题图问题 五、五、E图与图与H图问题图问题若若G G是是EulerEuler图，则任何一条图，则任何一条EulerEuler回路是最短投递路线回路是最短投递路线, ,都满足都满足条件，针对这种情况，条件，针对这种情况，FleuryFleury提出一种算法，能够在提出一种算法，能够在EulerEuler图图中找出中找出EulerEuler路径，解决了邮递员问题；路径，解决了邮递员问题；若若G G 不是不是EulerEuler图，则投递路图，则投递路线将重复经过某些街道，最线将重复经过某些街道，最优投递路线应使得重复经过优投递路线应使得重复经过的街道的总长度最短。的街道的总长度最短。例如，确定右图是否例如，确定右图是否EulerEuler图，若是，图，若是，找出图中的找出图中的EulerEuler回路回路。2 3 6 5 4 1662022年年7月月26日日 五、五、E图与图与H图问题图问题672022年年7月月26日日 五、五、E图与图与H图问题图问题682022年年7月月26日日 五、五、E图与图与H图问题图问题692022年年7月月26日日 五、五、E图与图与H图问题图问题702022年年7月月26日日 五、五、E图与图与H图问题图问题712022年年7月月26日日 五、五、E图与图与H图问题图问题上述例题的上述例题的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 11v2v3v4v5v例：确定所示的赋权图是否例：确定所示的赋权图是否EulerEuler图，图，若是，找出图中的若是，找出图中的EulerEuler回路。回路。 五、五、E图与图与H图问题图问题732022年年7月月26日日 五、五、E图与图与H图问题图问题运行结果如下：运行结果如下：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 02v3v4v5v1v称经过图称经过图 G G =( =(V V, ,E E) )的每个点恰好一次的路为的每个点恰好一次的路为HamiltonHamilton路路，经过，经过G G的每个点恰好一次的回路为的每个点恰好一次的回路为HamiltonHamilton回路回路。称有。称有HamiltonHamilton回路的回路的图为图为HamiltonHamilton图图。1112345678910121314151617181920十二面体的平面嵌入十二面体的平面嵌入为为 Hamilton 图图 Hamilton 图与图与 Euler 图图在定义上很相似，但判在定义上很相似，但判断一个图是否断一个图是否 Hamilton 图较判断它是否图较判断它是否 Euler 图图要困难得多，目前还没要困难得多，目前还没有易验证的充要条件。有易验证的充要条件。 五、五、E图与图与H图问题图问题在国际象棋中，马跳动一次只能沿着一个在国际象棋中，马跳动一次只能沿着一个 2 23 3 的长方形的对角的长方形的对角线从一个角跳到另一个角，问是否存在一串符合规定的着法使得线从一个角跳到另一个角，问是否存在一串符合规定的着法使得马可以从任一格子出发跳遍马可以从任一格子出发跳遍 8 88 8 的整个棋盘，并只到达每个格的整个棋盘，并只到达每个格子一次？子一次？ 56415835503960334744554059345138425746493653326145484354316237522053063221116132964214171425106192278231215128718326924* 五、五、E图与图与H图问题图问题旅行推销员问题旅行推销员问题 （货郎担问题）（货郎担问题） 一个推销员要去一些城市访问他的客户然后返回出发城市，一个推销员要去一些城市访问他的客户然后返回出发城市，问如何选择旅行路线可以使得总路程最短？问如何选择旅行路线可以使得总路程最短？ 以城市为点，以两个城市之间的旅行距离为权，构造一个以城市为点，以两个城市之间的旅行距离为权，构造一个赋权完全图赋权完全图 G G = ( = (V V , ,E ,wE ,w) ) 。 推销员的旅行路线应是推销员的旅行路线应是G G 的一条经过每个点至少一次的回路，的一条经过每个点至少一次的回路，且回路的长度尽可能短。且回路的长度尽可能短。 五、五、E图与图与H图问题图问题 与最短路问题相反，至今未找到有求解旅行商问题的有与最短路问题相反，至今未找到有求解旅行商问题的有效算法，我们试图寻找一个比较好的方法，但不一定是最优效算法，我们试图寻找一个比较好的方法，但不一定是最优解；首先给出近似最优的改良后的最邻近算法，称为解；首先给出近似最优的改良后的最邻近算法，称为改良圈改良圈算法，算法，改良圈算法是一种近似算法，给出的结果不一定是最改良圈算法是一种近似算法，给出的结果不一定是最优的，但是有理由认为它常常是比较好的。优的，但是有理由认为它常常是比较好的。 该算法的该算法的matlabmatlab程序为：程序为： 五、五、E图与图与H图问题图问题782022年年7月月26日日 五、五、E图与图与H图问题图问题792022年年7月月26日日 五、五、E图与图与H图问题图问题例：例：给定给定4 4个点的坐标为个点的坐标为(0,0),(100,1000),(0,2),(1000,0),(0,0),(100,1000),(0,2),(1000,0),试试用改良圈算法求通过这用改良圈算法求通过这4 4个点的个点的HamiltonHamilton圈。圈。 该问题的该问题的matlabmatlab程序为：程序为：clearv=0 0; 100 1000;0 2; 1000 0;for i=1:4 for j=1:4 w(i,j)=sqrt(v(i,1)-v(j,1)2+(v(i,2)-v(j,2)2); end endglf(w);802022年年7月月26日日 五、五、E图与图与H图问题图问题例：例：给定给定1414个点的坐标为个点的坐标为(51,67),(37,84),(41,94),(2,99), (51,67),(37,84),(41,94),(2,99), (18,54),(4,50),(24,42),(25,38),(13,40),(7,64),(