第10章_图与网络分析(清华教材).ppt

第10章图与网络分析,第一节图论的基本概念（1）,引言,十八世纪的哥尼斯堡城中流过一条河（普雷.格尔河），河上有7座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样一个游戏：一个游者怎样才能一次连续走过这7座桥，回到原出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，这就是著名的“哥尼斯堡7桥”难题。,第一节图论的基本概念（2）,“哥尼斯堡7桥”难题最终在1736年由数学家Euler的一篇论文给予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论的发展是缓慢的，直到1936年匈牙利数学家O.Knig写出了图论的第一本专著有限图与无限图的理论。,在图论的发展过程中还有两位著名科学家值得一提，他们是克希霍夫和凯莱。克希霍夫在研究电网络时对图的独立回路理论作出了重要的贡献，而化学家凯莱在对碳氢化合物的同分异构体的数量进行计数时推动了图论中树的计数问题的研究。,第一节图论的基本概念（3）,图论的历史上最具有传奇色彩的问题也许要数著名的“四色猜想”了历史上许许多多数学猜想之一。,它描述对一张地图着色的问题，曾经有一位数学家这样说：“对于这个问题，一位数学家可以用不到五分钟的时间向马路上任何一位行人讲述清楚它，然后，两人都明白这一问题，但是，两人都无能为力。”,幸运的是在1970s终于由美国的两位数学家借助大型计算机将其证明了。,第一节图论的基本概念（4）,定义：有序二元组G=(V,E)称为一个图，其中,(1)V=v1,v2,vn是有穷非空集，称为顶点集，其中的元素叫图G的顶点.(2)E=eij称为边集，其中的元素叫图G的边.若eij=Vi,Vj是个无序二元组，则图G是个无向图,则图为右图形式：,例1设G=(V,E)，其中V=v1,v2,v3,v4，E=e1,e2,e3,e4,e5,第一节图论的基本概念（5）,端点：若eij=Vi,Vj，则称eij连接Vi和Vj,点Vi和Vj称为eij的端点,一条边的端点称为与这条边关联,例1设G=(V,E)，其中V=v1,v2,v3,v4，E=e1,e2,e3,e4,e5,点邻接的：与同一条边关联的两个端点称为邻接的,第一节图论的基本概念（4）,常用术语：,(1)端点相同的边称为环,(4)边和它的端点称为互相关联的,(5)既没有环也没有多重边的图，称为简单图,(2)若一对顶点之间有两条以上的边联结，则这些边称为重边,(3)有边联结的两个顶点称为相邻的顶点，有一个公共端点的边称为相邻的边,(6)一个没有环但允许多重边的图，称为多重图,第一节图论的基本概念（5）,顶点的次数:(1)在无向图中，与顶点v关联的边的数目（环算两次）称为v的次数，记为d(v)(2)悬挂点：次为1的点。悬挂边：悬挂点的关联边。孤立点：次为零的点。,第一节图论的基本概念（6）,定理1:,定理2任何图中奇次顶点的总数必为偶数,链：如果图中的某些点、边可以排列成点和边的交错序列，则称此为一条链。,圈：如一条链中起点和终点重合，则称此为一条圈。,初等链（圈）：如果链（圈）中点都是不同的，就称之为初等链（圈）。,简单链（圈）：如果链（圈）中边均不相同，就称之为初等链（圈）。,连通图：如果图中的任意两点之间至少存在一条链，则称图为连通图，否则为不连通图。,支撑子图：给了一个图G=(V,E),如果图G=(V,E),使V=V及E包含于E,则称G是G的一个支撑子图。,基础图：设给了一个有向图,D=(V,A),从D中去掉所有弧上得箭头就得到一个无向图,称之为D的基础图,记为G(D).,对无向图链与路（圈与回路）这两个概念是一致的。,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向图,路,链（点不同）,简单链（边不同）,第一节图论的基本概念（13）,对有向简单图G（V，E）对应着一个|V|V|阶矩阵A（aik)，其中,则称矩阵A是图G的邻接矩阵,例设图为,则其邻接矩阵为,返回,第二节图的连通与割集（1）,在图G中的，一个点和边的交替序列（ni，eij，nj，nk，ekl，nl）称为G中由ni到nl的一条路，记为ni,nl,简单路：如果路中的边不重复，称为简单路,当G是简单图时，,一、图的连通,初级路：如果路中的点不重复，称为初级路,由ni到nl的一条路可以用点的序列,来表示：（ni，nj，nk，nl）,回路：在G中，一条至少包含一条边，并且ninl的ni,nl称为G点一条回路。,树：一个无圈的连通图称为树。性质：树G=（V，E）的顶点数为p，边数为q，则q=p-1。,例如：,支撑树：图T=（V，E）是图G=（V，E）的支撑子图，若图T是一个树，则称T是图G的一个支撑树。,10.2树10.2.1树与支撑树,定理3：设图G=(V,E)是一个树,顶点个数,则G中至少有两个悬挂点。定理4：设图G=(V,E)是一个树的充分必要条件是G不含圈，且恰有条边。,定理5：设图G=(V,E)是一个树的充分必要条件是G是连通图，且边数定理6：设图G=(V,E)是一个树的充分必要条件是G的任意顶点之间恰有一条链。,（1）G不含圈（2）G是连通图（3）（4）图G=(V,E)是一个树上述条件有两个成立，就推出其余条件成立。,树的性质：1在图中任意两点之间必有一条而且只有一条通路。2在图中划去一条边，则图不连通。树是边最少的连通图3在图中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。4图中边数有n=p-1（p为顶点数）,支撑树和最小支撑树的实际应用,在实际生活中，支撑树和最小支撑树有许多重要的应用。例如：用网络G表示n个城市之间的通信线路，其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价，由此构造了一个赋权图。我们可以通过求该图的最小支撑树达到求解通信线路或总代价最小的最佳方案。,求支撑树“破圈法”和“避圈法”,v1,v2,v3,v5,e2,e3,e5,e1,e6,e7,e8,e4,v4,定理7：图G有支撑树，当且仅当图G是连通的。,v1,v2,v5,e2,e3,e5,e1,e6,e7,e8,e4,v4,我们给定一个连通图，如右所示，求它的支撑树。,破圈法：在图中任选一个圈，从这个圈中去掉一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。,v3,v1,v2,v5,e2,e3,e5,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,10.2.2最小支撑树问题,最小支撑树：给图G中的每一条边（vi，vj）一个相应的数ij，则称G为赋权图。ij称为边（vi,vj）的权数。在赋权图G的所有支撑树中，必有某个支撑树，其所有边的权数和最小，称这个树为图G的最小支撑树。求赋权图G的最小支撑树的方法也有两种，“破圈法”和“避圈法”。,破圈法：在原图中，任选一个圈，从圈中去掉权最大的一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。,6,5,5,1,7,2,3,4,4,v1,v2,v3,v4,v5,v6,v3,v2,1,v4,2,v5,3,v6,4,v1,5,6,5,5,1,7,2,3,4,4,v1,v2,v3,v4,v5,v6,避圈法：开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选边不构成圈的边。,第三节最短路问题（1）,路的权（或者路的长）：给定一个有（无）向网络G=(V,A,W)，设P为G中的一条有向路，令,则称W(P)为路径P的权（或长）,最短路：在网络G中，从顶点u到顶点v的具有最小权的路P(u,v)称为顶点u到顶点v的最短路。,在无向网络图中，最短路就简称为最短路在有向网络图中，最短路称为最短有向路,最短路是一条路径，且最短路的任一段也是最短路,最短路有一个重要而明显的性质：,第三节最短路问题（6）,Dijkstra算法中的符号：,P：表示某个点的P标号（永久标号）T：表示某个点的T标号（临时标号）,Si：表示第i步时具有P标号点的集合,(v)m：表示从Vs到V的最短路上，V的前一个点是Vm,(v)M：表示G中不含从Vs到V的路,(v)0：表示VVs,Dijkstra算法的具体步骤：,第三节最短路问题（7）,Dijkstra算法步骤：,第0步：(开始i=0）令S0=Vs，(Vs)0,对每一个VVs,令T（V），(V)M,令Ks,第1步：若Si=V，则算法终止，这时每个V都在Si中，最短路长为P(V),第2步：考察每个(Vk,Vj)E,且VjSi的点Vj,如果T(Vj)P(Vk)+wkj,则把T(Vj)修改为P(Vk)+wkj，把(Vj)修改为k,否则转第3步,第3步：令,若T(Vji),则Vji的T标号变为P标号，P(Vji)=T(Vji),令Si+1=SiVjik=ji,把i换成i+1,转第1步，否则终止,第三节最短路问题（8）,例求V1到其余各点的最短距离,第三节最短路问题（9）,例求下图下列有向图的顶点u1到其余顶点的最短有向路,解：第一步,置i=0，S0=V1,P(V1)=0,(V1)=0,令T（Vi），(Vi)M,(i=2,3,6),k=1,0,5,3,4,第三节最短路问题（10）,0,5,3,4,3,10,8,把T(V2)修改为P(V1)+W12=5,(V2)=1,同理T(V4)3,T(V6)4(V4)1,在所有T标号中T(V4)=3最小，令P(V4)=3,S1=V1,V4,k=4,第三节最短路问题（11）,4,i=1，把T(V5)=8,T(V3)=10,(V5)4,(V3)=4,在所有T标号中T(V6)=4最小，令P(V6)=4,S2=V1,V4,V6,k=6,第二步,第三节最短路问题（12）,置P=1,4,6，T=2,3,5,置P=1,2,4,6，T=3,5,第三节最短路问题（13）,置P=1,2,4,6，T=3,5,置P=1,2,3,4,6，T=5,第三节最短路问题（14）,置P=1,2,3,4,6，T=5,置P=1,2,3,4,5.6，T=,第三节最短路问题（15）,例2求下图从顶点V1到其余顶点的最短路,解：第一步,置u1=0，uj=w1j，j=2,3,8，P=1，T=2,3,8,0,2,8,1,第2步在T中寻找一点k，使得,第三节最短路问题（16）,第2步在T中寻找一点k，使得,得k=3,置P=1,3，T=2,4,5,6,7,8,1,第三节最短路问题（17）,第三节最短路问题（18）,第三节最短路问题（19）,第三节最短路问题（20）,第三节最短路问题（21）,最短路的应用（1）,一、可化为最短路问题的多阶段决策问题,最短路的应用（1-1）,解：把这个问题化为最短路问题。,设bi表示设备在第i年年初的购买费,ci表示设备使用i年后的维修费,V=v1,v2,v6,点vi表示第i年年初购进一台新设备,虚设一个点v6表示第5年年底.E=vivj|1ij6.,这样上述设备更新问题就变为：在有向赋权图G=(V,E,F)(图解如下)中求v1到v6的最短路问题.,最短路的应用（5）,也可构造加权有向图G2(V,E),（1）顶点集V=，表第i年初购置新设备的决策，表第五年底.,(2)弧集E=(Vi,Vj),i=1,2,3,4,5;ij6,弧(Vi,Vj)表第i年初购进一台设备一直使用到第j年初的决策，其权W(Vi,Vj)表由这一决策在第i年初到第j年初的总费用，如W(V1,V4)=11+5+6+8=30.,(3)问题转化为求V1到V6的最短路问题，求得两条最短路为，,权为53，与图G1(V,E)的解相同,由实际问题可知,设备使用三年后应当更新,因此删除该图中v1到v5,v1到v6,v2到v6的连线；又设备使用一年后就更新则不划算,因此再删除该图中v1v2,v2v3,v3v4,v4v5,v5v6五条连线后得到,从上图中容易得到v1到v6只有两条路：,v1v3v6（费用22+31）和v1v4v6（费用22+31）.,而这两条路都是v1到v6的最短路.,-,0,(v1,),(v1,),(v1,),(v1,1),v1,1,(v1,6),(v1,6),(v1,3),(v1,),(v1,),(v4,11),(v1,),(v1,),(v1,),(v1,3),v1,3,(v1,),(v1,),(v1,),(v1,),(v3,5),v3,5,(v4,11),(v4,11),(v1,),(v1,),(v2,6),v2,6,(v1,),(v5,9),v5,9,(v5,10),(v5,12),(v1,),(v5,10),v5,10,(v5,12),(v1,),(v1,),(v5,12),v5,12,(v1,),(v1,),v1,对无向图，用类似方法可求,例：利用Dijkstra标号法求右图中v1到v8的最短路。,v1,v2,v3,v4,v5,v6,v7,v8,v9,6,1,2,2,3,1,10,6,4,10,2,4,3,2,6,3,v8,v5,v2,v3,v1,给一个有向图D(V,A)，指定两个点，一个称为发点，记为vs，另一个点称为收点，记为vt，其余点称为中间点。对于D中的每一个弧(vi,vj)，相应地给一个数cij（cij0），称为弧(vi,vj)的容量。我们把这样的D称为网络（或容量网络），记为D(V,A,C)。如上图。,10.4最大流问题10.4.1基本概念和定理,3,5,1,1,4,2,3,5,2,vs,v2,v1,v3,v4,vt,所谓网络上的流，是指定义在弧集A上的函数ff(vi,vj)，并称f(vi,vj)为弧(vi,vj)上的流量，简记为fij。,3,1,5,2,1,0,1,0,4,1,2,2,3,1,5,2,2,1,vs,v2,v1,v3,v4,vt,容量：每个弧上的最大通过能力，用cij表示，即弧上的第一个数字；流量：弧上实际通过的流量，用xij表示，弧上的第二个数字；显然0=xij=cij，如果xij=cij则称为饱和弧；,截集：分离始点vs和终点vt的弧的集合，叫做截集截量：截集的容量叫做截量,可行流：（1）（2）各点流入量=流出量，且vs的流出量=vt的流入量，这样的流称之为可行流,的弧称为饱和弧；的弧称为非饱和弧。的弧称为零流弧；的弧称为非零流弧。若是网络中从发点到收点的链，链上的弧分为两类：一类与链的方向一致，叫做前向弧，记为；另一类与链的方向相反，叫做后向弧，记为。增广链：是可行流，是一条从发点到收点的链，若在前向弧上，即在中每一弧是非饱和弧；在后向弧上，即在中每一弧是非零流，则称此链为增广链。,vs,vt,v2,v1,v4,v3,(3,3),(5,1),(1,1),(4,3),(1,1),(2,2),(3,0),(2,1),(5,3),增广链：是可行流，是一条从发点到收点的链，若在前向弧上，即在中每一弧是非饱和弧；在后向弧上，即在中每一弧是非零流，则称此链为增广链。,是一个增广链,显然图中增广链不止一条,4、容量网络G=（V，E，C），vs为始点，vt为终点。如果把V分成两个非空集合使，则所有始点属于S，而终点属于的弧的集合，称为由S决定的截集,记作。截集中所有弧的容量之和，称为这个截集的容量，记为。,容量为24,求下图所示网络中的最大流，弧旁数为,最小截集,13(11),9(9),4(0),5(5),6(6),5(5),5(4),5(4),4(4),4(3),9(9),10(7),截集1,截集2,最小截量为：9+6+5=20,（120）,（230）,（150）,（200）,1标号方法很简单：首先找到一条增广链，沿此进行最大可能调整，再找增广链，再调整，直到没有增广链。寻找增广链的标号法：先给vs标号（0，+）,而后依次审查各条弧（vi,vj）：对前向弧，饱和否？不饱和（使其增加），给vj点标号（vi，l(vj);对后向弧，是否非零流弧（使其减少）？是，给vj标号（-vi,l(vj)）,直到给vt标上号，就得到了增广链。调整对于增广链，,求最大流的方法,调整令：得到新的可行流，重新标号，直至标不下去为止。,例：解水网最大流问题,vs,V2,(0,+),V1,(3,3),(5,1),(1,1),(4,3),(1,1),(2,2),(3,0),(5,3),(2,1),V4,V3,Vt,(vs,4),(-v1,1),(-v2,1),(v2,1),(v3,1),1标号,对前向弧，饱和否？不饱和（使其增加），给vj点标号（vi，l(vj);对后向弧，是否非零流弧（使其减少）？是，给vj标号（-vi,l(vj)）,直到给vt标上号，就得到了增广链。,vs,V2,(0,+),V1,(3,3),(5,2),(1,0),(4,3),(1,0),(2,2),(3,0),(5,3),(2,2),V4,V3,Vt,(vs,3),2沿增广链进行调整，前向弧增加1，后向弧减少l。,vs,V2,(0,+),V1,(3,3),(5,2),(1,0),(4,3),(1,0),(2,2),(3,0),(5,3),(2,2),V4,V3,Vt,(vs,3),vs,V2,V1,V3,V4,Vt,(3,3),(5,2),(4,3),(1,0),(1,0),(2,2),(3,0),(5,3),(2,2),(0,+),(vs,3),重新标号，直至标不下去为止。最小截集为（vs，v2），（v1，v3),容量为5。最大流也为5。,例1：求从发点V1到收点V7的最大流。弧的流量放在括号内。如图.V=20,4(3),关于最大流问题的定理：定理1可行流f*fij*是最大流，当且仅当D中不存在关于f*的增广链。定理2（最大流最小截定理）任一网络中，最大流的流