图论在大学生数学建模竞赛中的应用PPT课件

1、1,图论在大学生数学建模 竞赛中的应用,2,摘要：随着图论的发展，图论的理论和方法广泛应用于大学生数学建模竞赛中，讨论了大学生数学建模竞赛中如下图论问题的应用：二分图的最大匹配，最大点独立集；最佳推销员回路，哈密尔顿图；最小生成树等。,图论是数学的一个重要分支，它广泛应用于物理学，现代控制论，信息论，管理科学，计算机技术等诸多领域，对于自然科学，工程技术，经济管理和社会现象等诸多方面的问题，利用图论的理论和方法能够提供有力的数学模型使问题得到解决，在国内外大学生数学建模竞赛中，与图论的知识和方法有关的问题已出现多次，这里有针对性的讨论图论在大学生数学建模竞赛中的应用,3,1 二分图的最大匹配，

2、最大点独立集在大学生数学建模竞赛中的应用,定义1 若V(G)=XY，XY=,X,Y均非空，且图G的每一条边的两个顶点分别在X和Y中，则称图G为二分图。 定义2 图G的互不相邻的顶点子集称为点独立集。 问题1 某锁具厂生产一批锁具，每个锁具的钥匙有5个槽，每个槽的高度从（1,2,3,4,5,6）6个数中任取一个，由于工艺及其它原因，制造锁具时对五个槽的高度还有两个限制：至少有三个不同的数；相邻两槽的高度之差不能是5。满足以上条件的所有互不相同的锁具称为一批，另外，若两个锁具对应的5个槽中有四个高相同，另一个槽高只相差1，则可能互开，其他情形不可能互开。现在的问题是：一批锁具具有多少个？若60个装

3、一箱，团体购买多少箱不会出现互开现象？,4,分析 6种高度5个槽的钥匙最多可能有65=7776.通过排列组合，除去不满足条件的各种情况，可以算出一批锁具的总数为5880件。 由于两个锁具对应的5个槽高中有四个相同，另一个只相差1，被视为互开，那么它们各自槽高之和必为一个奇数，一个偶数。另外，槽高之和为奇数和偶数的锁具可以一一对应，因而各占一半：2940件。槽高之和为奇数（或偶数）的两锁具之间不能互开，所以若60个装一箱，2940个锁具可以装49箱，这49箱槽高之和为奇数或偶数的锁具，肯定不能互开，现在的问题是49箱是不是最大可能的？,5,建立模型 将锁具的互开关系用图表示，锁具集合用V=V1V

4、2表示，其中V1和V2分别表示槽高之和为奇数和偶数的锁具集合，若viV1，vjV2能够互开，则两点连一边，这样构成一个二分图，V1和V2都是点独立集，因为他们内部的点互不相邻，为了说明他们都是最大的独立集，引入点覆盖的概念，图G的顶点子集K称为一个点覆盖，如果图G的每一条边，至少有一个顶点包含在K里，点独立集与点覆盖有互补的关系。 设(G),(G)分别表示图G的最大点独立集所含点数，最小点覆盖所含点数，由上面的讨论有 定理1 (G)+(G)=|V(G)|. 类似地给出边独立集（匹配）和边覆盖的概念与关系，图G的边子集E1称为边覆盖，如果图G的任何一个顶点至少是E1当中一条边的顶点，(G)，(G

5、)分别表示图G的最大匹配所含边数，最小边覆盖所含边数，它们之间有如下关系： 定理2 若图G没有孤立顶点，即顶点的最小度大于0，则(G)+(G)=|V(G)|. 对于任何的匹配M和任何的点覆盖K，因为K至少要覆盖M当中的每一条边，所以|M|K|,当然最大匹配和最小点覆盖之间也有关系(G)(G)，特别地： 定理3 对于二分图G，有(G)=(G)，且如果顶点的最小度大于0，则 (G)=(G)。,6,引理1 二分图G=( V1V2 ,E) 存在饱和V1 的每个顶点的匹配等价于对所有V1的子集S有|NG(S)|S|，其中NG(S)表示S在图G的邻点集合。 模型求解 对问题1构造的二分图，由于奇数类锁具与

6、偶数类锁具的对称性，引理1满足，所以存在饱和 V1的每个顶点的匹配 M,而 V1的顶点互不相邻，因此2 940=IV1I lMI (G)= (G)=I VI-(G)， 从而点独立数 (G) I lV|-2 940=2 940由于奇数类点独立集和偶数类点独立集都有2 940个点，所以(G)=2 940，说明奇数类点集和偶数类点集都是最大的点独立集，因此49箱是不能互开的最大可能,7,2 哈密尔顿图、最佳推销员回路在大学生数学建模竞赛中的应用 定义3 经过图G的每个顶点正好一次的圈，称为图G的哈密尔顿圈，简称H圈 定义4 在加权图G=(V ,E)中,1,权最小的哈密尔顿圈称为最佳H圈；2,经过每个

7、顶点至少一次且权最小的闭通路称为最佳推销员回路 问题2 1998年全国大学生数学建模竞赛B题：灾情巡视路线问题题目给出了某县的乡(镇)、村公路网示意图，今年夏天该县遭受水灾为考察灾情、组织自救，县领导带领有关部门负责人到全县各乡(镇)、村巡视巡视路线指从县政府出发，走遍各乡(镇)、村，最后回到县政府的路线问题是:若分三组巡视，试设计总路程最短且各组尽可能均衡的巡视路线 分析 灾情巡视路线问题是一个寻求最佳推销员回路的问题最佳推销员回路的问题可转化为最佳H圈的问题。,8,建立模型 求最佳推销员回路的方法是由给定的图G=( V，E)构造一个以 V为顶点集的完备图G =(V ,E )，E 中每条边(

8、x ,y)的权等于顶点x 与y在图G中最短路径的权。 在图论中有以下定理 定理4 加权图G的最佳推销员回路的权和G 的最佳H圈的权相同 定理5 在加权完备图中求最佳H圈的问题是NP完全问题 模型求解 下面给出求加权图G=( V,E )的最佳推销员回路的近似算法： 1. 用图论软件包求出G中任意两个顶点间的最短路，构造出完备图G =(V ,E ). 2. 输入图G 的一个初始H圈 3. 用对角线完全算法产生一个初始H圈； 4. 随机搜索出G 中若干个H圈； 5.对2,3,4步所得每个H圈，用二边逐次修正法进行优化，得到近似最佳 H圈； 6求出的所有 H圈中,找出权最小的一个，此即要找的最佳H圈的

9、近似解然后用这个方法求解得出问题的解.,9,算法简介,二边逐次修正法,（1）任取初始H圈 C0=v1,v2,vi,vj,vm,v1 （2）对所有的i,j,1i+1jm，若 w(vi,vj)+w(vi+1,vj+1) w(vi,vi+1)+w(vj,vj+1) 则在C0中删去边（vi,vi+1）和（vj,vj+1）而加入边（vi,vj）和(vi+1,vj+1)，形成新的H圈C，即 C=v1,v2,vi,vj,vj-1,vi+1,vj+1,vi,v1 （3）C0C,重复步骤（2），直到条件不满足为止，最后得到的C即为所求。,10,例对下图的K6,用二边逐次修正法求较优H圈.,较优H圈:,其权为W(

10、C3)=192,11,3 最小生成树在大学生数学建模竞赛中的应用 有一石油公司计划为它拥有的许多存储站设计一个管道连接系统，它共有9个存储站，如果两个存储站之间可以修管道，就用一条边连接起来，用一个数表示修这两站之间的管道所需的费用，这样这个公司所有的存储站和可能修管道的情况，如图所示,12,设计计划要求：管道网可以把任意两个存储站都连接起来，且修管道的费用最低 分析从图论的角度来说，该图是一个连通图，每一个边都被赋予了一个数，称之为赋权图问题是确定出另一个连通图，其顶点集与原图的顶点集一样，仅保留原图中的一部分边，把这一确定的新图称作原图的生成子图，并且使子图的所有边的权之和最小 建立模型要

11、找的子图必须是连通的，直观地说子图具有的边应尽量地少，即这个子图不能含有任何回路，因为去掉回路中的任何边都不会影响它的连通性质，我们把不包含回路的生成子图称为原图的生成树不含回路的连通图，又称树树图中的顶点有两类，一类是度为1的顶点，称为悬挂点，另一类是度大于l的顶点，称为割点一旦去掉割点及与之相连的边，图就不连通了 容易得出以下结论： 定理7 一个具有n个顶点的连通图，连通子图是生成树的充要条件为它具有n一1条边且无回路 现在的问题变成了求权重最小的生成树了，简称为最小生成树下面给出一个求最小生成树的算法：,13,第一步：我们把所有的边按其权重从小到大排列起来； 第二步：先选定第一条边； 第三步：边序列中选择下一条边的原则是此边与前面的边全在一起不构成回路； 第四步：直到选出n-1条边,第一步：我们按权重从小到大把边排列为： h(9O)一g(90)f(90)一e(100)一a(100)一b(100)一d(100)一 i(150)一c(200)一j(200)一l(200) 一p(300)一