《第六章图论Graph.ppt》由会员分享,可在线阅读,更多相关《第六章图论Graph.ppt(51页珍藏版)》请在三一文库上搜索。
1、第六章 图论(Graph),Graph: a diagram showing by a line or lines the connection between two quantities. Diagram: a plan or figure drawn to explain an idea drawing which shows the arrangement of something rather than what it actually looks like.,第一节 图论的起源 第二节 图的基本概念 第三节 路与圈 第四节 图的矩阵表示 第五节 带权图的最短路径 第六节 Euler
2、图 第七节 Hamilton图 第八节 二分图 第九节 平面图 第十节 树(无向树、有根树),第一节 图论的起源,图论最早处理的问题是哥尼斯堡(konigsberg)城pregel河上的七桥问题。1736年,瑞士数学家 L.Eluer 在他发表的“哥尼斯堡七座桥”的著名文章中阐述了解决这个问题的观点,从而被誉为图论之父。 问题是这样的:在公元十八世纪的东普鲁士有个哥尼斯堡城(后属于苏联立陶宛苏维埃社会主义共和国,现名为加里宁格勒;现属于立陶宛共和国)。哥尼斯堡城位于pregel河畔,河中有两个岛,城市中的各个部分由七座桥相连。当时,城中的居民热衷于这样一个问题,从四块陆地的任一块出发,怎样才能
3、做到经过每座桥一次且仅一次,然后回到出发点。问题看来并不复杂,但当地的居民和游人做了不少的尝试,却都没有取得成功。,A,B,C,D,图 1,图实际上是反映了客观事物 之间的相互关系,图 2,后来,在1736年,瑞士的数学家L.Euler解决了这个问题。他将四块陆地表示成四个结点,凡陆地间有桥相连的,便在两点间连一条线,这样图1就转化为图2了。此时,哥尼斯堡七桥问题归结为:在图2 所示的图中,从 A, B, C, D 任一点出发,通过每条边一次且仅一次而返回出发点的回路是否存在? 欧拉断言这样的回路是不存在的。理由是:从图2中的任一点出发,为了要回到原来的出发点,要求与每个点相关联的边数均为偶数
4、。这样才能保证从一条边进入某点后,再从另一条边出去,从一个点的不同的两条边一进一出才能回到出发点,而图2中的A, B, C, D全是与奇数条边相连,由此可知所要求的回路是不可能存在的。 Leonhard Euler (1707-1783) 瑞士数学家,2 图的定义及基本概念,2.1 无序积和有序积 2.2 图的定义 2.3 图中的基本术语 2.4 图中节点的度数 2.5 子图与补图 2.6 图的同构,2.1 无序积和有序积 定义1 设A,B是两个集合,称集合a,b| aAbB为A,B的无序积,记为A&B。无序积A&B的子集称为A和B上的二元关系。 当BA时,称无序积A&B的子集为A上的二元关系
5、。 例:在哥尼斯堡七桥问题中,可用上的无序积的子集来表示。 设X=A,B,C,D表示四块陆地,x和y有关系当且仅当x和y有桥相连。于是有A,B,B,C,A,C,A,C,A,D,A,D,B,D. 集合中的每个元素表示一座桥。 定义2 设A,B是两个集合,称集合(a,b) | aAbB为A,B的有序积,记为AB,有序积A B的子集称为A到B的二元关系。 当BA时,称有序积AB的子集为A上的二元关系。 例:在家族关系图中,均用上的有序积的子集来表示“半序关系”。,2.2 图的定义 定义3 设 G = (V, E) ,其中 1)V是一个非空的有限集合; 2) EV&V,且V&V中的元素可在 E 中出现
6、多次; 则称G是无向图(Undirected graph)。 V中的元素称为结点vertex,node 。 E中的元素称为无向边edge 。 例1 Euler图是无向图。 定义4 设G = (V,E),其中 1) V是一个非空的有限集合。 2) EVV,且VV中的元素可在 E 中出现多次。 则称G是有向图(directed graph)。 V中的元素称为结点 vertex, node 。 E中的元素称为有向边 arrow 。 例2 半序关系中的Hasse图是有向图。,图的几种特殊情况: 若在图G中,|V| = n,|E| = m,则称G为 ( n, m ) 图。 若在图G中, V = ,则称G
7、为空图。Empty graph 若在图G中,|V| = 1,则称G为平凡图。Trivial graph 若在图G中, E = ,则称G为零图。 Null graph 若在图G中,既有有向边又有无向边,则称G为混合图。 Mixed graph,2.3 图中的基本术语 1. 设 G = (V, E) 是无向图。 1) 任取 eE,若 e = vi , vj,则称 vi , vj 是 e 的端点。并称 e 与 vi , vj 关联。 2) 任取vi , vj V,若 vi , vjE,则称 vi , vj 相邻。 3) 任取 ei,ej E,若 ei,ej 有公共的端点,则称 ei,ej 邻接。 4
8、) 以同一结点为两个端点的边称为自环。 5) 若 ei,ej 有相同的两端点,则称 ei,ej 是平行边。 6) 若 G 中有平行边,则称 G 为多重无向图。 7) 若 G 中无平行边,无自环,则称 G 为简单无向图。,2. 设 G = (V, E) 是有向图。 1) 任取 eE,若 e = (vi , vj),则称 vi 是 e 的起点, vj 是 e 的终点。并称 e 与 vi , vj 关联。 2) 任取 vi , vj V,若 (vi , vj)E,则称 vi , vj 单向相邻。 3) 任取ei,ejE,若ei的终点与ej的起点相同,则称 ei,ej邻接。 4) 以同一节点为起点和终
9、点的边称为自环。 5) 若 ei,ej 有相同起点和终点,则称 ei,ej 是平行边。 6) 若 G 中有平行边,则称 G 为多重有向图。 7) 若 G 中无平行边,无自环,则称 G 为简单有向图。,2.4 图中节点的度数 定义5 设G = (V,E) 是无向图。任取 vV,称与v相关联的边的条数为v的度。记为deg(v)。 1) 当 v 的度为偶数时,称 v 为偶结点。 2) 当 v 的度为奇数时,称 v 为奇结点。 3) 当 v 的度为零时,称 v 为孤立点。 4) 当 v 的度为1时,称 v 为悬挂点。与悬挂点关联的边为悬挂边。,例 在图2中,deg(v1)=2, deg(v2)=5,
10、deg(v3)=0, deg(v4)=1 故 v1 是偶结点, v2 是奇结点, v3 是孤立点, v4 是悬挂点, v2, v4 是悬挂边。,图2,定理1 设 G = (V, E) 是 (n,m) 无向图,则 。 定理2 设 G = (V, E) 是无向图,则 G 中奇结点的个数为偶数。 例 在一次集会上,同奇数个人握手的人的个数为偶数。 原因是:如果用结点表示人,用边表示相互握手的两个人,便可得到一个图。这个图表达了参加集会的人之间彼此握手的情况。于是直接运用定理2即可知结论成立。,V = 2, 3, 4, 5, 6, 7, 8, 9 ,deg(2) = 4 deg(6) = 2 deg(
11、3) = 5 deg(7) = 7 deg(4) = 4 deg(8) = 4 deg(5) = 7 deg(9) = 5,故和奇数个数互素的数的个数为偶数,4个3,5,7,9,例 在一个有限个自然数的集合中,与奇数个数互素的数的个数是偶数。 解:取每个数为结点,两个结点有边当且仅当两个数互素。由定理2知上述结论成立。,定义6 设 G = (V, E) 是有向图,任取vV。 1) G中以v为起点的边数称为v的出度,记为 。 2) G中以v为终点的边数称为v的入度,记为 。 3) 结点v的出度与入度之和称为v的度,记为 deg(v)。 定理3 设G = (V, E)是有向图,则 。 其中 V=
12、n,E= m。 证:由于每条有向边都对应一个入度和一个出度,如一个结点具有一个出度(或入度),则它必关联一条有向边,并通过此有向边与另一结点相邻,且为此结点提供一入度(或出度)。所以在有向图中,入度之和等于出度之和,并等于边数。即有,2.5 子图与补图 定义7 设G = (V,E)是简单无向图。若E = (V&V)v,v|vV ,则称G为无向完全图。,(a) 是三个结点的完全无向图。 (b) 是四个结点的完全无向图。 (c) 是五个结点的完全无向图。 在n个结点的完全无向图中,每个结点的度数为(n1),且 边数为n(n1)/2。 定义8 设 G = (V, E)是简单有向图。若E=(VV)(v
13、,v)|vV,则称 G 为有向完全图。 在 n 个结点的有向完全图中,每个结点的度数为 2(n1),且边数为 n(n1) 。,(a),定义9 设G = (V, E) 和设G = (V, E)是两个图。(无向,有向) 1) 若 V V 且 E E,则称 G 为 G 的子图。 2) 若 V V 或 E E,则称 G 为 G 的真子图。 3) 若 V = V 且 E E,则称 G 为 G 的生成子图。 当(V = V 且 E = E) 或( V = V 且 E =)时,称这两个子图为平凡子图。 定义10 设 G = (V, E) 为简单图, G* = (V, E*) 为完全图。 称 为完全图的补图。
14、其中 。,例,上图中的四个图示,表面形状虽然不同,但这四个图示反映的结点的个数,边的条数,及结点与边之间的联系是相同的。若将(b)中的边v1, v3拉长,即可发现(b)与(a)是一个图。(c)只是将(a)中的结点换了个名字。而(d)也只是将(a)中的结点换了名字,且改变了边1, 3的位置。所以上图中的四个图示所反映的问题的实质是一样的。,2.6 图的同构 观察如下四个图示:,定义11 设G = (V, E), G = (V, E)是两个简单无向图,若存在从V到V的双射函数g,使得 e=vi , vj E当且仅当 e = g(vi),g(vj)E,则称图G与G同构。,作函数 g:VV g(v1)
15、 = v1, g(v2) = v3, g(v3) = v5 g(v4) = v2, g(v5) = v6, g(v6) = v4 , 由双射函数的定义知 g 是双射函数。 v1, v4,v1, v5,v1, v6,v2, v4,v2, v5,v2, v6, v3, v4,v3, v5,v3, v6 v1, v2,v1, v6,v1, v4,v3, v2,v3, v6,v3, v4, v5, v2,v5, v6,v5, v4 由定义11知这两个图同构 。,定义12 设G = (V, E), G = (V, E)是两个简单有向图,若 存在从V到V的双射函数g,使得 e = (vi , vj)E 当
16、且仅当 e = (g(vi),g(vj)E,则称图 G 与 G 同构。,作函数g:VV。 g(v1)= v3, g(v2) = v4, g(v3)= v1, g(v4)= v2 (v2, v1), (v4, v1), (v3, v2), (v3, v4) (v4, v3), (v2, v3), (v1, v4), (v1, v2) 由定义12知这两个图同构。,由上面的讨论不难看出,若两个图同构,它们必须满足: 结点个数相等; 边数相等; 度数相同的结点个数相等。 然而,上面的三个条件只是两个图同构的必要条件,不是 充分条件。,上图中(a),(b)两图示满足上述三个条件,但由于(a)中度数为3的
17、结点v1与两个度数为1的结点v2, v3相邻,而在(b)中,度数为3的结点u1只与一个度数为1的结点u2相邻,故(a),(b) 不同构。,容易看出,同构关系是一个等价关系,对于图,我们感兴趣的问题是边与点的连接关系,所以在画图示时有时省去标号。有了同构的概念后,可以把一个无标号的图看作是同构图的等价类代表。,3 路与圈 3.1 基本概念 定义1 设 G = (V, E) 为图,G 的有限非空点边交错序列 w = v0 e1 v1 e2 v2 . ek vk 称w为 G 中的一条从v0到vk的途径。 1) 称 v0 为途径的起点,称 vk 为途径的终点; 2) 称 k 为途径的长度; 3) 若
18、v0 vk 称 w 是从 v0 到 vk 的一条路; 4) 若 v0= vk,称 w 是圈。 在实际应用中,常将途径表示为边列或点列,如 w = (e1,e2,. , ek) = (v0 , v1 ),(v1 , v2 ), . , (vk-1, vk) w = (v0,v1,v2,. , vk),定义2 设G = (V, E)为图,P是G中从u到v的一条路。 1)若P中无重复边,则称P为简单路; 2)若P中无重复点,则称P为初级路。 定义3 设G = (V, E)为图,C是G中的一个圈。 1)若C中无重复边,则称C为简单圈; 2)若C中无重复点,则称C为初级圈。 从上述定义可知,一条初级路(
19、圈)必定是简单路(圈),反之不然。 对于给定的一条从u到v的路P,必可找到一条从u到v的初级路P。方法是删去P中所有的圈。同理,对于给定的圈C,只要删去其中所有的子圈,即可得到一个初级圈。,例1 在图中, 从结点v1到结点v3的路有 p1:(1,2,3) p2:(1,4,3) p3:(1,2,4,3) p4:(1,2,4,1,2,3) p5:(1,2,4,1,4,3) p6:(1,1,2,3) . . P1, P2, P3是初级路, P5 , P6是简单路, P4既非初级路又非简单路。,从v1到 v1的圈有: C1: (1,1), C2: (1,2,1), C3: (1,2,3,1), C4:
20、 (1,4,3,1), C5: (1,2,3,2,1), C6: (1,2,3,2,3,1) . . C1, C2, C3, C4是初级圈, C5是简单圈, C6既非初级圈又非简单圈。,例2 路的概念可用来描述很多东西,如 1) 在PASCAL语言中,一个复合语句以BEGIN开始,以END结束,其中若干语句用逗号分开。所以,执行一个PASCAL语言中的复合语句,可以认为是从BEGIN开始到END结束的一条路。 2) PASCAL语言中的标识符可认为是从入口到出口的一条路。 3) 一个二进制数可以认为是从入口到出口的一条路。 定理1 设G = (V, E)为简单图, |V| = n,则 1) G
21、中任一初级路的长度不超过n1; 2) G中任一初级圈的长度不超过n。,3.2 可达性 定义4 设G = ( V, E )为图,u, vV,若在G中存在从u到v的路,则称u可达v。 在无向图中,可达的概念是对称的,即若u可达v,则v可达u,即u,v相互可达。在有向图中,u可达v不一定能保证v可达u,所以对u,v相互可达要作如下解释: u,v相互可达 u可达v 且 v可达u。 一般来讲,当从u 可达v时,它们之间不一定只有一条路,可能会有几条路,我们称从u到v所有路中长度最短的那条路线为短程线,并将短程线的长度称为从u到v的距离,用d(u,v)表示,并规定 1) d(u,u)=0; 2) 若u不可
22、达v,则 d(u,v) = 。,短程线不一定是唯一的,如图4所示,从v1到 v3的短程线有三条, d(v1, v3) = 2;而由v3到v1的短程线只有一条d(v3, v1) = 1。,按通常的理解,距离应具有下列性质: 1) d(u,v) 0; 2) d(u,v) = d(v,u); 3) d(u,v) + d(v,w) d(u,w) 。,对无向图,上述性质依然成立,然而对有向图来说,第二条性质不成立。,3.3 图的连通性 定义5 设G = (V, E)是无向图,若G中任一两结点间均可达,则称G是连通的。 由于无向图中的可达性是自反的,对称的,传递的,故可达性建立了图中结点集合上的一种等价关
23、系,从而确定了结点集合上的一个划分,每个划分都是给定图的一个连通子图,而且在每一个划分中结点间的可达性已达到极大限度。下面我们给这样的极大连通子图一个专有名字。 定义6 设G = (V, E)是无向图,G的一个极大连通子图称为G的一个连通支(连通分支)。 由连通支的概念可知,图G中每个结点及每条边,必处于且也只处于某个连通支中,图G是连通的当且仅当G的连通支数为1。,对有向图,由于其可达性不具有对称的性质,所以有向图连通性的概念相对于无向图要复杂些。 定义7 设G = (V, E)是有向图 1) 若G中任意两结点相互可达,则称G是强连通的。 2) 若G中任意两结点间至少有一结点可达另一结点,则
24、称G是单向连通的。 3) 若略去边的方向后,G的无向图是连通的,则称G是弱连通的。,例1 在图中,(a)是强连通的,(b)是单向连通的,(c)是弱连通的。 由上述定义知,若图G是强连通的,则必为单向连通,若图G是单向连通的,则必为弱连通。反之不然。,定义8 设G = (V, E)是简单有向图 1) 称G的极大强连通子图为G的强连通支(强分图) 2) 称G的极大单向连通子图为G的单向连通支(单向分图) 3) 称G的极大弱连通子图为G的弱连通支(弱分图),例2,在图中,有三个强连通支,它们是 G1=(v1 ,v2 , v3 ,(v1,v3),(v3,v2),(v2,v1) G2= (v4 , v5
25、 ,(v4,v5),(v5,v4) G3= (v6 , ) 在图中,有两个单向连通支,它们是 G4 =(v1 ,v2 , v3 , v4 , v5, (v1,v3),(v3,v2),(v2,v1),(v3,v4),(v4,v5),(v5,v4) G5 = (v4 , v5 , v6 ,(v4,v5),(v5,v4),(v6,v5) 在图中,有一个弱连通支,它们是 G6 =(v1 ,v2 , v3 , v4 , v5 , v6, (v1,v3),(v3,v2),(v2,v1),(v3,v4),(v4,v5),(v5,v4),(v6,v5),定理2 设G = (V, E)是简单有向图 1) 每个结
26、点恰在一个强连通支中 2) 每个结点,每条边至少属于一个单向连通支 3) 每个结点及每条边恰在一个弱连通支中,例3 在多道程序的计算机系统中,在同一时间内,n个程序并行运行。在各个程序的执行过程中需要动态的申请一些资源(如cpu,内存,外存,输入,输出设备等)。有时就可能出现冲突,如程序A占有资源R1需要申请资源R2,而程序B占有资源R2,需要申请资源R1,这时两个程序都无法进行工作。这种情况被称为死锁状态。可以用有向图模拟资源分配及产生死锁的特征,从而解决死锁的测定于纠正。 资源分配图G是一个有向图,它表达了时刻t系统中申请资源的分配状态。在图G中,结点表示系统的资源,当程序pk占有资源Ri
27、而要申请资源Rj时,则从结点Ri到结点Rj用一条有向边相连,从而构成G的边集E。现设 R= R1 ,R2 ,R3 ,R4为时刻t的资源集合 P = P1 ,P2 ,P3 ,P4为时刻t的运行的程序集合,资源的分配状况如下: P1占有资源R4要申请资源R1 P2占有资源R1要申请资源R2及R3 P3占有资源R2要申请资源R3 P4占有资源R3要申请资源R1及R4 它们的资源分配图如图8所示 由于:时刻t系统产生死锁G中含有强连通支,而在上面例子中,图8表示的有向图是强连通的,故必产生死锁现象。,R2,R1,R4,R3,P1,P2,P3,P4,图8,例4 在程序设计中,程序设计人员需要弄清一个过程
28、是否递归,但在多个过程中,其递归特性很不明显。可以用有向图来刻画过程间的调用关系,并用有向图的特性来表示某过程的递归调用。 我们用结点表示过程。如果过程Pi调用过程Pj ,则用一条从Pi到Pj的有向边表示,这样便可用有向图描述过程间的调用关系。 设过程集合为P=p1 , p2 , p3 , p4 , p5。它们的调用关系如下: p1调用p2, p2调用p4 p3调用p1,p4调用p5, p5调用p2,则反映过程间调用关系的有向图如图9所示,可以看出过程递归调用G中含有强连通支 由图9可知,(p2,p4,p5(p2 , p4) ,(p4 , p5) ,(p5 , p2)是强连通支,所以p2,p4
29、,p5是递归的。,p1,p2,p5,p4,p3,图9,4 图的矩阵表示 怎样将一个图存储起来,方便在计算机中处理,这是人们十分关注的一个问题。比较简单的方法是将图用一个矩阵表示出来,而矩阵在计算机中用一个二维数组就可以表示清楚,这样图的存储问题也就解决了。这里我们主要介绍简单有向图的矩阵表示。 4.1 邻接矩阵 定义1 设G = (V, E)是简单有向图,V = v1 ,v2 , . ,vn,则称n阶方阵A = (aij)nn为G的邻接矩阵。其中 ,aij =,(vi ,vj)E,(vi ,vj)E,1,0,例1 G = (V, E)如图所示, V = v1 ,v2 , v3 ,v4,则G的邻
30、接矩阵如下:,v1,v2,v4,v3, ,由邻接矩阵定义不难看出它主对角线上的元素必然全为零。 一个图的邻接矩阵完整的刻画了图中结点间的邻接关系。也就是说:对于一个给定的简单有向图,我们能用一个主对角线全为零的方阵将结点间的邻接关系反映出来。反之,对于一个主对角线全为零,元素为0或1的方阵,我们可以将其表示成一个图。,A=,V1 V2 V3 V4,v2 v3 v4 0 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0,v1,一个图若是零图,则其邻接矩阵的元素全为零; 一个图若是完全图,则其邻接矩阵除对角线上的元素外,其余元素均为1; 一个图若是对称的,则其邻接矩阵按主对角线对称,即A
31、=AT; 对图中个结点的入度和出度,也可以通过邻接矩阵求得: , , 通过对邻接矩阵A进行运算,可以得到G中两点间是否有路及路的长短等信息。,A =A, A =( aij(1) ) nn, aij(1) =1表示存在一条边(vi, vj),即从vi到vj存在一条长度为1的路。 A2=A1 A1, A2= ( aij(2) ) nn , aij(2) = aik(1) akj(1) aij(2)=1 表示存在k0 , 使aik0 = ak0j =1。且当k k0 , aik akj =0。 由aik0 = 1和ak0j =1知存在边(vi, vk0)和(vk0,vj),即存在一条从vi 到vj的
32、长度为2的路。 aij(2)=2 表示存在k0 , k1,使aik0 = ak0j =1, aik1 = ak1j =1。 且当k k0 , k k1时 aik akj =0。即存在两条从vi到vj的长度为 2的路。一条是(vi, vk0), (vk0,vj),一条是(vi, vk1), (vk1,vj)。 由此得知aij(2)表示从vi到 vj长度为2的不同路的条数。而aij(2) 表示经过vi的长度为2的圈数。特别, aij(2)=0,表示从vi到vj没 有长度为2的路。 一般地, Al +1 = ( aij(l+1) ) nn , aij(l+1) = aik (l) akj (1) 。
33、 aij(l+1)表示从vi到vj的长度为l+1的路的总数。,定理1 设G为简单有向图,A是它的邻接矩阵,则Am中的元素aij(m)是从vi到vj长度为m的路的条数。 可用归纳法对其进行证明。 对例1中所举的例子有如下结果:,A1 =,A2 =,A3 =,A4 =, , , , ,0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 0,0 0 1 1 2 1 0 1 1 1 1 1 0 1 0 0,2 1 0 1 1 2 1 1 2 2 1 2 0 0 1 1,1 2 1 1 2 2 2 3 3 3 2 3 2 1 0 1,观察上面四个矩阵中的元素a24(1) , a24(2) , a
34、24(3) , a24(4) : a24(1) =1表示从v2到v4的长度为1的路只有一条; a24(2) =1表示从v2到v4的长度为2的路只有一条 (v2 , v3 , v4) a24(3) =1表示从v2到v4的长度为3的路只有一条(v2 , v3 , v2 , v4) a24(4) =3表示从v2到v4的长度为4的路共有三条,它们是 (v2 , v3 , v2 , v3 , v4), (v2 , v3 , v1 , v2 , v4), (v2 , v4 , v1 , v2 , v4)。 由前面的定理可知,在一个(n,m)图中,任意初级路的 长度n,而且若从vi到vj有路,则从vi到vj
35、必有一条初级路; 若从vi到vj有圈,则必有一条初级圈。为此,我们观察矩阵 B= A1 + A2 + A3 + .+ An。 此时B中包括了G的所有初级路及初级圈。,矩阵B的元素bij给出了从vi到vj的所有长度从1到n的路的总条数。 在前面的例中有 B= A1 + A2 + A3 + A4 = 其中 b24 =6,表示从结点v2到v4共有六条长度小于n的路可达。 在B中任一两结点间是否可达,清清楚楚,一目了然。通常我们所关心的是从vi到vj是否有路可达,而对于路的长度,及有多少条数并不关心。故从可达性的意义上来说,B矩阵的信息量有冗余,且计算太复杂。下面我们介绍一种简单的方法来解决图中各点间
36、的可达性问题。, ,3 4 2 3 5 5 4 6 7 7 4 7 3 2 1 2,4.2 可达矩阵 定义2 设G=(V,E)是简单有向图, V= v1 ,v2 , . ,vn,称n阶 方阵R = (rij) nn为图G的可达矩阵,其中 ,rij =,1,0,vi到vj有路可达,vi到vj无路可达,由于可达矩阵是一个布尔矩阵,而邻接矩阵也是一个布尔矩阵,因此有可能通过布尔运算从G的邻接矩阵求得G的可达矩阵。根据前面求A的方法的提示,我们将前面矩阵运算中加法和乘法换成布尔加与布尔乘,此时, Al+1 = ( aij(l+1) ) nn , aij(l+1) =( aik(l)akj(1) ) 于
37、是 R = A(1) A(2) . A(n) 。,例2 图G = (V,E)如图所示,1 2 1 1 2 2 2 3 3 3 2 3 2 1 0 1,v1,v4,v3,v2,Warshall算法: No1. R:=A No2. k:=1 No3. i:=1 No4. j:=1 No5. rij := rij( rikrkj ) No6. j:=j+1; if jn then goto No5 No7. i:=i+1; if in then goto No4 No8. k:=k+1;if kn then goto No3 No9. End.,Warshall算法的基本思想如下: 1) 首先故定一
38、个结点vk,讨论所有的结点对是否可以通过vk而相互到达; 2) 在讨论中,再固定结点vi,讨论vi是否可通过结点vk到达所有的结点vj j=1,2n; 3) 在讨论中,不会出现要求保留多个矩阵的情形,因为对于中间关键步骤 rij = rij( rikrkj )来说,赋值号右端的rij是上一轮的结果,因此一旦rij = 1,则rij就永远为1了,即vi到vj有路可达。利用计算机保留当前值的特点,在输入时,邻接矩阵为布尔矩阵,每一步的操作只改变这个矩阵中某个元素的值,最后输出时,仍是一个布尔矩阵,这就大大减少了机器的存储量。 4) 这里得到的只是可达性矩阵,即只知各个结点之间是否有路可达,既不知路
39、长为多少,也不知该路经过哪些结点。因为当最终rij = 1时,不知这个1是在第几轮中变为1的,而且这个1将保持到最后。,5) 在讨论的过程中不必担心有路遗漏。 例如(v6 , v4 , v3 , v1 , v2 , v5 )是图中的一条路,那么开始时有 r64= r43= r31= r12= r25=1;在讨论v1结点时有r64= r43= r32= r25=1;当讨 论v2结点时有r64= r43= r35=1;在讨论v3结点时有r64= r45=1;在讨论 v4结点时有r65=1,即v6到v5有路可达。对一般的情况也有相同的 结果(vi1 , vi2 , ., vi1 )是一条路,那么将i1 , i2, ., ik 按大小次序排 队,每讨论一个结点就连通若干结点,到最后就有ri1ik=1。即 vi1到 vik有路可达。 相对于前面的两种方法,用Warshall算法求图G的可达矩阵不仅节省时间而且节约内存。,4.3 可达矩阵与图的连通性 对于有向图的连通性,可以用可达矩阵来判断 G 是强连通的 R 的元素全为1; G 是单向连通的 RRT 除对角线外元素全为1; G 是弱连通的 由 AAT 确定的 R 的元素全为1; G 中有圈 R 的某些主对角线的元素为1。 例4 讨论下图中G1,G2,G3,G4的连通性。,
链接地址:https://www.31doc.com/p-2583906.html