数学建模方法之图论模型.ppt

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)最小生成树与算法;AKruskal算法（或避圈法）;例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符号阐明：加有底纹的表达前面通過并停留過,