运筹学__图与网络分析(11-11).ppt

第八章图与网络分析,引例,哥尼斯堡七桥问题,环球旅行问题：,环球旅行问题的解,第1节图与网络的基本知识,图可以用来做什么：管理当中，事物及事物间的联系可以用图来描述,五只球队的比赛情况,工作分配问题,图已经应用于物质结构、交通、信息传递等的描述,图与网络的基本概念（1）,图：这里讨论的图由点以及点与点间的连线构成，与平面几何的图不同，这里只关心图中有多少个点，点与点间有无连线，至于点与点间的连线是直线还是曲线，点的相对位置，则是无关紧要的。,图与网络的基本概念（2）,定义1一个图是由点集V=vi和V中的元素的无序对的一个集合E=ek所构成的二元组，记为G=(V,E)，V中的元素vi叫做顶点，E中的元素ek叫做边,V=v1,v2,v3,v4,v5E=e1,e2,e3,e4,e5,e6,e1=(v1,v1),e2=(v1,v2),例,图与网络的基本概念（3）,相邻：图中的两点间存在连线（边），则称这两点相邻，并称它们是这条边的端点；若两条边有公共的端点，则称这两条边相邻，并称它们是其公共端点的关联边。,边数：m(G)=|E|顶点数：n(G)=|V|,图与网络的基本概念（4）,无向边与无向图：若图中任一条边的端点无序，即(vi,vj)与(vj,vi)是同一条边，则称它为无向边，此时图称为无向图。有向图：若图中边(vi,vj)的端点是有序的，则称它是有向边（或弧），vi与vj分别称为这条有向边的始点和终点，相应的图称为有向图。,图与网络的基本概念（5）,v2,v1,v5,v3,v4,e2,e1,e3,e4,e5,e6,环(自回路),多重边,定义2不含环和多重边的图称为简单图。含多重边的图称为多重图。,图与网络的基本概念（6）,定义3每一对顶点间都有边相连的无向简单图称为无向完全图；有向完全图是指每一对顶点间有且仅有一条有向边的简单图。完全图顶点数n与边数m间成立如下关系:m=n(n-1)/2,图与网络的基本概念（7）,定义4图G=(V,E)的点集V可以分为两个非空子集X，Y，即XY=V，XY=，使得E中的每条边的两个端点中必有一个属于X，另一个属于Y，则称G为二部图（偶图），有时记为G=(X,Y,E),图与网络的基本概念（8）,定义5以v为端点的边数，叫做点v的次(degree)，记作deg(v),或简记为d(v)。,d(v1)=4,d(v2)=3,悬挂点,孤立点,悬挂边,偶点,奇点,图中顶点次的性质,定理1任何图中顶点次数的总和等于边数的2倍。定理2任何图中次为奇数的顶点必有偶数个。,定义6在有向图中，以顶点v为始点的边数称为顶点v的出次，记为d+(v)；以v为终点的边数称为v的入次，记为d-(v)。顶点v的出次与入次的和称为点v的次。,图与网络的基本概念（9）,定义7图G=(V,E),若E是E的子集，若V是V的子集，且E中的边仅与V中的顶点相关联，则称G=(V,E)为图G的一个子图，特别地，若V=V,则称G为G的一个生成子图（支撑子图）。,图与网络的基本概念（10）,有时需要用图来表示事物及事物之间的定量的联系，这时图中除了顶点与边外，还有与点或边有关的某些数量指标，常称它们为“权”，权在图中可以表示距离、费用、通过能力等。这种点或边带权的图称为网络（或赋权图）,连通图（1）,定义8无向图中一个点、边交错的序列，序列中的第一个和最后一个元素都是点，若其中每条边以序列中位于它之前和之后的点为端点，则称这个点边序列为图中连接其第一个点与最后一个点的链。链中所含的边数称为链长。,链，但只是简单链而非初等链,简单链：没有重复边；初等链：既无重复边也无重复点。对有向图可类似定义链，如果各边的方向一致，则称为道路。,连通图（2）,定义9若在无向图中，一条链的第一个点与最后一个点重合，则称这条链为圈。只有重复点而无重复边的圈为简单圈，既无重复点又无重复边的圈为初等圈。,初等圈,非简单的圈,连通图（3）,路(边的方向一致),不是路,连通图（4）,定义10一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图总可以分为若干个连通子图，每一个称为原图的一个分图（连通分支）。,连通图,非连通图,图的矩阵表示邻接矩阵,对于图G=(V,E),|V|=n,构造一个矩阵A=(aij)nn,其中：,图的矩阵表示权矩阵,对于网络（赋权图）G=(V,E),|V|=n,其中边(vi,vj)上有权wij，构造一个矩阵A=(aij)nn,其中：,欧拉回路（1）,定义13连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条道路为欧拉道路。若存在一条回路经过每边一次也仅一次，则称这条回路为欧拉回路。具有欧拉回路的图称为欧拉图（E图）。,定理3无向连通图G是欧拉图，当且仅当G中无奇点,欧拉回路（2）,推论1无向连通图G为欧拉图，当且仅当G的边集可以划分为若干个初等回路。推论2无向连通图G中有欧拉道路，当且仅当G中恰好有两个奇点。,哥尼斯堡七桥问题无解,一笔画问题,欧拉回路（3）,定理4连通有向图G是欧拉图，当且仅当它的每个顶点的出次等于入次。连通有向图G有欧拉道路，当且仅当这个图中除了两个顶点外，其余每个顶点的出次等于入次，且这两个顶点中，一个顶点的入次比出次多1，另一个的入次比出次少1。,树树的概念,定义14连通且不含圈的无向图称为树。树中次为1的点称为树叶，次大于1的点称为分枝点。,树树的性质,定理6T=(V,E),|V|=n,|E|=m,则下列关于树的说法是等价的。（1）T是一个树（即T是不含圈的连通图）,树树的性质,（2）T无圈，且m=n-1,树树的性质,（3）T连通，且m=n-1,树树的性质,（4）T无圈，但每加一新边就得到唯一的一个圈,T是边数最多的无圈图,树树的性质,（5）T连通，但任舍去一边就不连通,T是边数最少的连通图,树树的性质,（6）T中任意两点有唯一一条链相连,生成树概念,定义15若图G的生成子图是一棵树，则称该树为图G的生成树（支撑树），或简称为图G的树。,定理7图G有生成树的充分必要条件是图G是连通的,生成树解法（1）,避圈法,这种方法是每步从连通图中选出一条边，使得它与已经选出的边不构成圈，直到选够n-1条边为止。,一个图的生成树不是唯一的。,避圈法的另一种表述,先去掉图G中所有边，只留下点，每次任意放回一条边，使之与已经放回的边不构成圈，反复进行，直到有（n-1）条边为止。,5个顶点，4条边,生成树解法（2）,破圈法,这种方法是每步从连通图中选一个圈，并去掉该圈的一条边，直到图中不含圈为止。,另一种解法,最小生成树概念,定义16连通图G=(V,E),每条边上有非负权L(e)，一棵生成树上各边的权之和，称为这棵生成树的权，具有最小权的生成树，称为最小生成树（最小支撑树），简称最小树。,例如如何用造价最省的电话线网将各有关单位连起来的问题，就归结为求最小生成树的问题。,3,5,4,3,6,7,1,2,4,非最小树,最小生成树解法1（Kruskal算法）,避圈法：这种方法每步从图中挑选一条边，满足：（1）它与已经选出的边不构成圈；（2）它是满足条件（1）的权最小的边，直到选够n-1条边为止。,9个顶点，8条边,避圈法另一种表述,先去掉图G的所有边，只留下顶点，每次放回一条权最小的边，使之与已经放回的边不构成圈，反复进行，直到有（n-1）条边为止。,9,4,8,2,3,3,3,7,9,1,4,2,3,3,1,6个顶点，5条边,最小生成树解法（2）,破圈法：这种方法每步从图中任选一个圈，然后去掉该圈中权最大的边，直到图中没有圈为止。,1,4,1,2,1,3,1,4,4,5,5,3,2,4,5,2,9个顶点，8条边,破圈法举例,9,4,8,2,3,3,3,7,9,1,9,4,8,2,3,3,3,7,9,1,6个顶点，5条边,破圈法举例,最小生成树的权=9,/,/,/,/,最短路问题,最短路问题是网络理论中应用最广泛的问题之一，许多优化问题，如设备更新、管道铺设、线路安排等都可以化为最短路问题求解。最短路问题的提法：设G=(V,E)为连通图，图中的各边(vi,vj)有非负权lij(lij=表示vi,vj间无边),vs,vt是图中任意两点，求一条道路，使它是从vs到vt的所有道路中总权最小的道路。,Dijkstra算法,原理：若(vs,v1,vn-1,vn)是vs到vn的最短路，则(vs,v1,vn-1)是vs到vn-1的最短路。思路：采用标号法。使用两种标号，T标号和P标号，一个点的P标号是永久性标号，表示起点到该点最短路的权，它一旦给出就不再改变；而点的T标号是临时性的标号，表示对起点到该点最短路的权的估计值，当得到更精确的估计值时要修改原来的T标号，此外算法的每一步要把某一个点的T标号改成P标号，当得到终点vt的P标号时算法结束。,Dijkstra算法步骤,第一步：给vs点P标号P(vs)=0,其余点T标号T(vi)=+第二步：若vi为刚获得P标号的点，则修改以vi为起点的各边终点的T标号为下两个数中的较小者：一个是vi的P标号与该边权之和，另一个是该终点原来的T标号。第三步：取所有具有T标号的点中T标号值最小的点，将其T标号改为P标号。若本次得到P标号的点为终点，算法终止，否则返回上一步。,例（p251）,给起点P标号0，其余点T标号（在下面的求解过程中，粉色的数字为P标号）,修改以刚获得P标号的点为起点的边的终点的T标号；然后将最小的T标号改成P标号,4,6,5,4,4,7,7,9,6,5,5,4,1,0,4,9,6,8,最短路线见图,v1,v2,v3,v4,v6,v5,v7,v8,3,8,4,2,2,4,3,3,1,2,3,3,4,0,T(v2)=min(,0+4)=4,T(v3)=min(,0+8)=8黄色数字表示P标号,最短路问题举例,v1,v2,v3,v4,v6,v5,v7,v8,3,8,4,2,2,4,3,3,1,2,3,3,4,0,4,8,比较所有的T标号，4最小。所以P（v2）=4,4,从v2出发，到v4,v5。T(v4)=min(,4+3)=7,T(v5)=min(,4+4)=8,7,8,v1,v2,v3,v4,v6,v5,v7,v8,3,8,4,2,2,4,3,3,1,2,3,3,4,0,4,8,比较所有的T标号，7最小。所以P（v4）=7,4,从v4出发，到v6。T(v6)=min(,7+3)=10,7,8,7,10,v1,v2,v3,v4,v6,v5,v7,v8,3,8,4,2,2,4,3,3,1,2,3,3,4,0,4,8,比较所有的T标号，8最小。所以P(v3)=P(v5)=8,4,从v3出发，到v7,T(v7)=min(,8+3)=11从v5出发，到v8,T(v8)=min(,8+4)=12,7,8,7,10,8,8,11,12,v1,v2,v3,v4,v6,v5,v7,v8,3,8,4,2,2,4,3,3,1,2,3,3,4,0,4,8,比较所有的T标号，10最小。所以P(v6)=10,4,从v6出发，到v7,T(v7)=min(11,10+3)=11比较所有的T标号，11最小。所以P(v7)=11,7,8,7,10,8,8,12,10,11,11,v1,v2,v3,v4,v6,v5,v7,v8,3,8,4,2,2,4,3,3,1,2,3,3,4,0,4,8,4