资源描述：
《2010集训专题三图论模型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2010数学建模集训班专题讲座--图论模型的建立与分析有图有真相，有你更精彩赵承业2010/7/15专题图的表示与锁具问题最小生成树、TSP和灾区巡视问题最短路、网络流和运输问题作业图的表示与锁具问题不积硅步，无以至千里--荀子·劝学图的矩阵表示邻接矩阵:1)对无向图，其邻接矩阵，其中：(以下均假设图为简单图).2)对有向图,其邻接矩阵,其中：其中：3)对有向赋权图,其邻接矩阵,对于无向赋权图的邻接矩阵可类似定义.关联矩阵1)对无向图，其关联矩阵,其中：2)对有向图，其关联矩阵,其中：两点间长度为k的路径数目如果已经一
2、个图的邻接矩阵A，我们想知道任意两个顶点之间长度为k的路径有多少条怎么办？一个简单的办法如下令A=A+IB=AXAX......XA（k个A相乘）那么B中元素bij的值就是从i点出发到j点的路径数目通过下面的案例我们讨论一下这个方法的应用1994年全国大学生数学建模竞赛B题(锁具装箱)某厂生产一种弹子锁具,每个锁具的钥匙有5个槽,每个槽的高度从{1,2,3,4,5,6}中任取一数.由于工艺及其它原因,制造锁具时对5个槽的高度还有两个限制:(1)至少有3个不同的数;(2)相邻两槽的高度之差不能为5.满足以上条件制造出来的
3、所有互不相同的锁具称为一批.我们的问题是如何确定每一批锁具的个数?求解上述问题的一般方法计算机枚举排列组合计数缺点：计算量都比较大图论方法易见,x=x1-x2,其中,x1=相邻两槽高度之差不为5的锁具数,即:满足限制条件(2)的锁具数;x2=相邻两槽高度之差不为5且槽高仅有1个或2个的锁具数,即:满足限制条件(2)但不满足限制条件(1)的锁具数.我们用图论方法计算x1和x2.图论方法基本引理令Ak=A×A×⋯×A－－－k次={a(k)ij}n×n,则a(k)ij=G中以vi,vj为端点的长度为k的道路数.为利用上述引理
4、计算x1和x2,我们构造无向图G=(V,E)(如图1所示)V={1,2,3,4,5,6},E={ij
5、i,j∈V且
6、i-j
7、≠5}.图论方法在G中,每一条长度为4的道路对应于一个相邻两槽高度之差不为5的锁具,即:满足限制条件(2)的锁具.反之,亦然.于是,可通过G的邻接矩阵A计算x1,具体步骤如下:图论方法因此又令x2=y1+y2+y3+y4+y5+y6,其中,yi=满足限制条件(2)但不满足限制条件(1)且首位为i的锁具数,(i=1,2,3,4,5,6).显然,y1=y6,y3=y4=y5=y2,我们只需计算y1和y
8、2.图论方法计算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,22,23,24,25,26的情形,类似计算可得y2=1+(4+4+4+4+4-1)×5=76.于是,x2=61×2+76×4=426,x=6306-426=588
9、0.最小生成树、TSP和灾区巡视问题山穷水尽疑无路，柳暗花明又一村--陆游·游山西村98年全国大学生数学建模竞赛B题最佳灾情巡视路线今年(1998年)夏天某县遭受水灾.为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视.巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.98年全国大学生数学建模竞赛B题最佳灾情巡视路线问题1若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线.分析本题显然是一个加权图上求最短回路的问题我们可以借助图论的方法解决主要考虑两个基本的方法
10、最小生成树方法旅行商（TSP）方法问题1的分析与求解--最小生成树法问题：如何分成相对均衡的三组？先求图的最小生成树，理由如下最小生成树包含图的所有顶点，且最小生成树的边权是相邻顶点之间的距离，它描述了顶点之间的相近程度，可以考虑利用它来进行分块问题1的分析与求解--最小生成树法利用Kruskal算法，求得最小生成树如下问题1的分析与求解--最小生成树法对上面的最小生成树分解成三个子树分解原则分解点为O点或尽量接近O点分解得到的子图的顶点数尽可能接近17尽量使得分解得到的子图为连通图尽量使子图与点O的最短路的上点在该子
11、图内尽量使各子图内部的点在内部形成回路问题1的分析与求解--最小生成树法分解的结果问题1的分析与求解--最小生成树法几个优化原则扩环原则子图有孤立枝，扩环后权值应减小增环原则环路上某个顶点有两枝，且有使两枝成环的边存在，考虑增环，增环后权值应减小换枝原则环路上某顶点长出一条枝，该枝末梢和环路另一顶点接近，可考虑换枝问题1的分析与求
