《图与网络模型讲义》由会员分享，可在线阅读，更多相关《图与网络模型讲义（128页珍藏版）》请在金锄头文库上搜索。
1、第十一章 图与网络模型,(Graph and Network Model),第十一章 图与网络模型,第一节 图与网络的基本概念 第二节 最短路问题（Dijkstra法） 第三节 最小生成树问题（破圈法） 第四节 最大流问题 第五节 最小费用最大流问题,第一节 图与网络的基本概念,自然界和人类社会中，大量的事物以及事物之间的关系，常可以用图形来描述。例如，为了反映5个队参加的球类比赛请况，可以用点表示球队，用点间连线表示两个队已经比赛过。又例如工作分配问题，我们可以用点表示工人与需要完成的工作，点间连线表示每个人可以胜任那些工作。 这样的例子很多，物质结构、电路网络、城市规划、交通运输、物资调配
2、等也都可以用点和线连接起来的图进行模拟。,1 点、边、无向图,点记为vi 边点之间的联线，记为ei 无向图由点和边构成的图叫无向图，记为G=(V,E),赵(v1),钱(v2),孙(v3),李(v4),陈(v7),周(v5),吴(v6),e1,e2,e3,e4,e5,点的集合,边的集合,G=(V,E) V=v1，v2，v3， v4，v5，v6， v7 E=e1，e2，e3， e4，e5,图是由点和线构成，可以反映一些对象之间的关系。图分为无向图和有向图。,2 点、弧、有向图,弧点之间带箭头的联线，记为ai 有向图由点和弧构成的图叫有向图，记为D=(V,A),赵(v1),钱(v2),孙(v3),李
3、(v4),陈(v7),周(v5),吴(v6),a1,a2,a3,a4,a5,点的集合,弧的集合,D=(V,A) V=v1，v2，v3， v4，v5，v6， v7 A=a1，a2，a3， a4，a5 ，a6，a7， a8，a9 ，a10,a6,a7,a9,a10,a8,3 无向图中的链、圈、连通图、权、赋权图概念,链在无向图中如果存在一个点、边的交错序列称为联结两点的链。例如：（v1， v2， v3） 圈若链的第一个点和最后一点相同，则称之为圈。例如：（v1， v2， v3 ， v1 ） 连通图对于一个无向图G，若任何两个不同的点之间至少存在一条链，则称G是连通图。 赋权图对于一个无向图G的每一
4、条边，如果相应有一个数，则称这样的图为赋权图，该数称为边上的权。,赵(v1),钱(v2),孙(v3),李(v4),陈(v7),周(v5),吴(v6),e1,e2,e3,e4,e5,4 有向图中的路、回路、权、赋权图、容量、网络概念,路在有向图中如果存在一个点、弧的交错序列称为联结两点的路，例如：（v1， v5， v7 ， v4 ） 回路若路的第一个点和最后一点相同，则称之为回路 （v1， v2， v3 ， v1 ） 赋权图对于一个有向图D的每一条弧，如果相应有一个数，称这样的图为赋权图，该数称为弧上的权。 如果在赋权有向图D中指定一点为发点（记为vs ），指定另一点为收点（记为vt ），其余的
5、点称为中间点，并把D中的每一条弧的赋权数称之为弧的容量，这样的赋权有向图就称之为网络,赵(v1),钱(v2),孙(v3),李(v4),陈(v7),周(v5),吴(v6),a1,a2,a3,a4,a5,a6,a7,a9,a10,a8,无向图和有向图的联系和区别,无向图：点、边、链、圈、权、赋权无向图、连通图 有向图：点、弧、路、回路、权（容量） 、赋权有向图（网络）无向图是有向图的特例,第二节 最短路问题,最短路问题是网络理论中应用最广的问题之一。许多优化问题可以是这个模型，如设备更新、管道铺设、线路安排、厂区布局等。图论方法比较有效。 前面我们用动态规划方法解决了一个赋权无向图的最短路问题。,
6、求解最短路的Dijkstra算法,最短路问题是对一个赋权有向图D中指定的两个点vs和vt找到一条从vs到vt的路，使得路上所有弧的权数的总和最小，这条路上所有弧的权数的总和被称之为从vs到vt的距离。,本算法由Dijkstra于1959年提出，可用于求解指定两点间的最短路，或从指定点到其余各点的最短路。 适用情况：适用于赋权有向图，且每条弧的权数都大于0的情况，目前被认为是求无负权网络最短路问题的最好方法 Dijkstra算法也称为双标号法。即对图中的点vj赋予两个标号(lj ，kj ),第一个标号lj表示从起点vs到vj的最短路的长度，第二个标号kj表示在vs到vj的最短路上vj前面一个邻点
7、的下标，从而找到vs到vt的最短路及vs与vt的距离。,求解最短路的Dijkstra算法,Dijkstra算法的基本步骤,1、给起点vs以标号(0,s)，表示从vs到vs的距离为0，在vs到vs的最短路上vs前面一个邻点的下标为s； 2、找出已标号的点的集合I，没标号的点的集合J，以及弧的集合(vi ,vj)| vi I, vjJ，这里这个弧的集合是指所有从已标号的点到未标号的点的弧的集合。 3、如果上述弧的集合是空集，则计算结束：如果vt已标号(lt ，kt )，则vs与vt的距离即为lt ，而从vs到vt的最短路径，则可以从vt反向追踪到起点vs而得到。如果vt未标号，则可以断言不存在从v
8、s到vt的有向路。 4、如果上述弧的集合不是空集，对弧的集合中的每一条弧，计算sij =li +cij，在所有的sij中，找到其值为最小的弧，给此弧的终点以双标号，返回步骤2。（出现最小的弧多条，可以任选一个标定，也可以都予以标定，可能出现多条最短路径）,举例,v1,v2,v3,5,3,2,2,1,5,3,5,1,7,v6,v5,v4,求v1到v6的最短路,解: (1)给起始点v1标以(0,s)，表示从v1到v1的距离为0， v1为起始点,(0,s),(2)这时已标定点集合 I =v1 ，未标定点集合 J=v2，v3，v4 ，v5，v6弧集合： A=(vi，vj)|viI, vj J= (v1
9、，v2)，(v1，v3)，(v1，v4) 计算： s12 =l1 +c12=0+3=3s13 =l1 +c13=0+2=2s14 =l1 +c14=0+5=5,因为min(s12, s13, s14) = s13=2 所以给弧(v1，v3)的终点v3标号(2,1)，表示从v1到v3的距离为2， 并且在v1到v3的最短路径中v3的前面一个点是v1,(2,1),v1,v2,v3,5,3,2,2,1,5,3,5,1,7,v6,v5,v4,(0,s),(3)这时已标定点集合I =v1 ， v3，未标定点集合J=v2，v4 ，v5，v6弧集合：A= (vi，vj)|viI, vj J= (v1，v2)，
10、(v1，v4)，(v3，v4) 计算： s12 =l1 +c12=0+3=3s14 =l1 +c14=0+5=5 s34 =l3 +c34=2+1=3,因为min(s12, s14, s34) = s12=s34=3 所以给弧(v1，v2)的终点v2标号(3,1)，表示从v1到v2的距离为3， 并且在v1到v2的最短路径中v2的前面一个点是v1给弧(v3，v4)的终点v4标号(3,3)，表示从v1到v4的距离为3， 并且在v1到v4的最短路径中v4的前面一个点是v3,(2,1),前面已经算出,(3,1),(3,3),v1,v2,v3,5,3,2,2,1,5,3,5,1,7,v6,v5,v4,(
11、0,s),(4)这时已标定点集合I =v1， v2 ， v3 ，v4 ，未标定点集合J=v5，v6弧集合：A=(vi，vj)|viI, vj J= (v2，v6)， (v4，v6 计算： s26 =l2 +c26=3+7=10s46 =l4 +c46=3+5=8,因为min(s26, s46) = s46=8 所以给弧(v4，v6)的终点v6标号(8,4)，表示从v1到v6的距离为8， 并且在v1到v6的最短路径中v6的前面一个点是v4,(2,1),(3,1),(3,3),(8,4),v1,v2,v3,5,3,2,2,1,5,3,5,1,7,v6,v5,v4,(0,s),(5)这时已标定点集合
12、I =v1， v2 ， v3 ，v4 ，v6，未标定点集合J=v5弧集合：A= (vi，vj)|viI, vj J= 计算结束,这时J=v5，也即v5还未标号 ，说明从v1到v5没有有向路,(2,1),(3,1),(3,3),(8,4),(6)通过反向追踪得到最优路径,根据终点v6的标号（8，4）可知道从v1到v6的距离是8，其最短路径中v6的前面一点是v4 ， 从v4的标号（3，3）可知v4的前面一点是v3 ，从v3的标号（2，1）可知v3的前面一点是v1 ，即此最短路径为v1 v3 v4 v6,课堂练习1 利用Dijkstra算法，求出图中，v1到v5的最短路的长度？,如图v0是一仓库，v
13、9是商店，利用Dijkstra算法 求一条从v0到v9的最短路。,课堂练习2,无向图和有向图的联系和区别,无向图：点、边、链、圈、权、赋权无向图、连通图 有向图：点、弧、路、回路、权（容量） 、赋权有向图（网络）无向图是有向图的特例,设备更新问题,某公司使用一台设备,在每年年初,公司就要决定是购买新的设备还是继续使用旧设备.如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，这样可以省去购置费，但维修费用就高了。现在需要我们制定一个五年之内的更新设备的计划，使得五年内购置费和维修费总的支付费用最小。,使用不同时间（年）的设备所需要的维修费(万元)如表所示：,这种
14、设备每年年初的价格(万元)如表所示：,解：将其转化为最短路问题：点Vi 表示第i年年初购买一台新设备，点V6理解为第5年底弧(Vi， Vi)表示第i年年初购进新设备，一直使用到第j年年初权Cij 表示第i年年初购买新设备，使用到第j-1年年底所花费的购置费及维修费的总和,V1,V2,V3,V4,V5,V6,11+5,11+5+6,11+5+6+8,11+5+6+8+11,11+5+6+8+11+18,11+5+6+8+11,11+5+6+8,11+5+6,11+5,12+5+6+8,12+5+6,12+5,12+5,12+5+6,13+5,V1,V2,V3,V4,V5,V6,16,22,30,
15、41,59,41,30,22,16,31,23,17,17,23,18,(1)始点v1 (0,s),(2) I =v1 J=v2，v3，v4 ，v5，v6A =(v1，v2)，(v1，v3)，(v1，v4 ) ，(v1，v5)，(v1，v6) s12 =l1 +c12=0+16=16 s13 =l1 +c13=0+22=22 s14 =l1 +c14=0+30=30 s15 =l1 +c15=0+41=41 s16 =l1 +c16=0+59=59 Mins12, s13 , s14 , s15 , s16= s12=16 v2 (16,1),(0,s),(16,1),V1,V2,V3,V4,
16、V5,V6,16,22,30,41,59,41,30,22,16,31,23,17,17,23,18,(3) I =v1 ， v2J=v3，v4 ，v5，v6A =(v1，v3)，(v1，v4 ) ，(v1，v5)，(v1，v6 ) ，(v2，v3 ) ，(v2，v4)，(v2，v5)，(v2，v6) s13 =l1 +c13=0+22=22 s14 =l1 +c14=0+30=30 s15 =l1 +c15=0+41=41 s16 =l1 +c16=0+59=59 s23 =l2 +c23=16+16=32 s24 =l2 +c24=16+22=38 s25 =l2 +c25=16+30=46 s26 =l2 +c26=16+41=57 Mins13 , s14 , s15 , s16 , s23 , s24 , s25 , s26 =s13=22 v3 (22,1),
