05_1图与网络分析[1_4].pptVIP

图与网络分析Graph Network Analysis;知识点要求;主要内容;图的基本概念与模型;;图的概念Graph;图的分类;图的定义与表达;G与几何学中的图的区别;网络图——NNet Graph;点与边Vertex Edge;点的次数degree，特殊的点;端点，关联边，相邻End Vertex, Incident Edge Adjacent Edge ;V2;链，路link, path ;V2;子图，部分图sub-graph, component graph ;图的模型 ;[例1];表6-1;图 6-3;例2;树和图的最小部分树第二节 ;T(V，E);树的性质 ;树的特点;图的部分树;图的最小部分树;寻找最小部分树的方法;避圈法;破圈法;寻找最小部分树举例;[解];解1：避圈法 ;以其他点为起点的结果？;解2：破圈法;;最短路问题shortest path problem ;;Dijkstra算法 ;Dijkstra算法的步骤-1;Dijkstra算法的步骤-1;Dijkstra算法举例;解题-1;(2)同v1相邻的未标号点有v2、v3。L1r=min{d12,d13}=min{5,2}=2=L13,即对点v3标号，将L13的值标注在v3旁的小方框内。将[v1,v3]加粗，并令 ;(3)同标号点v1、v3相邻的点有v2、v4、v6，故有 对v2点标号，将L12的值标注在v2点旁的小方框内，将[v1,v2]加粗，并令， ;解题-4;解题-5;解题-6;矩阵算法 ;矩阵算法举例;解题-1;解题-2;解题-3;解题-4;解题-5;一般地有 矩阵D(k)给出网络中任意两点之间直接到达，经过一个、两个……到（2k-1）个中间点到达时比较得到的最短距离。 设网络图有p个点，则一般计算到不超过D(k)，k的值按式 计算 即 如果计算中出现D(m+1)=D(m)时，计算即可结束，矩阵中D(m)的各个元素值即为各点间最短距离。 本例中， 所以最多计算到D(3)，;[例5];解题;;应用举例——设备更新问题;设备在各年年初的购置费用（千元/台）;用点vi表示“第i年年初购进一台设备”；用弧（vi，vj）表示在第i年年初购进的设备一直使用到第j年年初。则问题成为最短路径问题。;中国邮路问题;问题提出;哥尼斯堡七桥问题;欧拉“一笔画问题”;欧拉图;[例6];解题-1;解题-2;图 6-13;解题-4;解题-4;图 6-14