第九的基本概念及其矩阵表示

1、离散数学大连理工大学软件学院陈志奎第9章图的基本概念及其矩阵表示论2/128图论（GraphTheory）是数学的一个分支。它以图为研究对象。图论中的图是由若干定的点连接两点的线所构成的图形，这特形通用来描述某些事物之间的某种关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论起源斯堡的岛与河名的柯尼斯堡七桥问题。格尔河上有七座桥将河中结起来，如下图所示，A、在的B、C，表示陆地。3/128图论的起源 哥尼斯堡七桥问题：17世纪的东普鲁士有一座哥尼斯堡（Konigsberg）城，城中有一条普雷格尔（Pregel）河，全城共有七座桥将河中的岛及岛与河岸联结起来，如下图所示，a,

2、b,c,d表示陆。从四块陆地的任何一块出发，怎样通过且仅通过每座桥一次，最终回到出发地点？4/128图论的起源1736年瑞士大数学家列昂哈德欧拉（Leonhard Euler）解决了这一问题，他用了科学研究中最一般的方法抽象。字母a,b,c,d表示四块陆地，并用7用条7座桥，从而将七桥问题抽象为，寻找经过图中每边一次且仅一图的次的回路，后来人们把为欧拉图。这样回路的图称cadb5/128图论的起源欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的图可以某种方式的判定法。这项工作使欧拉成为图论始人。欧拉被称为图论之父，1736年也被称为“图论元年”。图论部分共分为三章：图的基本概

3、念及其矩阵表示，几种图的介绍，树。本章将首论图论中的一些基本概念，继之阐述图基本性质，而后介绍图的矩阵表示方法。6/128主要内容 图的基本概念 子图和图的运算基础知识 路径 图的 欧拉图路、连通性表示 哈密尔顿图 二部图、平面图 网络 树特殊图7/1289.1图的基本概念 图是由一些顶点和连接这些顶点的一些边所组成的离散结构。 根据连接顶点对的边的种类和数目的不同，图有多种类型。几乎每一门可以想到的学科，都有用图模型来解决的问题。8/128图的种类(1) 如果y : E ® v1, v2 v1 ÎV Ù v2ÎV，则称G = áV , E,y

4、 ñ为无向图。(2) 如果y : E ® V ´V，则称 G = áV , E,y ñ为有向图。图还是有向图，都统称为图，其中V无论是素称为图G的结点，E的元素称为图G的边，图G 点数目称为图的阶。可以用几何图形表示上面定义的图。用小圆圈的的向图中，若y (e) = v1 , v2 ，就用连接表示结点。结点v1和v2的无向线段表示边e。在有向图中，若y (e) = áv1 , v2 ñ，就用v1指向v2的有向线段表示边e。9/128图的基本概念定义： 设无向图G = áV , E,y ñ，e, e1 ,

5、e2Î E ，v1, v2ÎV(1)如果y (e) = v1 , v2，则称e与v1(或v2)互相关联。e连接v1和v2，v1和v2既是e的起点，也是e的终点，也称v1和v2为点邻接。(2)如果两条不同的边e1和e2与同一个结点关联，则称e1和e2为边邻接。也就是说，共边的点称为点邻接；共点的边称为边邻接。10/128图的基本概念定义：设有向图G = áV , E,y ñ, e Î E, v1, v2 ÎV。如果y (e) = áv1 , v2 ñ ，则称e连接v1和v2，e与v1(或v2)互相关联，分别称v1和v

6、2是e的起点和终点，也称v1和v2邻接。例：无向图e1连接v1和v2，v1和v2邻接，e1和e2邻接。11/128图的基本概念例：有向图v2和v1分别是e1的起点和终点，v2与v1邻接。12/128图的基本概念定义： 设图G = áV , E,y ñ ,e1和e2是G的两条不同的边。(1) 如果与e1关联的两个结点相同，则称e1为自圈(或称环和回路)。(2) 如果y (e1 ) =y (e2 ) ，则称e1与e2平行。(3)如果图G没有自单图。也没有平行边，则称G为简4)如边图图G没有自回路，有平行边，则称G为多重(5)如果图G既有自回路，又有平行边，则称G为伪图。13/1

7、28图的种类例：中国主要城市通讯图14/128图的种类15/128类型边允许平行边允许自环图无向否否多重图无向是否伪图无向是是有向图有向否是有向多重图有向是是图的同构从图的定义可以看出，图的最本质的内容是结点和边的关联关系。两个表面上看起来不同的图，可能表达相同的结点和边的关联关系。16/128图的同构实际中，利用图的同构可以研究是否有可能用同样的方式画两个图。例如化学里，表示过去已知化合物的图可以用来判定想象中的新化合物是否已经研究过了。17/128图的同构定义：设图G = áV , E,y ñ 和G ' = áV ', E ',y &#

8、39;ñ 。如果存在双射f :V ®V ' 和双射g : E ® E ', 使得对于任意的e Î E，v1, v2 ÎV都满足(e) = 若y (e)= v1 ,v2若y (e)= v1 ,v2并称f和g为G和G'之y则称G 间的同f (v1 ), f (v2 )f (v1 ), f (v2 )同构，记作 G G ，' 射，简称同构18/128图的同构换一种更简单的方法来描述：设图G = áV , E,y ñ 和图G ' = áV ', E ',y '

9、ñ，若存在从到的双射函数f，对于V中所有的结点a和b来说，在G中有a到b的边当且仅当在G与G同构。中有f(a)和f(b)的边，就说也就，两个同构的图有同样多的结点和边，并且映射f保持结点间的邻接关系，映射g保持边之的邻接关系。图同构的直观含义，是其中一个图经与另一个图完过旋转、平移、拉伸等全重合。19/128图的同构例：求证下图和同构。证明：两个图点、边的数目都相同。设函数f为f(u1)=v1,f(u2)=v4,f(u3)=v3,f(u4)=v2。G中相邻的点是u1与u2，u2与u4，u4与u3，u3与u1，对应的像点f(u1)=v1与f(u2)=v4,f(u2)=v4与f(u4)=

10、v2, f(u4)=v2与f(u3)=v3,f(u3)=v3与f(u1)=v1在H中相邻。因此，二图同构。20/128图的同构两个图同构必须满足的必要条件是：(1) 顶点个数相同(2) 边数相同(3) 度数相同的顶点个数相同(4)K度顶点的导出子图同构判定图的同构比较难，但是却可以通过上述四点证明图不同构。21/128图的同构例：判断下列两图是否同构。22/128图的同构例：判断下列两图是否同构。23/128 上面两个图不是同构的，因为左图中度结点都和两个度结点相关联，而右图中的度结点和一个度结点相关联还和一个度结点相关联。24/128图的同构例：判断下列两图是否同构。a2a1 b2b1e2f

11、2e1f1c2c1d2d125/128 上面两个图是同构的。我们只要构造双射函数 f:b1,c1,d1,e1,f11)=f2 ,f(b1)a2,b2,c2,d2,e2,f2,f(c1)=c2,f(f1)=e2 并且f)=d2 ,f(e1)=a2 f是个关系射函数,并且保持了边的邻接26/128图的同构判定两个图是否同构，已知的最好算法具有指数的最坏情形时间复杂度（对图的结点来说）。不过，解决这个问题的线性平均情形时间复杂度的算法已经找到，而且有希望找到判定两个图是否同构的多项式最坏情形时间复杂度算法。一个名叫NAUTY的最佳算法，目前可以在个人电脑上秒之内判定带有100个结点的两个图是否同构。

12、27/128图模型 图可以用在各种模型里，用于不同的行业。栖息地重叠图：顶点表示物种，若两个物种竞争（他们共享某些食物来源），则用无向边连接表示他们的顶点。猫头鹰浣熊鹰松鼠乌鸦负鼠啄木鸟老鼠28/128图模型熟人图：可以用模型表示人与人之间的各种关系。顶条无向表示人，当两个人互相认识时，用一连接这两个人。据估计，世界上所有人的熟人图有超过60亿条边。个顶点和可能超过1万莱坞图：好莱坞图用顶点表示演员，当两个顶点的演员共同出演一部电影时，就用一条无向边连接这两个顶点。根据无联网电影数据库， 在2001年11月，好莱坞图有574724个顶点和超过1600万条边，这些顶点所表示的演员出现在29260

13、9部影中。29/12830/128图模型循环赛图：每个队其其他所有队各有一次的比赛称为循环赛。其中每个顶点表示每个队，若a队击败b 队，则有一条从a指向b的有向边。31/128图模型合作图：合作图可以用来为学术论文的合作者关系建立模型。顶点表示某个文章的某个作者（人），如果两个人合作论文，则用无向边连接这两个人。已经发现在数学研究论文上合作的合作有超过337000个顶点和496000条边。网示网图：互联网可以用有向图来建模，用顶点表若有从网页a指向网页b的链接，则做一条从a向b的有向边。网络图几乎是连续变化的，几乎每秒都有新页面产生而又有其他页面被删除。目前网络图有超过10亿个顶点和几百亿条边

14、。许多研究者正解网络的特研究网。的性质，以便更好的理32/128图模型优先图与并发处理：通过并发的执行某些语句，计算机程序可能执行的更快。但重要的是，要避免语句执行时还要用到尚未执行语句的结果。语句与前面语句的相关性可以表示成有向图。用顶点表示某个语句，若在a语句执行完之前不能执行b语句，则引出一个从a到b的有向边，这样的图称为优先图。33/128图模型S6S5S1：a:=0S2:S3:S4:S5:S6:b:=0c:=a+1 d:=b+a e:=d+1f:=c+dS3S4S2S134/128度定义：G =< V , E > 。(1) 如果G是无向图，G中与v关联的边和与v关联的自回

15、路的数目之和称为v的度(或次)，记为dG (v)。(1) 如果G是有向图，中以v为起点的边的数目v) ；G中以v为终点的称为v的边的数目，记为为v的入记为 d - (v)；v的出度G与入度之和称为v的度，记为dG (v) 。注意，在计算无向图中结点的度时，自回路要考虑两遍，因为自回路也是边。35/128度例：计算下图中各结点的度。v3dG (v1 ) = 4 , dG (v2 ) = dG (v3 ) = 2v1v2d + (v ) = d + (v ) = d - (v ) = 2D1D2D3d - (v ) = 0,d - (v ) = 3D1D4d - (v ) = d + (v ) =

16、 d + (v ) = 1D2D3D4dD (v1 ) = 2dD (v2 ) = dD (v3 ) = 3dD (v4 ) = 436/128度定理：在无向图中，所有节点的度数之和等于边数的2倍。证：因为每条边给图G带来两度，设图G有m条边，所以图G共有2m度，等于图G的所有结点的度数之和。定理：在向图中，所有顶有顶点的入度的度数之和等于和等于所有节点的边的出度倍；和，都等于边数。37/128度 例：结点的度。38/128结点定义：度数为奇数的结点称为奇结点，度数为偶数的结点称为偶结点。定理：任何图都有偶数个奇结点。V1 = v v为奇点= v v为偶点V2å d (v) + &#

17、229; d (v) = å d (v) = 2må d (v)vÎV2vÎV1å d (v)vÎV1vÎV2vÎVV定义： 度为0的结点称为孤立结点，度为1的结点称为端点。39/128一些特殊的简单图零图：结点都是孤立结点的图称为零图。平凡图：零图称为平凡图。圈图（Cn(n3)）：是由n个顶点v1,v2,vn以及边v1,v2,v2,v3,vn-1,vn,vn,v1组成的。40/128一些特殊的简单图轮图：对来说，当给圈图Cn添加一个顶点， 并且把这个新顶点与Cn里的n个顶点逐个连接， 可以得到轮图Wn。41/12

18、8一些特殊的简单图正则图： 所有结点的度均为自然数d的无向图称为d度正则图。42/128一些特殊的简单图完全无向图：设n Î I+ ，如果n阶简单无向图G是n-1度正则图，则称G为完全无向图，记为Kn。注意：完全无向图的任意两个不同结点都邻接。一至五阶完全无向图43/128一些特殊的简单图完全有向图：设n Î I+ ，每个结点的出度和入度均为n-1的n阶简单有向图称为完全有向图。注意：完全有向图的任意两个不同结点之间都有一对方向相反的有向边相连接。一至三阶完全有向图44/128一些特殊的简单图45/128特殊类型的图的一些应用局域网：在一座大楼里，像小型计算机和个人电脑这样

19、的计算机，以及像打印机这样的外设，可以用局域网来连接。有三种常见的局域网拓扑结构。局域网的星形、环形及混合型拓扑46/1289.2子图和图的运算定义：设G = áV , E,y ñ和G¢ = áV ¢, E¢,y ¢ñ为图。(1)如果V ¢ Í V , E¢ Í E,y ¢ Í y ，则称G是G的子图， 记作 G¢ Í G ，并称G是G的母图。(2)如果V ¢ Í V , E¢ Ì E,y

20、62; Ì y记作 G¢ Ì G 。，则称G是G的真子图，(3)如果V ¢ = V , E¢ Í E,y ¢ Í y ，则称G'是G的生成子图。G = áV , E,y ñ，G本身以平凡生成子图：对于图及零图 G = áV , Æñ都是G的平凡生成子图。47/128子图定义： 设图G = áV , E,y ñ ，V ¢ Í V 且 V ¢ ¹ F。以V为结点集合，以起点和终点均在V中的边的全体为边集

21、合的G的子图，称由V导出的G的子图，记为GV。若V ¢ Ì V ，导出子图GV - V ¢，记为 G -V ¢。G -V ¢ 是从G中去掉V'中的结点以及与这些结点关联的边而得到的图G的子图。定义：设图G = áV , E,y ñ ，E¢ Í E 且 E，V ¢ = v | v ÎV Ù ($e)(e Î E¢ Ù v与e关联) 。以V ¢为结点集合，以 E 为边集合的G的子图称为由E'导出的子图。48/128子图从图示

22、看，图G的子图是图G的一部分，G的真子图的边数比G的边数少，G的生成子图与G有相同的结点，G的导出子图GV ¢ 是G的以 V ¢为结点集合的最大子图。例：ddccceefffhhaaabg(b)是(a)的子图、真子图和生成子图，(c)是(a)的由1,2,3,4导出的子图。49/128子图50/128图的运算定义：设图G = áV , E,y ñ 和G¢ = áV ¢, E¢,y ¢ñ 同为无向图或同为有向图。E¢具有y (e) = y ¢(e) ，则称(1)如果对于任意 e

23、Î EG 和 G¢是可运算的。(2)如果V IV ¢ = E I E¢ = F ，则称G和G¢是不相交的。(3)如果 E I E¢ = F ，则称G和 G¢ 是边不相交的。51/128图的运算= áV1 , E1 ,y1 ñ和 G2 = áV2 , E2 ,y 2 ñ为可运算的。设图G1(1)称以 V1边集合的G1V2 为结点集合，以 E1E为2和G2的公共子图为G1和G2的交，记为G1 I G2 。(2) 称以 E1 U E2为边集合，以与这些边关联的结点集合为点集的G1和G2的公共

24、母图为G1和G2的并， 记为G1 U G2 。(3) 称以V1 UV2为结点集合，以 E1 Å E2为边集合的的子图为G1和G2的环和，记为G1 Å G2。G1 U G252/128图的运算53/128图的运算e3v1v1v2e1e1v3ee24v2v3v4不是任何两个图都有交、并和环和。如上，(a)和(b)没有交和并，因为边e1在(a)中连接v1和v2，而在(b)中连接v2和v3。54/128图的运算= áV2 , E2 ,y 2 ñ 为可运算的。= áV1 , E1 ,y1 ñ和G2定理： 设图G1¹ F(1)如果V1

25、IV2，则存在唯一的 G1 I G2 。(2)存在唯一的G1 U G 和G1 Å G2 。证：设G1和G2同为同样证明。(1)定义y : E1 I E2 ® (V1 IV2 ) ´ (V1 IV2 )图，若同为无向图也可为：对任意的e Î E1 I E2，y (e) =y1(e) =y 2 (e)。显然，á(V1 IV2 ), (E1 I E2 ),y ñ = G1 I G2.设图G = áV1 IV2 , E1 I E2 ,y ñ和G¢ = áV1 IV2E,y ¢ñ 均为

26、G1和G2的交。因,y (e) =y1 (e).因为G¢ Í G1为G Í G1 ，对任意 Î EI，。这表明y =y ¢。因对任意e Î E1 I E2 ,y ¢(e) =y1 (e)此，G = G¢。55/128图的运算证： （2）定义y = E1 U E2® (V1 UV2 ) ´ (V1 UV2 )如下：e Î E1y (e) = ìy1 (e)íye Î E - E(e)î221然，áV1 UV2 , E1 U E2 ,y &

27、#241; = G1 UG2 。设G = áV1 UV2 , E1 U E2 ,y ñÍ G和G¢ = áV1 UV2 , E1 U E2 ,y ¢ñ均为G1和G2的并。因为 G1Í G¢ ，所以对任意eÎ E1 ，y (e) =y1(e) =y ¢(e)且G，1这表明 y =y ¢ ，因此G = G¢ 。对于存在唯一的G1 Å G2可同样证明。56/128图的运算定义： 设图G = áV , E,y ñ, E¢ Í

28、 E,记 áV , E - E¢,y /(E - E¢)ñ为G - E¢，对任意 e Î E ，记G -e为G - e。G - E¢是从G中去掉E'中的边所得到的G的子图。= áV , E,y ñ 和G¢ = áV ¢, E¢,y ¢ñ同为无向图，并且边不相交，记G + G¢为G + Ey¢ ¢。定义：设图或同为有向G + Ey¢ ¢是由G增加E'中的边所得到的图，其中y 

29、2;指出E'中的边与结点的关联关系。57/128图的运算58/128图的运算上面的例子中，(a)和(b)分别为G1和G2 ,则图c,d,e分别是 (G1 G2)-v5,v6,(G1 G2)-g,h, G2 +Ey其中gy=<g,v1,v3>59/1289.3路径、回路和连通性60/128路径和回路例：分析下列无向图v1a v2 fv5在该无向图中，v bv dv ev bv 是路23423径，但不是简单路径；cv3v2bv3cv3dv4是简单路径，但不是基本路径；v3cv3cv3 是闭路径，但不是简单闭路径。bedv4h从路径 v1gv3cv3中去掉另外，如闭路径v3cv3

30、到基本路径 v1 gv3。61/128路径和回路例：分析下列有向图ahebk fcd在该有向图中，1c4b1c4是，但不是简单路径；1a1c4 是简单路径，不是基本路径。从 1a1c4中去掉闭路径1a1就得到基本路径1a4。可以看出，从2至1存在多条有路径。62/128路但从1至2没路径和回路注意： 单独一个结因此，任何 在无向图中，也是路径，它是长度为0的基本路径。其自身总存在路径。结点v至结点v'存在路径，则从v'至v必存在路径。而在有向图中，从结点v至v'结点存在路径，而从v'至v却不一定存在路径。= v×× vn-1envn和P1 =

31、 vne '1 v '1××× v 'm-1 e 'me1v1 ××× vn-1envne '1 v '1××× v 'm-1 e 'm v 'm设路径P1v 'm，用P1P2记路63/128路径和回路例：“摆渡问题”：一个人带有一条狼、一头羊和一捆白菜，要从河的左岸渡到右岸去，河上仅有一条小船，而且只有人能划船，船上每次只能由人带一件东西过河。另外，不能让狼和羊、羊和菜单独留下。问怎样安排摆渡过程？64/128路径和回路解：

32、河左岸允许出现的情况有以下1羊菜、人羊、狼菜、狼、菜、羊及空情况：人狼羊菜、人狼羊、人狼菜、人物品已安全渡河），我们把这10种状态视为10个点，若一种状态通过一次摆渡后变为另一种状态，则在两种状态（点）之间画一直线，得到上图。这样摆渡问题就图中找出以“人羊菜”为起点，以“空”为终点的简，即：单路。容易看出，只有两条简单路符合要（1） 人狼羊菜、狼菜、人狼菜、菜、人羊菜、羊、人羊、空；（2） 人狼羊菜、狼菜、人狼菜、狼、人狼羊、羊、人羊、空。对于简单路（1）的安排为：人带羊过河；人回来；带狼过河；放下狼再将羊带回； 人再带菜过河；人回来；带羊过河。对于简单路（2）的安排为：人带羊过河；人回来；带

33、菜过河；放下菜再将羊带回； 人再带狼过河；人回来；带羊过河。次、回3次，且不会再有述的两种方案都是少次数的渡河办法了。65/128路径和回路定理： 设v和v'是图G中的结点。如果存在从v至v'的路径，则存在从v证：设当从v至v的基本路径。在长度小于l 的路径时，从v至v'必存在基本路径。如果存在路径v0e1v1 ××× vl -1e= v¢，并且= v, vl其中v0= v j ，则v0e1v1 ××× viej +1v j +1 ××× vl -1elvl路径。根据归纳

34、假设，存j £ l 且vi有i和j满足0 £ i £是从v至v'的长度为l-j 在从v至v'的基本路径66/128路径和回路定理：n阶图中的基本路径的长度小于或等于n-1。证：在任何基本路径中，出现于序列中的各结点都是互不相同的。在长度为l的任何基本路径中，不 同的结点数目是l+1。因为集合V仅有n个不同的结 点，所以任何基本路径的长度不会大于n-1。对于 长度为l的基本循环来说，序列中有l个不同的结点。因为是n阶图，所以任何基本循环的长度，都不会 超过n，综上所述，在n阶图中，基本路径的长度不会超过n-1。67/128路径和回路路径可以表示很多图

35、模型中的有用信息：熟人关系图通路（最小世界原理）合作图中的通路（数学埃德斯数）好莱坞图中的通路（演员的培根数（著名演员凯文.培根）68/128路径和回路定理：设v是图G的任意结点，G是回路或有向回路， 当且仅当G的阶与边数相等，并且在G中存在这样一条从v到v的闭路径，使得除了v在该闭路径中出现 两次外，其余结点和每条边都在该闭路径上恰出现一次。证：见书上。69/128路径和回路70/128路径和回路71/128路径和回路例：判断图(a)有没有有向回路。72/128连通性定义：设v1和v2是图G的结点。如果在G中存在从v1至v2的路径，则称在G中从v1可达v2或v1和v2 是连通的，否则称在G中

36、从v1不可达v2。对于图G的结点，用R(v)表示从v可达的全体结点的集合。图中，若从v1可达v2，则从v2必可向图中，从v1可达v2不能保证从v2 论无向图还是有向图，任何节点是可达的。注意：在达v1；而必可到自73/128连通性74/128连通性75/128连通性76/128连通图77/128连通图无向图 G = áV , E,y ñ是连通的，当且仅当对于任意v ÎV ，R(v) = V。78/128连通图由于可达性的非对称性，有向图的连通概念要复杂得多，这里需要用到基础图的概念。79/128连通图定义：设G是有向图。(1) 如果G中任意两个结点都互相可达，则称

37、G是强 连通的。(2) 如果对于G的任意两结点，必有一个结点可达另一个结点，则称G是单向连通的。(3) 如果G的基础图是连通的，则称G是弱连通的。v2v2e2v1v1e4v1e42eee111e2e4e2e3e3e3vvvvvv43434380/128子图和分支定义：设G'是G的具有某种性质的子图，并且对于G 的具有该性质的任意子图G''，只要G¢ÍG²，就有G'=G''，则称G'相对于该性质是G的极大子图。定义： 无向图G的极大连通子图称为G的分支。定义：设G是有：（1）G的极大强连通子图称为G的强分支。（

38、2）G的极向连通子图称为G的单向分支。（3）G的极大弱连同子图称为G的弱分支。81/128子图和分支定理：连通无向图恰有一个分支。非连通无向图有一个以上分支。定理：强连（单向连通，弱连通）有向图恰（单向分支，弱分支）；非强连有一个强通（非单向连通上强分支（单向分弱连通）有向图有一个以，弱分支）。82/128子图和分支e4例：v3vv46e3e2e5e6e1vvv215有4个强分支，即áv1, v2 , v3,e1, e2 , e3,áe1, áv1, v2 ññ,áe2 , áv2 , v3 ññ, &#

39、225;e3 , áv3 , v1ñññ, áv4, Æ, Æñ, áv5, Æ, Æñ, áv6, Æ, Æñ结点恰处于一个强分支中，而边e4 , e5 , e6 不每何强分支中。G有两个单向分支，即Gv6在和Gv5 , v6。显然，v5处于两个单向分支中，G只有一个弱分支，即其本身。83/128子图和分支 注意： 无向图的每个结点和每条边都恰在一个连通分支中；有向图中，并不是每个边都恰在一个强分支中 在简单有向中，每个结点每条边都恰

40、在。一 在弱分单有图每个结点每条边至少位。于一个单项分84/128子图和分支v由结点集合v1，v2，v3，v4，v5，v6和v7形成的诱导子图都是强分图;由结点集合v1，v2，v3，v4，v5，v7，v4，v5和v6，v5所成子图都是单向分图；由结点集合v1，v2，v5，v6，v7形成的诱导子图是弱分图。的v385/128资源分配图 下面给出简单有向图的一个应用资源分配图。 在多道程序的计算机系统中，可以同时执行多个程序。实际上，程序共享计算机系统中的资源，如磁带机、磁盘设备、CPU、主存贮器和编译程序等。操作系统对这些资源负责分配给各个程序。当一个程序要求使用某种资源，它要发出请求，操作系统

41、必须保证这一请求得到满足。86/128死锁状态 对资源的请求可能发生冲突。如程序A 控制着资源r1，请求资源r2；但程序B控制着资源r2，称为处于死锁状资源r1。这种情况然而冲突的请求必须解决，资源分配图有助发现和纠正死锁。87/128假设条件 假设某一程序对一些资源的请求，在该程序运行完之前必须都得到满足。在请求的时间里，被请求的资源是不能利用的，程序控制着可利用的资源，但对不可利用的资源则必须等待。88/128分析 令Pt = p1，p2，pm表示计算机系统在时间t的程序集合，Qt Í Pt是运行的程序集合， 或者说在时刻t至少分配一部分所请求的资源的程序集合。Rt = r1，r

42、2，rn是系统在时刻t的资源集合。资源分配图Gt = <Rt，E>是有向图，它表示了时间t系统中资源分配状态。把每个资源ri看作图中一个结点，其中i=1，2，n。<ri，rj>表示有向边，<ri，rj>E当且仅当程序pkPt已分配到资源ri且等源rj。89/128分析（续）例如，令Rt=r1，r2，r3，r4，Qt=p1，p2，p3，p4。资源分配状态是：p1占用资源r4且请求资源r1，p2占用资源r1且请求资源r2和r3， p3占用资源r2且请求资源r3，p4占用资源r3且请求资源r1和r4，于是，可得到资源分配图Gt=<Rt，E>如图16.2

43、.7所示。能够证明，在时刻t计算机系统处于死锁状态iff 资源分配图Gt中包含强连通图。90/128前例资源分配图91/128割集有时删除一个结点和它所关联的边，就产生带有比原图更多的连通分支的子图。把这样的结点称为割点。有时删除一条边，就产生分支的子图，把这样的边有比原图更多的连通做割边或者桥。92/1289.4图的矩阵表示邻接矩阵定义： 设 G = áV, E,y ñ 是一个简单有向图，其中的结点集合V =v1,v2 ,×××vn ，并且假定各结点已经有了从结点v1到vn的次序。试定义一个n×n的矩阵A，使得其中的元素当á

44、; vi ,v j ñÎ E当á vi ,v j ñÏ E1= a(1)i j0则称这样的矩阵A是图G的邻接矩阵。93/128邻接矩阵定义：元素或为0或为1的任何矩阵，都称为比特矩 阵或布尔矩阵。i行上值为1的元素的个列上值为1的元素的个数，邻接矩阵也是布尔矩阵，数，等于结点vi的出度； 等于结点vj的入度。94/128邻接矩阵图的邻接矩阵不具有唯一性。G = áV , E,y ñ来说，其邻接矩阵对于给定简单有向图依赖于集合V中的各元素间的次序关系。两个和相对应的邻接矩阵，如果首邻接矩阵中交换一些行，而后交在一个图换相对应的

45、各列，从能够求得另外一个图一个图的邻接矩阵，邻接矩阵，则事实上这互为同构的。样的两个向图，必95/128邻接矩阵例：写出下图的邻接矩阵，并计算各个节点的出度和入度。解：首先给各结点安排好一个次序，譬如说是v1 , v2 , v3 , v4 , v5。得出邻接矩阵如下：év1v210101v301000v400101v5 ùê 00 úvêê 0ú0 ú1A = v2ê 01 úvêú3ê 10 úv4êúv5 êë

46、10 úû96/128邻接矩阵上例中，如果重新把各结点排列成 v5 , v2 , v3 , v4 , v1，就能写出另外一个矩阵如下：év5v1 ùv210101v301000v410100ê 01 úvêê 0ú0 ú5A¢ = v2ê 10 úvêú3ê 01 úv4v1êúêë 00 úû97/128邻接矩阵 对于给定图G，显然不会因结点编序不同而使其结构会发生

47、任何变化，即图的结点所有不同编序实际上仍表示同一个图。换句话说，这些结点的不同编序的图都是同构的，并且它们的n！个邻接矩阵都是相似的。 今后将略去这种由于V中结点编序而引起邻接矩阵的任意性。而取该图的任一个邻接矩阵作为该图的矩阵表示。98/128邻接矩阵由邻接矩阵判断有向图的性质： 如果有向图是自反的，则邻接矩阵的主对角线上的各元素，必定都是1。 如果有向图是的各元素，必反是0则邻接矩阵的主对角线上对有向图来说，接矩阵也是对称的，于所有的i和j而言，都应有aij=aji。也就说则对于所有的i和j和给定有向图是反对称ij而言，aij=1 蕴含aji=0。99/128邻接矩阵可以把简单有向图的矩阵

48、表示的概念，推广到简单无向图、多重边图和加权图。对于简单无向图来说，这种推广会给出一个对称或加权图的情况下，可邻接矩阵，在多重边图= wijaij其中的wij，或者是边ávi , v j ñ的的权。另外，若ávi , v j ñÏ E ，数，或者是边ávi , v j ñ= 0wij。在零图的邻接矩阵中，所有元素都应该是0，亦即其邻接矩阵是个零矩阵。100/128邻接矩阵逆图的邻接矩阵：如果给定的图G = áV , E,ñ是一个简单有向图，并且其邻接矩阵是A，则图G的逆图的邻接矩阵 G 是A的转置 AT

49、。对于无向图或者对称的有向图来说，应= A 。有AT101/128B = AAT在图上的意义。设aij是邻接矩阵中的第i行和第j定义矩阵 B = AAT列上的(i, j) 元素，bij 是矩阵中的第i行和第j列上的元素(i,j)。于是，对于i, j = 1, 2, 3,×××, nbij= å aik a j k k -1来说，有n= 1 ，如果边áv j , vk ñ Î E ，如果边ávi , vk ñ Î E，则有aik则有ajk = 1 。对于某一个确定的k来说，如果ávi ,

50、 vk ñ 和ávj , vk ñ 都是给定图的边，则在表示bij 的上述求和表达式中，应该引入基值1。从结点vi和vj二者引出的边，如果能共同终止于一些结点的话，那么这样的一些结点的数目，就是元素bij的值。102/128B = AAT例：如图，求 AAT在图上的意义解：év1v5 ùév1v5 ùv210101v301000v400101v200100v301011v410000ê 00 úê 01 úvvêê 0ú0 úê

51、4; 1ú1 ú11A = v2= v2ATê 01 úê 00 úvvêúêú33ê 10 úê 01 úv4v5v4êúêúêë 10 úûv5 êë 00 úûé11ù010001030200011ê00úê= ê1ú2úAATê01ú

52、;êêë1ú3úû简单算法：原矩阵A中，第i行和第j行相交，有几个1，AAT的第i行第j列就是几。矩阵的主对角线的元素对应了各个节点的出度。103/128C = AT A在图上的意义设aij是邻接矩阵A中的(i,j)元素； cij 是矩阵C中的元素。于是，对于i = 1, 2,×××, n,Cij= å aki akjnk =1对于某一个确定的k来说，如果ávk , vi ñ, ávk , v j ñ都是给定图的边，则在上式中应引入基值1。可得从图中的一些

53、点所引出的边，如果能够同时终止于结点vi和vj的话，那么这样的一些结点的数目，就是元素Cij的值。104/128C = AT A例：如图，求 AT A解：在图上的意义év1v210101v301000v400101v5 ùév1v200100v301011v410000v5 ùê 00 úê 01 úvvêê 0ú0 úêê 1ú1 ú11A = v2= v2ê 01 úATê 00 úvv

54、34;úêú33ê 10 úê 01 úv4vêú4êúv5 êë 10 ûúêë 00 úûv5简单算法：原矩阵A中，第i列和第j 列相交，有几个1，ATA 的第i行第j列就是几。é20ù130210010012021ê11úêA = ê0ú0úATê11úêêë0ú

55、1úû矩阵的主对角线的元素对应了各个节点的入度。105/128邻接矩阵的幂对于n = 2, 3, 4,××× 来说，考察邻接矩阵A的幂An可知， 邻接矩阵A中的第i行和第j列上的元素值1，说明了图G中存在一条边<vi,vj>，也就是说，存在一条从结点vi到vj长度为1的路径。定义矩阵A2，使得A2中的各2 为元素 aijn= å a2aaijikkjk =12元素值 a等于从v 到v 长度为2的不同路径的ijij2数目。显然，矩阵中主对角线上的元素 a的ii值，表示了结点vi (i = 1, 2,××&

56、#215;, n) 上长度为2的循环的个数。矩阵A3中的元素值(i,j)依次类推。106/128邻接矩阵的幂例：é00ùé01ù011111010101100113020111111101ê01úê20úê= ê2ú0úê= ê1ú1úA2A3,ê00úê00úêêë1ú0úûêêë0ú1úûé20ùé11ù133121130211212336151331212413ê11úê21ú