《离散数学图的概念与表示》由会员分享，可在线阅读，更多相关《离散数学图的概念与表示（79页珍藏版）》请在金锄头文库上搜索。
1、第十六章第十六章 图的概念与表示图的概念与表示16.1 图的基本概念图的基本概念16.2 链链(或路或路)与圈与圈(或回路或回路)16.4 图的矩阵表示图的矩阵表示退出退出16.1 图的基本概念图的基本概念什什什什么么么么是是是是图图图图? ?可可可可用用用用一一一一句句句句话话话话概概概概括括括括，即即即即：图图图图是是是是用用用用点点点点和和和和线线线线来来来来刻刻刻刻划划划划离离离离散散散散事事事事物物物物集集集集合合合合中中中中的的的的每每每每对对对对事事事事物物物物间间间间以以以以某某某某种方式相联系的数学模型。种方式相联系的数学模型。种方式相联系的数学模型。种方式相联系的数学模型。
2、因因因因为为为为它它它它显显显显得得得得太太太太抽抽抽抽象象象象，不不不不便便便便于于于于理理理理解解解解，所所所所以以以以有有有有必必必必要要要要给给给给出出出出另另另另外外外外的的的的回回回回答答答答。下下下下面面面面便便便便是是是是把把把把图图图图作作作作为为为为代代代代数数数数结构的一个定义。结构的一个定义。结构的一个定义。结构的一个定义。定义定义定义定义16.1.116.1.1 一个图一个图一个图一个图G G定义为一个三元组定义为一个三元组定义为一个三元组定义为一个三元组 ，记作，记作，记作，记作G G= 。其中。其中。其中。其中V V是个非是个非是个非是个非空有限集合，它的元素称为
3、结点；空有限集合，它的元素称为结点；空有限集合，它的元素称为结点；空有限集合，它的元素称为结点；E E也是个有限也是个有限也是个有限也是个有限集合，其元素称为边，而集合，其元素称为边，而集合，其元素称为边，而集合，其元素称为边，而 是从是从是从是从E E到到到到V V中的有序中的有序中的有序中的有序对或无序对的映射。对或无序对的映射。对或无序对的映射。对或无序对的映射。由定义可知，图由定义可知，图由定义可知，图由定义可知，图G G中的每条边都与图中的中的每条边都与图中的中的每条边都与图中的中的每条边都与图中的无序或有序结点对相联系的。若边无序或有序结点对相联系的。若边无序或有序结点对相联系的。
4、若边无序或有序结点对相联系的。若边e eE E与无序与无序与无序与无序结点对结点对结点对结点对v vi i，v vj j相联系，则相联系，则相联系，则相联系，则 ( (e e)=)=v vi i，v vj j，这，这，这，这时边时边时边时边e e称为无向边，有时简称为边；若边称为无向边，有时简称为边；若边称为无向边，有时简称为边；若边称为无向边，有时简称为边；若边e eE E与与与与有序结点对有序结点对有序结点对有序结点对 相联系，则相联系，则相联系，则相联系，则 ( (e e)=)= ，此时边此时边此时边此时边e e称为有向边或弧，称为有向边或弧，称为有向边或弧，称为有向边或弧，v vi i
5、称为弧称为弧称为弧称为弧e e的始结点，的始结点，的始结点，的始结点，v vj j称为弧称为弧称为弧称为弧e e的终结点。的终结点。的终结点。的终结点。若结点若结点若结点若结点v vi i与与与与v vj j由一条边由一条边由一条边由一条边( (或弧或弧或弧或弧) )e e所联结，则所联结，则所联结，则所联结，则称结点称结点称结点称结点v vi i和和和和v vj j是边是边是边是边( (或弧或弧或弧或弧) )e e的端结点；同时也称结的端结点；同时也称结的端结点；同时也称结的端结点；同时也称结点点点点v vi i与与与与v vj j是邻接结点，记作是邻接结点，记作是邻接结点，记作是邻接结点，
6、记作v vi i adj adj v vj j；否则为非邻；否则为非邻；否则为非邻；否则为非邻接结点，记作接结点，记作接结点，记作接结点，记作v vi i nadj nadj v vj j；也说边；也说边；也说边；也说边( (或弧或弧或弧或弧) )e e关联关联关联关联v vi i与与与与v vj j或说结点或说结点或说结点或说结点v vi i与与与与v vj j关联边关联边关联边关联边( (或弧或弧或弧或弧) )e e。关联同一个结。关联同一个结。关联同一个结。关联同一个结点的两条边或弧称为邻接边或弧。而联结一结点的两条边或弧称为邻接边或弧。而联结一结点的两条边或弧称为邻接边或弧。而联结一结
7、点的两条边或弧称为邻接边或弧。而联结一结点与它自身的一条边，称为环。环的方向是无点与它自身的一条边，称为环。环的方向是无点与它自身的一条边，称为环。环的方向是无点与它自身的一条边，称为环。环的方向是无意义的。意义的。意义的。意义的。如果把图如果把图如果把图如果把图G G中的弧或边总看作联结两个结点，则图中的弧或边总看作联结两个结点，则图中的弧或边总看作联结两个结点，则图中的弧或边总看作联结两个结点，则图G G可简记为可简记为可简记为可简记为G G= ，其中，其中，其中，其中V V是非空结点集，是非空结点集，是非空结点集，是非空结点集，E E是联结是联结是联结是联结结点的边集或弧集。结点的边集或
8、弧集。结点的边集或弧集。结点的边集或弧集。定义定义定义定义16.1.216.1.2 在图在图在图在图G G= 中，如果每条边都是弧，中，如果每条边都是弧，中，如果每条边都是弧，中，如果每条边都是弧，该图称为有向图；若每条边都是无向边，该图该图称为有向图；若每条边都是无向边，该图该图称为有向图；若每条边都是无向边，该图该图称为有向图；若每条边都是无向边，该图G G称为无称为无称为无称为无向图；如果有些边是有向边，另一些边是无向边，图向图；如果有些边是有向边，另一些边是无向边，图向图；如果有些边是有向边，另一些边是无向边，图向图；如果有些边是有向边，另一些边是无向边，图G G称为混合图。称为混合图
9、。称为混合图。称为混合图。定定定定义义义义16.1.316.1.3 在在在在图图图图G G= 中中中中，如如如如果果果果任任任任何何何何两两两两结结结结点点点点间间间间不不不不多多多多于于于于一一一一条条条条边边边边( (对对对对于于于于有有有有向向向向图图图图中中中中，任任任任何何何何两两两两结结结结点点点点间间间间不不不不多多多多于于于于一一一一条条条条同同同同向向向向弧弧弧弧) )，并并并并且且且且任任任任何何何何结结结结点点点点无无无无环环环环，则则则则图图图图G G称称称称为为为为简简简简单单单单图图图图；若若若若两两两两结结结结点点点点间间间间多多多多于于于于一一一一条条条条边边边
10、边( (对对对对于于于于有有有有向向向向图图图图中中中中，两两两两结结结结点点点点间间间间多多多多于于于于一一一一条条条条同同同同向向向向弧弧弧弧) )图图图图G G称称称称为为为为多多多多重重重重图图图图，并并并并把把把把联联联联结结结结两两两两结结结结点点点点之之之之间间间间的的的的多多多多条条条条边或弧，称为平行边或弧，平行边或弧的条数称为重数。边或弧，称为平行边或弧，平行边或弧的条数称为重数。边或弧，称为平行边或弧，平行边或弧的条数称为重数。边或弧，称为平行边或弧，平行边或弧的条数称为重数。定定定定义义义义16.1.416.1.4 给给给给每每每每条条条条边边边边或或或或弧弧弧弧都都都
11、都赋赋赋赋予予予予权权权权的的的的图图图图G G= ，称称称称为为为为加加加加权权权权图图图图，记记记记为为为为G G= ，其其其其中中中中WW表表表表示示示示各各各各边边边边之权的集合。之权的集合。之权的集合。之权的集合。加加加加权权权权图图图图在在在在实实实实际际际际中中中中有有有有许许许许多多多多应应应应用用用用，如如如如在在在在输输输输油油油油管管管管系系系系统统统统图图图图中中中中权权权权表表表表示示示示单单单单位位位位时时时时间间间间流流流流经经经经管管管管中中中中的的的的石石石石油油油油数数数数量量量量；在在在在城城城城市市市市街街街街道道道道中中中中，权权权权表表表表示示示示表
12、表表表示示示示通通通通行行行行车车车车辆辆辆辆密密密密度度度度；在在在在航航航航空空空空交交交交通通通通图图图图中中中中，权权权权表表表表示示示示两两两两城市的距离等等。城市的距离等等。城市的距离等等。城市的距离等等。定定定定义义义义16.1.516.1.5 在在在在无无无无向向向向图图图图G G= 中中中中，如如如如果果果果V V中的每个结点都与其余的所有结点邻接，即中的每个结点都与其余的所有结点邻接，即中的每个结点都与其余的所有结点邻接，即中的每个结点都与其余的所有结点邻接，即( ( v vi i)( )( v vj j)( )(v vi i，v vj jV Vv vi i，v vj jE
13、 E) )则则则则该该该该图图图图称称称称为为为为无无无无向向向向完完完完全全全全图图图图，记记记记作作作作K K| |V V| |。若若若若| |V V|=|=n n，该图记作，该图记作，该图记作，该图记作K Kn n。 在在一一个个图图中中，如如果果一一个个结结点点不不与与任任何何其其他他结结点点邻邻接接，则则该该结结点点称称为为孤孤立立结结点点。仅仅有有孤孤立立结结点点的的图图称称为为零零图图。显显然然，在在零零图图中中边边集集为为空空集集。若若一一个个图图中中只只含含一一个个孤孤立结点，该图称为平凡图。立结点，该图称为平凡图。定定定定义义义义16.1.616.1.6 在在在在有有有有向
14、向向向图图图图G G= 中中中中，对对对对任任任任意意意意结结结结点点点点v vV V，以以以以v v为为为为始始始始结结结结点点点点的的的的弧弧弧弧的的的的条条条条数数数数，称称称称为为为为结结结结点点点点v v的的的的出出出出度度度度，记记记记为为为为d d+ +( (v v) )；以以以以v v为为为为终终终终结结结结点点点点的的的的弧弧弧弧的的的的条条条条条条条条数数数数，称称称称为为为为v v的的的的入入入入度度度度，记记记记作作作作d d- -( (v v) )；结结结结点点点点v v的的的的出出出出度度度度与与与与入入入入度度度度之之之之和和和和，称称称称为为为为结结结结点点点点
15、的的的的度度度度数数数数，记为记为记为记为d d( (v v) )，显然，显然，显然，显然d d( (v v)=)=d d+ +( (v v)+)+d d- -( (v v) )。对对对对于于于于无无无无向向向向图图图图G G= ，结结结结点点点点v vV V的的的的度度度度数数数数等等等等于于于于联联联联结结结结它它它它的的的的边边边边数数数数，也也也也记记记记为为为为d d( (v v) )。若若若若v v点点点点有有有有环环环环，规规规规定定定定该该该该点点点点度度度度因因因因环环环环而增加而增加而增加而增加2 2。显然，对于孤立结点的度数为零。显然，对于孤立结点的度数为零。显然，对于孤
16、立结点的度数为零。显然，对于孤立结点的度数为零。此外，对于无向图此外，对于无向图此外，对于无向图此外，对于无向图G G= ，记，记，记，记 ( (G G) )或或或或 = =maxmax d d( (v v)| )|v vV V ( (G G) )或或或或 = =minmin d d( (v v)| )|v vV V 它们分别称为图它们分别称为图它们分别称为图它们分别称为图G G的最大度和最小度。的最大度和最小度。的最大度和最小度。的最大度和最小度。关于无向图中的结点的度，欧拉给出一个关于无向图中的结点的度，欧拉给出一个关于无向图中的结点的度，欧拉给出一个关于无向图中的结点的度，欧拉给出一个定
17、理，这是图论中的第一个定理。定理，这是图论中的第一个定理。定理，这是图论中的第一个定理。定理，这是图论中的第一个定理。定理定理定理定理16.1.116.1.1 给定无向图给定无向图给定无向图给定无向图G G= ，则，则，则，则定理定理定理定理16.1.216.1.2 在任何无向图中，奇度结点的在任何无向图中，奇度结点的在任何无向图中，奇度结点的在任何无向图中，奇度结点的数目为偶数。数目为偶数。数目为偶数。数目为偶数。定定定定义义义义16.1.716.1.7 在在在在无无无无向向向向图图图图G G= 中中中中，如如如如果果果果每每每每个个个个结结结结点点点点的的的的度度度度是是是是k k，即即即
18、即( ( v v)( )(v vV Vd d( (v v)=)=k k) )，则则则则图图图图G G称为称为称为称为k k度正则图。度正则图。度正则图。度正则图。显然，对于显然，对于显然，对于显然，对于k k度正则图度正则图度正则图度正则图G G， ( (G G)=)= ( (G G)=)=k k。定定定定义义义义16.1.816.1.8 给给给给定定定定无无无无向向向向图图图图G G1 1= 和和和和G G2 2= ，于是，于是，于是，于是(1) (1) 如如如如果果果果V V2 2 V V1 1和和和和E E2 2 E E1 1，则则则则称称称称G G2 2为为为为G G1 1的的的的子子
19、子子图图图图，记记记记为为为为G G2 2 G G1 1。(2) (2) 如如如如果果果果V V2 2 V V1 1，E E2 2 E E1 1且且且且E E2 2 E E1 1，则则则则称称称称G G2 2为为为为G G1 1的的的的真子图，记为真子图，记为真子图，记为真子图，记为G G2 2 G G1 1。(3) (3) 如如如如果果果果V V2 2= =V V1 1，E E2 2 E E1 1，则则则则称称称称G G2 2为为为为G G1 1的的的的生生生生成成成成子子子子图图图图，记为记为记为记为G G2 2 G G1 1。定定定定义义义义16.1.916.1.9 设设设设图图图图G
20、G2 2= 是是是是图图图图G G1 1= 的的的的子子子子图图图图。若若若若对对对对任任任任意意意意结结结结点点点点u u和和和和v v，如如如如果果果果u u，v vE E1 1，有有有有u u，v vE E2 2，则则则则G G2 2由由由由V V2 2唯唯唯唯一一一一地地地地确确确确定定定定，并并并并称称称称G G2 2是是是是结结结结点点点点集集集集合合合合V V2 2的的的的诱诱诱诱导导导导子子子子图图图图，记记记记作作作作 或或或或G GV V2 2；如如如如果果果果G G2 2无无无无孤孤孤孤立立立立结结结结点点点点，且且且且由由由由E E2 2所所所所唯唯唯唯一一一一确确确确
21、定定定定，则则则则称称称称G G2 2是是是是边边边边集集集集E E2 2的的的的诱诱诱诱导导导导子子子子图图图图，记为记为记为记为 或或或或G GE E2 2。定定义义16.1.10 设设图图G1=和和图图G2=是是图图G=的的子子图图。如如果果E2=E-E1且且G2=，则则称称图图G2是是相相对对于图于图G的子图的子图G1的补图。的补图。定定定定义义义义16.1.1116.1.11 给给给给定定定定图图图图G G= ，若若若若存存存存在在在在图图图图G G1 1= ，并并并并且且且且E E1 1 E E= =和和和和图图图图 是是是是完完完完全全全全图图图图，则则则则G G1 1称称称称为
22、为为为相相相相对对对对于于于于完完完完全全全全图图图图的的的的G G的的的的补补补补图图图图，简称简称简称简称G G1 1是是是是G G的补图，并记为的补图，并记为的补图，并记为的补图，并记为G G1 1= = 。显然，显然，显然，显然，G G与与与与 互为补图。互为补图。互为补图。互为补图。在在在在图图图图的的的的定定定定义义义义中中中中，强强强强调调调调的的的的是是是是结结结结点点点点集集集集、边边边边集集集集以以以以及及及及边边边边与与与与结结结结点点点点的的的的关关关关联联联联关关关关系系系系，既既既既没没没没有有有有涉涉涉涉及及及及到到到到联联联联结结结结两两两两个个个个结结结结点点
23、点点的的的的边边边边的的的的长长长长度度度度、形形形形状状状状和和和和位位位位置置置置，也也也也没没没没有有有有给给给给出出出出结结结结点点点点的的的的位位位位置置置置或或或或者者者者规规规规定定定定任任任任何何何何次次次次序序序序。因因因因此此此此，对对对对于于于于给给给给定定定定的的的的两两两两个个个个图图图图，在在在在它它它它们们们们的的的的图图图图形形形形表表表表示示示示中中中中，即即即即在在在在用用用用小小小小圆圆圆圆圈圈圈圈表表表表示示示示结结结结点点点点和和和和用用用用直直直直线线线线或或或或曲曲曲曲线线线线表表表表示示示示联联联联结结结结两两两两个个个个结结结结点点点点的的的的
24、边边边边的的的的图图图图解解解解中中中中，看看看看起起起起来来来来很很很很不不不不一一一一样样样样，但但但但实实实实际际际际上上上上却却却却是是是是表表表表示示示示同同同同一一一一个个个个图图图图。因因因因而而而而，引引引引入入入入两两两两图图图图的的的的同同同同构构构构概概概概念便是十分必要的了。念便是十分必要的了。念便是十分必要的了。念便是十分必要的了。定定定定义义义义16.1.1216.1.12 给给给给定定定定无无无无向向向向图图图图( (或或或或有有有有向向向向图图图图) )G G1 1= 和和和和G G2 2= 。若若若若存存存存在在在在双双双双射射射射f fV V2 2V V1
25、1，使使使使得得得得对对对对任任任任意意意意v v，u uV V1 1，有有有有u u，v vE E1 1f f( (u u) )，f f( (v v) )E E2 2( (或或或或 E E1 1 )E E2 2) )则称则称则称则称G G1 1同构于同构于同构于同构于G G2 2，记为，记为，记为，记为G G1 1 G G2 2。显显显显然然然然，两两两两图图图图的的的的同同同同构构构构是是是是相相相相互互互互的的的的，即即即即G G1 1同同同同构构构构于于于于G G2 2，G G2 2同构于同构于同构于同构于G G1 1。由由由由同同同同构构构构的的的的定定定定义义义义可可可可知知知知，
26、不不不不仅仅仅仅结结结结点点点点之之之之间间间间要要要要具具具具有有有有一一一一一一一一对对对对应应应应关关关关系系系系，而而而而且且且且要要要要求求求求这这这这种种种种对对对对应应应应关关关关系系系系保保保保持持持持结结结结点点点点间间间间的的的的邻邻邻邻接接接接关关关关系系系系。对于有向图的同构还要求保持边的方向。对于有向图的同构还要求保持边的方向。对于有向图的同构还要求保持边的方向。对于有向图的同构还要求保持边的方向。一一般般说说来来，证证明明两两个个图图是是同同构构的的并并非非是是轻轻而而易易举举的的事事情情，往往往往需需要要花花些些气气力力。请读者证明图请读者证明图16.1.13中两
27、个图是同构的。中两个图是同构的。根据图的同构定义，可以给出图同构的必根据图的同构定义，可以给出图同构的必根据图的同构定义，可以给出图同构的必根据图的同构定义，可以给出图同构的必要条件如下：要条件如下：要条件如下：要条件如下：(1) (1) 结点数目相等；结点数目相等；结点数目相等；结点数目相等；(2) (2) 边数相等；边数相等；边数相等；边数相等；(3) (3) 度数相同的结点数目相等。度数相同的结点数目相等。度数相同的结点数目相等。度数相同的结点数目相等。但这仅仅是必要条件而不是充分条件。但这仅仅是必要条件而不是充分条件。但这仅仅是必要条件而不是充分条件。但这仅仅是必要条件而不是充分条件。
28、 满足上述三个条件，然而并不满足上述三个条件，然而并不满足上述三个条件，然而并不满足上述三个条件，然而并不同构。因此在同构。因此在同构。因此在同构。因此在( (a a) )中度数为中度数为中度数为中度数为3 3的结点的结点的结点的结点x x与两个度数为与两个度数为与两个度数为与两个度数为1 1的结点邻接，而的结点邻接，而的结点邻接，而的结点邻接，而( (b b) )中度数为中度数为中度数为中度数为3 3的结点的结点的结点的结点y y仅与一个度仅与一个度仅与一个度仅与一个度数为数为数为数为1 1的结点邻接。的结点邻接。的结点邻接。的结点邻接。寻找一种简单有效的方法来判定图的同构，寻找一种简单有效
29、的方法来判定图的同构，寻找一种简单有效的方法来判定图的同构，寻找一种简单有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。至今仍是图论中悬而未决的重要课题。至今仍是图论中悬而未决的重要课题。至今仍是图论中悬而未决的重要课题。 例如例如例如例如图图图图10.1.1410.1.14中中中中( (a a) )与与与与( (b b) )图 10.1.13返回返回返回返回图图 1.1.1416.2 链链(或路或路)与圈与圈(或回路或回路)在在在在无无无无向向向向图图图图( (或或或或有有有有向向向向图图图图) )的的的的研研研研究究究究中中中中，常常常常常常常常考考考考虑虑虑虑从从从从一一一一
30、个个个个结结结结点点点点出出出出发发发发，沿沿沿沿着着着着一一一一些些些些边边边边( (或或或或弧弧弧弧) )连连连连续续续续移移移移动动动动而而而而达达达达到到到到另另另另一一一一个个个个指指指指定定定定结结结结点点点点，这这这这种种种种依依依依次次次次由由由由结结结结点点点点和和和和边边边边( (或弧或弧或弧或弧) )组成的序列，便形成了链组成的序列，便形成了链组成的序列，便形成了链组成的序列，便形成了链( (或路或路或路或路) )的概念。的概念。的概念。的概念。定义定义定义定义16.2.116.2.1 给定无向图给定无向图给定无向图给定无向图( (或有向图或有向图或有向图或有向图) )G
31、 G= 。令。令。令。令v v0 0，v v1 1，v vmmV V，边，边，边，边( (或弧或弧或弧或弧) )e e1 1，e e2 2，e emmE E，其，其，其，其中中中中v vi i-1-1，v vi i是是是是e ei i的结点，交替序列的结点，交替序列的结点，交替序列的结点，交替序列v v0 0e e1 1v v1 1e e2 2v v2 2e emmv vmm称为连接称为连接称为连接称为连接v v0 0到到到到v vmm的链的链的链的链( (或路或路或路或路) )。v v0 0和和和和v vmm分别称为链分别称为链分别称为链分别称为链( (或路或路或路或路) )的始结点的始结点
32、的始结点的始结点和终结点，而边和终结点，而边和终结点，而边和终结点，而边( (或弧或弧或弧或弧) )的数目称为链的数目称为链的数目称为链的数目称为链( (或路或路或路或路) )的长度。若的长度。若的长度。若的长度。若v v0 0= =v vmm时，该链时，该链时，该链时，该链( (或路或路或路或路) )称为圈称为圈称为圈称为圈( (或回路或回路或回路或回路) )。定义定义定义定义16.2.216.2.2 在一条链在一条链在一条链在一条链( (或路或路或路或路) )中，若出现的中，若出现的中，若出现的中，若出现的边边边边( (或弧或弧或弧或弧) )都是不相同的，称该链都是不相同的，称该链都是不相
33、同的，称该链都是不相同的，称该链( (或路或路或路或路) )为简单为简单为简单为简单链链链链( (或简单路或简单路或简单路或简单路) )；若出现的结点都是不相同的，；若出现的结点都是不相同的，；若出现的结点都是不相同的，；若出现的结点都是不相同的，称该链称该链称该链称该链( (或路或路或路或路) )为基本链为基本链为基本链为基本链( (或基本路或基本路或基本路或基本路) )。显然，每条基本链显然，每条基本链显然，每条基本链显然，每条基本链( (或基本路或基本路或基本路或基本路) )必定是简单必定是简单必定是简单必定是简单链链链链( (或简单路或简单路或简单路或简单路) )。定义定义定义定义16
34、.2.316.2.3 在一圈在一圈在一圈在一圈( (或回路或回路或回路或回路) )中，若出现的每条边中，若出现的每条边中，若出现的每条边中，若出现的每条边( (或弧或弧或弧或弧) )恰好一次，称该圈恰好一次，称该圈恰好一次，称该圈恰好一次，称该圈( (或回路或回路或回路或回路) )为简单圈为简单圈为简单圈为简单圈( (或简单回或简单回或简单回或简单回路路路路) )；若出现的每个结点恰好一次，称该圈；若出现的每个结点恰好一次，称该圈；若出现的每个结点恰好一次，称该圈；若出现的每个结点恰好一次，称该圈( (或回路或回路或回路或回路) )为为为为基本圈基本圈基本圈基本圈( (或基本回路或基本回路或基
35、本回路或基本回路) )。可以看出，对于简单图来说，链可以看出，对于简单图来说，链可以看出，对于简单图来说，链可以看出，对于简单图来说，链( (或路或路或路或路) )和圈和圈和圈和圈( (或回或回或回或回路路路路) )能够仅用结点序列表示之。能够仅用结点序列表示之。能够仅用结点序列表示之。能够仅用结点序列表示之。定定定定理理理理16.2.116.2.1 在在在在一一一一个个个个图图图图中中中中，若若若若从从从从结结结结点点点点v vi i到到到到结结结结点点点点v vj j存存存存在在在在一一一一条条条条链链链链( (或或或或路路路路) )，则则则则必必必必有有有有一一一一条条条条从从从从v v
36、i i到到到到v vj j的的的的基基基基本链本链本链本链( (或基本路或基本路或基本路或基本路) )。定理定理定理定理16.2.216.2.2 在一个具有在一个具有在一个具有在一个具有n n个结点的图中，则个结点的图中，则个结点的图中，则个结点的图中，则(1) (1) 任何基本链任何基本链任何基本链任何基本链( (或路或路或路或路) )的长度均不大于的长度均不大于的长度均不大于的长度均不大于n n-1-1。(2) (2) 任何基本圈任何基本圈任何基本圈任何基本圈( (或路或路或路或路) )的长度均不大于的长度均不大于的长度均不大于的长度均不大于n n。定定定定义义义义16.2.416.2.4
37、 在在在在一一一一个个个个图图图图中中中中，若若若若从从从从v vi i到到到到v vj j存存存存在在在在任任任任何何何何一一一一条条条条链链链链( (或路或路或路或路) )，则称从，则称从，则称从，则称从v vi i到到到到v vj j是可达的，或简称是可达的，或简称是可达的，或简称是可达的，或简称v vi i可达可达可达可达v vj j。为完全起见，规定每个结点到其自身是可达的。为完全起见，规定每个结点到其自身是可达的。为完全起见，规定每个结点到其自身是可达的。为完全起见，规定每个结点到其自身是可达的。对对对对于于于于无无无无向向向向图图图图G G来来来来说说说说，不不不不难难难难证证证
38、证明明明明结结结结点点点点间间间间的的的的可可可可达达达达性性性性是是是是结结结结点点点点集集集集合合合合上上上上的的的的等等等等价价价价关关关关系系系系。因因因因此此此此它它它它将将将将结结结结点点点点集集集集合合合合给给给给出出出出一一一一个个个个划划划划分分分分，并并并并且且且且划划划划分分分分中中中中的的的的每每每每个个个个元元元元素素素素形形形形成成成成一一一一个个个个诱诱诱诱导导导导子子子子图图图图；两两两两结结结结点点点点之之之之间间间间是是是是可可可可达达达达的的的的当当当当且且且且仅仅仅仅当当当当它它它它们们们们属属属属于于于于同同同同一一一一个个个个子子子子图图图图，称称称
39、称这这这这种种种种子子子子图图图图为为为为图图图图G G的连通分图，图的连通分图，图的连通分图，图的连通分图，图G G的连通分图的个数，记为的连通分图的个数，记为的连通分图的个数，记为的连通分图的个数，记为 ( (G G) )。定义定义定义定义16.2.516.2.5 若图若图若图若图G G只有一个连通分图，则称只有一个连通分图，则称只有一个连通分图，则称只有一个连通分图，则称G G是连是连是连是连通图；否则，称图通图；否则，称图通图；否则，称图通图；否则，称图G G为非连通图或分离图。为非连通图或分离图。为非连通图或分离图。为非连通图或分离图。在在在在图图图图的的的的研研研研究究究究中中中中
40、，常常常常常常常常需需需需要要要要考考考考虑虑虑虑删删删删去去去去与与与与增增增增加加加加结结结结点点点点、结结结结点点点点集集集集、边边边边和和和和边边边边集集集集（或或或或弧弧弧弧集集集集）的的的的问问问问题题题题。所所所所谓谓谓谓从从从从图图图图G G= 中中中中删删删删去去去去结结结结点点点点集集集集S S，是是是是指指指指作作作作V V- -S S以以以以及及及及从从从从E E中中中中删删删删去去去去与与与与S S中中中中的的的的全全全全部部部部结结结结点点点点相相相相联联联联结结结结的的的的边边边边而而而而得得得得到到到到的的的的子子子子图图图图，记记记记作作作作G G- -S S
41、；特特特特别别别别当当当当S S=|=|v v| |时时时时，简简简简记记记记为为为为G G- -v v；所所所所谓谓谓谓从从从从图图图图G G= 中中中中删删删删去去去去边边边边集集集集（或或或或弧弧弧弧集集集集）T T，是是是是指指指指作作作作E E- -T T，且且且且T T中中中中的的的的全全全全部部部部边边边边所所所所关关关关联联联联的的的的结结结结点点点点仍仍仍仍在在在在V V中中中中而而而而得得得得到到到到的的的的子子子子图图图图，记记记记为为为为G G- -T T；特特特特别别别别当当当当T T=e e 时时时时，简记作简记作简记作简记作G G- -e e。所谓图所谓图所谓图所
42、谓图G G= 增加结点集增加结点集增加结点集增加结点集S S，是指作，是指作，是指作，是指作V VT T以及向以及向以及向以及向E E中并入中并入中并入中并入S S中、中、中、中、S S与与与与V V中所成的边而得中所成的边而得中所成的边而得中所成的边而得到的图，记作到的图，记作到的图，记作到的图，记作G G+ +S S；特别当；特别当；特别当；特别当S S=v v 时，简记为时，简记为时，简记为时，简记为G G+ +v v；图；图；图；图G G= 增加边集（或弧集）增加边集（或弧集）增加边集（或弧集）增加边集（或弧集）T T是指作是指作是指作是指作E ET T所得到的图，记作所得到的图，记作
43、所得到的图，记作所得到的图，记作G G+ +T T，这里，这里，这里，这里T T中全部边中全部边中全部边中全部边（或弧）的关联结点属于（或弧）的关联结点属于（或弧）的关联结点属于（或弧）的关联结点属于V V。定义定义定义定义16.2.616.2.6 给定连通无向图给定连通无向图给定连通无向图给定连通无向图G G= ，S S V V。若若若若 ( (G G- -S S) ) ( (G G) )，但，但，但，但 T T S S有有有有 ( (G G- -T T)=)= ( (G G) )，则称，则称，则称，则称S S是是是是G G的一个分离结点集。若图的一个分离结点集。若图的一个分离结点集。若图的
44、一个分离结点集。若图G G的分离结点集的分离结点集的分离结点集的分离结点集S S=v v ，则称，则称，则称，则称v v是是是是G G的割点。的割点。的割点。的割点。类似地可定义图类似地可定义图类似地可定义图类似地可定义图G G的分离边集的分离边集的分离边集的分离边集T T；若图；若图；若图；若图G G的分离边的分离边的分离边的分离边集集集集T T=e e ，则称，则称，则称，则称e e是是是是G G的割边或桥。的割边或桥。的割边或桥。的割边或桥。对对对对于于于于连连连连通通通通的的的的非非非非平平平平凡凡凡凡图图图图G G，称称称称 ( (G G)= )= | |S S| |S S是是是是G
45、 G的的的的分分分分离离离离结结结结点点点点集集集集 为为为为图图图图G G的的的的结结结结点点点点连连连连通通通通度度度度，它它它它表表表表明明明明产产产产生生生生不不不不连连连连通通通通图图图图而而而而需需需需要要要要删删删删去去去去结结结结点点点点的的的的最最最最少少少少数数数数目目目目。于于于于是是是是，对对对对于于于于分分分分离离离离图图图图G G， ( (G G)=0)=0；对对对对于于于于存存存存在在在在割割割割点的连通图点的连通图点的连通图点的连通图G G， ( (G G)=1)=1。类似地定义边连通度类似地定义边连通度类似地定义边连通度类似地定义边连通度 ( (G G)= )
46、= | |T T| |T T是是是是G G的分离边集的分离边集的分离边集的分离边集 ，它表明产生不连通图而需要删，它表明产生不连通图而需要删，它表明产生不连通图而需要删，它表明产生不连通图而需要删去边的最少数目。可见，对于分离图去边的最少数目。可见，对于分离图去边的最少数目。可见，对于分离图去边的最少数目。可见，对于分离图G G， ( (G G)=0)=0；对于完全图；对于完全图；对于完全图；对于完全图G G， ( (G G)=0)=0；对于图；对于图；对于图；对于图K K1 1， ( (K K1 1)=0)=0；对于存在割边的连通图；对于存在割边的连通图；对于存在割边的连通图；对于存在割边的
47、连通图G G， ( (G G)=1)=1；对于完全；对于完全；对于完全；对于完全图图图图K Kn n， ( (K Kn n)=)=n n-1-1。下面是由惠特尼下面是由惠特尼下面是由惠特尼下面是由惠特尼(H.Whitney)(H.Whitney)于于于于19321932年得到的关于年得到的关于年得到的关于年得到的关于结点连通度、边连通度和最小度的不等式联系的定理：结点连通度、边连通度和最小度的不等式联系的定理：结点连通度、边连通度和最小度的不等式联系的定理：结点连通度、边连通度和最小度的不等式联系的定理：定理定理定理定理16.2.316.2.3 对于任何一个无向图对于任何一个无向图对于任何一个
48、无向图对于任何一个无向图G G，有，有，有，有 ( (G G) ( (G G) ( (G G) )。定定定定理理理理16.2.416.2.4 一一一一个个个个连连连连通通通通无无无无向向向向图图图图G G中中中中的的的的结结结结点点点点v v是是是是割割割割点点点点存在两个结点存在两个结点存在两个结点存在两个结点u u和和和和w w，使得联结，使得联结，使得联结，使得联结u u和和和和w w的每条链都经过的每条链都经过的每条链都经过的每条链都经过v v。定定定定理理理理16.2.516.2.5 一一一一个个个个连连连连通通通通无无无无向向向向图图图图G G中中中中的的的的边边边边e e是是是是
49、割割割割边边边边存存存存在两个结点在两个结点在两个结点在两个结点u u和和和和w w，使得联结，使得联结，使得联结，使得联结u u与与与与w w的每条链都经过的每条链都经过的每条链都经过的每条链都经过e e。下面再给出一个判定一条边是割边的充要条件。下面再给出一个判定一条边是割边的充要条件。下面再给出一个判定一条边是割边的充要条件。下面再给出一个判定一条边是割边的充要条件。定定定定理理理理16.2.616.2.6 连连连连通通通通无无无无向向向向图图图图G G中中中中的的的的一一一一条条条条边边边边e e是是是是割割割割边边边边e e不不不不包含在图的任何基本圈中。包含在图的任何基本圈中。包含
50、在图的任何基本圈中。包含在图的任何基本圈中。对对对对于于于于有有有有向向向向图图图图而而而而言言言言，结结结结点点点点间间间间的的的的可可可可达达达达性性性性不不不不再再再再是是是是等等等等价价价价关关关关系系系系，它它它它仅仅仅仅仅仅仅仅是是是是自自自自反反反反的的的的和和和和传传传传递递递递的的的的。一一一一般般般般说说说说来来来来，不不不不是是是是对对对对称称称称的的的的。因因因因此此此此，有有有有向向向向图图图图的的的的连连连连通通通通概概概概念念念念较较较较之无向图要复杂得多。之无向图要复杂得多。之无向图要复杂得多。之无向图要复杂得多。对对对对于于于于给给给给定定定定的的的的有有有有
51、向向向向力力力力G G，要要要要略略略略去去去去G G中中中中每每每每条条条条边边边边的的的的方向便得到一个无向图方向便得到一个无向图方向便得到一个无向图方向便得到一个无向图G G1 1，称，称，称，称G G1 1是是是是G G的基础图。的基础图。的基础图。的基础图。定义定义定义定义16.2.716.2.7 在简单有向图在简单有向图在简单有向图在简单有向图G G中，若中，若中，若中，若G G中任何两个结中任何两个结中任何两个结中任何两个结点间都是可达的，则称点间都是可达的，则称点间都是可达的，则称点间都是可达的，则称G G是强连通的；若任何两个结点是强连通的；若任何两个结点是强连通的；若任何两
52、个结点是强连通的；若任何两个结点间至少是从一个结点可达另一个结点，则称间至少是从一个结点可达另一个结点，则称间至少是从一个结点可达另一个结点，则称间至少是从一个结点可达另一个结点，则称G G是单向连是单向连是单向连是单向连通的；若有向图通的；若有向图通的；若有向图通的；若有向图G G不是单向连通的，但其基础图是连通不是单向连通的，但其基础图是连通不是单向连通的，但其基础图是连通不是单向连通的，但其基础图是连通的，则称的，则称的，则称的，则称G G是弱连通的。是弱连通的。是弱连通的。是弱连通的。从从从从上上上上面面面面定定定定义义义义可可可可知知知知，若若若若图图图图G G是是是是强强强强连连连
53、连通通通通的的的的，则则则则它它它它必必必必是是是是单单单单向向向向连连连连通通通通的的的的，但但但但反反反反之之之之未未未未必必必必真真真真；若若若若图图图图G G是是是是单单单单向向向向连连连连通通通通的的的的，则则则则它它它它必是弱连通的，反之不真。必是弱连通的，反之不真。必是弱连通的，反之不真。必是弱连通的，反之不真。定定定定理理理理16.2.716.2.7 有有有有向向向向图图图图G G是是是是强强强强连连连连通通通通的的的的G G中中中中有有有有一一一一回回回回路路路路，它至少通过每个结点一次。它至少通过每个结点一次。它至少通过每个结点一次。它至少通过每个结点一次。令令令令G G是
54、是是是简简简简单单单单有有有有向向向向图图图图，对对对对于于于于某某某某种种种种性性性性质质质质而而而而言言言言，若若若若G G中中中中再再再再没没没没有有有有其其其其它它它它包包包包含含含含子子子子图图图图G G1 1的的的的真真真真子子子子图图图图具具具具有有有有这这这这种种种种性性性性质质质质，则则则则称称称称G G1 1是是是是G G的关于该性质的极大子图。的关于该性质的极大子图。的关于该性质的极大子图。的关于该性质的极大子图。定定定定义义义义16.2.816.2.8 在在在在简简简简单单单单有有有有向向向向图图图图中中中中，具具具具有有有有强强强强连连连连通通通通性性性性质质质质的的
55、的的极极极极大大大大子子子子图图图图，称称称称为为为为强强强强分分分分图图图图；具具具具有有有有单单单单向向向向连连连连通通通通性性性性质质质质的的的的极极极极大大大大子子子子图图图图，称称称称为为为为单单单单向向向向分分分分图图图图；具具具具有有有有弱弱弱弱连连连连通通通通性性性性质质质质的的的的极极极极大大大大子子子子图图图图，称称称称为为为为弱弱弱弱分分分分图。图。图。图。定定定定理理理理16.2.816.2.8 简简简简单单单单有有有有向向向向图图图图中中中中的的的的任任任任一一一一个个个个结结结结点点点点恰恰恰恰位于一个强分图中。位于一个强分图中。位于一个强分图中。位于一个强分图中。
56、注注注注意意意意，有有有有向向向向图图图图中中中中的的的的任任任任意意意意一一一一弧弧弧弧未未未未必必必必恰恰恰恰位位位位于于于于一一一一个个个个强强强强分分分分图图图图中中中中，例例例例如如如如，在在在在图图图图10.2.610.2.6中中中中，弧弧弧弧 位位位位于于于于 结结结结 点点点点 集集集集 合合合合 v v1 1, ,v v2 2, ,v v3 3 的的的的 诱诱诱诱 导导导导 子子子子 图图图图 中中中中 ， 但但但但 弧弧弧弧 不位于任何强分图之中。不位于任何强分图之中。不位于任何强分图之中。不位于任何强分图之中。类似地可以证明下面两个定理：类似地可以证明下面两个定理：类似地
57、可以证明下面两个定理：类似地可以证明下面两个定理：定理定理定理定理16.2.916.2.9 简单有向图中的每个结点和每条弧至简单有向图中的每个结点和每条弧至简单有向图中的每个结点和每条弧至简单有向图中的每个结点和每条弧至少位于一个单向分图中。少位于一个单向分图中。少位于一个单向分图中。少位于一个单向分图中。定理定理定理定理16.2.1016.2.10 简单有向图中的每个结点和每条弧恰简单有向图中的每个结点和每条弧恰简单有向图中的每个结点和每条弧恰简单有向图中的每个结点和每条弧恰位于一个弱分图中。位于一个弱分图中。位于一个弱分图中。位于一个弱分图中。如果结点如果结点如果结点如果结点u u可达结点
58、可达结点可达结点可达结点v v，它们之间可能存在不止一，它们之间可能存在不止一，它们之间可能存在不止一，它们之间可能存在不止一条链条链条链条链( (或路或路或路或路) )。在所有这些链。在所有这些链。在所有这些链。在所有这些链( (或路或路或路或路) )中，最短链中，最短链中，最短链中，最短链( (或路或路或路或路) )的的的的长度称为结点长度称为结点长度称为结点长度称为结点u u和和和和v v之间的距离或短程线或测地线，记作之间的距离或短程线或测地线，记作之间的距离或短程线或测地线，记作之间的距离或短程线或测地线，记作d d 。距离满足下列性质：距离满足下列性质：距离满足下列性质：距离满足下
59、列性质：d d 00d d =0=0d d +d d d d 如果如果如果如果u u不可达不可达不可达不可达v v，则，则，则，则d d =+=+。此外，要注意，即使此外，要注意，即使此外，要注意，即使此外，要注意，即使u u与与与与v v相互可达，相互可达，相互可达，相互可达，d d 未必等于未必等于未必等于未必等于d d 。下面给出简单有向图的一个应用下面给出简单有向图的一个应用下面给出简单有向图的一个应用下面给出简单有向图的一个应用资源资源资源资源分配图。分配图。分配图。分配图。在多道程序的计算机系统中，可以同时执在多道程序的计算机系统中，可以同时执在多道程序的计算机系统中，可以同时执在
60、多道程序的计算机系统中，可以同时执行多个程序。实际上，程序共享计算机系统中行多个程序。实际上，程序共享计算机系统中行多个程序。实际上，程序共享计算机系统中行多个程序。实际上，程序共享计算机系统中的资源，如磁带机、磁盘设备、的资源，如磁带机、磁盘设备、的资源，如磁带机、磁盘设备、的资源，如磁带机、磁盘设备、CPUCPU、主存贮、主存贮、主存贮、主存贮器和编译程序等。操作系统对这些资源负责分器和编译程序等。操作系统对这些资源负责分器和编译程序等。操作系统对这些资源负责分器和编译程序等。操作系统对这些资源负责分配给各个程序。当一个程序要求使用某种资源，配给各个程序。当一个程序要求使用某种资源，配给各
61、个程序。当一个程序要求使用某种资源，配给各个程序。当一个程序要求使用某种资源，它要发出请求，操作系统必须保证这一请求得它要发出请求，操作系统必须保证这一请求得它要发出请求，操作系统必须保证这一请求得它要发出请求，操作系统必须保证这一请求得到满足。到满足。到满足。到满足。对资源的请求可能发生冲突。如程序对资源的请求可能发生冲突。如程序对资源的请求可能发生冲突。如程序对资源的请求可能发生冲突。如程序A A控制控制控制控制着资源着资源着资源着资源r r1 1，请求资源，请求资源，请求资源，请求资源r r2 2；但程序；但程序；但程序；但程序B B控制着资源控制着资源控制着资源控制着资源r r2 2，
62、请求资源，请求资源，请求资源，请求资源r r1 1。这种情况称为处于死锁状态。然。这种情况称为处于死锁状态。然。这种情况称为处于死锁状态。然。这种情况称为处于死锁状态。然而冲突的请求必须解决，资源分配图有助发现而冲突的请求必须解决，资源分配图有助发现而冲突的请求必须解决，资源分配图有助发现而冲突的请求必须解决，资源分配图有助发现和纠正死锁。和纠正死锁。和纠正死锁。和纠正死锁。假设某一程序对一些资源的请求，在该程假设某一程序对一些资源的请求，在该程假设某一程序对一些资源的请求，在该程假设某一程序对一些资源的请求，在该程序运行完之前必须都得到满足。在请求的时间序运行完之前必须都得到满足。在请求的时
63、间序运行完之前必须都得到满足。在请求的时间序运行完之前必须都得到满足。在请求的时间里，被请求的资源是不能利用的，程序控制着里，被请求的资源是不能利用的，程序控制着里，被请求的资源是不能利用的，程序控制着里，被请求的资源是不能利用的，程序控制着可利用的资源，但对不可利用的资源则必须等可利用的资源，但对不可利用的资源则必须等可利用的资源，但对不可利用的资源则必须等可利用的资源，但对不可利用的资源则必须等待。待。待。待。令令令令P Pt t=p p1 1，p p2 2，p pmm 表示计算机系统在表示计算机系统在表示计算机系统在表示计算机系统在时间时间时间时间t t的程序集合，的程序集合，的程序集合
64、，的程序集合，Q Qt t P Pt t是运行的程序集合，或是运行的程序集合，或是运行的程序集合，或是运行的程序集合，或者说在时刻者说在时刻者说在时刻者说在时刻t t至少分配一部分所请求的资源的程至少分配一部分所请求的资源的程至少分配一部分所请求的资源的程至少分配一部分所请求的资源的程序集合。序集合。序集合。序集合。R Rt t=r r1 1，r r2 2，r rn n 是系统在时刻是系统在时刻是系统在时刻是系统在时刻t t的的的的资源集合。资源分配图资源集合。资源分配图资源集合。资源分配图资源集合。资源分配图G Gt t= 是有向图，是有向图，是有向图，是有向图，它表示了时间它表示了时间它表
65、示了时间它表示了时间t t系统中资源分配状态。把每个资系统中资源分配状态。把每个资系统中资源分配状态。把每个资系统中资源分配状态。把每个资源源源源r ri i看作图中一个结点，其中看作图中一个结点，其中看作图中一个结点，其中看作图中一个结点，其中i i=1=1，2 2，n n。 表示有向边，表示有向边，表示有向边，表示有向边， E E当且仅当程序当且仅当程序当且仅当程序当且仅当程序p pk kQ Qt t已分配到资源已分配到资源已分配到资源已分配到资源r ri i且等待资源且等待资源且等待资源且等待资源r rj j。例如，令例如，令例如，令例如，令R Rt t=r r1 1, ,r r2 2,
66、 ,r r3 3, ,r r4 4 ，Q Qt t=p p1 1, ,p p2 2, ,p p3 3, ,p p4 4 。资源分配状态是：。资源分配状态是：。资源分配状态是：。资源分配状态是：p p1 1占用资源占用资源占用资源占用资源r r4 4且请求资源且请求资源且请求资源且请求资源r r1 1；p p2 2占用资源占用资源占用资源占用资源r r1 1且请求资源且请求资源且请求资源且请求资源r r2 2和和和和r r3 3；p p3 3占用资源占用资源占用资源占用资源r r2 2且请求资源且请求资源且请求资源且请求资源r r3 3；p p4 4占用资源占用资源占用资源占用资源r r3 3且
67、请求资源且请求资源且请求资源且请求资源r r1 1和和和和r r4 4。于是，可得到资源分配图于是，可得到资源分配图于是，可得到资源分配图于是，可得到资源分配图G Gt t= ，如图，如图，如图，如图10.2.710.2.7所示。所示。所示。所示。能够证明，在时刻能够证明，在时刻能够证明，在时刻能够证明，在时刻t t计算机系统处于死锁状计算机系统处于死锁状计算机系统处于死锁状计算机系统处于死锁状态态态态资源分配图资源分配图资源分配图资源分配图G Gt t中包含强分图。于是，对于中包含强分图。于是，对于中包含强分图。于是，对于中包含强分图。于是，对于图图图图10.2.710.2.7，G Gt t
68、是强连通的，即处于死锁状态。是强连通的，即处于死锁状态。是强连通的，即处于死锁状态。是强连通的，即处于死锁状态。图图 10.2.716.4 图的矩阵表示图的矩阵表示为什么要用矩阵来表示图？为什么要用矩阵来表示图？给给定定一一个个图图G=，使使用用G=这种表示法存在两个缺陷：这种表示法存在两个缺陷：1、在图比较复杂时不够直观；、在图比较复杂时不够直观；2、不方便计算。、不方便计算。一个简单图一个简单图一个简单图一个简单图G G= 由由由由V V中每两个结点间中每两个结点间中每两个结点间中每两个结点间的邻接关系唯一地确定，这种关系可以用一个的邻接关系唯一地确定，这种关系可以用一个的邻接关系唯一地确
69、定，这种关系可以用一个的邻接关系唯一地确定，这种关系可以用一个矩阵给出，而矩阵形式与图中结点的编序有密矩阵给出，而矩阵形式与图中结点的编序有密矩阵给出，而矩阵形式与图中结点的编序有密矩阵给出，而矩阵形式与图中结点的编序有密切关系，这是用矩阵表示图值得注意的一点。切关系，这是用矩阵表示图值得注意的一点。切关系，这是用矩阵表示图值得注意的一点。切关系，这是用矩阵表示图值得注意的一点。定义定义定义定义16.4.116.4.1 给定简单图给定简单图给定简单图给定简单图G G= ，V V=v v1 1，v v2 2，v vn n ，V V中的结点按下标由小到大编序，则中的结点按下标由小到大编序，则中的结
70、点按下标由小到大编序，则中的结点按下标由小到大编序，则n n阶方阵阶方阵阶方阵阶方阵A A= =( (a aij ij) )称为图称为图称为图称为图G G的邻接矩阵。其中的邻接矩阵。其中的邻接矩阵。其中的邻接矩阵。其中 i i，j j=1=1，2 2，n n。有时为强调邻接矩阵依赖于图有时为强调邻接矩阵依赖于图有时为强调邻接矩阵依赖于图有时为强调邻接矩阵依赖于图G G，把图，把图，把图，把图G G的邻接矩的邻接矩的邻接矩的邻接矩阵记为阵记为阵记为阵记为A A( (G G) )。v2v1v3v4v5v1v5v2v3v40 1 1 1 11 0 1 0 01 1 0 1 01 0 1 0 11 0
71、 0 1 0A(G1)=0 1 0 0 11 0 1 0 10 1 0 1 10 0 1 0 11 1 1 1 0A(G2)=G1G2v2v1v3v4v5v1v5v2v3v40 0 1 1 11 0 1 0 00 0 0 1 00 0 0 0 00 0 0 1 0A(G3)=0 1 0 0 10 0 1 0 00 0 0 0 00 0 1 0 00 1 1 1 0A(G4)=G3G4今今今今后后后后将将将将略略略略去去去去这这这这种种种种由由由由于于于于V V中中中中结结结结点点点点编编编编序序序序而而而而引引引引起起起起邻邻邻邻接接接接矩矩矩矩阵阵阵阵的的的的任任任任意意意意性性性性，而而而
72、而取取取取该该该该图图图图的的的的任任任任一一一一个个个个邻邻邻邻接接接接矩矩矩矩阵阵阵阵作作作作为为为为该该该该图图图图的的的的矩矩矩矩阵表示。阵表示。阵表示。阵表示。 有关图同构的判断问题的讨论可以参考以下网址：有关图同构的判断问题的讨论可以参考以下网址：有关图同构的判断问题的讨论可以参考以下网址：有关图同构的判断问题的讨论可以参考以下网址： 邻接矩阵可展示相应图的一些性质：邻接矩阵可展示相应图的一些性质：邻接矩阵可展示相应图的一些性质：邻接矩阵可展示相应图的一些性质：1 1、若邻接矩阵的元素全为零，则其对应的、若邻接矩阵的元素全为零，则其对应的、若邻接矩阵的元素全为零，则其对应的、若邻接
73、矩阵的元素全为零，则其对应的图是零图；图是零图；图是零图；图是零图；2 2、若邻接矩阵的元素除主对角线元素外全、若邻接矩阵的元素除主对角线元素外全、若邻接矩阵的元素除主对角线元素外全、若邻接矩阵的元素除主对角线元素外全为为为为1 1，则其对应的图是连通的且为简单完全图；，则其对应的图是连通的且为简单完全图；，则其对应的图是连通的且为简单完全图；，则其对应的图是连通的且为简单完全图；3 3、当给定的简单图是无向图时，邻接矩阵、当给定的简单图是无向图时，邻接矩阵、当给定的简单图是无向图时，邻接矩阵、当给定的简单图是无向图时，邻接矩阵是对称矩阵；是对称矩阵；是对称矩阵；是对称矩阵；问题问题 1、当给
74、定的简单图是有向图时，邻接矩、当给定的简单图是有向图时，邻接矩阵不是对称矩阵；阵不是对称矩阵； 以上结论是否成立？以上结论是否成立？ 2、当给定的图是多重图时，如何用邻接、当给定的图是多重图时，如何用邻接矩阵表示？矩阵表示？4 4、在给定简单有向图的邻接矩阵中，第、在给定简单有向图的邻接矩阵中，第、在给定简单有向图的邻接矩阵中，第、在给定简单有向图的邻接矩阵中，第i i行元行元行元行元素是由结点素是由结点素是由结点素是由结点vi vi出发的弧所确定，故第出发的弧所确定，故第出发的弧所确定，故第出发的弧所确定，故第i i行中值为行中值为行中值为行中值为1 1的的的的元素数目等于结点元素数目等于结
75、点元素数目等于结点元素数目等于结点v vi i的出度。同理，第的出度。同理，第的出度。同理，第的出度。同理，第j j列中值为列中值为列中值为列中值为1 1的元素数目等于结点的元素数目等于结点的元素数目等于结点的元素数目等于结点v vj j的入度。的入度。的入度。的入度。即即即即d d+ +( (v vi i)= )= 和和和和d d- -( (v vj j)=)=。v1v2v30 1 01 0 10 1 0A=GA2=0 1 01 0 10 1 00 1 01 0 10 1 0.=1 0 10 2 01 0 1A3=1 0 10 2 01 0 10 1 01 0 10 1 0.=0 2 02
76、0 20 2 0v1v2v30 2 02 0 20 2 0A3=GA4=0 2 02 0 20 2 00 1 01 0 10 1 0.=2 0 20 4 02 0 2A5=2 0 20 4 02 0 20 1 01 0 10 1 0.=0 4 04 0 40 4 0 由给定简单图由给定简单图由给定简单图由给定简单图G G的邻接矩阵的邻接矩阵的邻接矩阵的邻接矩阵A A可计算出矩阵可计算出矩阵可计算出矩阵可计算出矩阵A A的的的的l l次幂，即次幂，即次幂，即次幂，即A Al l。若第。若第。若第。若第i i行第行第行第行第j j列上的元素列上的元素列上的元素列上的元素a al lij ij便是便
77、是便是便是G G中从第中从第中从第中从第i i个结点个结点个结点个结点v vi i到第到第到第到第j j个结点个结点个结点个结点v vj j长度为长度为长度为长度为l l的链（或路）的数目。的链（或路）的数目。的链（或路）的数目。的链（或路）的数目。为说明此事实，今给出下面定理。为说明此事实，今给出下面定理。为说明此事实，今给出下面定理。为说明此事实，今给出下面定理。定理定理定理定理16.4.116.4.1 设设设设A A为简单图为简单图为简单图为简单图G G的邻接矩阵，则的邻接矩阵，则的邻接矩阵，则的邻接矩阵，则A Al l中的中的中的中的i i行行行行j j列元素列元素列元素列元素a al
78、 lij ij等于等于等于等于G G中联结中联结中联结中联结v vi i到到到到v vj j的长度为的长度为的长度为的长度为l l的链的链的链的链( (或路或路或路或路) )的数目。的数目。的数目。的数目。在在在在一一一一些些些些实实实实际际际际问问问问题题题题中中中中，有有有有时时时时要要要要判判判判定定定定图图图图中中中中结结结结点点点点v vi i到到到到结结结结点点点点v vj j是是是是否否否否可可可可达达达达，或或或或者者者者说说说说v vi i到到到到v vj j是是是是否否否否存存存存在在在在一一一一要要要要链链链链（或或或或路路路路）。如如如如果果果果要要要要利利利利用用用用
79、图图图图G G的的的的邻邻邻邻接接接接矩矩矩矩阵阵阵阵A A，则则则则应应应应计计计计算算算算A A2 2，A A3 3，A An n，。当当当当发发发发现现现现其其其其中中中中某某某某个个个个A Ar r中中中中 11，就就就就表表表表明明明明v vi i可达可达可达可达v vj j或或或或v vi i到到到到v vj j存在一条链（或路）。存在一条链（或路）。存在一条链（或路）。存在一条链（或路）。但这种计算繁琐量大，又不知计算但这种计算繁琐量大，又不知计算但这种计算繁琐量大，又不知计算但这种计算繁琐量大，又不知计算A Ar r到何时为止。到何时为止。到何时为止。到何时为止。根据定理根据定
80、理根据定理根据定理16.2.216.2.2可知，对于有可知，对于有可知，对于有可知，对于有n n个结点的图，任何个结点的图，任何个结点的图，任何个结点的图，任何基本链（或路）的长度不大于基本链（或路）的长度不大于基本链（或路）的长度不大于基本链（或路）的长度不大于n n-1-1和任何基本圈（或回和任何基本圈（或回和任何基本圈（或回和任何基本圈（或回路）的长度不大于路）的长度不大于路）的长度不大于路）的长度不大于n n。因此，只需考虑。因此，只需考虑。因此，只需考虑。因此，只需考虑 就可以了，就可以了，就可以了，就可以了，其中其中其中其中11r r n n。即只要计算。即只要计算。即只要计算。即
81、只要计算B Bn n= =A A+ +A A2 2+ +A A3 3+A An n。如果关心的是结点间可达性或结点间是否有链如果关心的是结点间可达性或结点间是否有链如果关心的是结点间可达性或结点间是否有链如果关心的是结点间可达性或结点间是否有链（或路），至于结点间的链存在多少条及长度是多少无（或路），至于结点间的链存在多少条及长度是多少无（或路），至于结点间的链存在多少条及长度是多少无（或路），至于结点间的链存在多少条及长度是多少无关紧要，那么便可用下面的定义图的可达矩阵来表示结关紧要，那么便可用下面的定义图的可达矩阵来表示结关紧要，那么便可用下面的定义图的可达矩阵来表示结关紧要，那么便可用下
82、面的定义图的可达矩阵来表示结点间可达性。点间可达性。点间可达性。点间可达性。定义定义定义定义16.4.216.4.2 给定图给定图给定图给定图G G= ，将其结点按下标编，将其结点按下标编，将其结点按下标编，将其结点按下标编序得序得序得序得V V=v v1 1，v v2 2，v vn n 。定义一个。定义一个。定义一个。定义一个n n阶方阵阶方阵阶方阵阶方阵P P=(=(p pij ij) )，其，其，其，其中中中中 1 1 v vi i到到到到v vj j可达可达可达可达P Pij ij= = 0 0 否则否则否则否则则称矩阵则称矩阵则称矩阵则称矩阵P P是图是图是图是图G G的可达矩阵。的
83、可达矩阵。的可达矩阵。的可达矩阵。可见，可达矩阵表明了图中任意两结点间可见，可达矩阵表明了图中任意两结点间可见，可达矩阵表明了图中任意两结点间可见，可达矩阵表明了图中任意两结点间是否至少存在一条链是否至少存在一条链是否至少存在一条链是否至少存在一条链( (或路或路或路或路) )以及在结点处是否以及在结点处是否以及在结点处是否以及在结点处是否有圈有圈有圈有圈( (或回路或回路或回路或回路) )。从图从图从图从图G G的邻接矩阵的邻接矩阵的邻接矩阵的邻接矩阵A A可以得到可达矩阵可以得到可达矩阵可以得到可达矩阵可以得到可达矩阵P P，即令即令即令即令B Bn n= =A A+ +A A2 2+ +
84、A A3 3+A An n，再从，再从，再从，再从B Bn n中非零元素中非零元素中非零元素中非零元素改为改为改为改为1 1而零元素不变，这种变换后的矩阵即是可而零元素不变，这种变换后的矩阵即是可而零元素不变，这种变换后的矩阵即是可而零元素不变，这种变换后的矩阵即是可达矩阵达矩阵达矩阵达矩阵P P。假假假假 设设设设 矩矩矩矩 阵阵阵阵 中中中中 的的的的 元元元元 素素素素 是是是是 属属属属 于于于于 布布布布 尔尔尔尔 代代代代 数数数数 ,0,1的的的的B B中中中中元元元元素素素素，其其其其中中中中B B=0,1=0,1，则则则则称称称称该该该该矩矩矩矩阵阵阵阵为为为为布布布布尔尔尔
85、尔矩矩矩矩阵阵阵阵。显显显显然然然然邻邻邻邻接接接接矩矩矩矩阵阵阵阵是是是是一一一一个个个个布布布布尔尔尔尔矩矩矩矩阵阵阵阵，同同同同样样样样可可可可达达达达矩矩矩矩阵阵阵阵也也也也是是是是布布布布尔尔尔尔矩矩矩矩阵阵阵阵。下下下下面面面面定定定定义两个布尔矩阵义两个布尔矩阵义两个布尔矩阵义两个布尔矩阵B B与与与与C C的运算：的运算：的运算：的运算：令令令令B B和和和和C C的布尔和、布尔积分别记为的布尔和、布尔积分别记为的布尔和、布尔积分别记为的布尔和、布尔积分别记为B B C C和和和和BoCBoC，其定义为，其定义为，其定义为，其定义为( (B B C C) )ij ij= =b
86、bij ij c cij ij( (B B C C) )ij ij= (= (b bikik c ckjkj) )i i, ,j j=1,2,=1,2,n n。其中。其中。其中。其中b bij ij，c cij ij分别是分别是分别是分别是B B和和和和C C的的的的i i行行行行j j列元素。列元素。列元素。列元素。特别地，对于邻接矩阵特别地，对于邻接矩阵特别地，对于邻接矩阵特别地，对于邻接矩阵A A，记，记，记，记A A A A= =A A(2)(2)，对任何对任何对任何对任何r r=2,3,=2,3,有有有有A A( (r r-1) -1) A A= =A A( (r r) )要注意的是
87、要注意的是要注意的是要注意的是A Ar r与与与与A A( (r r) )的差别。的差别。的差别。的差别。A Ar r中中中中 表明表明表明表明从从从从v vi i到到到到v vj j长度为长度为长度为长度为r r的链（或路）的数目，而的链（或路）的数目，而的链（或路）的数目，而的链（或路）的数目，而A A( (r r) )中中中中 是指出：若是指出：若是指出：若是指出：若v vi i到到到到v vj j至少存在一条链（或路）时，至少存在一条链（或路）时，至少存在一条链（或路）时，至少存在一条链（或路）时，=1=1，否则，否则，否则，否则， =0 =0。由上说明，便得到可达矩阵由上说明，便得到
88、可达矩阵由上说明，便得到可达矩阵由上说明，便得到可达矩阵P P为：为：为：为：P P= =A A A A(2)(2) A A(3)(3) A A( (n n) )= = A A( (k k) )对对于于简简单单有有向向图图G=，显显然然有有E V V。因因此此，弧弧集集合合E可可解解释释成成B中中的的二二元元关关系系，而而二二元元关关系系是是可可用用矩矩阵阵表表示示的的，通通常常称称这这种种矩矩阵阵为为关关系系矩矩阵阵，其其定定义义如下：如下：设两个有限集合设两个有限集合设两个有限集合设两个有限集合X X= = x x1 1, ,x x2 2,x xmm 和和和和Y Y= = y y1 1,
89、,y y2 2,y yn n ，则关系，则关系，则关系，则关系R R X X Y Y的关系矩阵的关系矩阵的关系矩阵的关系矩阵MMR R=(=(r rij ij) )，其中，其中，其中，其中1, 1, R R r rij ij= = 0, 0, 否则否则否则否则i i=1,2,=1,2,mm；j j=1,2,=1,2,n n。由定义可知，关系由定义可知，关系由定义可知，关系由定义可知，关系R R与其关系矩阵与其关系矩阵与其关系矩阵与其关系矩阵MMR R是一是一是一是一一对应的，即可以相互确定。一对应的，即可以相互确定。一对应的，即可以相互确定。一对应的，即可以相互确定。根据集合论可知，对于域根据
90、集合论可知，对于域根据集合论可知，对于域根据集合论可知，对于域F F( (R R)=)=V V而而而而| |V V|=|=n n的的的的关系关系关系关系R R的传递闭包的传递闭包的传递闭包的传递闭包R R+ +可计算如下：可计算如下：可计算如下：可计算如下：R R+ += =R RR R2 2R R3 3R Rk k ( (k k n n) )于是，关系于是，关系于是，关系于是，关系R R1 1和和和和R R2 2的关系矩阵分别为的关系矩阵分别为的关系矩阵分别为的关系矩阵分别为A A1 1和和和和A A2 2，则关系，则关系，则关系，则关系R R1 1R R2 2的关系矩阵为的关系矩阵为的关系
91、矩阵为的关系矩阵为A A1 1 A A2 2。用归纳。用归纳。用归纳。用归纳法可以证明法可以证明法可以证明法可以证明R R+ +的关系矩阵是的关系矩阵是的关系矩阵是的关系矩阵是 = = 对于对于对于对于G G= 的邻接矩阵的邻接矩阵的邻接矩阵的邻接矩阵A A是关系是关系是关系是关系E E的关系的关系的关系的关系矩阵，因为矩阵，因为矩阵，因为矩阵，因为E E2 2= =EoEEoE，即若存在一个结点，即若存在一个结点，即若存在一个结点，即若存在一个结点v vk k，使，使，使，使得得得得v vi iEvEvk k，和，和，和，和v vk kEvEvj j，则必有，则必有，则必有，则必有v vi
92、iE E2 2v vj j，亦即从，亦即从，亦即从，亦即从v vi i到到到到v vj j若若若若至少存在一条长度为至少存在一条长度为至少存在一条长度为至少存在一条长度为2 2的链（或路），那么的链（或路），那么的链（或路），那么的链（或路），那么E E2 2的的的的关系矩阵中的关系矩阵中的关系矩阵中的关系矩阵中的( (i i, ,j j) )元素值为元素值为元素值为元素值为1 1。这表明矩阵。这表明矩阵。这表明矩阵。这表明矩阵A A(2)(2)是关系是关系是关系是关系E E2 2的关系矩阵。以此类推，的关系矩阵。以此类推，的关系矩阵。以此类推，的关系矩阵。以此类推，A A( (k k) )是
93、是是是E Ek k的关的关的关的关系矩阵，系矩阵，系矩阵，系矩阵，k k=2,3,=2,3,n n。因此。因此。因此。因此A A+ += =A A A A(2)(2) A A(3)(3) A A( (n n) )亦即亦即亦即亦即 A A+ += =A A A A(2)(2) A A(3)(3) A A( (n n) )= =P P可见，关系可见，关系可见，关系可见，关系E E的传递闭包的传递闭包的传递闭包的传递闭包E E+ +的关系矩阵的关系矩阵的关系矩阵的关系矩阵A A+ +与可达矩阵相同。与可达矩阵相同。与可达矩阵相同。与可达矩阵相同。为了计算为了计算为了计算为了计算A A+ +或或或或P
94、 P，自然可先依次求得，自然可先依次求得，自然可先依次求得，自然可先依次求得A A(2)(2)，A A(3)(3)，A A( (n n) )，然后再计算，然后再计算，然后再计算，然后再计算 A A( (k k) )，其结，其结，其结，其结果即为所求，这是计算果即为所求，这是计算果即为所求，这是计算果即为所求，这是计算A A+ +或或或或P P的一种方法，还可的一种方法，还可的一种方法，还可的一种方法，还可介绍一种现有效的方法介绍一种现有效的方法介绍一种现有效的方法介绍一种现有效的方法WarshallWarshall算法，它由算法，它由算法，它由算法，它由邻接矩阵邻接矩阵邻接矩阵邻接矩阵A A依
95、下面给出的步骤便能计算依下面给出的步骤便能计算依下面给出的步骤便能计算依下面给出的步骤便能计算A A+ +。其步。其步。其步。其步骤如下：骤如下：骤如下：骤如下：(1) (1) P PA A(2) (2) k k1 1(3) (3) i i1 1(4) (4) 若若若若p pikik=1=1，对，对，对，对j j=1,2,=1,2,n n作作作作p pij ijp pij ij p pkjkj(5) (5) i ii i+1+1，若，若，若，若i i n n则转则转则转则转(4)(4)(6) (6) k kk k+1+1，若，若，若，若k k n n则转到则转到则转到则转到(3)(3)，否则停
96、止。，否则停止。，否则停止。，否则停止。该算法的关键的一步是该算法的关键的一步是该算法的关键的一步是该算法的关键的一步是(4)(4)，它判定如果，它判定如果，它判定如果，它判定如果p pikik=1=1，将第，将第，将第，将第i i行和第行和第行和第行和第k k行的各对应元素作布尔和行的各对应元素作布尔和行的各对应元素作布尔和行的各对应元素作布尔和或逻辑加后送到第或逻辑加后送到第或逻辑加后送到第或逻辑加后送到第i i行中去。行中去。行中去。行中去。给给给给定定定定关关关关系系系系E E1 1和和和和关关关关系系系系E E2 2，它它它它们们们们的的的的关关关关系系系系矩矩矩矩阵阵阵阵分分分分别
97、别别别为为为为A A= =( (a aij ij) )和和和和B B=(=(b bij ij) )，则则则则关关关关系系系系交交交交E E1 1 E E2 2的的的的关关关关系系系系矩矩矩矩阵阵阵阵记记记记为为为为A AB B，其定义如下：其定义如下：其定义如下：其定义如下：( (A AB B) )ij ij= =a aij ijb bij ij于于于于是是是是，由由由由可可可可达达达达矩矩矩矩阵阵阵阵和和和和利利利利用用用用关关关关系系系系交交交交的的的的关关关关系系系系矩矩矩矩阵阵阵阵可可可可求求求求出包含图中任何指定结点的强分图。出包含图中任何指定结点的强分图。出包含图中任何指定结点的强
98、分图。出包含图中任何指定结点的强分图。定定定定理理理理16.3.216.3.2 给给给给定定定定简简简简单单单单有有有有向向向向图图图图G G中中中中的的的的任任任任意意意意结结结结点点点点v vi i，若若若若P P= =( (p pij ij) )是是是是G G的的的的可可可可达达达达矩矩矩矩阵阵阵阵，P PT T=(=(p pji ji) )是是是是P P的的的的转转转转置置置置矩矩矩矩阵阵阵阵，则则则则P PP PT T的的的的第第第第i i行行行行元元元元素素素素为为为为1 1的的的的列列列列号号号号为为为为下下下下标标标标的的的的结结结结点点点点构构构构成成成成了了了了包包包包含含
99、含含v vi i的的的的强强强强分图。分图。分图。分图。利利利利用用用用简简简简单单单单有有有有向向向向图图图图的的的的可可可可达达达达矩矩矩矩阵阵阵阵，能能能能够够够够确确确确定定定定某某某某过程是否为递归的。过程是否为递归的。过程是否为递归的。过程是否为递归的。假假假假设设设设V VP P= = p p1 1, ,p p2 2,p pn n 是是是是程程程程序序序序P P中中中中的的的的过过过过程程程程集集集集合合合合，做做做做有有有有向向向向图图图图G G= ，其其其其中中中中p pi i V VP P，i i=1,2,=1,2,n n； E Ep pi i调调调调用用用用p pj j。
100、如如如如果果果果图图图图G G中中中中有有有有包包包包含含含含p pi i的的的的回回回回路路路路，则则则则可可可可断断断断言言言言p pi i是是是是递递递递归归归归的的的的。为为为为此此此此，由由由由图图图图G G的的的的邻邻邻邻接接接接矩矩矩矩阵阵阵阵A A=(=(a aij ij) )计计计计算算算算出出出出可可可可达达达达矩矩矩矩阵阵阵阵A A+ +=( =( ) )。如如如如果果果果A A+ +中中中中的的的的主主主主对对对对角角角角线线线线上上上上的的的的某某某某元元元元素素素素 =1=1，则则则则p pi i是是是是递归的。递归的。递归的。递归的。在在图图的的矩矩阵阵表表示示中
101、中，除除邻邻接接矩矩阵阵外外，还还有有关关联联矩矩阵阵、圈圈（或或回回路路）矩矩阵阵、权权矩矩阵阵等等，在在此此就就不不都都予予涉涉及及了了，只只是是再再给给出出权矩阵的概念以结束本小节。权矩阵的概念以结束本小节。已知加权的简单图已知加权的简单图已知加权的简单图已知加权的简单图G G= ，定义一个矩，定义一个矩，定义一个矩，定义一个矩阵阵阵阵WW=(=(w wij ij) )，其中：，其中：，其中：，其中： w w, , w w是边是边是边是边 v vi i, ,v vj j （或弧（或弧（或弧（或弧 ） E E 的权的权的权的权w wij ij= = 0 0， v vi i与与与与v vj j不相邻不相邻不相邻不相邻则称则称则称则称WW为图为图为图为图G G的权矩阵的权矩阵的权矩阵的权矩阵
