数学建模最短路VIP免费

第八章最短路问题8.1图论基本概念与最小生成树8.2最短路问题y实际背景例1（公路连接问题）某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么如何决定在哪些城市间修建高速公路总成本最小？例2（最短路问题）一名货车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货车的运行速度是恒定的，那么这个问题相当于需要找到一条从甲地到乙地的最短路。例3（运输问题）某种原材料有M个产地，现在需要将原材料从产地运往N个使用工厂。假定M个产地的产量和N个工厂的需求量已知，单位产品从任一产地到任一工厂的运费已知，那么，如何安排运输方案可以使总运输成本最低？实际背景例4（指派问题）一家公司经理准备安排n名员工去完成n项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的收益不同，如何分配工作方案使总回报最大？例5（中国邮递员问题）一名邮递员负责投递某个街区的邮件。如何为他设计一条最短的投递路线？即从邮局出发，经过投递区内每条街道至少一次，最后返回邮局。例6（旅行商问题）一名推销员准备前往若干城市推销产品。如何为他设计一条最短的旅行路线？即从驻地出发，经过每个城市恰好一次，最后返回驻地。实际背景共同特点：（1）它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为优化问题。（2）它们都易于用图形的形式直观的描述和表达，数学上把这种与图相关的结构称为网络，与图和网络相关的优化问题称为网络优化。图论基本概念与最小生成树一、图的概念1、图的定义2、顶点的次数3、子图二、图的矩阵表示1、关联矩阵2、邻接矩阵三、最小生成树定义有序二元组G=(V,E)称为一个图.[1]是有穷非空集，称为顶点集其中的元素叫图G的顶点。[2]E称为边集，其中的元素称为图G的边。例设G=(V,E),其中G的图解如图12,,,nVvvv123412345,,,,,,,VvvvvEeeeee定义在图G中，与V中的有序偶(vi，vj)对应的边e，称为图的有向边（或弧），而与V中顶点的无序偶vivj相对应的边e，称为图的无向边.每一条边都是无向边的图，叫无向图；每一条边都是有向边的图，称为有向图；既有无向边又有有向边的图称为混合图.定义若将图G的每一条边e都对应一个实数w(e)，称w(e)为边的权，并称图G为赋权图.规定用记号和分别表示图的顶点数和边数.常用术语：（１）端点相同的边称为环．（２）若一对顶点之间有两条以上的边联结，则这些边称为重边．（３）有边联结的两个顶点称为相邻的顶点，有一个公共端点的边称为相邻的边．（４）边和它的端点称为互相关联的．（５）既没有环也没有平行边的图，称为简单图．（６）任意两顶点都相邻的简单图，称为完备图，记为Kn，其中n为顶点的数目．(7)若V=XY，XY=，X中任两顶点不相邻，Y中任两顶点不相邻，称G为二元图；若X中每一顶点皆与Y中一切顶点相邻，称为完备二元图，记为Km,n，其中m,n分别为X与Y的顶点数目．顶点的次数定义（１）在无向图中，与顶点v关联的边的数目（环算两次）称为v的次数，记为d(v)．（２）在有向图中，从顶点v引出的边的数目称为v的出度，记为d+(v)，从顶点v引入的边的数目称为的入度，记为d-(v)，d(v)=d+(v)+d-(v)称为v的次数．4)(4vd5)(3)(2)(444vdvdvd定理１)(2)()(GvdGVv推论１任何图中奇次顶点的总数必为偶数．例在一次聚会中，认识奇数个人的人数一定是偶数。子图定义设图G=(V,E),G1=(V1,E1)(1)若V1V，E1E,且V1则称G1是G的子图．特别地，若V1=V，则G1称为G的生成子图．(2)设V1V，且V1，以V1为顶点集、两个端点都在V1中的图G的边为边集的图G的子图，称为G的由V1导出的子图，记为G[V1].(3)设E1E,且E1,以E1为边集,E1的端点集为顶点集的图G的子图,称为G的由E1导出的子图,记为G[E1].GG[{v1,v4,v5}]G[{e1,e2,e3}]关联矩阵对无向图Ｇ，其关联矩阵Ｍ＝)(ijm，...