《图与网络分析》PPT课件.ppt

第八章图与网络分析,(GraphTheoryandNetworkAnalysis),本章内容,图与网络的基本知识树最短路问题最大流问题最小费用流问题,哥尼斯堡七空桥,一笔画问题,1图与网络的基本知识,环球旅行问题,一个图是由点集V=vj和V中元素的无序对的一个集合E=ek构成的二元组，记为G=(V,E),其中V中的元素vj叫做顶点，V表示图G的点集合；E中的元素ek叫做边，E表示图G的边集合。,例,图1,定义1,图及其分类,如果一个图是由点和边所构成的，则称其为无向图，记作G=(V,E)，连接点的边记作vi,vj,或者vj,vi。,如果一个图是由点和弧所构成的，那么称它为有向图，记作D=(V,A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。,V=v1,v2,v3,v4,v5,v6，A=(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6),图2,图及其分类,一条边的两个端点是相同的,那么称为这条边是环。如果两个端点之间有两条以上的边，那么称为它们为多重边。,一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。,每一对顶点间都有边相连的无向简单图称为完全图。有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。,定义2,定义3,图及其分类,定义4,图G=(V,E)的点集V可以分为两个非空子集X，Y，即XY=V,XY=，使得E中每条边的两个端点必有一个端点属于X，另一个端点属于Y，则称G为二部图(偶图)，有时记作G=(X,Y,E)。,X:v1,v3,v5,Y:v2,v4,v6,图及其分类,度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的关联边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。,以点v为端点的边的个数称为点v的度（次），记作。,图中d(v1)=4，d(v6)=4（环计两度）,定义5,顶点的次,有向图中，以vi为始点的边数称为点vi的出次，用表示；以vi为终点的边数称为点vi的入次，用表示；vi点的出次和入次之和就是该点的次。所有顶点的入次之和等于所有顶点的出次之和。,定理1,定理2,所有顶点度数之和等于所有边数的2倍。,在任一图中，奇点的个数必为偶数。,定义6,顶点的次,图G=(V,E)，若E是E的子集，V是V的子集，且E中的边仅与V中的顶点相关联，则称G=(V,E)是G的一个子图。特别是，若V=V，则G称为G的生成子图(支撑子图)。,定义7,子图,在实际应用中，给定一个图G=（V,E）或有向图D=（V,A）,在V中指定两个点，一个称为始点（或发点），记作v1，一个称为终点（或收点），记作vn，其余的点称为中间点。对每一条弧，对应一个数，称为弧上的“权”。通常把这种赋权的图称为网络。,定义8,无向图G=(V,E)，若图G中某些点与边的交替序列可以排成(vi0,ei1,vi1,ei2,vik-1,eik,vik)的形式，且eit=(vit-1,vit)(t=1,k)，则称这个点边序列为连接vi0与vik的一条链，链长为k。点边列中没有重复的点和重复边者为初等链。,连通图,连通图,无向图G中，连结vi0与vik的一条链，当vi0与vik是同一个点时，称此链为圈。圈中既无重复点也无重复边者为初等圈。,定义9,定义10,一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图都可以分为若干个连通子图，每一个称为原图的一个分图。,对于有向图可以类似于无向图定义链和圈，初等链、圈，此时不考虑边的方向。而当链(圈)上的边方向相同时，称为道路(回路)。对于无向图来说，道路与链、回路与圈意义相同。,对于网络（赋权图）G=（V,E）,其中边有权，构造矩阵，其中：称矩阵A为网络G的权矩阵。,设图G=（V,E）中顶点的个数为n，构造一个矩阵，其中：称矩阵A为网络G的邻接矩阵。,定义11,定义12,图的矩阵表示,当G为无向图时，邻接矩阵为对称矩阵。,例,权矩阵为：,邻接矩阵为：,图的矩阵表示,欧拉回路与中国邮路问题,定义13,连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。具有欧拉回路的图称为欧拉图(E图)。在引言中提到的哥尼斯堡七桥问题就是要在图中寻找一条欧拉回路。,定理3,无向连通图G是欧拉图，当且仅当G中无奇点。,定理4,连通有向图G是欧拉图，当且仅当它每个顶点的出次等于入次。,欧拉回路与中国邮路问题,定理5,已知图G*=G+E1无奇点，则最小的充分必要条件为：(1)每条边最多重复一次；(2)对图G中每个初等圈来讲，重复边的长度和不超过圈长的一半。,本章内容,图与网络的基本知识树最短路问题最大流问题最小费用流问题,2树,运动员,乒乓球单打比赛,树的概念和性质,定理6,定义14,连通且不含圈的无向图称为树。树中次为1的点称为树叶，次大于1的点称为分枝点。,图T=(V,E),|V|=n,|E|=m，则下列关于树的说法是等价的。(1)T是一个树。(2)T无圈，且m=n-1。(3)T连通，且m=n-1。(4)T无圈，但每加一新边即得惟一一个圈。(5)T连通，但任舍去一边就不连通。(6)T中任意两点，有惟一链相连。,一个图G有生成树的充要条件是G是连通图。,设图是图G=(V,E)的一支撑子图，如果图是一个树,那么称K是G的一个生成树（支撑树），或简称为图G的树。图G中属于生成树的边称为树枝，不在生成树中的边称为弦。,定义15,定理7,图的生成树,（一）避圈法,在图中任取一条边e1，找一条与e1不构成圈的边e2，再找一条与e1，e2不构成圈的边e3。一般设已有e1，e2，ek，找一条与e1，e2，ek中任何一些边不构成圈的边ek+1，重复这个过程，直到不能进行为止。,e5,v1,v2,v5,e2,e3,e1,e6,e7,e8,e4,v4,v1,v2,e1,v3,e2,e4,v4,v5,e6,v3,v1,v2,v3,v5,e1,e6,e8,e4,v4,（二）破圈法,用破圈法求出下图的一个生成树。,最小生成树问题,定义16,如果图是图G的一个生成树，那么称E1上所有边的权的和为生成树T的权，记作S(T)。如果图G的生成树T*的权S(T*)，在G的所有生成树T中的权最小，即那么称T*是G的最小生成树。,某六个城市之间的道路网如图所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。,v1,v2,v3,v4,v5,1,4,2,3,1,3,5,2,根据破圈法和避圈法两种方式得到了图的两个不同的支撑树，由此可以看到连通图的支撑树不是唯一的。,最小树的两种算法,算法1（Kruskal算法）,算法2（破圈法）,树根及其应用,定义17,若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树。,定义18,有向树T，恰有一个结点入次为0，其余各点入次均为1，则称T为根树(又称外向树)。,定义19,在根树中，若每个顶点的出次小于或等于m，称这棵树为m叉树。若每个顶点的出次恰好等于m或零，则称这棵树为完全m叉树。当m=2时，称为二叉树、完全二叉树。,本章内容,图与网络的基本知识树最短路问题最大流问题最小费用流问题,最短路的一般提法为：设为连通图，图中各边有权（表示之间没有边），为图中任意两点，求一条路，使它为从到的所有路中总权最短。即：最小。,3最短路问题,(一)狄克斯屈拉(Dijkstra)算法适用于wij0，给出了从vs到任意一个点vj的最短路。,Dijkstra算法是在1959年提出来的。目前公认，在所有的权wij0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj的最短路。,算法步骤：1.给始点vs以P标号，这表示从vs到vs的最短距离为0，其余节点均给T标号，2.设节点vi为刚得到P标号的点，考虑点vj，其中，且vj为T标号。对vj的T标号进行如下修改：3.比较所有具有T标号的节点，把最小者改为P标号，即：当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。,例9用Dijkstra算法求下图从v1到v8的最短路。,解（1）首先给v1以P标号，给其余所有点T标号。,（2）,（3）,（4）,v1,v7,v2,v3,v6,v4,v8,v5,4,5,9,4,5,4,6,4,6,7,1,5,7,比较所有T标号，T(v2)最小，令P(v2)=4，并记录路径(v1,v2),比较所有T标号，T(v3)最小，令P(v3)=6,并记录路径(v1,v3),比较所有T标号，T(v5)最小，令P(v5)=8,并记录路径(v2,v3),比较所有T标号，T(v4)最小，令P(v4)=9,并记录路径(v2,v4),比较所有T标号，T(v6)最小，令P(v6)=13,并记录路径(v5,v6),比较所有T标号，T(v7)最小，令P(v7)=14,并记录路径(v7,v8),Dijkstra算法仅适合于所有的权wij=0的情形。如果当赋权有向图中存在有负权弧时，则该算法失效。,如图，有一批货物要从v1运到v9，弧旁数字表示该段路长，求最短运输路线。,标号法练习,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,6,6,5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,6,6,5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,6,7,5,6,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,6,7,5,6,8.5,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,6,7,5,6,8.5,9,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,4,6,7,5,6,8.5,9,练习：求从v1到v8的最短路,(0),(1,1),(1,3),(3,5),(2,6),(5,10),(5,9),(5,12),标号法练习,求从v1到v8的最短路,(2,6),算法的基本思路与步骤：首先：设任一点vi到任一点vj都有一条弧。显然，从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi,vj)到vj。则v1到vi的这条路必然也是v1到vi的所有路中的最短路。设P1j表示从v1到vj的最短路长，P1i表示从v1到vi的最短路长，则有下列方程：开始时，令即用v1到vj的直接距离做初始解。第二步，使用递推公式：求，当进行到第t步，若出现则停止计算，即为v1到各点的最短路长。,（二）逐次逼近法,例10,求图中v1到各点的最短路,类似可得,表中最后一列数字表示v1到各点的最短路长,例11求：5年内，哪些年初购置新设备，使5年内的总费用最小。解：（1）分析：可行的购置方案（更新计划）是很多的，如：1)每年购置一台新的，则对应的费用为：11+11+12+12+13+5+5+5+5+5=842)第一年购置新的，一直用到第五年年底，则总费用为：11+5+6+8+11+18=59显然不同的方案对应不同的费用。,（2）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。求解步骤：1）画赋权有向图：设vi表示第i年初，(vi,vj)表示第i年初购买新设备用到第j年初（j-1年底），而Wij表示相应费用，则5年的一个更新计划相当于从v1到v6的一条路。2）求解（标号法）,W12=11+5=16W13=11+5+6=22W14=11+5+6+8=30W15=11+5+6+8+11=41W16=11+5+6+8+11+18=59,W23=11+5=16W24=11+5+6=22W25=11+5+6+8=30W26=11+5+6+8+11=41,W45=12+5=17W46=12+5+6=23W56=13+5=18,W34=12+5=17W35=12+5+6=23W36=12+5+6+8=31,（三）Floyd算法,可直接求出网络中任意两点间的最短路；,本章内容,图与网络的基本知识树最短路问题最大流问题最小费用流问题,4最大流问题,最大流问题是一类应用极为广泛的问题，例如在交通运输网络中有人流、车流、货物流，供水网络中有水流，金融系统中有现金流，通信系统中有信息流，等等。20世纪50年代福特(Ford)、富克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成部分。,问题引入,上图可看作输油管道网，vs为起点，vt为终点，v1,v2,v3,v4为中转站，边上的数表示该管道的最大输油能力，问应如何安排各管道输油量，才能使从vs到vt的总输油量最大?,网络D上的流，是指定义在弧集合E上的一个函数其中f(vi,vj)=fij叫做弧(vi，vj)上的流量。,最大流有关概念,定义20,设一个赋权有向图D=（V,E）,在V中指定一个发点vs和一个收点vt,其它的点叫做中间点。对于D中的每一个弧（vi,vj）E,都有一个非负数cij,叫做弧的容量。我们把这样的图D叫做一个容量网络，简称网络，记做D=（V，E，C）。,称满足下列条件的流为可行流：（1）容量条件：对于每一个弧（vi,vj）E有0fijcij。（2）平衡条件：对于发点vs，有对于收点vt，有对于中间点，有,可行流中fijcij的弧叫做饱和弧，fijcij的弧叫做非饱和弧。fij0的弧为非零流弧，fij0的弧叫做零流弧。,定义21,容量网络G=(V,E,C),vs,vt为发、收点，若有边集E为E的子集，将G分为两个子图G1,G2，其顶点集合分别记S，S=V,S=,vs,vt分属S，满足：G(V,E-E)不连通；E为E的真子集，而G(V,E-E)仍连通，则称E为G的割集，记E=(S,)。,最大流-最小流定理,定理11,设f为网络G=(V,E,C)的任一可行流，流量为W，(S，)是分离vs,vt的任一割集，则有WC(S,)。,定理10,(最大流-最小割定理)任一个网络G中，从vs到vt的最大流的流量等于分离vs、vt的最小割的容量。,可行流f是最大流的充分必要条件是不存在从vs到vt的关于f的一条可增广链。,定义22,推论,求最大流的标号算法,设已有一个可行流f，标号的方法可分为两步：第1步是标号过程，通过标号来寻找可增广链；第2步是调整过程，沿可增广链调整f以增加流量。,从网络中的一个可行流f出发（如果D中没有f，可以令f是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。,一、标号过程：1给发点vs标号（0，+）。2取一个已标号的点vi，对于vi一切未标号的邻接点vj按下列规则处理：（1）如果边，且，那么给vj标号，其中：（2）如果边，且，那么给vj标号，其中：3重复步骤2，直到vt被标号或标号过程无法进行下去，则标号结束。若vt被标号，则存在一条增广链，转调整过程；若vt未被标号，而标号过程无法进行下去，这时的可行流就是最大流。,二、调整过程设1令2去掉所有标号，回到第一步，对可行流重新标号。,例：求下图所示网络中的最大流，弧旁数为,(1,1),(2,0),例：求下图所示网络中的最大流，弧旁数为,(2,1),(1,1),例14求下图所示网络中的最大流，弧旁数为,图8-40,解.用标号法。1.标号过程。1）首先给vs标号（0，+）2）看vs:在弧(vs,v1)上,fs2=2cs2=4,具备标号条件。故给v2标号(+vs,v2),其中v2=min(cs2-fs2),vs=min2,+=4.3）看v2:在弧(v2,v5)上,f25=0c25=3,具备标号条件。故给v5标号(+v2,2),其中v5=min3，2=2.vt类似前面的步骤，可由v4得到标号+v4，2由于vt已得到标号，说明存在可增广链，所以标号过程结束。,（，+）,（-v5，2）,（+v1，2）,（+v4，2）,（+v2，2）,（+vS，1）,（+vs，2）,图8-41,2.转入调整过程,令=vt=2为调整量，从vt点开始，由逆可增广链方向按标号+v4,2找到点v4,令f4t=f4t+2。再由v4点标号+v1,2找到前一个点v1，并令f14=f14+2。按v1点标号找到点v5，由于标号为-v5,(v5,v1)为反向边，令f15=f15-2。由v5点的标号再找到v2，令f25=f25+2。由v2点找到vs，令fs2=fs2+2。调整过程结束，调整中的可增广链见图8-41中的粗线边，调整后的可行流见图8-42,（，+）,（+vS，1）,图8-42,重新开始标号过程，寻找可增广链，当标到v3点为+vs,1以后，与vs,v3点邻接的v1,v2,v6点都不满足标号条件，所以标号过程无法再继续，而vt点并未得到标号，如图8-42。这时W=fs1+fs2+fs3=f4t+f5t+f6t=11，即为最大流的流量，算法结束。,本章内容,图与网络的基本知识树最短路问题最大流问题最小费用流问题,5最小费用流问题,最小费用流问题的一般提法：已知容量网络G=(V,E,C)，每条边(vi,vj)除了已给出容量cij外，还给出了单位流量的费用dij(0)，记G=(V,E,C,d)。求G的一个可行流f=fij，使得流量W(f)=v，且总费用最小。d(f)=(vi,vj)Edijfij特别地，当要求f为最大流时，此问题即为最小费用最大流问题。,最小费用流问题的常用算法有两种：原始算法；(2)对偶算法。下面只介绍第二种算法，本算法是有效算法。,5最小费用流问题,已知网络G=（V，E，C，d），f是G上的一个可行流，为一条从vs到vt的增广链，称为链的费用。,定义24,若*是从vs到vt的增广链中费用最小的增广链，则称*是最小费用增广链。,定理12,若f是流量为W(f)的最小费用流，是关于f的从vs到vt的一条最小费用可增广链，则f经过调整流量得到新可行流f(记为f=f)，一定是流量为W(f)+的可行流中的最小费用流。,1.当，令,寻找关于f的最小费用增广链：构造一个关于f的赋权有向图L(f)，其顶点是原网络G的顶点，而将G中的每一条弧(vi,vj)变成两个相反方向的弧（vi,vj）和(vj,vi)，并且定义图中弧的权lij为：,在网络G中寻找关于f的最小费用增广链等价于在L(f)中寻求从vs到vt的最短路。,2.当（vj,vi）为原来网络G中(vi,vj)的反向弧,令,步骤：（1）取零流为初始可行流，f(0)=0。（2）一般地，如果在第k-1步得到最小费用流f(k-1)，则构造图L(f(k-1)。（3）在L(f(k-1)中，寻求从vs到vt的最短路。若不存在最短路，则f(k-1)就是最小费用最大流；否则转(4)。（4）如果存在最短路，则在可行流f(k1)的图中得到与此最短路相对应的增广链，在增广链上，对f(k1)进行调整，调整量为：,令,得到新可行流f(k)。对f(k)重复上面步骤，返回（2）。,例16在图8-48所示运输网络上求流量v为10的最小费用最大流，弧旁权是（cij,dij）,d(f(1)=51+52+51=20,d(f(2)=42+51+52+71=30,d(f(3)=24+81+52+33+32+71=48f(3)即为所求的最小费用流。,