第十一章图与网络分析.ppt

第十一章 图与网络分析,Graph theory and network analysis,第十一章 图与网络分析,11.1 引言,引言,图论是专门研究图的理论的一门数学分支，属于离散数学范畴，与运筹学有交叉，它有200多年历史，大体可划分为三个阶段。,引言,第一阶段 从十八世纪中叶到十九世纪中叶，处于萌芽阶段，多数问题由游戏而产生，最有代表性的工作是所谓的Euler七桥问题，即一笔画问题。,引言,第二阶段 从十九世纪中叶到二十世纪中叶，这时，图论问题大量出现，如Hamilton问题，地图染色的四色问题以及可平面性问题等，这时，也出现用图解决实际问题，如Cayley把树应用于化学领域，Kirchhoff用树去研究电网络等.,引言,第三阶段 二十世纪中叶以后，由生产管理、军事、交通、运输、计算机网络等方面提出实际问题，以及大型计算机使大规模问题的求解成为可能，特别是以Ford和Fulkerson建立的网络流理论，与线性规划、动态规划等优化理论和方法相互渗透，促进了图论对实际问题的应用。,哥尼斯堡七桥问题,哥尼斯堡七桥问题,最后，数学家Euler在1736年巧妙地给出了这个问题的答案，并因此奠定了图论的基础Euler把A、B、C、D四块陆地分别收缩成四个顶点，把桥表示成连接对应顶点之间的边，问题转化为从任意一点出发，能不能经过各边一次且仅一次，最后返回该点。这就是著名的Euler问题。,A,B,C,D,哥尼斯堡七桥问题,哥尼斯堡七桥问题,A,C,B,D,围坐问题,有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？,用顶点表示人，用边表示两者相邻，因为最初任何两个人都允许相邻，所以任何两点都可以有边相连。,1,2,3,7,6,4,5,围坐问题,假定第一次就座方案是（1，2，3，4，5，6，7，1），那么第二次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,假定第二次就座方案是（1，3，5，7，2，4，6，1），那么第三次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,假定第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边，只留下7点孤立点，所以该问题只有三个就座方案。,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,1,2,3,7,6,4,5,围坐问题,假定第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边，只留下7点孤立点，所以该问题只有三个就座方案。,围坐问题,哈密顿（Hamilton）回路是十九世纪英国数学家哈密顿提出，给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处的周游世界线路（并不要求经过每条边）。,哈密顿回路,哈密顿回路,哈密顿回路,哈密顿回路,哈密顿回路,哈密顿回路,哈密顿回路,哈密顿回路,哈密顿回路,哈密顿回路,哈密顿回路,哈密顿回路,哈密顿回路,哈密顿回路,哈密顿回路,哈密顿回路,哈密顿回路,哈密顿回路,哈密顿回路,引言,瑞士数学家 Euler 在1736年发表的一篇题为“依据几何位置的解题方法”的论文，有效的解决了哥尼斯堡七桥问题，是有记载的第一篇图论论文，Euler被认为是图论的创始人。图论的第一本专著是匈牙利的 O Konig写的“有限图与无限图的理论”，发表于1936。从1736到1936，前后200年，总的来讲这一时期图论发展缓慢。直到20世纪中叶，电子计算机的发展和零散数学问题具有越来越重要的地位，使得图论得以迅速发展,第十一章 图与网络分析,11.1 引言11.2 图与网络的基本概念,11.2 图与网络的基本概念,图论是专门研究图的理论的一门数学分支，主要研究点和线之间的几何关系,11.2 图与网络的基本概念,定义：图是由点集 V=（vi）和 V 中元素的无序对的一个集合 E=（ek）所构成的二元组，记为G=（V，E），其中：V=（v1，v2，.vm）是m个顶点集合；E=（e1，e2，.en）是n条边集合。当V，E为有限集合时，G称为有限图，否则称为无限图，本章只讨论有限图。,11.2 图与网络的基本概念,11.2 图与网络的基本概念,V=（v1，v2，.v6）E=（e1，e2，.e8）,e1=（v1，v2）e2=（v1，v2）e7=（v3，v5）e8=（v4，v4）称为自回路(环)；,11.2 图与网络的基本概念,说明：（1）V非空，即没有顶点的图不讨论；（2）E无非空条件，即允许没有边；（3）E是一个不与V 中顶点相交的边集合；（指点只在边的端点处相交）（4）任一条边必须与一对顶点关联，反之不然。,11.2 图与网络的基本概念,V=（v1，v2，.v6）E=（e1，e2，.e8）,e1=（v1，v2）e2=（v1，v2）e7=（v3，v5）e8=（v4，v4）称为自回路(环)；,11.2 图与网络的基本概念,定义对任一条边（vi，vj）属于E，如果边（vi，vj）的端点无序，则它是无向边，此时图为无向图。如果如果边（vi，vj）的端点有序，则它表示以vi为始点，vj为终点的有向边（或称为弧），此时图为有向图。,11.2 图与网络的基本概念,11.2 图与网络的基本概念,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向图,11.2 图与网络的基本概念,定义（链）如果图中的某些点、边可以排列成点和边的交错序列，则称此为一条链。定义（圈）如一条链中起点和终点重合，则称此为一条圈。,11.2 图与网络的基本概念,11.2 图与网络的基本概念,11.2 图与网络的基本概念,链，点边交错序列v1,e5,v4,e4,v3,11.2 图与网络的基本概念,圈,起点和终点重合v1,e5,v4,e4,v3,e6,v1,11.2 图与网络的基本概念,11.2 图与网络的基本概念,定义（链）如果图中的某些点、边可以排列成点和边的交错序列，则称此为一条链。定义（圈）如一条链中起点和终点重合，则称此为一条圈。,11.2 图与网络的基本概念,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,链：v3,e2,v2,11.2 图与网络的基本概念,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,链：v3,e2,v2,e4,v4,11.2 图与网络的基本概念,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,链：v3,e2,v2,e4,v4,e3,v1,11.2 图与网络的基本概念,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,链：v3,e2,v2,e4,v4,e7,v5,v1,v5,v4,v2,e1,e7,e6,e3,11.2 图与网络的基本概念,v1,v5,v4,v2,e1,e7,e6,e3,11.2 图与网络的基本概念,v1,v5,v4,v2,e1,e7,e6,e3,11.2 图与网络的基本概念,v1,v5,v4,v2,e1,e7,e6,e3,11.2 图与网络的基本概念,11.2 图与网络的基本概念,定义（链）如果图中的某些点、边可以排列成点和边的交错序列，则称此为一条链。定义（圈）如一条链中起点和终点重合，则称此为一条圈。,11.2 图与网络的基本概念,图的矩阵表示 一个图非常直观，但是不容易计算，特别不容易在计算机上进行计算，一个有效的解决办法是将图表示成矩阵形式，通常采用的矩阵是邻接矩阵、边长邻接矩阵、弧长矩阵和关联矩阵。,11.2 图与网络的基本概念,邻接矩阵表示图 G 的顶点之间的邻接关系，它是一个 n x n 的矩阵，如果两个顶点之间有边相联时，记为1，否则为0。,11.2 图与网络的基本概念,v1,v2,v3,v4,v1 v2 v3 v4 v1 0 1 1 1v2 1 1 1 0v3 1 1 0 1v4 1 0 1 0,11.2 图与网络的基本概念,v1 v2 v3 v4 v5v1 0 0 0 1 1v2 1 0 0 1 0v3 0 1 1 0 0v4 0 1 1 0 1v5 1 0 0 1 0,11.2 图与网络的基本概念,赋权图或网络在图的各边上一个数量指标（cij），具体表示这条边的权（距离，单价，通过能力等）。无向网络；有向网络；混合网络；边权网络；点权网络。,第十一章 图与网络分析,11.1 引言11.2 图与网络的基本概念11.3 最短路问题,11.3 最短路问题,对一个赋权的有向图 D;指定的两个点 Vs 和 Vt；找到一条从 Vs 到 Vt 的路，使得这条路上所有弧的权数的总和最小；这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数总和被称为从Vs到Vt的距离。,11.3 最短路问题,一、求解最短路的Dijkstra算法(迪科斯彻，双标号法）对图中的点 Vj 赋予两个标号（lj,kj）,第一个标号 lj 表示从起点 Vs 到 Vj 的最短路的长度，第二个标号 kj 表示在 Vs 到 Vj 的最短路上 Vj 前面一个邻点的下标。例如：V6（8,4)表示，从起点 V 到 V 的最短路的长度为在这条最短路上V 的前一个邻点为V。,11.3 最短路问题,步骤：给出点 V1 以标号(0，s)找出已标号点的集合I，没标号的点的集合J,以及弧的集合 如果上述弧的集合是空集，则计算结束。如果 Vt 已标号（lt,kt），则 Vs 到 Vt 的距离为lt。如果Vt 未标号，则可以断言不存在从 Vs到Vt的有向路。如果上述的弧的集合不是空集，则转下一步。对上述弧的集合中的每一条弧，计算 sij=li+cij。在所有的 sij中，找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（scd,c）,返回步骤2。,11.3 最短路问题,例 求下图中 v1 到 v6 的最短路,11.3 最短路问题,解采用Dijkstra算法,.给出点 V1 以标号(0，s),(0，s),11.3 最短路问题,解采用Dijkstra算法,(0，s),.找出已标号点的集合I，没标号的点的集合J，以及弧的集合,11.3 最短路问题,解采用Dijkstra算法,(0，s),.找出已标号点的集合I，没标号的点的集合J,以及弧的集合,IV1J V2,V3,V4,V5,V6,11.3 最短路问题,解采用Dijkstra算法,v2,3,5,2,7,5,3,1,5,1,2,v1,v6,v5,v3,v4,(0，s),.找出已标号点的集合I，没标号的点的集合J,以及弧的集合,IV1J V2,V3,V4,V5,V6 弧的集合(V1,V2),(V1,V3),(V1,V4),11.3 最短路问题,解采用Dijkstra算法,v2,3,5,2,7,5,3,1,5,1,2,v1,v6,v5,v3,v4,(0，s),2.对每一条弧，计算 sij=li+cij。找到其值为最小的弧,给此弧的终点以双标号,s12=l1+c12=0+3=3 s13=l1+c13=0+2=2 s14=l1+c14=0+5=5 MIN(s12,s13,s14)=s13=2,(2，1),11.3 最短路问题,解采用Dijkstra算法,(0，s),3.找出已标号点的集合I，没标号的点的集合J,以及弧的集合,IV1,V3 J V2,V4,V5,V6,(2，1),11.3 最短路问题,解采用Dijkstra算法,v2,3,5,2,7,5,3,1,5,1,2,v1,v6,v5,v3,v4,(0，s),3.找出已标号点的集合I，没标号的点的集合J,以及弧的集合,IV1,V3 J V2,V4,V5,V6 弧的集合(V1,V2),(V1,V4),(V3,V4),(2，1),11.3 最短路问题,解采用Dijkstra算法,v2,3,5,2,7,5,3,1,5,1,2,v1,v6,v5,v3,v4,(0，s),3.对每一条弧，计算 sij=li+cij。找到其值为最小的弧,给此弧的终点以双标号,s12=l1+c12=0+3=3 s14=l1+c14=0+5=5 s34=l3+c34=2+1=3 MIN(s12,s14,s34)=s12=s34=3,(2，1),(3，1),(3，3),11.3 最短路问题,解采用Dijkstra算法,(0，s),4.找出已标号点的集合I，没标号的点的集合J,以及弧的集合,IV1,V2,V3,V4 J V5,V6,(2，1),(3，1),(3，3),11.3 最短路问题,解采用Dijkstra算法,v2,3,5,2,7,5,3,1,5,1,2,v1,v6,v5,v3,v4,(0，s),4.找出已标号点的集合I，没标号的点的集合J,以及弧的集合,IV1,V2,V3,V4 J V5,V6弧的集合(V2,V6),(V4,V6),(2，1),(3，1),(3，3),11.3 最短路问题,解采用Dijkstra算法,v2,3,5,2,7,5,3,1,5,1,2,v1,v6,v5,v3,v4,(0，s),4.对每一条弧，计算 sij=li+cij。找到其值为最小的弧,给此弧的终点以双标号,s26=l2+c26=3+7=10 s46=l4+c46=3+5=8MIN(s26,s46)=s46=8,(2，1),(3，1),(3，3),(8，4),11.3 最短路问题,解采用Dijkstra算法,(0，s),5.找出已标号点的集合I，没标号的点的集合J,以及弧的集合,IV1,V2,V3,V4,V6 J V6,(2，1),(3，1),(3，3),上述弧的集合是空集，计算结束。,11.3 最短路问题,解采用Dijkstra算法,v2,3,5,2,7,5,3,1,5,1,2,v1,v6,v5,v3,v4,(0，s),(2，1),(3，1),(3，3),(8，4),由于V 已标号（,）则 V 到 V的距离为。最短路径为(由倒推得到)V V V V,11.3 最短路问题,例 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。,11.3 最短路问题,这是一个求无向图的最短路的问题。可以把无向图的每一边（vi,vj）都用方向相反的两条弧（vi,vj）和（vj,vi）代替，就化为有向图，也可直接在无向图中用Dijkstra算法来求解。只要在算法中把从已标号的点到未标号点弧的集合改成已标号点到未标号点边的集合即可。,11.3 最短路问题,例 求下图中 v1 到 v 的最短路,V1,15,17,6,2,4,4,3,10,6,5,V2,V3,V4,V5,V6,V7,11.3 最短路问题,解采用Dijkstra算法,.给出点 V1 以标号(0，s),(0，s),V1,15,17,6,2,4,4,3,10,6,5,V2,V3,V4,V5,V6,V7,11.3 最短路问题,解采用Dijkstra算法,2.已标号点至没标号的点的边的集合(V1,V2),(V1,V3),(0，s),V1,15,17,6,2,4,4,3,10,6,5,V2,V3,V4,V5,V6,V7,11.3 最短路问题,解采用Dijkstra算法,s12=l1+c12=0+15=15s13=l1+c13=0+10=10MIN(s12,s13)=s13=10,2.已标号点至没标号的点的边的集合(V1,V2),(V1,V3),(0，s),V1,15,17,6,2,4,4,3,10,6,5,V2,V3,V4,V5,V6,V7,(10，1),11.3 最短路问题,解采用Dijkstra算法,3.已标号点至没标号的点的边的集合(V1,V2),(V3,V2),(V3,V5),(0，s),V1,15,17,6,2,4,4,3,10,6,5,V2,V3,V4,V5,V6,V7,(10，1),11.3 最短路问题,解采用Dijkstra算法,3.已标号点至没标号的点的边的集合(V1,V2),(V3,V2),(V3,V5),(0，s),V1,15,17,6,2,4,4,3,10,6,5,V2,V3,V4,V5,V6,V7,(10，1),s12=l1+c12=0+15=15 s32=l3+c32=10+3=13 s35=l3+c35=10+4=14MIN(s12,s32,s35)=s32=13,(13，3),11.3 最短路问题,解采用Dijkstra算法,4.已标号点至没标号的点的边的集合(V2,V4),(V2,V7),(V3,V5),(0，s),V1,15,17,6,2,4,4,3,10,6,5,V2,V3,V4,V5,V6,V7,(10，1),(13，3),11.3 最短路问题,解采用Dijkstra算法,s24=l2+c24=13+6=19 s27=l2+c27=13+17=30 s35=l3+c35=10+4=14MIN(s24,s27,s35)=s35=14,4.已标号点至没标号的点的边的集合(V2,V4),(V2,V7),(V3,V5),(0，s),V1,15,17,6,2,4,4,3,10,6,5,V2,V3,V4,V5,V6,V7,(10，1),(13，3),(14，3),11.3 最短路问题,解采用Dijkstra算法,5.已标号点至没标号的点的边的集合(V2,V4),(V2,V7),(V5,V4),(V5,V6),(0，s),V1,15,17,6,2,4,4,3,10,6,5,V2,V3,V4,V5,V6,V7,(10，1),(13，3),(14，3),11.3 最短路问题,解采用Dijkstra算法,5.已标号点至没标号的点的边的集合(V2,V4),(V2,V7),(V5,V4),(V5,V6),(0，s),V1,15,17,6,2,4,4,3,10,6,5,V2,V3,V4,V5,V6,V7,(10，1),(13，3),(14，3),s24=l2+c24=13+6=19 s27=l2+c27=13+17=30 s54=l5+c54=14+4=18 s56=l5+c56=14+2=16MIN(s24,s27,s54,s56)=s56=16,(16，5),11.3 最短路问题,解采用Dijkstra算法,6.已标号点至没标号的点的边的集合(V2,V4),(V2,V7),(V5,V4),(V6,V7),(0，s),V1,15,17,6,2,4,4,3,10,6,5,V2,V3,V4,V5,V6,V7,(10，1),(13，3),(14，3),(16，5),11.3 最短路问题,解采用Dijkstra算法,6.已标号点至没标号的点的边的集合(V2,V4),(V2,V7),(V5,V4),(V6,V7),(0，s),V1,15,17,6,2,4,4,3,10,6,5,V2,V3,V4,V5,V6,V7,(10，1),(13，3),(14，3),(16，5),s24=l2+c24=13+6=19 s27=l2+c27=13+17=30 s54=l5+c54=14+4=18 s67=l6+c67=16+6=22MIN(s24,s27,s54,s67)=s54=18,(18，5),11.3 最短路问题,解采用Dijkstra算法,7.已标号点至没标号的点的边的集合(V2,V7),(V4,V7),(V6,V7),(0，s),V1,15,17,6,2,4,4,3,10,6,5,V2,V3,V4,V5,V6,V7,(10，1),(13，3),(14，5),(16，5),(18，5),11.3 最短路问题,解采用Dijkstra算法,7.已标号点至没标号的点的边的集合(V2,V7),(V4,V7),(V6,V7),(0，s),V1,15,17,6,2,4,4,3,10,6,5,V2,V3,V4,V5,V6,V7,(10，1),(13，3),(14，5),(16，5),(18，5),s27=l2+c27=13+17=30 s47=l4+c47=18+5=23 s67=l6+c67=16+6=22MIN(s27,s47,s67)=s67=22,(22，6),11.3 最短路问题,解采用Dijkstra算法,8.已标号点至没标号的点的边的集合为空，计算结束,(0，s),V1,15,17,6,2,4,4,3,10,6,5,V2,V3,V4,V5,V6,V7,(10，1),(13，3),(14，5),(16，5),(18，5),(22，6),11.3 最短路问题,解采用Dijkstra算法,(0，s),V1,15,17,6,2,4,4,3,10,6,5,V2,V3,V4,V5,V6,V7,(10，1),(13，3),(14，3),(16，5),(18，5),(22，6),由于V7 已标号（22,6）则 V 到 V的距离为22。最短路径为 V V3 V5 V6 V7,11.3 最短路问题,习题采用Dijkstra算法求 V 到 V8 的最短路,4,9,5,4,1,6,7,6,5,4,4,7,5,V1,V8,V2,V4,V6,V3,V5,V7,11.3 最短路问题,4,9,5,4,1,6,7,6,5,4,4,7,5,V1,V8,V2,V4,V6,V3,V5,V7,(0，s),11.3 最短路问题,4,9,5,4,1,6,7,6,5,4,4,7,5,V1,V8,V2,V4,V6,V3,V5,V7,(0，s),(4，1),11.3 最短路问题,4,9,5,4,1,6,7,6,5,4,4,7,5,V1,V8,V2,V4,V6,V3,V5,V7,(0，s),(4，1),11.3 最短路问题,4,9,5,4,1,6,7,6,5,4,4,7,5,V1,V8,V2,V4,V6,V3,V5,V7,(0，s),(4，1),(6，1),11.3 最短路问题,4,9,5,4,1,6,7,6,5,4,4,7,5,V1,V8,V2,V4,V6,V3,V5,V7,(0，s),(4，1),(6，1),11.3 最短路问题,4,9,5,4,1,6,7,6,5,4,4,7,5,V1,V8,V2,V4,V6,V3,V5,V7,(0，s),(4，1),(6，1),(8，2),11.3 最短路问题,4,9,5,4,1,6,7,6,5,4,4,7,5,V1,V8,V2,V4,V6,V3,V5,V7,(0，s),(4，1),(6，1),(8，2),11.3 最短路问题,4,9,5,4,1,6,7,6,5,4,4,7,5,V1,V8,V2,V4,V6,V3,V5,V7,(0，s),(4，1),(6，1),(8，2),(9，2),11.3 最短路问题,4,9,5,4,1,6,7,6,5,4,4,7,5,V1,V8,V2,V4,V6,V3,V5,V7,(0，s),(4，1),(6，1),(8，2),(9，2),11.3 最短路问题,4,9,5,4,1,6,7,6,5,4,4,7,5,V1,V8,V2,V4,V6,V3,V5,V7,(0，s),(4，1),(6，1),(8，2),(9，2),(13，5),11.3 最短路问题,4,9,5,4,1,6,7,6,5,4,4,7,5,V1,V8,V2,V4,V6,V3,V5,V7,(0，s),(4，1),(6，1),(8，2),(9，2),(13，5),11.3 最短路问题,4,9,5,4,1,6,7,6,5,4,4,7,5,V1,V8,V2,V4,V6,V3,V5,V7,(0，s),(4，1),(6，1),(8，2),(9，2),(13，5),(14，5),11.3 最短路问题,4,9,5,4,1,6,7,6,5,4,4,7,5,V1,V8,V2,V4,V6,V3,V5,V7,(0，s),(4，1),(6，1),(8，2),(9，2),(13，5),(14，5),11.3 最短路问题,4,9,5,4,1,6,7,6,5,4,4,7,5,V1,V8,V2,V4,V6,V3,V5,V7,(0，s),(4，1),(6，1),(8，2),(9，2),(13，5),(14，5),(15，7),11.3 最短路问题,4,9,5,4,1,6,7,6,5,4,4,7,5,V1,V8,V2,V4,V6,V3,V5,V7,(0，s),(4，1),(6，1),(8，2),(9，2),(13，5),(14，5),(15，7),由于V8 已标号（15,7）则 V 到 V8的距离为15。最短路径为 V V2 V5 V7 V8,11.3 最短路问题,6,V1,V8,V2,V5,V7,(0，s),(4，1),(8，2),(14，5),(15，7),由于V8 已标号（15,7）则 V 到 V8的距离为15。最短路径为 V V2 V5 V7 V8,11.3 最短路问题,例某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。,11.3 最短路问题,设备每年年初的价格表设备维修费如下表,11.3 最短路问题,例3的解：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,16,22,30,41,59,16,22,30,41,31,23,17,18,17,23,11.3 最短路问题,例3的解：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,16,22,30,41,59,16,22,30,41,31,23,17,18,17,23,11.3 最短路问题,例3的解：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,（v1,v4）表示，第1年年初购进一台新设备，使用到第4年年初。（v4,v5）表示，第4年年初购进一台新设备，使用到第5年年初（v5,v6）表示，第5年年初购进一台新设备，使用到第6年年初,30,17,18,11.3 最短路问题,例3的解：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,16,22,30,41,59,16,22,30,41,31,23,17,18,17,23,(0，s),11.3 最短路问题,例3的解：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,16,22,30,41,59,16,22,30,41,31,23,17,18,17,23,(0，s),(16，1),11.3 最短路问题,例3的解：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,16,22,30,41,59,16,22,30,41,31,23,17,18,17,23,(0，s),(16，1),11.3 最短路问题,例3的解：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,16,22,30,41,59,16,22,30,41,31,23,17,18,17,23,(0，s),(16，1),(22，1),11.3 最短路问题,例3的解：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,16,22,30,41,59,16,22,30,41,31,23,17,18,17,23,(0，s),(16，1),(22，1),11.3 最短路问题,例3的解：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,16,22,30,41,59,16,22,30,41,31,23,17,18,17,23,(0，s),(16，1),(22，1),(30，1),11.3 最短路问题,例3的解：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,16,22,30,41,59,16,22,30,41,31,23,17,18,17,23,(0，s),(16，1),(22，1),(30，1),11.3 最短路问题,例3的解：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,16,22,30,41,59,16,22,30,41,31,23,17,18,17,23,(0，s),(16，1),(22，1),(30，1),(41，1),11.3 最短路问题,例3的解：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,16,22,30,41,59,16,22,30,41,31,23,17,18,17,23,(0，s),(16，1),(22，1),(30，1),(41，1),11.3 最短路问题,例3的解：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,16,22,30,41,59,16,22,30,41,31,23,17,18,17,23,(0，s),(16，1),(22，1),(30，1),(41，1),(53，3),(53，4),11.3 最短路问题,例3的解：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,16,22,30,41,59,16,22,30,41,31,23,17,18,17,23,(0，s),(16，1),(22，1),(30，1),(41，1),(53，3),(53，4),11.3 最短路问题,其最短路有两条:V V3 V6;V V4 V6.即第1年年初购进新设备使用到第3年年初，第3年年初购进新设备使用到第5年年底；或第1年年初购进新设备使用到第4年年初，第4年年初购进新设备使用到第5年年底。费用均为53。,v1,v2,v3,v4,v5,v6,16,22,30,41,59,16,22,30,41,31,23,17,18,17,23,(0，s),(16，1),(22，1),(30，1),(41，1),(53，3),(53，4),11.3 最短路问题,其最短路有两条:V V3 V6;V V4 V6.即第1年年初购进新设备使用到第3年年初，第3年年初购进新设备使用到第5年年底；或第1年年初购进新设备使用到第4年年初，第4年年初购进新设备使用到第5年年底。费用均为53。,v1,v2,v3,v4,v5,v6,31,18,22,(53，3),(22，1),11.3 最短路问题,其最短路有两条:V V3 V6;V V4 V6.即第1年年初购进新设备使用到第3年年初，第3年年初购进新设备使用到第5年年底；或第1年年初购进新设备使用到第4年年初，第4年年初购进新设备使用到第5年年底。费用均为53。,v1,v2,v3,v4,v5,v6,30,23,(53，4),(30，1),11.3 最短路问题,习题：工厂使用一台设备，每年年初作出决定，如果继续使用旧的，要支付维修费，如果购买新的支付购买费。试制定五年更新计划,11.3 最短路问题,v1,v2,v3,v4,v5,v6,12,19,28,40,59,表示，第1年年初购进一台新设备，使用到第2-6年年初的费用。,v1,v2,v3,v4,v5,v6,12,19,28,40,59,20,29,41,表示，第2年年初购进一台新设备，使用到第3-6年年初的费用。,13,v1,v2,v3,v4,v5,v6,12,19,28,40,59,20,29,41,表示，第3年年初购进一台新设备，使用到第4-6年年初的费用。,14,21,30,13,v1,v2,v3,v4,v5,v6,12,19,28,40,59,20,13,29,41,表示，第4年年初购进一台新设备，使用到第5-6年年初的费用。,14,21,30,15,22,v1,v2,v3,v4,v5,v6,12,19,28,40,59,20,13,29,41,表示，第5年年初购进一台新设备，使用到第6年年初的费用。,14,21,30,15,22,15,v1,v2,v3,v4,v5,v6,12,19,28,40,59,20,13,29,41,14,21,30,15,22,15,(0，s),v1,v2,v3,v4,v5,v6,12,19,28,40,59,20,13,29,41,14,21,30,15,22,15,(0，s),(12，2),v1,v2,v3,v4,v5,v6,12,19,28,40,59,20,13,29,41,14,21,30,15,22,15,(0，s),(12，2),(19，3),v1,v2,v3,v4,v5,v6,12,19,28,40,59,20,13,29,41,14,21,30,15,22,15,(0，s),(12，2),(19，3),(49，3),v1,v2,v3,v4,v5,v6,12,19,28,40,59,20,13,29,41,表示，第2年年初购进一台新设备，使用到第3-6年年初的费用。,14,21,30,15,22,15,第十一章 图与网络分析,11.1 引言11.2 图与网络的基本概念11.3 最短路问题11.4 最小生成树问题,11.4 最小生成树问题,树是图论中的重要概念，所谓树就是一个无圈的连通图。,11.4 最小生成树问题,树是图论中的重要概念，所谓树就是一个无圈的连通图。,v1,v2,v3,v4,v5,v6,v7,v8,v9,v1,v2,v3,v5,v8,v7,v6,v4,v1,v2,v3,v4,v5,v7,v6,v8,v9,(a),(b),(c),无圈,连通,11.4 最小生成树问题,无向图G=(V,E)，保留G的所有点，而删掉部分G的边或者保留部分G的边，所获得的图G，称之为G的生成子图;,11.4 最小生成树问题,无向图G=(V,E)，保留G的所有点，而删掉部分G的边或者保留部分G的边，所获得的图G，称之为G的生成子图;,11.4 最小生成树问题,无向图G=(V,E)，保留G的所有点，而删掉部分G的边或者保留部分G的边，所获得的图G，称之为G的生成子图;,11.4 最小生成树问题,无向