图和网络分析到最短路问题.ppt

第六章???图与网络分析;第八章???图与网络分析; 图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。; 1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。即一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。如图1所示。 ; 在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。; 有六支球队进行足球比赛，我们分别用点v1…v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用下图所示的有向图反映出来。 ;图的基本概念与模型;对 称 关 系;图的相关概念;若某条边两个端点相同，称这条边为环。 若两点之间有多于一条的边，称这些边为多重边。 ; 图G中以点v为端点的边的数目，称为v在G中的次(度）， 记为d（v）。;给定图G=（V，E），若图G’=（V’，E’），其中V’?V，E’? E ，则称G’是G的子图。;图的连通性;图的连通性;图的矩阵表示;v4;图G=（V，E），p=n，构造矩阵;其邻接矩阵为： ; 思考：有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛，下表中打的是个运动员报名参加比赛的项目，问六个项目的比赛顺序应如何安排？做到每名运动员都不连续地参加两项比赛。;第八章???图与网络分析;第六章???图与网络分析;7个村庄要在他们之间架设电话线，要求任何两个村庄都可以互相通电话(允许中转)，并且电话线根数最少？;树;1;i;2;7;第六章???图与网络分析;第八章???图与网络分析;什么是最短路问题？ 固定起点的最短路 Dijkstra(狄克斯拉) (荷兰)算法：标号法 每 对 顶 点 之 间 的 最 短 路 矩阵算法 ;最短路问题提出 ;有向图;有向网络与混合图;最短路问题引例;从v1到v8： P1=（v1，v2，v5，v8） 费用 6+1+6=13 P2=（v1，v3，v4， v6， v7， v8） 费用 3+2+10+2+4=21 P3= ……;几个概念;设P是以点vs为始点，以点vt为终点的所有路的集合， 如果 ,且 ，则称p0是以点vs 为始点，以点vt为终点的最短路。而称其路长为点 vi到点vj的距离，记为 。 ;最短路问题求解方法;最短路问题求解方法;求解最短路问题的Dijkstra算法;Dijkstra算法基本思想;Dijkstra算法步骤：;v1,6;v1,6;v5;v5;v5;v5;v5;Dijkstra算法步骤：;例 求如下交通网络中v1 到各点间最短路路长。;5;无向网络:;最短路问题求解方法;逐次逼近算法思想 ;用于计算指定点v1到其余各点的最短路;例 计算从点v1到所有其它顶点的最短路;v1 v2 v3 v4 v5 v6 v7 v8;逐次逼近算法思想 ;最短路问题求解方法;已知有7个村子，相互间道路的距离如下图示。拟合建一所小学，已知A处有小学生30人，B处40人，C处25人，D处20人，E处50人，F处60人， G处60人,问小学应建在哪一个村子，使学生上学最方便（原则①所有人走的总路程最短；②尽可能公平。）。;A;;得到权矩阵为;A处30人，B处40人，C处25人，D处20人，E处50人，F处60人， G处60人.;某工厂使用一台设备，每年年初工厂都要作出决定：如果继续使用旧的，要付维修费；如果买新的，要付购置费。试制定一个五年更新计划，使工厂总支出最少？;最短路问题算例2(设备更新问题);项目