图论模型1.问题引入与分析2.图论的基本概念3.最短路问题及算法回回4.最小生成树及算法5.旅行售货员问题停停下下6.模型建立与求解1.问题引入与分析198年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：今年1998年夏天某县遭受水灾.为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视.巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.1）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线.2）假定巡视人员在各乡（镇）停留时间T2小时，在各村停留时间t1小时，汽车行驶速度V35公里/小时.要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.公路边的数字为该路段的公里数.2问题分析：本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到点O，使得总权（路程或时间）最小.本题是旅行售货员问题的延伸－多旅行售货员问题.本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.显然本问题更应属于NP完全问题.有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.2.图论的基本概念1图的概念2赋权图与子图3图的矩阵表示4图的顶点度5路和连通1图的概念定义一个图G是指一个二元组VGEG，其中:1VGv1v2v是非空有限集，称为顶点集，其中元素称为图G的顶点.2EG是顶点集VG中的无序或有序的元素偶对vivj组成的集合，即称为边集其中元素称为边.定义图G的阶是指图的顶点数VG用v来表示；图的边的数目EG用来表示.用GVGEG表示图，简记GVE.也用vivj来表示边vivj.例设GVGEG，其中：VGv1v2v3v4，EGe1e2e3e4e5e6，e1v1v1，e2v2v3，e3v1v3，e4v1v4，5v3v4，6v3v4.ee（见图2）定义若一个图的顶点集和边集都是有限集，则称其为有限图.只有一个顶点的图称为平凡图，其他的所有图都称为非平凡图.定义若图G中的边均为有序偶对vivj称G为有向图.称边evivj为有向边或弧称evivj是从vi连接vj，称vi为e的尾，称vj为e的头.若图G中的边均为无序偶对vivj，称G为无向图.称边evivj为无向边，称e连接vi和vj，顶点vi和vj称为e的端点.既有无向边又有有向边的图称为混合图.例设HVHEH，其中：VHu1u2u3u4u5，EHa1a2a3a4a5a6a7，a1u1u2，a2u2u2，a3u4u2，a4u4u5，a5u4u3，a6u3u4，a7u1u3.（见右图3）常用术语1边和它的两端点称为互相关联.2与同一条边关联的两个端点称为相邻的顶点，与同一个顶点点关联的两条边称为相邻的边.3端点重合为一点的边称为环，端点不相同的边称为连杆.4若一对顶点之间有两条以上的边联结，则这些边称为重边．5既没有环也没有重边的图，称为简单图．常用术语6任意两顶点都相邻的简单图称为完全图.记为Kv.7若VGXY，Y，且X中任意两顶点不X相邻，Y中任意两顶点不相邻，则称为二部图或偶图；若X中每一顶点皆与Y中一切顶点相邻称为完全二部图或完全偶图记为KmnmXnY．，8图K1n叫做星.X:x1x2x3X:x1x2x3Y:y1y2y3y4Y:y1y2y3y4K14K6二部图K342赋权图与子图定义若图GVGEG的每一条边e都赋以一个实数we，称we为边e的权，G连同边上的权称为赋权图.定义设GVE和GVE是两个图.1若VVEE称G是G的一个子图记GG.2若VV，E，则称G是G的生成子图.E3若VV，且V，以V为顶点集，以两端点均在V中的边的全体为边集的图G的子图，称为G的由V导出的子图，记为GV.4若EE，且E，以E为边集，以E的端点集为顶点集的图G的子图，称为G的由E导出的边导出的子图，记为GE.Gv1v2v3Ge3e4e5e63若VV，且V，以V为顶点集，以两端点均在V中的边的全体为边集的图G的子图，称为G的由V导出的子图，记为GV.4若EE，且E，以E为边集，以E的端点集为顶点集的图G的子图，称为G的由E导出的边导出的子图，记为GE.3图的矩阵表示邻接矩阵:以下均