教案图论模型.pptx

1. 问题引入与分析;1. 问题引入与分析; 1）若分三组（路）巡视，试设计总路程最;公路边的数字为该路段的公里数.;2) 问题分析：;　 如第一问是三个旅行售货员问题，第二问是四;2.图论的基本概念;1) 图的概念; 定义 若一个图的顶点集和边集都是有限集，则称; 定义若图G中的边均为有序偶对; 常用术语; 常用术语;2) 赋权图与子图 ;;3) 图的矩阵表示 ;2) 对有向图 ,其邻接矩阵 ,其中： ;其中：;关联矩阵 ;2) 对有向图 ，其关联矩阵 ,;4) 图的顶点度;5) 路和连通; 定义; 6) 图G中任意两点皆连通的图称为连通图． ;3．最短路问题及算法; 2) 在赋权图G中，从顶点u到顶点v的具有最小权;1) 赋权图中从给定点到其余顶点的最短路;Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.;Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.;Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.;Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.;Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.;Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.;Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.;Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.;Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.;Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.;Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.;Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.;定义 根据顶点v的标号l(v)的取值途径，使 到v;;Dijkstra算法：求G中从顶点u0到其余顶点的最短路;算法步骤：;首先写出带权邻接矩阵;;2) 求赋权图中任意两顶点间的最短路;算法的基本思想;（I）求距离矩阵的方法.;（II）求路径矩阵的方法.;;（IV）Floyd算法：求任意两顶点间的最短路.;例 求下图中加权图的任意两点间的距离与路径. ;;;;;;;4．最小生成树及算法;定理2 设G是具有n个顶点的图，则下述命题等价：;2）图的生成树;;（II）找图中生成树的方法;A 避圈法 ;a) 深探法;13;3;3;B 破圈法;B 破圈法;3) 最小生成树与算法;A Kruskal算法（或避圈法）;例10用Kruskal算法求下图的最小树.;B破圈法;5. 旅行售货员问题;旅行售货员问题或货郎担问题. ;一个可行的???法 :;定义 若对于某一对i和j，有;例对下图16的K6,用二边逐次修正法求较优H圈.; 分析: 找出的这个解的好坏可用最优H圈的权;6. 最佳灾情巡视路线的模型的建立与求解;最佳旅行售货员问题是NP—完全问题,采用一种; 问题一 若分为三组巡视，设计总路程最短且各;; 而图中节点数较多，为53个，我们只能去寻求;从O点出发到其它点共有6条干枝，它们的名称;分组2:(①,②),(③,④),(⑤,⑥);分组2的近似解 ;因为该分组的均衡度;;因该分组的均衡度 ; 由于T=2小时,t=1小时,V=35公里/小时,需访问; 现在尝试将顶点分为4组.分组的原则：除遵从;表3符号说明：加有底纹的表示前面经过并停留过,;再见