资源描述：
《图与网络模型ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图与网络的基本概念图与网络用来反映一些对象之间的关系图论中，图与网络结构由下面两个元素构成节点边例如：在一个人群中，对相互认识这个关系我们可以用图来表示，下图就是一个表示这种关系的图。(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5图与网络的基本概念一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的无向图：边是无向的有向图：边是有向的如：将上述例子中“相互认识”关系改为“认识”如：familytree一个图结构可记作G=（V，E）V为节点集合，E为边的集合图与网络的基本概念路：一个节
2、点与边相互交错的序列（vi1,ei1,vi2,ei2,…,vik-1,eik-1,vik），其中，对于无向图，eit的两个端点是vit-1和vit对于有向图，eit的起点是vit-1，终点是vit路的起点为vi1，路的终点为vik圈：起点和终点是同一个节点的路连通图：对于无向图而言，如果图中的任意两个节点都有一条路将之连接，则这个图称为连通图。图与网络的基本概念赋权图：对一个G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。网络：在赋权的有向图G中指定一点，称为发点（vs），指定另一点称为收点（vt），其它点称为中
3、间点，并把G中的每一条边的赋权数称为边的容量，G就称为网络。最短路问题对一个赋权的有向图G中的指定的两个点vs和vt找到一条从vs到vt的路，使得这条路上所有弧的权数的总和最小这条路被称之为从vs到vt的最短路。这条路上所有弧的权数的总和被称为从vs到vt的距离。Dijkstra算法适用范围：适用于每条边上的赋权数为非负值的情况Dijkstra算法也称为双标号法双标号：图中的每一个节点vj都赋予两个标号（lj,kj），其中lj表示从起点vs到vj的最短路长度，kj表示在vs到vj的最短路上vj前一个节点的下标。Dijkstra算法的基本步骤给出点v1以标号(0,s)
4、找出已标号的点的集合I，没标号的点的集合J以及边的集合查看vt是否已标号如果vt已标号（lt,kt），则vs到vt的距离为lt，而从vs到vt的最短路径，则可以从kt反向追踪到起点vs而得到。如果vt未标号，则如果上述边的集合是空集，则计算结束，可以断言不存在从vs到vt的有向路。如果上述的弧的集合不是空集，则转下一步对上述边的集合中的每一条边，计算sij=li+wij。在所有的sij中，找到其值为最小的边。不妨设此边为（vc,vd），则给此边的终点以双标号（scd,c）,返回步骤2。最短路问题的例子求下图中v1到v6的最短路v23527531512v1v6v5v3
5、v4(0,s)352(2,1)3(3,1)(3,3)108(8,4)采用Dijkstra算法，可解得最短路径为v1v3v4v6最短路问题的应用电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。v1（甲地）1517624431065v2v7（乙地）v3v4v5v6最短路问题的应用无向图可以表示成为有向图无向图的最短路问题同样可以使用Dijkstra算法求解v1（甲地）1517624431065v2v7（乙地）v3v4v5v61510(0,s)(10,1)1314(13,3)30
6、19(14,3)1618(16,5)22(18,5)23(22,6)最短路问题的应用设备更新问题：某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。设备每年年初的价格表和设备维修费如下。年份12345年初价格1111121213使用年份0-11-22-33-44-5每年维修费用5681118最短路问题的应用解：可以转化为最短路问题。构造一个有
7、向图，即图中的边皆为有向的。用vi表示“第i年年初购进一台新设备”，边（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。v1v2v3v4v5v6最短路问题的应用所有边上的权数表123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723最短路问题的应用最终得到下图，可知，v1到v6的距离是53，最短路径有两条：v1v3v6和v1v4v6v1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723v2（
