第10章图的概念与表示精选PPT.ppt

《第10章图的概念与表示精选PPT.ppt》由会员分享，可在线阅读，更多相关《第10章图的概念与表示精选PPT.ppt（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第10章图的概念与表示章图的概念与表示第1页，此课件共76页哦10.1 图的基本概念图的基本概念什什么么是是图图?可可用用一一句句话话概概括括，即即：图图是是用用点点和和线线来来刻刻划划离离散散事事物物集集合合中中的的每每对对事事物物间间以以某某种种方方式式相相联联系系的的数数学学模模型型。因因为为它它显显得得太太抽抽象象，不不便便于于理理解解，所所以以有有必必要要给给出出另另外外的的回回答答。下下面便是把图作为代数结构的一个定义。面便是把图作为代数结构的一个定义。第2页，此课件共76页哦定义定义10.1.1 一个图一个图G定义为一个三元组定义为一个三元组，记作，记作G=。其中。其中V是个非

2、空是个非空有限集合，它的元素称为结点；有限集合，它的元素称为结点；E也是个有限集也是个有限集合，其元素称为边，而合，其元素称为边，而是从是从E到到V中的有序对中的有序对或无序对的映射。或无序对的映射。第3页，此课件共76页哦由定义可知，图由定义可知，图G中的每条边都与图中的中的每条边都与图中的无序或有序结点对相联系的。若边无序或有序结点对相联系的。若边eE与无序与无序结点对结点对vi，vj相联系，则相联系，则(e)=vi，vj，这，这时边时边e称为无向边，有时简称为边；若边称为无向边，有时简称为边；若边eE与与有序结点对有序结点对相联系，则相联系，则(e)=，此时边此时边e称为有向边或弧，称为

3、有向边或弧，vi称为弧称为弧e的始结点，的始结点，vj称为弧称为弧e的终结点。的终结点。第4页，此课件共76页哦若结点若结点vi与与vj由一条边由一条边(或弧或弧)e所联结，则称所联结，则称结点结点vi和和vj是边是边(或弧或弧)e的端结点；同时也称结点的端结点；同时也称结点vi与与vj是邻接结点，记作是邻接结点，记作vi adj vj；否则为非邻接；否则为非邻接结点，记作结点，记作vi nadj vj；也说边；也说边(或弧或弧)e关联关联vi与与vj或说结点或说结点vi与与vj关联边关联边(或弧或弧)e。关联同一个结点。关联同一个结点的两条边或弧称为邻接边或弧。而联结一结点的两条边或弧称为邻

4、接边或弧。而联结一结点与它自身的一条边，称为环。环的方向是无意与它自身的一条边，称为环。环的方向是无意义的。义的。第5页，此课件共76页哦如果把图如果把图G中的弧或边总看作联结两个结中的弧或边总看作联结两个结点，则图点，则图G可简记为可简记为G=，其中，其中V是非空是非空结点集，结点集，E是联结结点的边集或弧集。是联结结点的边集或弧集。定义定义10.1.2 在图在图G=中，如果每条中，如果每条边都是弧，该图称为有向图；若每条边都是无边都是弧，该图称为有向图；若每条边都是无向边，该图向边，该图G称为无向图；如果有些边是有向边，称为无向图；如果有些边是有向边，另一些边是无向边，图另一些边是无向边，

5、图G称为混合图。称为混合图。第6页，此课件共76页哦定定义义10.1.3 在在图图G=中中，如如果果任任何何两两结结点点间间不不多多于于一一条条边边(对对于于有有向向图图中中，任任何何两两结结点点间间不不多多于于一一条条同同向向弧弧)，并并且且任任何何结结点点无无环环，则则图图G称称为为简简单单图图；若若两两结结点点间间多多于于一一条条边边(对对于于有有向向图图中中，两两结结点点间间多多于于一一条条同同向向弧弧)图图G称称为为多多重重图图，并并把把联联结结两两结结点点之之间间的的多多条条边边或或弧弧，称为平行边或弧，平行边或弧的条数称为重数。称为平行边或弧，平行边或弧的条数称为重数。第7页，此

6、课件共76页哦定定义义10.1.4 给给每每条条边边或或弧弧都都赋赋予予权权的的图图G=，称称为为加加权权图图，记记为为G=，其中，其中W表示各边之权的集合。表示各边之权的集合。加加权权图图在在实实际际中中有有许许多多应应用用，如如在在输输油油管管系系统统图图中中权权表表示示单单位位时时间间流流经经管管中中的的石石油油数数量量；在在城城市市街街道道中中，权权表表示示表表示示通通行行车车辆辆密密度度；在在航空交通图中，权表示两城市的距离等等。航空交通图中，权表示两城市的距离等等。第8页，此课件共76页哦定定义义10.1.5 在在无无向向图图G=中中，如如果果V中的每个结点都与其余的所有结点邻接，

7、即中的每个结点都与其余的所有结点邻接，即(vi)(vj)(vi，vjV vi，vjE)则则该该图图称称为为无无向向完完全全图图，记记作作K|V|。若若|V|=n，该图记作，该图记作Kn。第9页，此课件共76页哦 在在一一个个图图中中，如如果果一一个个结结点点不不与与任任何何其其他他结结点点邻邻接接，则则该该结结点点称称为为孤孤立立结结点点。仅仅有有孤孤立立结结点点的的图图称称为为零零图图。显显然然，在在零零图图中中边边集集为为空空集集。若若一一个个图图中中只只含含一一个个孤孤立立结结点点，该该图图称称为为平凡图。平凡图。第10页，此课件共76页哦定定义义10.1.6 在在有有向向图图G=中中，

8、对对任任意意结结点点vV，以以v为为始始结结点点的的弧弧的的条条数数，称称为为结结点点v的的出出度度，记记为为d+(v)；以以v为为终终结结点点的的弧弧的的条条条条数数，称称为为v的的入入度度，记记作作d-(v)；结结点点v的的出出度度与与入入度度之之和和，称称为为结结点点的的度度数数，记记为为d(v)，显显然然d(v)=d+(v)+d-(v)。对对于于无无向向图图G=，结结点点vV的的度度数数等等于于联联结结它它的的边边数数，也也记记为为d(v)。若若v点点有有环环，规定该点度因环而增加规定该点度因环而增加2。第11页，此课件共76页哦显然，对于孤立结点的度数为零。显然，对于孤立结点的度数为

9、零。此外，对于无向图此外，对于无向图G=，记，记(G)或或=max d(v)|vV(G)或或=min d(v)|vV 它们分别称为图它们分别称为图G的最大度和最小度。的最大度和最小度。关于无向图中的结点的度，欧拉给出一个关于无向图中的结点的度，欧拉给出一个定理，这是图论中的第一个定理。定理，这是图论中的第一个定理。第12页，此课件共76页哦定理定理10.1.1 给定无向图给定无向图G=，则，则定理定理10.1.2 在任何无向图中，奇度结点的在任何无向图中，奇度结点的数目为偶数。数目为偶数。第13页，此课件共76页哦定定义义10.1.7 在在无无向向图图G=中中，如如果果每每个个结结点点的的度度

10、是是k，即即(v)(vVd(v)=k)，则则图图G称为称为k度正则图。度正则图。显然，对于显然，对于k度正则图度正则图G，(G)=(G)=k。第14页，此课件共76页哦定定义义10.1.8 给给定定无无向向图图G1=和和G2=，于是，于是(1)如如果果V2 V1和和E2 E1，则则称称G2为为G1的的子子图，记为图，记为G2 G1。(2)如如果果V2 V1，E2 E1且且E2E1，则则称称G2为为G1的真子图，记为的真子图，记为G2 G1。(3)如如果果V2=V1，E2 E1，则则称称G2为为G1的的生生成子图，记为成子图，记为G2 G1。第15页，此课件共76页哦定定义义10.1.9 设设图

11、图G2=是是图图G1=的的子子图图。若若对对任任意意结结点点u和和v，如如果果u，vE1，有有u，vE2，则则G2由由V2唯唯一一地地确确定定，并并称称G2是是结结点点集集合合V2的的诱诱导导子子图图，记记作作或或GV2；如如果果G2无无孤孤立立结结点点，且且由由E2所所唯唯一一确确定定，则则称称G2是是边边集集E2的的诱诱导导子子图图，记记为为或或GE2。第16页，此课件共76页哦定定 义义 10.1.10 设设 图图G1=和和 图图G2=是是图图G=的的子子图图。如如果果E2=E-E1且且G2=，则则称称图图G2是是相相对对于于图图G的子图的子图G1的补图。的补图。第17页，此课件共76页

12、哦定定义义10.1.11 给给定定图图G=，若若存存在在图图G1=，并并且且E1E=和和图图是是完完全全图图，则则G1称称为为相相对对于于完完全全图图的的G的的补补图图，简简称称G1是是G的补图，并记为的补图，并记为G1=。显然，显然，G与与 互为补图。互为补图。第18页，此课件共76页哦在在图图的的定定义义中中，强强调调的的是是结结点点集集、边边集集以以及及边边与与结结点点的的关关联联关关系系，既既没没有有涉涉及及到到联联结结两两个个结结点点的的边边的的长长度度、形形状状和和位位置置，也也没没有有给给出出结结点点的的位位置置或或者者规规定定任任何何次次序序。因因此此，对对于于给给定定的的两两

13、个个图图，在在它它们们的的图图形形表表示示中中，即即在在用用小小圆圆圈圈表表示示结结点点和和用用直直线线或或曲曲线线表表示示联联结结两两个个结结点点的的边边的的图图解解中中，看看起起来来很很不不一一样样，但但实实际际上上却却是是表表示示同同一一个个图图。因因而而，引引入入两两图图的的同同构构概概念便是十分必要的了。念便是十分必要的了。第19页，此课件共76页哦定定义义10.1.12 给给定定无无向向图图(或或有有向向图图)G1=和和G2=。若若存存在在双双射射fV2V1，使使得得对对任任意意v，uV1，有有u，vE1f(u)，f(v)E2(或或E1E2)则则称称G1同构于同构于G2，记为，记为

14、G1 G2。显显然然，两两图图的的同同构构是是相相互互的的，即即G1同同构构于于G2，G2同构于同构于G1。由由同同构构的的定定义义可可知知，不不仅仅结结点点之之间间要要具具有有一一一一对对应应关关系系，而而且且要要求求这这种种对对应应关关系系保保持持结结点点间间的的邻邻接接关关系系。对对于于有有向向图图的的同同构构还还要要求求保保持边的方向。持边的方向。第20页，此课件共76页哦一一般般说说来来，证证明明两两个个图图是是同同构构的的并并非非是是轻轻而而易易举举的的事事情情，往往往往需需要要花花些些气气力力。请请读读者者证明图证明图10.1.13中两个图是同构的。中两个图是同构的。第21页，此

15、课件共76页哦根据图的同构定义，可以给出图同构的必根据图的同构定义，可以给出图同构的必要条件如下：要条件如下：(1)结点数目相等；结点数目相等；(2)边数相等；边数相等；(3)度数相同的结点数目相等。度数相同的结点数目相等。第22页，此课件共76页哦但这仅仅是必要条件而不是充分条件。但这仅仅是必要条件而不是充分条件。满足上述三个条件，然而并不满足上述三个条件，然而并不同构。因此在同构。因此在(a)中度数为中度数为3的结点的结点x与两个度数为与两个度数为1的结点邻接，而的结点邻接，而(b)中度数为中度数为3的结点的结点y仅与一个度仅与一个度数为数为1的结点邻接。的结点邻接。寻找一种简单有效的方法

16、来判定图的同构，寻找一种简单有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。至今仍是图论中悬而未决的重要课题。高等学校高等学校2121世纪教材世纪教材 例如图例如图10.1.1410.1.14中中中中(a)与与(b)第23页，此课件共76页哦图 10.1.13返回返回第24页，此课件共76页哦返回返回图图 1.1.14第25页，此课件共76页哦10.2 链链(或路或路)与圈与圈(或回路或回路)在在无无向向图图(或或有有向向图图)的的研研究究中中，常常常常考考虑虑从从一一个个结结点点出出发发，沿沿着着一一些些边边(或或弧弧)连连续续移移动动而而达达到到另另一一个个指指定定结结点点，这

17、这种种依依次次由由结结点点和和边边(或或弧弧)组成的序列，便形成了链组成的序列，便形成了链(或路或路)的概念。的概念。第26页，此课件共76页哦定义定义10.2.1 给定无向图给定无向图(或有向图或有向图)G=。令。令v0，v1，vmV，边，边(或弧或弧)e1，e2，emE，其中，其中vi-1，vi是是ei的结点，交替序列的结点，交替序列v0e1v1e2v2emvm称为连接称为连接v0到到vm的链的链(或路或路)。v0和和vm分别称为链分别称为链(或路或路)的始结点和终结点，而边的始结点和终结点，而边(或弧或弧)的数目称为链的数目称为链(或路或路)的长度。若的长度。若v0=vm时，时，该链该链

18、(或路或路)称为圈称为圈(或回路或回路)。第27页，此课件共76页哦定义定义10.2.2 在一条链在一条链(或路或路)中，若出现的边中，若出现的边(或弧或弧)都是不相同的，称该链都是不相同的，称该链(或路或路)为简单链为简单链(或或简单路简单路)；若出现的结点都是不相同的，称该链；若出现的结点都是不相同的，称该链(或路或路)为基本链为基本链(或基本路或基本路)。显然，每条基本链显然，每条基本链(或基本路或基本路)必定是简单链必定是简单链(或简单路或简单路)。第28页，此课件共76页哦定义定义10.2.3 在一圈在一圈(或回路或回路)中，若出现的每中，若出现的每条边条边(或弧或弧)恰好一次，称该

19、圈恰好一次，称该圈(或回路或回路)为简单圈为简单圈(或简单回路或简单回路)；若出现的每个结点恰好一次，称；若出现的每个结点恰好一次，称该圈该圈(或回路或回路)为基本圈为基本圈(或基本回路或基本回路)。可以看出，对于简单图来说，链可以看出，对于简单图来说，链(或路或路)和圈和圈(或回路或回路)能够仅用结点序列表示之。能够仅用结点序列表示之。第29页，此课件共76页哦定定理理10.2.1 在在一一个个图图中中，若若从从结结点点vi到到结结点点vj存存在在一一条条链链(或或路路)，则则必必有有一一条条从从vi到到vj的的基基本本链链(或基本路或基本路)。定理定理10.2.2 在一个具有在一个具有n个

20、结点的图中，则个结点的图中，则(1)任何基本链任何基本链(或路或路)的长度均不大于的长度均不大于n-1。(2)任何基本圈任何基本圈(或路或路)的长度均不大于的长度均不大于n。第30页，此课件共76页哦定定义义10.2.4 在在一一个个图图中中，若若从从vi到到vj存存在在任任何何一一条条链链(或或路路)，则则称称从从vi到到vj是是可可达达的的，或或简简称称vi可达可达vj。为为完完全全起起见见，规规定定每每个个结结点点到到其其自自身身是是可可达的。达的。对对于于无无向向图图G来来说说，不不难难证证明明结结点点间间的的可可达达性性是是结结点点集集合合上上的的等等价价关关系系。因因此此它它将将结

21、结点点集集合合给给出出一一个个划划分分，并并且且划划分分中中的的每每个个元元素素形形成成一一个个诱诱导导子子图图；两两结结点点之之间间是是可可达达的的当当且且仅仅当当它它们们属属于于同同一一个个子子图图，称称这这种种子子图图为为图图G的的连连通分图，图通分图，图G的连通分图的个数，记为的连通分图的个数，记为(G)。第31页，此课件共76页哦定义定义10.2.5 若图若图G只有一个连通分图，则只有一个连通分图，则称称G是连通图；否则，称图是连通图；否则，称图G为非连通图或分离为非连通图或分离图。图。在在图图的的研研究究中中，常常常常需需要要考考虑虑删删去去与与增增加加结结点点、结结点点集集、边边

22、和和边边集集（或或弧弧集集）的的问问题题。所所谓谓从从图图G=中中删删去去结结点点集集S，是是指指作作V-S以以及及从从E中中删删去去与与S中中的的全全部部结结点点相相联联结结的的边边而而得得到到的的子子图图，记记作作G-S；特特别别当当S=|v|时时，简简记记为为G-v；所所谓谓从从图图G=中中删删去去边边集集（或或弧弧集集）T，是是指指作作E-T，且且T中中的的全全部部边边所所关关联联的的结结点点仍仍在在V中中而而得得到到的的子子图图，记记为为G-T；特特别别当当T=e 时时，简记作简记作G-e。第32页，此课件共76页哦所谓图所谓图G=增加结点集增加结点集S，是指作，是指作VT以及向以及

23、向E中并入中并入S中、中、S与与V中所成的边而得中所成的边而得到的图，记作到的图，记作G+S；特别当；特别当S=v 时，简记为时，简记为G+v；图；图G=增加边集（或弧集）增加边集（或弧集）T是指作是指作ET所得到的图，记作所得到的图，记作G+T，这里，这里T中全部边（或弧）中全部边（或弧）的关联结点属于的关联结点属于V。第33页，此课件共76页哦定义定义10.2.6 给定连通无向图给定连通无向图G=，S V。若。若(G-S)(G)，但，但 T S有有(G-T)=(G)，则称，则称S是是G的一个分离结点集。若图的一个分离结点集。若图G的分离结点集的分离结点集S=v，则称，则称v是是G的割点。的

24、割点。类似地可定义图类似地可定义图G的分离边集的分离边集T；若图；若图G的的分离边集分离边集T=e，则称，则称e是是G的割边或桥。的割边或桥。第34页，此课件共76页哦对对于于连连通通的的非非平平凡凡图图G，称称(G)=|S|S是是G的的分分离离结结点点集集 为为图图G的的结结点点连连通通度度，它它表表明明产产生生不不连连通通图图而而需需要要删删去去结结点点的的最最少少数数目目。于于是是，对对于于分分离离图图G，(G)=0；对对于于存存在在割割点的连通图点的连通图G，(G)=1。第35页，此课件共76页哦类似地定义边连通度类似地定义边连通度(G)=|T|T是是G的分离边集的分离边集，它表明产生

25、不连通图而需要删，它表明产生不连通图而需要删去边的最少数目。可见，对于分离图去边的最少数目。可见，对于分离图G，(G)=0；对于完全图；对于完全图G，(G)=0；对于图；对于图K1，(K1)=0；对于存在割边的连通图；对于存在割边的连通图G，(G)=1；对于完全；对于完全图图Kn，(Kn)=n-1。第36页，此课件共76页哦下面是由惠特尼下面是由惠特尼(H.Whitney)于于1932年得到年得到的关于结点连通度、边连通度和最小度的不等的关于结点连通度、边连通度和最小度的不等式联系的定理：式联系的定理：定理定理10.2.3 对于任何一个无向图对于任何一个无向图G，有，有(G)(G)(G)。定定

26、理理10.2.4 一一个个连连通通无无向向图图G中中的的结结点点v是是割割点点存存在在两两个个结结点点u和和w，使使得得联联结结u和和w的的每每条链都经过条链都经过v。第37页，此课件共76页哦定定理理10.2.5 一一个个连连通通无无向向图图G中中的的边边e是是割割边边存存在在两两个个结结点点u和和w，使使得得联联结结u与与w的的每每条条链都经过链都经过e。下下面面再再给给出出一一个个判判定定一一条条边边是是割割边边的的充充要要条件。条件。定定理理10.2.6 连连通通无无向向图图G中中的的一一条条边边e是是割割边边e不包含在图的任何基本圈中。不包含在图的任何基本圈中。第38页，此课件共76

27、页哦对对于于有有向向图图而而言言，结结点点间间的的可可达达性性不不再再是是等等价价关关系系，它它仅仅仅仅是是自自反反的的和和传传递递的的。一一般般说说来来，不不是是对对称称的的。因因此此，有有向向图图的的连连通通概概念念较较之无向图要复杂得多。之无向图要复杂得多。对对于于给给定定的的有有向向力力G，要要略略去去G中中每每条条边边的的方向便得到一个无向图方向便得到一个无向图G1，称，称G1是是G的基础图。的基础图。第39页，此课件共76页哦定义定义10.2.7 在简单有向图在简单有向图G中，若中，若G中任何中任何两个结点间都是可达的，则称两个结点间都是可达的，则称G是强连通的；若是强连通的；若任

28、何两个结点间至少是从一个结点可达另一个任何两个结点间至少是从一个结点可达另一个结点，则称结点，则称G是单向连通的；若有向图是单向连通的；若有向图G不是单不是单向连通的，但其基础图是连通的，则称向连通的，但其基础图是连通的，则称G是弱连是弱连通的。通的。从从上上面面定定义义可可知知，若若图图G是是强强连连通通的的，则则它它必必是是单单向向连连通通的的，但但反反之之未未必必真真；若若图图G是是单单向连通的，则它必是弱连通的，反之不真。向连通的，则它必是弱连通的，反之不真。第40页，此课件共76页哦定定理理10.2.7 有有向向图图G是是强强连连通通的的G中中有有一一回路，它至少通过每个结点一次。回

29、路，它至少通过每个结点一次。令令G是是简简单单有有向向图图，对对于于某某种种性性质质而而言言，若若G中中再再没没有有其其它它包包含含子子图图G1的的真真子子图图具具有有这这种种性质，则称性质，则称G1是是G的关于该性质的极大子图。的关于该性质的极大子图。定定义义10.2.8 在在简简单单有有向向图图中中，具具有有强强连连通通性性质质的的极极大大子子图图，称称为为强强分分图图；具具有有单单向向连连通通性性质质的的极极大大子子图图，称称为为单单向向分分图图；具具有有弱弱连连通通性质的极大子图，称为弱分图。性质的极大子图，称为弱分图。第41页，此课件共76页哦定定理理10.2.8 简简单单有有向向图

30、图中中的的任任一一个个结结点点恰恰位于一个强分图中。位于一个强分图中。注注意意，有有向向图图中中的的任任意意一一弧弧未未必必恰恰位位于于一一个个强强分分图图中中，例例如如，在在图图10.2.6中中，弧弧位位于于 结结 点点 集集 合合 v1,v2,v3 的的 诱诱 导导 子子 图图 中中，但但 弧弧不位于任何强分图之中。不位于任何强分图之中。第42页，此课件共76页哦类似地可以证明下面两个定理：类似地可以证明下面两个定理：定理定理10.2.9 简单有向图中的每个结点和每简单有向图中的每个结点和每条弧至少位于一个单向分图中。条弧至少位于一个单向分图中。定理定理10.2.10 简单有向图中的每个结

31、点和每简单有向图中的每个结点和每条弧恰位于一个弱分图中。条弧恰位于一个弱分图中。如果结点如果结点u可达结点可达结点v，它们之间可能存在，它们之间可能存在不止一条链不止一条链(或路或路)。在所有这些链。在所有这些链(或路或路)中，最中，最短链短链(或路或路)的长度称为结点的长度称为结点u和和v之间的距离或短之间的距离或短程线或测地线，记作程线或测地线，记作d。第43页，此课件共76页哦距离满足下列性质：距离满足下列性质：d0d=0d+dd如果如果u不可达不可达v，则，则d=+。此外，要注意，即使此外，要注意，即使u与与v相互可达，相互可达，d未必等于未必等于d。第44页，此课件共76页哦下面给出

32、简单有向图的一个应用下面给出简单有向图的一个应用资源资源分配图。分配图。在多道程序的计算机系统中，可以同时执在多道程序的计算机系统中，可以同时执行多个程序。实际上，程序共享计算机系统中行多个程序。实际上，程序共享计算机系统中的资源，如磁带机、磁盘设备、的资源，如磁带机、磁盘设备、CPU、主存贮、主存贮器和编译程序等。操作系统对这些资源负责分器和编译程序等。操作系统对这些资源负责分配给各个程序。当一个程序要求使用某种资源，配给各个程序。当一个程序要求使用某种资源，它要发出请求，操作系统必须保证这一请求得它要发出请求，操作系统必须保证这一请求得到满足。到满足。第45页，此课件共76页哦对资源的请求

33、可能发生冲突。如程序对资源的请求可能发生冲突。如程序A控制控制着资源着资源r1，请求资源，请求资源r2；但程序；但程序B控制着资源控制着资源r2，请求资源请求资源r1。这种情况称为处于死锁状态。然而。这种情况称为处于死锁状态。然而冲突的请求必须解决，资源分配图有助发现和冲突的请求必须解决，资源分配图有助发现和纠正死锁。纠正死锁。假设某一程序对一些资源的请求，在该程假设某一程序对一些资源的请求，在该程序运行完之前必须都得到满足。在请求的时间序运行完之前必须都得到满足。在请求的时间里，被请求的资源是不能利用的，程序控制着里，被请求的资源是不能利用的，程序控制着可利用的资源，但对不可利用的资源则必须

34、等可利用的资源，但对不可利用的资源则必须等待。待。第46页，此课件共76页哦令令Pt=p1，p2，pm 表示计算机系统在表示计算机系统在时间时间t的程序集合，的程序集合，Qt Pt是运行的程序集合，或是运行的程序集合，或者说在时刻者说在时刻t至少分配一部分所请求的资源的程至少分配一部分所请求的资源的程序集合。序集合。Rt=r1，r2，rn 是系统在时刻是系统在时刻t的资的资源集合。资源分配图源集合。资源分配图Gt=是有向图，它是有向图，它表示了时间表示了时间t系统中资源分配状态。把每个资源系统中资源分配状态。把每个资源ri看作图中一个结点，其中看作图中一个结点，其中i=1，2，n。表示有向边，

35、表示有向边，E当且仅当程序当且仅当程序pkQt已分配到资源已分配到资源ri且等待资源且等待资源rj。第47页，此课件共76页哦例如，令例如，令Rt=r1,r2,r3,r4，Qt=p1,p2,p3,p4。资源分配状态是：资源分配状态是：p1占用资源占用资源r4且请求资源且请求资源r1；p2占用资源占用资源r1且请求资源且请求资源r2和和r3；p3占用资源占用资源r2且请求资源且请求资源r3；p4占用资源占用资源r3且请求资源且请求资源r1和和r4。第48页，此课件共76页哦于是，可得到资源分配图于是，可得到资源分配图Gt=，如图，如图10.2.7所示。所示。能够证明，在时刻能够证明，在时刻t计算

36、机系统处于死锁状计算机系统处于死锁状态态资源分配图资源分配图Gt中包含强分图。于是，对于中包含强分图。于是，对于图图10.2.7，Gt是强连通的，即处于死锁状态。是强连通的，即处于死锁状态。第49页，此课件共76页哦图图 10.2.7第50页，此课件共76页哦10.3 图的矩阵表示图的矩阵表示给给定定一一个个图图G=，使使用用图图形形表表示示法法很很容容易易把把图图的的结结构构展展现现出出来来，而而且且这这种种表表示示直直观观明明了了。但但这这只只在在结结点点和和边边(或或弧弧)的的数数目目相相当当小小的的情情况况下下才才是是可可行行的的。显显然然这这限限制制了了图图的的利利用用。本本节节提提

37、供供另另一一种种图图的的表表示示法法图图的的矩矩阵阵表表示示法法。它它不不仅仅克克服服了了图图形形表表示示法法的的不不足足，而而且且这这种种表表示示可可以以充充分分利利用用现现代代工工具具电电子子计计算算机机，以以达到研究图的目的。达到研究图的目的。第51页，此课件共76页哦一个简单图一个简单图G=由由V中每两个结点间中每两个结点间的邻接关系唯一地确定，这种关系可以用一个的邻接关系唯一地确定，这种关系可以用一个矩阵给出，而矩阵形式与图中结点的编序有密矩阵给出，而矩阵形式与图中结点的编序有密切关系，这是用矩阵表示图值得注意的一点。切关系，这是用矩阵表示图值得注意的一点。第52页，此课件共76页哦

38、定义定义10.3.1 给定简单图给定简单图G=，V=v1，v2，vn，V中的结点按下标由小到大编序，中的结点按下标由小到大编序，则则n阶方阵阶方阵A=(aij)称为图称为图G的邻接矩阵。其中的邻接矩阵。其中 i，j=1，2，n。有时为强调邻接矩阵依赖于图有时为强调邻接矩阵依赖于图G，把图，把图G的的邻接矩阵记为邻接矩阵记为A(G)。第53页，此课件共76页哦对对于于给给定定图图G，显显然然不不会会因因结结点点编编序序不不同同而而使使其其结结构构发发生生任任何何变变化化，即即图图的的结结点点所所有有不不同同的的编编序序实实际际上上仍仍表表示示同同一一个个图图。换换句句话话说说，这这些些结结点点的

39、的不不同同编编序序的的图图都都是是同同构构的的，并并且且它它们的邻接矩阵都是相似的。于是们的邻接矩阵都是相似的。于是G H存在置换矩阵存在置换矩阵P，使，使A(H)=P-1A(G)P今今后后将将略略去去这这种种由由于于V中中结结点点编编序序而而引引起起邻邻接接矩矩阵阵的的任任意意性性，而而取取该该图图的的任任一一个个邻邻接接矩矩阵阵作为该图的矩阵表示。作为该图的矩阵表示。第54页，此课件共76页哦邻接矩阵可展示相应图的一些性质：邻接矩阵可展示相应图的一些性质：若邻接矩阵的元素全为零，则其对应的图若邻接矩阵的元素全为零，则其对应的图是零图；是零图；若邻接矩阵的元素除主对角线元素外全为若邻接矩阵的

40、元素除主对角线元素外全为1，则其对应的图是连通的且为简单完全图。，则其对应的图是连通的且为简单完全图。第55页，此课件共76页哦此外，当给定的简单图是无向图时，邻接此外，当给定的简单图是无向图时，邻接矩阵是对称矩阵；反之，若给定任何对称矩阵矩阵是对称矩阵；反之，若给定任何对称矩阵A，显然可以唯一地作出以，显然可以唯一地作出以A为其邻接矩阵的简单为其邻接矩阵的简单图图G。于是，所有。于是，所有n个结点的不同编序的简单图个结点的不同编序的简单图的集合与所有的集合与所有n阶对称矩阵的集合可建立一一对阶对称矩阵的集合可建立一一对应。应。第56页，此课件共76页哦当给一的图是简单有向图时，其邻接矩阵当给

41、一的图是简单有向图时，其邻接矩阵并非一定是对称矩阵，但所有并非一定是对称矩阵，但所有n个结点的不同编个结点的不同编序的简单图的集合，与所有序的简单图的集合，与所有n阶邻接矩阵的集合阶邻接矩阵的集合亦可建立一一对应。亦可建立一一对应。不仅如此，通过对矩阵元素的一些计算还不仅如此，通过对矩阵元素的一些计算还可以得到对应图的某些数量的特征。可以得到对应图的某些数量的特征。第57页，此课件共76页哦在给定简单有向图的邻接矩阵中，第在给定简单有向图的邻接矩阵中，第i行元行元素是由结点素是由结点vi出发的弧所确定，故第出发的弧所确定，故第i行中值为行中值为1的元素数目等于结点的元素数目等于结点vi的出度。

42、同理，第的出度。同理，第j列中列中值为值为1的元素数目等于结点的元素数目等于结点vj的入度。即的入度。即d+(vi)=和和d-(vj)=。第58页，此课件共76页哦由给定简单图由给定简单图G的邻接矩阵的邻接矩阵A可计算出矩阵可计算出矩阵A的的l次幂，即次幂，即Al。若第。若第i行第行第j列上的元素列上的元素alij便是便是G中从第中从第i个结点个结点vi到第到第j个结点个结点vj长度为长度为l的链（或的链（或路）的数目。为说明此事实，今给出下面定理。路）的数目。为说明此事实，今给出下面定理。定理定理10.3.1 设设A为简单图为简单图G的邻接矩阵，则的邻接矩阵，则Al中的中的i行行j列元素列元

43、素alij等于等于G中联结中联结vi到到vj的长度为的长度为l的链的链(或路或路)的数目。的数目。第59页，此课件共76页哦在在一一些些实实际际问问题题中中，有有时时要要判判定定图图中中结结点点vi到到结结点点vj是是否否可可达达，或或者者说说vi到到vj是是否否存存在在一一要要链链（或或路路）。如如果果要要利利用用图图G的的邻邻接接矩矩阵阵A，则则应应计计算算A2，A3，An，。当当发发现现其其中中某某个个Ar中中 1，就就表表明明vi可可达达vj或或vi到到vj存存在在一一条条链链（或或路路）。但但这这种种计计算算繁繁琐琐量量大大，又又不不知知计计算算Ar到何时为止。到何时为止。第60页，

44、此课件共76页哦根据定理根据定理10.2.2可知，对于有可知，对于有n个结点的图，个结点的图，任何基本链（或路）的长度不大于任何基本链（或路）的长度不大于n-1和任何基和任何基本圈（或回路）的长度不大于本圈（或回路）的长度不大于n。因此，只需考。因此，只需考虑虑 就可以了，其中就可以了，其中1rn。即只要计算。即只要计算Bn=A+A2+A3+An。如果关心的是结点间可达性或结点间是否如果关心的是结点间可达性或结点间是否有链（或路），至于结点间的链存在多少条及有链（或路），至于结点间的链存在多少条及长度是多少无关紧要，那么便可用下面的定义长度是多少无关紧要，那么便可用下面的定义图的可达矩阵来表示

45、结点间可达性。图的可达矩阵来表示结点间可达性。第61页，此课件共76页哦定义定义10.3.2 给定图给定图G=，将其结点，将其结点按下标编序得按下标编序得V=v1，v2，vn。定义一个。定义一个n阶方阵阶方阵P=(pij)，其中，其中 1 vi到到vj可达可达Pij=0 否则否则则称矩阵则称矩阵P是图是图G的可达矩阵。的可达矩阵。第62页，此课件共76页哦可见，可达矩阵表明了图中任意两结点间可见，可达矩阵表明了图中任意两结点间是否至少存在一条链是否至少存在一条链(或路或路)以及在结点处是否有以及在结点处是否有圈圈(或回路或回路)。从图从图G的邻接矩阵的邻接矩阵A可以得到可达矩阵可以得到可达矩阵

46、P，即令即令Bn=A+A2+A3+An，再从，再从Bn中非零元素改中非零元素改为为1而零元素不变，这种变换后的矩阵即是可达而零元素不变，这种变换后的矩阵即是可达矩阵矩阵P。第63页，此课件共76页哦假假 设设 矩矩 阵阵 中中 的的 元元 素素 是是 属属 于于 布布 尔尔 代代 数数的的B中中元元素素，其其中中B=0,1，则则称称该该矩矩阵阵为为布布尔尔矩矩阵阵。显显然然邻邻接接矩矩阵阵是是一一个个布布尔尔矩矩阵阵，同同样样可可达达矩矩阵阵也也是是布布尔尔矩矩阵阵。下下面面定定义义两个布尔矩阵两个布尔矩阵B与与C的运算：的运算：第64页，此课件共76页哦令令B和和C的布尔和、布尔积分别记为的

47、布尔和、布尔积分别记为B C和和BoC，其定义为，其定义为(B C)ij=bij cij(BoC)ij=(bik ckj)i,j=1,2,n。其中。其中bij，cij分别是分别是B和和C的的i行行j列元素。列元素。第65页，此课件共76页哦特别地，对于邻接矩阵特别地，对于邻接矩阵A，记，记AoA=A(2)，对，对任何任何r=2,3,有有A(r-1)oA=A(r)要注意的是要注意的是Ar与与A(r)的差别。的差别。Ar中中 表明从表明从vi到到vj长度为长度为r的链（或路）的数目，而的链（或路）的数目，而A(r)中中 是指出：若是指出：若vi到到vj至少存在一条链（或路）时，至少存在一条链（或路

48、）时，=1，否则，否则，=0。由上说明，便得到可达矩阵由上说明，便得到可达矩阵P为：为：P=A A(2)A(3)A(n)=A(k)第66页，此课件共76页哦对对 于于 简简 单单 有有 向向 图图G=，显显 然然 有有E V V。因因此此，弧弧集集合合E可可解解释释成成B中中的的二二元元关关系系，而而二二元元关关系系是是可可用用矩矩阵阵表表示示的的，通通常常称称这种矩阵为关系矩阵，其定义如下：这种矩阵为关系矩阵，其定义如下：第67页，此课件共76页哦设两个有限集合设两个有限集合X=x1,x2,xm 和和Y=y1,y2,yn，则关系，则关系R X Y的关系矩阵的关系矩阵MR=(rij)，其中，其

49、中1,R rij=0,否则否则i=1,2,m；j=1,2,n。第68页，此课件共76页哦由定义可知，关系由定义可知，关系R与其关系矩阵与其关系矩阵MR是一是一一对应的，即可以相互确定。一对应的，即可以相互确定。根据集合论可知，对于域根据集合论可知，对于域F(R)=V而而|V|=n的的关系关系R的传递闭包的传递闭包R+可计算如下：可计算如下：R+=RR2R3Rk (kn)于是，关系于是，关系R1和和R2的关系矩阵分别为的关系矩阵分别为A1和和A2，则关系，则关系R1R2的关系矩阵为的关系矩阵为A1 A2。用归纳。用归纳法可以证明法可以证明R+的关系矩阵是的关系矩阵是 =第69页，此课件共76页哦

50、对于对于G=的邻接矩阵的邻接矩阵A是关系是关系E的关系的关系矩阵，因为矩阵，因为E2=EoE，即若存在一个结点，即若存在一个结点vk，使，使得得viEvk，和，和vkEvj，则必有，则必有viE2vj，亦即从，亦即从vi到到vj若若至少存在一条长度为至少存在一条长度为2的链（或路），那么的链（或路），那么E2的的关系矩阵中的关系矩阵中的(i,j)元素值为元素值为1。这表明矩阵。这表明矩阵A(2)是是关系关系E2的关系矩阵。以此类推，的关系矩阵。以此类推，A(k)是是Ek的关系的关系矩阵，矩阵，k=2,3,n。因此。因此A+=A A(2)A(3)A(n)亦即亦即 A+=A A(2)A(3)A(n