图与网络分析 讲稿.ppt

《图与网络分析 讲稿.ppt》由会员分享，可在线阅读，更多相关《图与网络分析 讲稿.ppt（34页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、图与网络分析 第一页，讲稿共三十四页哦1.图的基本知识图的基本知识一、图一、图1、图：由一些点及一些点的连线所组成的图形。、图：由一些点及一些点的连线所组成的图形。若若V=V1,V2,Vn是空间是空间n个点的集合个点的集合 E=e1,e2,em是空间是空间m个点的集合个点的集合满足满足1)V非空非空 2)E中每一条线中每一条线ei是以是以V中两个点中两个点Vs,Vt为端点为端点 3)E中任意两条线之间除端点之外无公共点中任意两条线之间除端点之外无公共点.则由则由V、E构成的二元组合构成的二元组合G=(V，E)就是图。就是图。2、子图：已知图、子图：已知图G1（V1，E1）若）若V1 V，E1

2、E 则称图则称图G1（V1，E1）是图）是图G=(V，E)的子图的子图3、若在图若在图G中，某个边的两个端点相同，则称中，某个边的两个端点相同，则称e是环。是环。4、多重边：图中某两点之间有多余一条的边，称之为多重边。、多重边：图中某两点之间有多余一条的边，称之为多重边。多重图：含有多重边的图。多重图：含有多重边的图。5、简单图：无环、无多重边的图。、简单图：无环、无多重边的图。第二页，讲稿共三十四页哦 二、连通图二、连通图1、链：给定一个图、链：给定一个图G=(V,E)，一个点边的交错序列，一个点边的交错序列(vi1,ei1,vi2,ei2,vik-1,eik-1,vik)，如果满足，如果满

3、足eit=vit,vit+1(t=1,2,k-1)，则称为一条联结，则称为一条联结vi1和和vik的的链链，称点，称点vi2,vi3,vik-1为链的中间点。为链的中间点。2、圈：链、圈：链(vi1,vi2,vik)中，若中，若vi1=vik,，则称之为一个，则称之为一个圈圈。3、简单链：若链、简单链：若链(vi1,vi2,vik)中，点中，点vi1,vi2,vik都都是不同的，则称之为是不同的，则称之为简单链。简单链。4、连通图：图、连通图：图G中，若任何两个点之间，至少有一条链。中，若任何两个点之间，至少有一条链。第三页，讲稿共三十四页哦三、树三、树1、定义：一个无圈的连通图称为树。、定义

4、：一个无圈的连通图称为树。2、树的性质：、树的性质：1）图）图G是树的充分必要条件是任意两个顶点是树的充分必要条件是任意两个顶点之间恰有一条链。之间恰有一条链。2）在树中去掉任意一条边则构成一个不连通）在树中去掉任意一条边则构成一个不连通图，不再是树；在树中不相邻的两点之间添图，不再是树；在树中不相邻的两点之间添加一条边，恰好形成了一个圈，也就不再是加一条边，恰好形成了一个圈，也就不再是树。树。3）树中顶点的个数为）树中顶点的个数为P，则其边数必为，则其边数必为P-1。第四页，讲稿共三十四页哦3、支撑树：设图、支撑树：设图T=(V,E)是图是图G（V，E）的）的支撑子图，如果图支撑子图，如果图

5、T=(V,E)是一个树，则是一个树，则称称T是是G的一个支撑树。的一个支撑树。4、寻找支撑树的方法、寻找支撑树的方法1）破圈法：在图中任取一个圈，从圈中去掉）破圈法：在图中任取一个圈，从圈中去掉任一边，对余下的图重复上述操作，即可得任一边，对余下的图重复上述操作，即可得到一个支撑树。到一个支撑树。2）避圈法：每一步选取与已选的边构不成圈）避圈法：每一步选取与已选的边构不成圈的边，直到不能继续为止。的边，直到不能继续为止。第五页，讲稿共三十四页哦 5、最小支撑树、最小支撑树1）赋权图：给图）赋权图：给图G=(V,E)，对，对G中的每一条边中的每一条边vi,vj，相应地有一个数相应地有一个数wij

6、，则称这样的图，则称这样的图G为赋权图，为赋权图，wij称称为边为边vi,vj上的权。上的权。2）最小支撑树：如果）最小支撑树：如果T=(V,E)是是G的一个支撑树，称的一个支撑树，称E中所有边的权之和为支撑树中所有边的权之和为支撑树T的权，记为的权，记为w(T)，即，即 w(T)=wij (vi,vj)T如果支撑树如果支撑树T*的权的权w(T*)是是G的所有支撑树的权中最小的所有支撑树的权中最小者，则称者，则称T*是是G的最小支撑树的最小支撑树(简称最小树简称最小树)w(T*)=min w(T)T第六页，讲稿共三十四页哦3）求最小树的方法：）求最小树的方法：方法一方法一(避圈法避圈法)开始选

7、一条最小权的边，以后每一步中，总从未开始选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成被选取的边中选一条权最小的边，并使之与已选取的边不构成圈。圈。方法二方法二(破圈法破圈法)任取一个圈，从圈中去掉一条权最大的边。在余任取一个圈，从圈中去掉一条权最大的边。在余下的图中，重复这个步骤，一直到一个不含圈的图为止，这时的下的图中，重复这个步骤，一直到一个不含圈的图为止，这时的图便是最小树。图便是最小树。例例 用破圈法求下图的最小树用破圈法求下图的最小树12222312222333445第七页，讲稿共三十四页哦 四、一笔划问题四、一笔划问题1、次：图中的点

8、、次：图中的点V，以，以V为端点的边的个数，称为为端点的边的个数，称为V的次，记的次，记为为d(V)。2、定理、定理1：图：图G=(V,E)中，所有点的次之和是边数的两倍，中，所有点的次之和是边数的两倍，即设即设q边数，则边数，则d(vi)=2q，其中，其中vi V3、奇点：次为奇数的点。否则称为偶点。奇点：次为奇数的点。否则称为偶点。4、任一图中，奇点的个数为偶数。、任一图中，奇点的个数为偶数。5、一笔划：、一笔划：可以一笔划：没有或仅有两个奇次点的图形可以一笔划：没有或仅有两个奇次点的图形 如没有奇次点：任取一点，它既是起点又是终点。如没有奇次点：任取一点，它既是起点又是终点。两个奇次点：

9、分别选为起点和终点。两个奇次点：分别选为起点和终点。第八页，讲稿共三十四页哦五、有向图五、有向图1、无向图：、无向图：G（V，E）点集）点集+边集边集2、弧：点与点之间有方向的边，叫做弧。、弧：点与点之间有方向的边，叫做弧。弧集：弧集：A=a1,a1,am3、有向图：由点及弧所构成的图，记为、有向图：由点及弧所构成的图，记为D=(V,A)，V,A分分别是别是D的点集合和弧集合。的点集合和弧集合。4、环：某一条孤起点、环：某一条孤起点=终点，称为环。终点，称为环。5、基础图：给定一个有向图、基础图：给定一个有向图D=(V,A)，从，从D中去掉所有弧上中去掉所有弧上的箭头，所得到的无向图。记之为的

10、箭头，所得到的无向图。记之为G(D)。第九页，讲稿共三十四页哦 6、链：设、链：设(vi1,ai1,vi2,ai2,vik-1,aik-1,vik)是是D中的中的一个点弧交错序列，如果这个序列在基础图一个点弧交错序列，如果这个序列在基础图G(D)中所对中所对应的点边序列是一条链，则称这个点弧交错序列是应的点边序列是一条链，则称这个点弧交错序列是D的一的一条条链链。7、路：如果、路：如果(vi1,ai1,vi2,ai2,vik-1,aik-1,vik)是是D中中的一条链，并且对的一条链，并且对t=1,2,k-1，均有，均有ait=(vit,vit+1)，称之为从称之为从vi1到到vik的一条的一

11、条路路。8、回路：若路的第一个点和最后一点相同，则称之、回路：若路的第一个点和最后一点相同，则称之为回路。为回路。第十页，讲稿共三十四页哦六、图的矩阵表示六、图的矩阵表示1、网络（赋权图）、网络（赋权图）G=（V，E），其边（），其边（vi,vj）有权）有权wij,构造矩阵构造矩阵A=（aij）nn,其中：其中：wij（vi,vj）E 0 其他其他称矩阵称矩阵A为网络为网络G的权矩阵。的权矩阵。2、对于图、对于图G=（V，E），），V =n,构造一个矩阵构造一个矩阵A=（aij）nn,其其中：中：wij（vi,vj）E 0 其他其他称矩阵称矩阵A为网络为网络G的权。的权。第十一页，讲稿共三十四

12、页哦第二节 最短路问题一、引例：一、引例：如下图中如下图中V1：油田，：油田，V9：原油加工厂：原油加工厂求使从求使从V1到到V9总铺路设管道最短方案。总铺路设管道最短方案。V1V4V2V3V6V9V8V7V542466234442第十二页，讲稿共三十四页哦二、最短路算法二、最短路算法1、情况一：、情况一：wij0(E.W.Eijkstra算法算法)原理：原理：Bellman最优性定理最优性定理方法：图上作业法（标号法）方法：图上作业法（标号法）标号：对于点标号：对于点,若已求出到若已求出到Vi的最短值，标号（的最短值，标号（i,i)i：表示到的最短路值：表示到的最短路值 i:表示最短路中最后

13、经过的点表示最短路中最后经过的点标号法步骤：标号法步骤：1）给）给V1标号标号(0,Vs)2）把所有顶点分成两部分）把所有顶点分成两部分,X：已标号的点；：已标号的点；X未标号的点未标号的点考虑与已标号点相邻的弧是存在这样的弧（考虑与已标号点相邻的弧是存在这样的弧（Vi，Vj）,Vi X,Vj X若不存在，此问题无解，否则转若不存在，此问题无解，否则转3）3）选取未标号中所有入线的起点与未标号的点）选取未标号中所有入线的起点与未标号的点Vj进行计算进行计算:mini+wij=j并对其进行标号并对其进行标号(j,Vi)，重复，重复2）第十三页，讲稿共三十四页哦2、情况二：、情况二：wij0设从设

14、从V1到到Vj(j=1,2,t)的最短路长为的最短路长为P1jV1到到Vj无任何中间点无任何中间点 P1j（1）=wijV1到到Vj中间最多经过一个点中间最多经过一个点 P1j（2）=min P1j（1）+wijV1到到Vj中间最多经过两个点中间最多经过两个点 P1j（3）=min P1j（2）+wij.V1到到Vj中间最多经过中间最多经过t-2个点个点 P1j（t-1）=min P1j（t-2）+wij终止原则：终止原则：1）当）当P1j（k）=P1j（k+1）可停止，最短路可停止，最短路P1j*=P1j（k）2）当）当P1j（t-1）=P1j（t-2）时，再多迭代一次时，再多迭代一次P1j

15、（t），若，若P1j（t）=P1j（t-1），则原问题无解，存在负回路。，则原问题无解，存在负回路。第十四页，讲稿共三十四页哦 例：例：求下图所示有向图中从求下图所示有向图中从v1到各点的最短到各点的最短路。路。v1v4v2v3v5v6v7v825-34674-23-1-342第十五页，讲稿共三十四页哦 wij d(t)(v1,vj)v1 v2 v3 v4 v5 v6 v7 v8v1v2 v3 v4v5v6v7v8025-30-2406400-3 0720320t=1 t=2 t=3 t=4 t=5 t=6025-3020-3611020-36615020-3361410020-3369100

16、20-336910说明：表中空格处为说明：表中空格处为+。第十六页，讲稿共三十四页哦例例 设备更新问题设备更新问题制订一设备更新问题，使得总费用最小制订一设备更新问题，使得总费用最小 第第1年年 第第2年年 第第3年年 第第4年年 第第5年年 购买费购买费 13 14 16 19 24 使用年数使用年数 0-1 1-2 2-3 3-4 4-5 维修费维修费 8 10 13 18 27 解解设以设以vi(i=1,2,3,4,5)表示表示“第第i年初购进一台年初购进一台新设备新设备”这种状态，以这种状态，以v6表示表示“第第5年末年末”这种状态；以弧这种状态；以弧(vi,vj)表示表示“第第i年初

17、购置的一台设备一直使用到第年初购置的一台设备一直使用到第j年年初初”这一方案，以这一方案，以wij表示这一方案所需购置费和维护费表示这一方案所需购置费和维护费之和。之和。第十七页，讲稿共三十四页哦这样，可建立本例的网络模型。于是，该问题就可归这样，可建立本例的网络模型。于是，该问题就可归结为从图中找出一条从结为从图中找出一条从v1到到v6的最短路问题。的最短路问题。用用Dijkstra标号法，求得最短路为标号法，求得最短路为 v1v3v6 即第一年初购置的设备使用到第三年初予以更新，然即第一年初购置的设备使用到第三年初予以更新，然后一直使用到第五年末。这样五年的总费用最少，为后一直使用到第五年

18、末。这样五年的总费用最少，为78。第十八页，讲稿共三十四页哦v1v2v3v5v6v4214432228962316345244734273732(0，Vs)(0，V1)(31,V1)(44,V1)(62,V1)(78,V3)第十九页，讲稿共三十四页哦第三节第三节 最大流问题最大流问题 如下是一运输网络，弧上的数字表示每条弧上如下是一运输网络，弧上的数字表示每条弧上的容量，问：该网络的最大流量是多少？的容量，问：该网络的最大流量是多少？vsv2v1v3v4vt432312234第二十页，讲稿共三十四页哦一、一、基本概念和基本定理基本概念和基本定理1、网络与流、网络与流定义定义1：给定一个有向图：

19、给定一个有向图D=(V,A),在在V中有一个发点中有一个发点vs和一和一收点收点vt，其余的点为中间点。对于每一条弧，其余的点为中间点。对于每一条弧(vi,vj),对对应有一个应有一个c(vi,vj)0,(cij)称为弧的容量。这样的有向图称称为弧的容量。这样的有向图称为网络。记为为网络。记为D=(V,A,C)。网络的流：定义在弧集合网络的流：定义在弧集合A上的一个函数上的一个函数f=f(vi,vj)，称，称f(vi,vj)为弧为弧(vi,vj)上的流量，简记上的流量，简记fij。第二十一页，讲稿共三十四页哦2、可行流与最大流、可行流与最大流定义定义2 满足下列条件的流称为满足下列条件的流称为

20、可行流可行流：1)0 fij cij2)平衡条件：平衡条件：中间点中间点 fij=fji(vi,vj)A(vj,vi)A发点发点vs fsj fjs=v(f)(vs,vj)A(vj,vs)A ftj fjt=v(f)(vt,vj)A收点收点vt，(vj,vt)A式中式中v(f)称为这个可行流的流量，即发点的净输出量（或收点称为这个可行流的流量，即发点的净输出量（或收点的净输入量）。的净输入量）。第二十二页，讲稿共三十四页哦最大流问题：求一流最大流问题：求一流fij满足满足0 fij cij v(f)i=s fij fji=0 i s，t v(f)i=t且使且使v(f)达到最大。达到最大。第二十

21、三页，讲稿共三十四页哦3、增广链、增广链 给定可行流给定可行流f=fij，使，使fij=cij的弧称为的弧称为饱和弧饱和弧，使，使fij0的的弧称为弧称为非零流弧非零流弧。若若 是网络中连接发点是网络中连接发点vs和收点和收点vt的一条链，定义的一条链，定义链的方向是从链的方向是从vs到到vt，则链上的弧被分成两类：，则链上的弧被分成两类：前向弧：弧的方向与链的方向一致前向弧：弧的方向与链的方向一致 全体全体+后向弧：弧的方向与链的方向相反后向弧：弧的方向与链的方向相反 全体全体 定义定义3 设设f是一可行流，是一可行流，是从是从vs到到vt的一条链，的一条链，若若 满满足下列条件，则称之为（

22、关于流足下列条件，则称之为（关于流f的）一条增广链：的）一条增广链：在弧在弧(vi,vj)+上，上，0 fijcij 在弧在弧(vi,vj)上，上，0fij cij第二十四页，讲稿共三十四页哦 4、截集与截量、截集与截量 定义定义4 给定网络给定网络D=(V,A,C)，若点集，若点集V被剖分被剖分为两个非空集合为两个非空集合V1和和V1，使，使vs V1，vt V1，则把弧集，则把弧集(V1,V1)称为是（分离称为是（分离vs和和vt的）截的）截集。集。截集是从截集是从vs到到vt的必经之路。的必经之路。定义定义5 给定一截集给定一截集(V1,V1)，把截集，把截集(V1,V1)中所中所有弧的

23、容量之和称为这个截集的容量有弧的容量之和称为这个截集的容量(截量截量),记为记为C(V1,V1)。v(f)C(V1,V1)第二十五页，讲稿共三十四页哦 若对于一可行流若对于一可行流f*，网络中有一截集，网络中有一截集(V1*,V1*)，使得使得v(f*)=C(V1*,V1*)，则，则f必是最大流，而必是最大流，而(V1*,V1*)，必定是容量最小的截集，即最小截集。，必定是容量最小的截集，即最小截集。定理定理1 可行流可行流f*是最大流的充要条件是不存在是最大流的充要条件是不存在关于关于f*的最大流。的最大流。若若f*是最大流，则网络中必存在一个截集是最大流，则网络中必存在一个截集(V1*,V

24、1*)，使得，使得 v(f*)=C(V1*,V1*)定理定理2 任一网络任一网络D中，中，从从vs到到vt的最大流的流量等的最大流的流量等于分离于分离vs，vt的最小截集的截量。的最小截集的截量。第二十六页，讲稿共三十四页哦步骤：步骤：2、标号过程标号过程1、选取一个可行流（可选择零流弧）、选取一个可行流（可选择零流弧）从从Vs出发，在前向弧上出发，在前向弧上(vi,vj)，若，若fij0，则给，则给vj标号标号(Vi,l(vj)，其，其中中l(vj)=minl(vi)，fji。二、寻找最大流的标号法二、寻找最大流的标号法(Ford Fulkerson)思想：从一可行流出发，检查关于此流是否存

25、思想：从一可行流出发，检查关于此流是否存在增广链。若存在增广链，则增大流在增广链。若存在增广链，则增大流量，使此链变为量，使此链变为非增广链；这时再检查是非还有增广链，若还有，继续非增广链；这时再检查是非还有增广链，若还有，继续调整，直至不存在增广链为止。调整，直至不存在增广链为止。第二十七页，讲稿共三十四页哦 3、若标号延续到、若标号延续到vt，表明得到一条从，表明得到一条从vs到到vt的增广链的增广链，转入调整阶段，转入调整阶段4，否则当前流即为最大流。，否则当前流即为最大流。4、调整过程、调整过程令调整量为令调整量为=l(vt)令令 fij+(vi,vj)+fij=fij (vi,vj)

26、fij (vi,vj)去掉所有的标号，对新的可行流去掉所有的标号，对新的可行流f=fij，重新进入标，重新进入标号过程。号过程。第二十八页，讲稿共三十四页哦可结合下图理解其实际涵义。可结合下图理解其实际涵义。vsv1v2v3v4vt(4,4)(8,1)(4,3)(2,2)(4,0)(2,2)(1,1)(7,2)(9,2)第二十九页，讲稿共三十四页哦vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)例例 求下列网络的最大流与最小截集。求下列网络的最大流与最小截集。解解一、标号过程一、标号过程 （2）检查）检查vs,在弧在弧(vs,v

27、1)上上,fs1=7,cs1=9,fs1cs1,则则v1的标号为的标号为(vs,l(v1)，其中，其中第三十页，讲稿共三十四页哦l(v1)=minl(vs)，cs1fs1=min+，9 2=2（3）检查）检查v1,在弧在弧(v1,v4)上上,f14=7,c14=9,f140，则则v3的标号为的标号为(-v4,l(v3)，其中，其中l(v3)=minl(v4)，f34=min2，1=1（5）检查）检查v3,在弧在弧(v3,vt)上上,f3t=3,c3t=6,f3tc3t,第三十一页，讲稿共三十四页哦则则vt的标号为的标号为(v3,l(vt)，其中，其中l(vt)=minl(v3)，c3tf3t=

28、min1，6-3=1这样，我们得到了一增广链这样，我们得到了一增广链,如图所示。如图所示。vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)(0,)(vs,2)(v1,2)(-v4,1)(v3,1)其中其中+=(vs,v1),(v1,v4),(v3,vt)，=(v3,v4)第三十二页，讲稿共三十四页哦二、调整过程二、调整过程取调整量为取调整量为=1，在，在 上调整上调整f。在在+上：上：fs1+=7+1=8 f14+=2+1=3 f4t+=5+1=6在在 上：上：f43=11=0其余弧上的流量不变，这样得到一个新的流，如下图所示。

29、其余弧上的流量不变，这样得到一个新的流，如下图所示。s1vtv4v23(9,8)(5,3)(3,2)(5,5)(3,2)(2,0)(6,4)(7,7)第三十三页，讲稿共三十四页哦 在上图中重复上述标号过程，依次给在上图中重复上述标号过程，依次给vs,v2,v1,v4标号后，标号后，由于标号无法继续下去，算法结束。这时的流为最大流，最由于标号无法继续下去，算法结束。这时的流为最大流，最大流的流量为大流的流量为vvv(4,4)v(f)=8+3=11 与此同时，可找到最小截集与此同时，可找到最小截集(V1,V1)，其中，其中V1为标号点集合，为标号点集合，V1为未标号点集合，弧集合为未标号点集合，弧集合(V1,V1)即为最小截集。即为最小截集。此例中，此例中，V1=vs,v2,v1,v4,V1=v3,vt,(V1,V1)=(v1,v3)，(v4,vt)第三十四页，讲稿共三十四页哦