图论数学建模精品文稿.ppt

图论数学建模第1页，本讲稿共43页1引言引言 图论起源于图论起源于1818世纪。第一篇图论论文是瑞士数学家世纪。第一篇图论论文是瑞士数学家欧拉于欧拉于1736 1736 年发表的年发表的“哥尼斯堡的七座桥哥尼斯堡的七座桥”。图论中所谓的图论中所谓的“图图”是指是指某类具体事物和这些某类具体事物和这些事物之间的联系事物之间的联系。如果我们用。如果我们用点点表示这些表示这些具体事物具体事物，用连接两点的用连接两点的线段线段（直的或曲的）表示两个（直的或曲的）表示两个事物的特事物的特定的联系定的联系，就得到了描述这个，就得到了描述这个“图图”的几何形象。图的几何形象。图论为任何一个包含了一种二元关系的离散系统提供论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来。有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来。问题是问题是要从这四块陆地中的任何一块开始通过每一座桥正要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。好一次，再回到起点。第2页，本讲稿共43页第3页，本讲稿共43页 当然可以通过试验去尝试解决这个问题，但该当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有用连接相应两点的一条线来代替，从而得到一个有四四个个“点点”，七条，七条“线线”的的“图图”。问题成为。问题成为从任一点出从任一点出发一笔画出七条线再回到起点发一笔画出七条线再回到起点。欧拉考察了一般一笔画。欧拉考察了一般一笔画的结构特点，给出了的结构特点，给出了一笔画的一个判定法则一笔画的一个判定法则：这个这个图是连通的，且每个点都与偶数线相关联，图是连通的，且每个点都与偶数线相关联，将这个将这个判定法则应用于七桥问题，得到了判定法则应用于七桥问题，得到了“不可能走通不可能走通”的结的结果，不但彻底解决了这个问题，而且开创了图论研究果，不但彻底解决了这个问题，而且开创了图论研究的先河。的先河。第4页，本讲稿共43页 我们首先通过一些例子来了解网络优化问题。我们首先通过一些例子来了解网络优化问题。例例1 1 最短路问题最短路问题（SPPSPPshortest path problemshortest path problem）一名货柜车司机奉命在最短的时间内将一车货物从甲地一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。条从甲地到乙地的最短路。例例2 2 公路连接问题公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？在哪些城市间修建高速公路，使得总成本最小？第5页，本讲稿共43页例例3 3 指派问题指派问题（assignment problemassignment problem）一家公司经理准备安排名员工去完成项任务，一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员每人一项。由于各员工的特点不同，不同的员 工去完成同一项任务时所获得的回报是不同的。工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？如何分配工作方案可以使总回报最大？例例4 4 中国邮递员问题中国邮递员问题（CPPCPPchinese postman chinese postman problem problem）一名邮递员负责投递某个街区的邮件。如何为他一名邮递员负责投递某个街区的邮件。如何为他 （她）设计一条最短的投递路线（从邮局出发，（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授？由于这一问题是我国管梅谷教授19601960年首先年首先 提的，所以国际上称之为中国邮递员问题。提的，所以国际上称之为中国邮递员问题。第6页，本讲稿共43页例例5 5 运输问题运输问题（transportation problemtransportation problem）某种原材料有个产地，现在需要将原材料从产地运往某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定个产地的产量和家工个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本运费已知，那么如何安排运输方案可以使总运输成本最低？最低？上述问题有两个共同的特点：上述问题有两个共同的特点：一是一是它们的目的都是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化安排或方案，数学上把这种问题称为最优化或优化（optimizationoptimization）问题；）问题；二是二是它们都易于用图形的形它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称式直观地描述和表达，数学上把这种与图相关的结构称为网络（为网络（networknetwork）。与图和网络相关的最优化问题就是）。与图和网络相关的最优化问题就是网络最优化或称网络优化网络最优化或称网络优化 （netwok optimizationnetwok optimization）问）问题。题。第7页，本讲稿共43页2图与网络的基本概念图与网络的基本概念 2.1 2.1 无向图无向图 一个无向图一个无向图(undirected graph)(undirected graph)是由一个非空有限集合是由一个非空有限集合 和和 中某些元素的无序对集合中某些元素的无序对集合 构成的二元组，记构成的二元组，记为为 。其中其中 称为称为图的顶点集图的顶点集（vertex setvertex set）或节点集（或节点集（node setnode set），），中的每一个元素中的每一个元素 称为该图的一个顶点（称为该图的一个顶点（vertexvertex）或节点（）或节点（nodenode）；）；称为称为图的边集图的边集 （edge setedge set），），中的每一个元素中的每一个元素 记为记为 或或 ，被称为该图，被称为该图的一条从的一条从 到到 的边（的边（edgeedge）第8页，本讲稿共43页一个图称为一个图称为有限图有限图，如果它的顶点集和边集都有，如果它的顶点集和边集都有 限。图的顶点数用符号限。图的顶点数用符号 或或 表示，边数用表示，边数用 或或 表示。表示。当讨论的图只有一个时，总是用当讨论的图只有一个时，总是用G G来表示这个图。从来表示这个图。从而在图论符号中我们常略去字母而在图论符号中我们常略去字母G G，例如，例如:分别用分别用 代替代替 。端点重合为一点的边称为端点重合为一点的边称为环环(loop)(loop)。一个图称为一个图称为简单图简单图(simple graph)(simple graph)，如果它既没有环也，如果它既没有环也没有两条边连接同一对顶点。没有两条边连接同一对顶点。第9页，本讲稿共43页2.2 2.2 有向图有向图定义定义 一个有向图（一个有向图（directed graphdirected graph或或 digraphdigraph）G G是由是由一个非空有限集合一个非空有限集合V V和和V V中某些元素的有序对集合构成的中某些元素的有序对集合构成的二元组，记为二元组，记为 其中其中 称为图的称为图的顶点集或节点集顶点集或节点集 .称为图的称为图的弧集弧集（arc setarc set），），A A中的每中的每一个元素一个元素(即中某两个元素的有序对即中某两个元素的有序对)记为记为 或或 ，当弧当弧 时，时，称为尾（称为尾（tailtail），），为头（为头（headhead）.第10页，本讲稿共43页2.3 2.3 完全图、二分图完全图、二分图每一对不同的顶点都有一条边相连的简单图称为每一对不同的顶点都有一条边相连的简单图称为完完全图全图(complete graph)(complete graph)。n n个顶点的完全图记为个顶点的完全图记为 。若若 ，（这里（这里 表示集合表示集合X X中的元素个数），中的元素个数），X X中无相邻顶点对，中无相邻顶点对，Y Y中亦然，则称中亦然，则称G G为为二分图二分图(bipartite graph)(bipartite graph)；特别地，若；特别地，若 ，则，则 ，则称，则称G G为为完全二分图完全二分图，记成，记成 。第11页，本讲稿共43页2.4 2.4 子图子图 如果如果 ,图图H H叫做图叫做图G G的子图的子图（subgraphsubgraph），记作），记作 。若。若H H是是G G的子图，则的子图，则G G称称为为H H的母图。的母图。2.5 2.5 顶点的度顶点的度 设设 ，G G中与中与v v关联的边数（每个环算作两条边）关联的边数（每个环算作两条边）称为称为v v的度的度(degree)(degree)，记作，记作 。若。若 是奇数，称是奇数，称v v是奇顶点是奇顶点(odd point)(odd point)；若是偶数，称；若是偶数，称v v是偶顶点是偶顶点(even(even point)point)。关于顶点的度，我们有如下结果：。关于顶点的度，我们有如下结果：(i)(i)(ii)(ii)任意一个图的奇顶点的个数是偶数任意一个图的奇顶点的个数是偶数。第12页，本讲稿共43页2.6 2.6 图与网络的数据结构图与网络的数据结构网络优化研究的是网络上的各种优化模型与算法网络优化研究的是网络上的各种优化模型与算法为了在计算机上实现网络优化的算法，首先我们必为了在计算机上实现网络优化的算法，首先我们必须有一种方法（即数据结构）在计算机上来描述图须有一种方法（即数据结构）在计算机上来描述图与网络。与网络。这里我们介绍计算机上用来描述图与网络的这里我们介绍计算机上用来描述图与网络的5 5种常用种常用表示方法：表示方法：邻接矩阵表示法、关联矩阵表示法、弧表表示邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法。法、邻接表表示法和星形表示法。在下面数据结构的讨论中，我们首先假设在下面数据结构的讨论中，我们首先假设是是一个简单有向图一个简单有向图，并假设，并假设V中的中的顶点用自然数顶点用自然数1,2,n表示或编号，表示或编号，A中的弧用自然数中的弧用自然数1,2,m表示或编号。表示或编号。第13页，本讲稿共43页（i）邻接矩阵表示法）邻接矩阵表示法邻接矩阵表示法是将图以邻接矩阵（邻接矩阵表示法是将图以邻接矩阵（adjacency adjacency matrixmatrix）的形式存储在计算机中。图）的形式存储在计算机中。图 的邻的邻接矩阵是如下定义的：接矩阵是如下定义的：C C是一个是一个n*nn*n的的0-10-1矩阵，即矩阵，即也就是说，如果两节点之间有一条弧，则邻接矩阵中对应也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为的元素为1 1；否则为；否则为0 0。第14页，本讲稿共43页例例1 1 对于所示的图，可以用邻接矩阵表示为对于所示的图，可以用邻接矩阵表示为同样，对于网络中的权，也可以用类似邻接矩阵的矩阵同样，对于网络中的权，也可以用类似邻接矩阵的矩阵表示。只是此时一条弧所对应的元素不再是表示。只是此时一条弧所对应的元素不再是1 1，而是，而是相相应的权应的权而已。如果网络中每条弧赋有多种权，则可以用多而已。如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权。个矩阵表示这些权。第15页，本讲稿共43页（iiii）关联矩阵表示法）关联矩阵表示法关联矩阵表示法是将图以关联矩阵（关联矩阵表示法是将图以关联矩阵（incidence incidence matrixmatrix）的形式存储在计算机中）的形式存储在计算机中 图图 的关联矩阵的关联矩阵B B是如下定义的：是如下定义的：B B是一个是一个n*mn*m的矩阵，即的矩阵，即第16页，本讲稿共43页如果一个节点是一条弧的如果一个节点是一条弧的起点起点，则关联矩阵中对应的元，则关联矩阵中对应的元素为素为1 1；如果一个节点是一条弧的；如果一个节点是一条弧的终点终点，则关联矩阵，则关联矩阵中对应的元素为中对应的元素为-1-1；如果一个节点与一条弧；如果一个节点与一条弧不关联不关联，则关联矩阵中对应的元素为则关联矩阵中对应的元素为0 0。例例2 2 对于例对于例1 1所示的图，如果关联矩阵中每列对应弧的所示的图，如果关联矩阵中每列对应弧的顺序为顺序为(1,2)(1,2)，(1,3)(1,3)，(2,4)(2,4)，(3,2)(3,2)，(4,3)(4,3)，(4,5)(4,5)，(5,3)(5,3)和和(5,4)(5,4)，则关联矩阵表示为，则关联矩阵表示为（列单位为弧）（列单位为弧）第17页，本讲稿共43页（iiiiii）弧表示法）弧表示法弧表表示法将图以弧表（弧表表示法将图以弧表（arc listarc list）的形式存储）的形式存储在计算机中。所谓图的弧表，也就是图的弧集合在计算机中。所谓图的弧表，也就是图的弧集合中的所有有序对。中的所有有序对。例例3 3，假设弧，假设弧(1,2)(1,2)，(1,3)(1,3)，(2,4)(2,4)，(3,2)(3,2)，(4,3)(4,3)，(4,5)(4,5)，(5,3)(5,3)和和(5,4)(5,4)上的权分别为上的权分别为8 8，9 9，6 6，4 4，0 0，3 3，6 6和和7 7，则弧表表示如下：，则弧表表示如下：起点起点11234455终终点点23423534权权89640367第18页，本讲稿共43页（iviv）邻接表表示法）邻接表表示法邻接表表示法将图以邻接表（邻接表表示法将图以邻接表（adjacency listsadjacency lists）的形）的形式存储在计算机中。式存储在计算机中。所谓图的邻接表，也就是图的所有节点的邻接表的集合；所谓图的邻接表，也就是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是它的所有出弧而对每个节点，它的邻接表就是它的所有出弧。邻接。邻接表表示法就是对图的每个节点，用一个单向链表列出从该表表示法就是对图的每个节点，用一个单向链表列出从该节点出发的所有弧，链表中每个单元对应于一条出弧。节点出发的所有弧，链表中每个单元对应于一条出弧。为为了记录弧上的权，链表中每个单元除列出弧的另一个端点了记录弧上的权，链表中每个单元除列出弧的另一个端点外，还可以包含弧上的权等作为数据域外，还可以包含弧上的权等作为数据域。图的整个邻接。图的整个邻接表可以用一个指针数组表示。表可以用一个指针数组表示。第19页，本讲稿共43页对于有向图对于有向图，一般用，一般用表示节点的邻接表，即节点的所有出弧构成的集合或表示节点的邻接表，即节点的所有出弧构成的集合或链表（实际上只需要列出弧的另一个端点，即弧的链表（实际上只需要列出弧的另一个端点，即弧的头）。例如上面例子，头）。例如上面例子，等。等。第20页，本讲稿共43页（v v）星形表示法）星形表示法星形（星形（starstar）表示法的思想与邻接表表示法的思想）表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点，它也是记录从该有一定的相似之处。对每个节点，它也是记录从该节点出发的所有弧，但它不是采用单向链表而是采节点出发的所有弧，但它不是采用单向链表而是采用一个单一的数组表示。用一个单一的数组表示。记录弧信息的数组弧编号12345678起点11234455终点23423534权89640367第21页，本讲稿共43页3应用应用最短路问题最短路问题3.1 3.1 两个指定顶点之间的最短路径两个指定顶点之间的最短路径问题如下：给出了一个连接若干个城镇的铁路网络，问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。在这个网络的两个指定城镇间，找一条最短铁路线。以各城镇为图以各城镇为图G G的顶点，两城镇间的直通铁路为图的顶点，两城镇间的直通铁路为图G G相相应两顶点间的边，得图应两顶点间的边，得图G G。对。对G G的每一边的每一边e e，赋以一个实，赋以一个实数数 直通铁路的长度，称为直通铁路的长度，称为e e的权，得到赋权图的权，得到赋权图G G。G G的子图的权是指子图的子图的权是指子图G G的各边的权和。的各边的权和。问题就是求赋权图中指定的两个顶点问题就是求赋权图中指定的两个顶点 间的具最小权间的具最小权的轨。这条轨叫做的轨。这条轨叫做 间的最短路，它的权叫做间的最短路，它的权叫做 间的距离，亦记作间的距离，亦记作 。第22页，本讲稿共43页求最短路已有成熟的算法：求最短路已有成熟的算法：迪克斯特拉迪克斯特拉（DijkstraDijkstra）算法，其基本思想是按距算法，其基本思想是按距 从近到远为顺序，依次从近到远为顺序，依次求得求得 到的到的G G各顶点的最短路和距离，直至（或直各顶点的最短路和距离，直至（或直至的所有顶点），算法结束。为避免重复并保留每至的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法一步的计算信息，采用了标号算法。下面是该算法。(i)(i)令令 ，对，对 令令 ，。(ii)(ii)对每个对每个 ,用用 代替代替 计算计算 ，把达到这个最小值的一个顶点，把达到这个最小值的一个顶点 记为记为 ，令，令 。(iii)(iii)若若 ，停止；若，停止；若 ，用，用i+1i+1代替代替 i i，转，转(ii)(ii)。第23页，本讲稿共43页找出找出u0u0到其他各点的最短路径到其他各点的最短路径第24页，本讲稿共43页第25页，本讲稿共43页3.2每对顶点之间的最短路径每对顶点之间的最短路径计算赋权图中各对顶点之间最短路径，显然可以调用计算赋权图中各对顶点之间最短路径，显然可以调用DijkstraDijkstra算法。具体方法是：算法。具体方法是：每次以不同的顶点作每次以不同的顶点作为起点为起点，用，用DijkstraDijkstra算法求出从该起点到其余顶点的最算法求出从该起点到其余顶点的最短路径，反复执行次这样的操作，就可得到从每一个顶点短路径，反复执行次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。到其它顶点的最短路径。第二种解决这一问题的方法是由第二种解决这一问题的方法是由Floyd R WFloyd R W提出的算提出的算法，称之为法，称之为FloydFloyd算法。算法。第26页，本讲稿共43页假设图权的邻接矩阵为，假设图权的邻接矩阵为，来存放各边长度，其中：来存放各边长度，其中：；之间没有边，在程序中以各边都不之间没有边，在程序中以各边都不 可能达到的充分大的数代替；可能达到的充分大的数代替；是是 i,ji,j之间边的长度，之间边的长度，。第27页，本讲稿共43页FloydFloyd算法的基本思想是：递推产生一个矩阵序列算法的基本思想是：递推产生一个矩阵序列 ，其中，其中 表示从顶点表示从顶点 到顶点到顶点 的路径上所经过的顶点序号不大于的路径上所经过的顶点序号不大于k k 的最短路径长度。的最短路径长度。计算时用迭代公式：计算时用迭代公式：k k是迭代次数，是迭代次数，。最后，当最后，当k=nk=n时，时，即是各顶点之间的最短通路值。即是各顶点之间的最短通路值。(例题见附件例题见附件)第28页，本讲稿共43页4树树4.1 4.1 基本概念基本概念连通的无圈图叫做树，记之为连通的无圈图叫做树，记之为T T。4.2 4.2 应用应用连线问题连线问题 欲修筑连接欲修筑连接n n个城市的铁路，已知城与城之间的铁个城市的铁路，已知城与城之间的铁路造价为路造价为 ，设计一个线路图，使总造价最低。，设计一个线路图，使总造价最低。连线问题的数学模型是在连通赋权图上求权最小连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具有最小权的生成树叫做最小生的生成树。赋权图的具有最小权的生成树叫做最小生成树。成树。第29页，本讲稿共43页定理定理定理定理 设设设设GG是具有是具有是具有是具有n n个顶点的图，则下述命题等价：个顶点的图，则下述命题等价：个顶点的图，则下述命题等价：个顶点的图，则下述命题等价：1)G是树（是树（G无圈且连通）；无圈且连通）；2)G无圈，且有无圈，且有n-1条边；条边；3)G连通，且有连通，且有n-1条边；条边；4)G无圈，但添加任一条新边恰好产生一个圈无圈，但添加任一条新边恰好产生一个圈;5)G连通，且删去一条边就不连通了（即连通，且删去一条边就不连通了（即G为为最最最小连通图最小连通图）；）；6)G中任意两顶点间有唯一一条路中任意两顶点间有唯一一条路.第30页，本讲稿共43页找图中生成树的方法找图中生成树的方法可分为两种：避圈法和破圈法可分为两种：避圈法和破圈法A避圈法避圈法:深探法和广探法深探法和广探法B破圈法破圈法第31页，本讲稿共43页A A 避圈法避圈法 这种方法就是在已给的图这种方法就是在已给的图G中，每步选出一条边中，每步选出一条边使它与已选边不构成圈，直到选够使它与已选边不构成圈，直到选够n-1条边为止条边为止.这种这种方法可称为方法可称为“避圈法避圈法”或或“加边法加边法”在避圈法中，按照边的选法不同，找图中生成树的方在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：法可分为两种：深探法深探法和和广探法广探法.第32页，本讲稿共43页a)深探法深探法若这样的边的另一端均已有标号，就退到标号为若这样的边的另一端均已有标号，就退到标号为步骤如下：步骤如下：i)在点集在点集V中任取一点中任取一点u,ii)若某点若某点v已得标号，检已得标号，检端是否均已标号端是否均已标号.若有边若有边vw之之w未标号未标号,则给则给w代代v，重复，重复ii).i-1的的r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止.给以标号给以标号0.查一端点为查一端点为v的各边，另一的各边，另一w以标号以标号i+1，记下边，记下边vw.令令012345678910111213例例用深探法求出下图用深探法求出下图10的一棵生成树的一棵生成树第33页，本讲稿共43页b)广探法广探法步骤如下：步骤如下：i)在点集在点集V中任取一点中任取一点u,ii)令所有标号令所有标号i的点集为的点集为是否均已标号是否均已标号.对所有未标对所有未标号之点均标以号之点均标以i+1,记下这些记下这些iii)对标号对标号i+1的点重复步的点重复步步骤步骤ii)，直到全部点得到，直到全部点得到给给u以标号以标号0.Vi,检查检查Vi,VVi中的边端点中的边端点边边.例例用广探法求出下图用广探法求出下图10的一棵生成树的一棵生成树标号为止标号为止.图1031012213212234第34页，本讲稿共43页B B 破圈法破圈法破圈法破圈法 相对于避圈法，还有一种求生成树的方法叫做相对于避圈法，还有一种求生成树的方法叫做“破破圈法圈法”.这种方法就是在图这种方法就是在图G G中任取一个圈，任意舍弃一中任取一个圈，任意舍弃一条边，将这个圈破掉，重复这个步骤直到图条边，将这个圈破掉，重复这个步骤直到图G G中没有圈为止中没有圈为止.例例用破圈法求出用破圈法求出下图的一棵生成树下图的一棵生成树.图的生成树不是唯一的图的生成树不是唯一的.第35页，本讲稿共43页A A A A Kruskal Kruskal Kruskal Kruskal算法（或避圈法）算法（或避圈法）算法（或避圈法）算法（或避圈法）步骤如下：步骤如下：1)选择边选择边e1，使得，使得w(e1)尽可能小；尽可能小；2)若已选定边若已选定边，则从，则从中选取中选取，使得，使得:i)为无圈图，为无圈图，ii)是满足是满足i)的尽可能小的权，的尽可能小的权，3)当第当第2)步不能继续执行时，则停止步不能继续执行时，则停止.定理定理4由由Kruskal算法构作的任何生成树算法构作的任何生成树都是最小树都是最小树.最小生成树与算法最小生成树与算法第36页，本讲稿共43页例例用用Kruskal算法求下图的最小树算法求下图的最小树.在左图中在左图中权值权值最小的边有最小的边有任取一条任取一条在在中选取权值中选取权值最小的边最小的边中权值最小边有中权值最小边有,从中选从中选任取一条边任取一条边会与已选边构成圈会与已选边构成圈,故停止故停止,得得中选取在中选取中选取在中选取中选取中选取.但但与与都都第37页，本讲稿共43页B B破圈法破圈法破圈法破圈法算法算法2步骤如下：步骤如下：1)1)从图从图G G中任选一棵树中任选一棵树T T1 1.2)2)加上一条弦加上一条弦e e1 1，T T1 1+e+e1 1中中 立即生成一个圈立即生成一个圈.去掉此去掉此圈中最大权边，得到新圈中最大权边，得到新树树T T2 2,以以T T2 2代代T T1 1,重复重复2)2)再再检查剩余的弦，直到全检查剩余的弦，直到全部弦检查完毕为止部弦检查完毕为止.例例用破圈法求下图的最小树用破圈法求下图的最小树.第38页，本讲稿共43页 prim prim算法构造最小生成树算法构造最小生成树 设置两个集合设置两个集合P P和和Q,Q,其中其中P P用于存放的最小生成用于存放的最小生成树树G G中的顶点，集合中的顶点，集合Q Q存放的最小生成树存放的最小生成树G G中的边。令中的边。令集合集合P P的初值为的初值为 （假设构造最小生成树时，从（假设构造最小生成树时，从顶点顶点 出发），集合出发），集合Q Q的初值为的初值为 。primprim算法的思想是算法的思想是，从所有，从所有 ，的边的边中，选取具有最小权值的边中，选取具有最小权值的边 ，将顶点，将顶点v v加入加入集合集合P P中，将边中，将边pvpv加入集合加入集合Q Q中，如此不断重复，直中，如此不断重复，直到到 P=V P=V 时，最小生成树构造完毕，这时集合时，最小生成树构造完毕，这时集合Q Q中包中包含了最小生成树的所有边。含了最小生成树的所有边。第39页，本讲稿共43页例例11用用prim算法求右图的最小生成树。算法求右图的最小生成树。我们用的第一、二、三行分别表示生成树边的起点、终点、权集合。我们用的第一、二、三行分别表示生成树边的起点、终点、权集合。MatlabMatlab程序如下：程序如下：clc;clear;clc;clear;M=1000;M=1000;a(1,2)=50;a(1,3)=60;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;a(5,6)=70;a=a;zeros(2,7);a=a;zeros(2,7);a=a+a;a(find(a=0)=M;a=a+a;a(find(a=0)=M;result=;p=1;tb=2:length(a);result=;p=1;tb=2:length(a);while length(result)=length(a)-1 while length(result)=length(a)-1 result=temp=a(p,tb);temp=temp(:);temp=a(p,tb);temp=temp(:);125447d=min(temp);d=min(temp);254673 jb,kb=find(a(p,tb)=d);jb,kb=find(a(p,tb)=d);504050304245 j=p(jb(1);k=tb(kb(1);j=p(jb(1);k=tb(kb(1);result=result,j;k;d;p=p,k;tb(find(tb=k)=;result=result,j;k;d;p=p,k;tb(find(tb=k)=;endendresultresult第40页，本讲稿共43页例例 从北京（从北京（PePe）乘飞机到东京）乘飞机到东京(T)(T)、纽约、纽约(N)(N)、墨西哥城墨西哥城(M)(M)、伦敦、伦敦(L)(L)、巴黎、巴黎(Pa)(Pa)五城市做旅游，五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如下表使旅程最短？各城市之间的航线距离如下表：LMNPaPeTL5635215160M5621577870N3521366868Pa2157365161Pe5178685113T6070686113第41页，本讲稿共43页解：编写程序如下：clc,cleara(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;a(3,4)=36;a(3,5)=68;a(3,6)=68;a(4,5)=51;a(4,6)=61;a(5,6)=13;a(6,:)=0;a=a+a;c1=5 1:4 6;L=length(c1);flag=1;while flag0 flag=0;for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1)0 flag=0;for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1).a(c1(m),c1(m+1)+a(c1(n),c1(n+1)flag=1;c1(m+1:n)=c1(n:-1:m+1);end end endendsum1=0;for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1);endif sum1sum sum=sum1;circle=c1;endcircle,sum第43页，本讲稿共43页