离散数学课件

《离散数学课件》由会员分享，可在线阅读，更多相关《离散数学课件（71页珍藏版）》请在金锄头文库上搜索。

1、一、图定义一个图是一个三元组,简记为G。7-1 图的基本概念其中：其中：1)1)V Vvv1 1,v,v2 2,v,v3 3,v vn n 是是一个非空集合一个非空集合,v,vi i(i(i1,2,3,n)1,2,3,n)称为称为结点结点, ,简称简称点点,V,V为为结点集结点集；2)2)E Eee1 1,e,e2 2,e,e3 3,e em m 是是一个有限的集合，一个有限的集合，e ei i(i(i1,2,3,m)1,2,3,m)称为称为边边,E,E为为边集边集，E E中的每个元素都有中的每个元素都有V V中的结点对（有序偶或无序偶）与之对应。中的结点对（有序偶或无序偶）与之对应。3)3)

2、例例1离散数学图的术语图的术语 图的术语图的术语若边若边e e与结点无序偶与结点无序偶(u(u，v)v)相对应，则称边相对应，则称边e e为为无向边无向边, ,记为记为e e(u(u，v)v)，这时称这时称u u，v v是边是边e e的两个的两个端点端点；2)2)若若边边e e与与结结点点有有偶偶uv相相对对应应，则则称称边边e e为为有有向向边边( (或或弧弧) )，记记为为e euv，这这时时称称u u是是边边e e的的始始点点( (或或弧弧尾尾).v).v是是边边e e的的终终点点( (或或弧头弧头) )，统称为，统称为e e的的端点端点；3)3)在在一一个个图图中中，关关联联结结点点v

3、 vi i和和v vj j的的边边e e，无无论论是是有有向向的的还还是是无无向向的的，均均称称边边e e与与结结点点v vI I和和v vj j相相关关联联，而而v vi i和和v vj j称称为为邻邻接接点点，否否则称为则称为不邻接的不邻接的；2离散数学续：续：续：续：4)4)关联于同一个结点的两条边称为关联于同一个结点的两条边称为邻接边邻接边；5)5)图中关联同一个结点的边称为图中关联同一个结点的边称为自回路自回路( (或或环环) )；6)6)图中不与任何结点相邻接的结点称为图中不与任何结点相邻接的结点称为孤立结点孤立结点；7)7)仅由孤立结点组成的图称为仅由孤立结点组成的图称为零图零图

4、；8)8)仅含一个结点的零图称为仅含一个结点的零图称为平凡图平凡图；9)9)含有含有n n个结点、个结点、m m条边的图称为条边的图称为(n(n，m)m)图图；3离散数学续：续：续：续：每条边都是无向边的图称为每条边都是无向边的图称为无向图无向图；每条边都是有向边的图称为每条边都是有向边的图称为有向图有向图；有些边是无向边，而另一些是有向边的图称为有些边是无向边，而另一些是有向边的图称为混合图混合图。在在有有向向图图中中，两两个个结结点点间间( (包包括括结结点点自自身身间间) )若若有有同同始始点点和和同同终终点点的的几几条条边边，则则这这几几条条边边称称为为平平行行边边，在在无无向向图图中

5、中，两两个个结结点点间间( (包包括括结结点点自自身身间间) )若若有有几几条条边边，则则这这几几条条边边称称为为平平行行边边，两两结结点点vivi，vjvj间间相相互互平平行行的的边边的的条条数数称称为为边边(vi(vi，vjvj) )或或vi 的的重数重数；含含有有平平行行边边的的图图称称为为多多重重图图。非非多多重重图图称称为为线线图图；无无自自回回路的线图称为路的线图称为简单图简单图。4离散数学(a)例：(b)(c)(c)(d)(d)例：5离散数学(e)(f)(f)例：例：(g)6离散数学二、度数定义 在无向图G中，与结点v(vV)关联的边的条数，称为该结点的度数，记为deg(v)；二

6、、度数定义 在有向图G中，以结点v(vV)为始点引出的边的条数，称为该结点的引出度数,简称出度,记为deg+(v)；以结点v(vV)为终点引入的边的条数，称为该结点的引入度数，简称入度,记为deg-(v)；而结点的出度和入度之 和 称 为 该 结 点 的 度 数 ， 记 为 deg(v)， 即 deg(v)deg+(v)+deg-(v)；(G)最小度，(G)最大度定义 在图G中，对任意结点vV，若度数deg(v)为奇数，则称此结点为奇度数结点，若度数deg(v)为偶数，则称此结点为偶度数结点。7离散数学例：deg(v1)3，deg+(v1)2，deg-(v1)1；deg(v2)3，deg+(v

7、2)2，deg-(v2)1；deg(v3)5，deg+(v3)2，deg-(v3)3；deg(v4)deg+(v4)deg-(v4)0；deg(v5)1，deg+(v5)0，deg-(v5)1；例：8离散数学定理定理定理定理1.1.在在图图G GVE中中，则则所所有有结结点点的的度度数数的的总总和和等等于于边边数数的两倍，即：的两倍，即：2.2.在有向图在有向图G GVE中，则所有结点的出度之和等于所中，则所有结点的出度之和等于所有结点的入度之和，即：有结点的入度之和，即：3.3.定理定理 在所有图中，度数为奇数的结点个数为偶数度数为奇数的结点个数为偶数. .9离散数学定理定理。证明证明设设V

8、 V1 1v|vv|v V V且且deg(v)deg(v)奇数奇数 ，V V2 2v|vv|v V V且且deg(v)deg(v)偶数偶数 。显然，。显然，V V1 1VV2 2，且，且V V1 1VV2 2V V，于是，于是有：有：由于上式中的由于上式中的2m2m和偶度数结点度数之和均为偶数，因而和偶度数结点度数之和均为偶数，因而也为偶数。于是也为偶数。于是|V|V1 1| |为偶数为偶数( (因为因为V V1 1中的结点中的结点v v之之deg(v)deg(v)都都为奇数为奇数) )，即奇度数的结点个数为偶数。，即奇度数的结点个数为偶数。10离散数学三、完全图三、完全图定义 在图G中，若所

9、有结点的度数均有相同度数d，则称此图为d次正则图。定义 一个(n，m)(n2)的简单无向图，若它为n-1次正则图，则称该(n，m)图为无向简单完全图，简称完全图,记为Kn。有向完全图定理定理 设无向完全图设无向完全图G G有有n n个顶点，则个顶点，则G G有有 条边。条边。11离散数学四、子图和补图定义 设有图G和图G1，若G和G1满足：若V1V，E1E，则称G1是G的子图，记为G1G；若G1G，且G1G(即V1V或E1E)，则称G1是G的真子图，记为G1G；定义 若V1V，E1E，则称G1是G的生成子图，记为G1G；定义设有图G和图G2，若V2V，V2，以V2为结点集，以两个端点均在V2中

10、的边的全体为边集的G的子图称为V2导出的子图，简称G的导出子图。四、子图和补图12离散数学例：例：它的真子图G和生成子图G。13离散数学四、子图和补图定义 设G为具有n个结点的简单图,从完全图Kn中删去G中的所有的边而得到的图称为G的补图(或G的补)，记为 。关于完全图的子图的补图称为此子图的关于完全图的子图的补图称为此子图的绝对补图绝对补图。定定义义 是是图图， 是是的的子子图图，”，” ” 是是”中中边边所所关关联联的的所所有有顶顶点点集集合合，则则” ”称为称为关于的关于的相对补图相对补图。 四、子图和补图14离散数学例：例：求下图的补图。15离散数学五、图的同构五、图的同构例:如下图

11、(a)、(b)、(c)、(d)所示。图图(a)(a)、图、图(b)(b)、图、图(c)(c)和图和图(d)(d)所表示的图形实际上都是一样的所表示的图形实际上都是一样的16离散数学定义定义定义定义 设有图设有图G G和图和图G G1 1V,如果存在双如果存在双射函数射函数g:VVg:VV1 1, ,且且e e(v(vi i,v,vj j)()(或或)是是G G的一条边的一条边当当且仅当且仅当e e1 1(g(v(g(vi i),g(v),g(vj j) () (或或) 是是G G1 1的一的一条边条边则称则称G G和和G G1 1同构同构，记为，记为GGGG1 1。同构的充要条件：同构的充要条

12、件：两个图的结点和边分别存在一一对应，两个图的结点和边分别存在一一对应，且保持关联关系。且保持关联关系。17离散数学例：例：如图(a)、(b)所示的两个图G和G1，GG1？解解：显然，定义函数：显然，定义函数g g：VVVV1 1，满足，满足g(vg(vi i) )v vi i（i i1 1，2 2，3 3，4 4，5 5），可以验证），可以验证g g一定是一个满足定义的双射，一定是一个满足定义的双射，所以所以GGGG1 1。18离散数学必要条件两个图同构的必要条件：结点数目相同；边数相同；度数相同的结点数相同。注意注意：这三个条件并不是充分条件。例如下面两个图满：这三个条件并不是充分条件。例

13、如下面两个图满足这三个条件，但它们不同构。足这三个条件，但它们不同构。19离散数学7-2 路与回路 一、路定定义义 给给定定图图G G= =V,EV,E, ,设设v v0 0，v v1 1，v vn nV V, ,e e1 1，e e2 2，e en nE E, ,其其中中e ei i是是关关联联结结点点v vi i-1-1, ,v vi i的的边边, ,交交替替序序列列v v0 0e e1 1v v1 1e e2 2e en nv vn n称为联结称为联结v v0 0到到v vn n的路。的路。vv v0 0,v,vn n分别为该路的起点和终点，统称为路的分别为该路的起点和终点，统称为路的端

14、点端点。v路中边的条数称为该路中边的条数称为该路的长度路的长度。v此时，若此时，若v v0 0v vn n，则该路称为则该路称为回路回路。20离散数学若路中所有边全不相同所有边全不相同，则称此路为一条迹；若路中所有结点全不相同所有结点全不相同，则称此路为通路。 若回路中除v0vn以外所有结点全不相同，则称此圈。（闭的通路）在简单图中一条路v0e1v1e2envn ，由它的结点序列v0v1 vn确定,所以简单图的路,由可由其结点序列v0v1 vn表示。在有向图中,结点数大于1的一条路可由边序列e1e2 en 表示。续：21离散数学例：考虑如下路：例：22离散数学定理定理定理定理在一个具有在一个具

15、有n n个结点的图中，如果从结点个结点的图中，如果从结点v vj j到结点到结点v vk k存在存在一条路，则从结点一条路，则从结点v vj j到结点到结点v vk k必必存在一条不多于存在一条不多于n n-1-1条边的路。条边的路。 推论推论在无向图在无向图G G中，如果从结点中，如果从结点v vj j到结点到结点v vk k存在一条路，存在一条路，则必存在一条从则必存在一条从v vj j到到v vk k而而长度小于长度小于n n的通路。的通路。23离散数学二、无向图的连通性二、无向图的连通性 定义 设G是一个图，对vi，vjV，从vi到vj如存在一条路，则称路，则称结点结点v vi i和和

16、v vj j是连通的是连通的。定义 设G是一个无向图，该无向图G中的每个连通的划分块称为G的一个连通分支，用W(G)表示G中的连通分支数。定义 设G是一个无向图，若G中任意两个结点之间都是连通的，即图G只有一个连通分支，则称该无向图G是一个无向连通图，否则，则称G是一个非连通图(或分离图)。24离散数学G1是连通图，W(G1)1；G2是非连通图，且W(G2)4。例：例：25离散数学定定义义设无向图G=V,E为连通的，若有结点集V1是V的真子集，使得图G删除了V1所有结点后，所得的子图是不连通的，而删除了V1的任意真子集后，所得的子图仍然是连通图。则称集合V1为图G的点割集。若某一结点就构成点割

17、集，则称该结点为割点。这样，一个连通图，删除它的一个点割集后，将分成两个或多于两个连通分支。割点26离散数学割点若G不是完全图，我们定义k(G)=min| V1 | |V1是G的点割集为G的点连通度(或连通度)。连通度k(G)是为了产生一个不连通图需要删去的点的最少数目。 一个不连通图的连通度等于 存在着割点的连通图的点连通度 完全图Kp的点连通度27离散数学定定义义 设无向图G=V,E为连通的，若有边集E1是E的真子集，使得图G删除了E1所有边后，所得的子图是不连通的，而删除了E1的任意真子集后，所得的子图仍然是连通图。则称集合E1为图G的边割集。若某一边构成边割集，则称该边为割边(或桥)。

18、 G的割边也就是G中的一条边e使得W(G-e)W(G)。 例割边28离散数学割边与点连通度相似，我们定义非平凡图G的边连通度为：(G)=min| E1 |E1是G的边割集，边连通度(G)是为了产生一个不连通需要删去边的最少数目。平凡图(G ) 一个不连通图(G) 29离散数学定理定理 对于任何一个图G =V,E，有k(G)(G)(G)证明证明 若G不连通，则k(G)=(G)=0，故上式成立。若G连通，证证明明(G)(G)。若G是平凡图，则(G)=0(G)，若G是非平凡图，则因每一结点的所有关连边必含一个边割集，故(G)(G)。定理定理30离散数学再证k(G)(G).设(G)=1，即G有一割边，

19、显然此时k(G)=1，上式成立。.设(G)2，则必可删去某(G)条边，使G不连通，而删除(G)-1条边，它仍然连通，而且有一条桥e=(u，v)。对(G)-1条边中每一条边都选取一个不同于u，v的端点，将这些端点删去必至少删去(G)-1条边。若这样产生的图是不连通的，则k(G)(G)-1(G)，若这样产生的图是连通的，则e=(u，v)仍然是桥，此时再删去u，v，就必产生一个不连通图，故k(G)(G)。由此得k(G)(G)(G)。 续：31离散数学定定理理 一个连通无向图G =V,E的某一点v是图G的割点，当且仅当存在两个节点u和w，使得节点u和w的每一条路都通过v。定理定理32离散数学三、有向图

20、的连通性三、有向图的连通性 定义 设G是一个有向图，对vi，vjV，从vi到vj如存在一条路，则称路，则称结点结点v vi i到到v vj j是可达的。是可达的。在有向图中，如从在有向图中，如从v vi i到到v vj j可达，但从可达，但从v vj j到到v vi i则不一定是可达的。则不一定是可达的。为此，若将可达性看成是图为此，若将可达性看成是图G GVE的结点集合的结点集合V V上的二上的二元关系的话，元关系的话，对有向图来说，该可达性关系满足什么性质？对有向图来说，该可达性关系满足什么性质？33离散数学定义定义定义定义 在图在图G GVE中，对中，对 v vi i，v vj j V

21、V，如果从，如果从v vi i到到v vj j存存在路，则称长度最短的路为从在路，则称长度最短的路为从v vi i到到v vj j的的短程线短程线, ,从从v vi i到到v vj j的的短程线的长度称为从短程线的长度称为从v vi i到到v vj j的的距离距离，记为，记为d(vd(vi i,v,vj j) )。d(vd(vi i，v vj j) )满足下列性质：满足下列性质：d(vd(vi i，v vj j) ) 0 0；d(vd(vi i，v vi i) )0 0；d(vd(vi i，v vk k)+d(v)+d(vk k，v vj j) ) d(v d(vi i，v vj j) )；d

22、(vd(vi i，v vj j) ) ( (当当v vi i到到v vj j不可达不可达) )。此外，有关距离的概念对无向图也适用。此外，有关距离的概念对无向图也适用。34离散数学在(a)中有：d(v2，v1)d(v1，v2)d(v3，v1)d(v1，v3)在(b)中有：d(v1，v3)，d(v3，v7)，d(v1，v7)。例：例：35离散数学定义 设G是一个有向图，若G中任意两个结点之间都是相互可达的，则称该有向图G是一个强连通图 ；设G是一个有向图，若G中任意两个结点之间至少单方向可达的，则称该有向图G是一个单侧连通图；设G是一个有向图，若略去G中所有有向边的方向后所得到的无向图G1是一个

23、无向连通图，则称该有向图G是一个弱连通图。定义36离散数学例：例：37离散数学定理定理定理 一个有向图一个有向图G G是强连通图当且仅当是强连通图当且仅当G G中有一个回中有一个回路，它至少包含每一个结点一次。路，它至少包含每一个结点一次。证明证明：“”如如G G中有一个回路，它至少包含每个结点，则中有一个回路，它至少包含每个结点，则G G中任何两个结点间都是相互可达的，故中任何两个结点间都是相互可达的，故G G为强连通图。为强连通图。 “ “”如如G G是强连通图，则任意两个结点之间都是相互可达是强连通图，则任意两个结点之间都是相互可达的，设的，设G GVE，V Vvv1 1,v,v,v,v

24、,v,v ，则，则v v1 1到到v v2 2可达，可达，v v2 2到到v v3 3可达，可达，v v3 3到到v v4 4可达，可达，v v- -到到v v可达，可达，v vn n到到v v1 1可达，可达，由此可得到一条回路由此可得到一条回路(v(v1 1，v v，v v，v v，v v1 1) )，它至少，它至少包含每个结点一次。包含每个结点一次。38离散数学定义定义 设G是一个有向图，G1是G的导出子图，若若G G1 1是弱连通图是弱连通图( (单侧连通图，强连通图单侧连通图，强连通图) )，且没有，且没有包含包含G G1 1的更大的子图是弱连通图的更大的子图是弱连通图( (单侧连通

25、图，强连通图单侧连通图，强连通图) )，则称，则称G G1 1是是极大弱连通子图极大弱连通子图( (极大单侧连通子图，极大强连极大单侧连通子图，极大强连通子图通子图) )或称为或称为弱分图弱分图( (单侧分图，强分图单侧分图，强分图) )。39离散数学例：如上图(a)所示，有：例：由由vv 、vv 、vv1 1,v,v,v,v,v,v,v,v 所导出的子图构成了所导出的子图构成了该图的强分图；该图的强分图；由由vv1 1,v,v,v,v,v,v,v,v,v,v7 7 、vv1 1,v,v,v,v,v,v5 5,v,v,v,v 所导出所导出的子图构成了该图的单侧分图；的子图构成了该图的单侧分图；

26、(a)(a)图本身就是一个弱分图。图本身就是一个弱分图。40离散数学例：如上图如上图(b)(b)所示，有：所示，有：由由vv1 1 、vv 、vv3 3 、vv4 4 、vv5 5,v,v6 6,v,v 所导出的子图所导出的子图构成了该图的强分图；构成了该图的强分图；由由vv1 1,v,v,v,v 、vv1 1,v,v3 3,v,v4 4 、vv,v,v,v,v 所导出的子所导出的子图构成了该图的单侧分图；图构成了该图的单侧分图；由由vv1 1,v,v,v,v,v,v 、vv,v,v,v,v 所导出的子图构成了所导出的子图构成了该图的弱分图。该图的弱分图。41离散数学定理 在有向图G，它的每一

27、个结点必然位于且仅位于一个强分图中；在有向图G，它的每一个结点和每一条边都至少位于一个单向分图中；在有向图G，它的每一个结点和每一条边必然位于且仅位于一个弱分图中。定理42离散数学证：(仅以1)为例加以说明)证：. . 对对 v v V V，令，令S S是是G G中所有与中所有与v v相互可达的结点集，则有相互可达的结点集，则有v v S S，由，由于于v v与与S S中的一切结点相互可达，所以，由可达性具有传递性知：中的一切结点相互可达，所以，由可达性具有传递性知：S S中的一切结点之间是相互可达的，即中的一切结点之间是相互可达的，即S S是是G G的一个强分图，所以，的一个强分图，所以，v

28、 v位于一个强分图中；位于一个强分图中；. . 设设v v还位于另一个强分图还位于另一个强分图T T中，则由中，则由S S中的每个结点都与中的每个结点都与v v相互可相互可达，且达，且T T中的每个结点也都与中的每个结点也都与v v相互可达，所以，由可达性具有传递相互可达，所以，由可达性具有传递性知：性知：S S中的一切结点与中的一切结点与T T中的一切结点之间是相互可达的，即由中的一切结点之间是相互可达的，即由STST就构成了一个更大的强连通的子图，这就与就构成了一个更大的强连通的子图，这就与S S、T T都是两个强分都是两个强分图矛盾，故图矛盾，故G G的每个结点仅位于一个强分图中。的每个

29、结点仅位于一个强分图中。43离散数学例：在图(a)中，结点v1，v2，v3，v4仅位于强分图 v1，v2，v3，v4中，结点中，结点v v55仅位于强分图仅位于强分图 v v5 5 中，但边中，但边v 、v 都不位于强分图中；都不位于强分图中； 结点结点v v1 1，v v2 2，v v3 3，v v4 4，v v55仅位于单向分图仅位于单向分图 v v1 1，v v2 2，v v3 3，v v4 4，v v5 5 ，所有的边，所有的边也都仅位于单向分图中；也都仅位于单向分图中； 结点结点v v1 1，v v2 2，v v3 3，v v4 4，v v55仅位于弱分图仅位于弱分图 v v1 1，

30、v v2 2，v v3 3，v v4 4，v v5 5 ；所有的边也都仅位于弱分图中。；所有的边也都仅位于弱分图中。在图在图(b)(b)中，结点中，结点v v2 2，v v33和边和边v 同时位于两个单向分图同时位于两个单向分图 v v1 1，v v2 2，v v3 3 和和vv2 2，v v3 3，v v4 4 中。中。例：44离散数学7-3 图的矩阵表示一、邻接矩阵邻接矩阵设设G G是一个简单图，是一个简单图，V Vvv1 1,v,v2 2,v,vn n ，E Eee1 1,e,e2 2,e,en n ，则，则n n阶方阵阶方阵A(G)A(G)(a(aijij) )n n n n称为称为G

31、 G的的邻接矩阵邻接矩阵。其中：其中：由邻接矩阵的定义知：其矩阵的元素是一个二值元由邻接矩阵的定义知：其矩阵的元素是一个二值元素，所以，又称该矩阵为素，所以，又称该矩阵为位矩阵位矩阵或或布尔矩阵布尔矩阵。45离散数学例：邻接矩阵：例：46离散数学性质设设G GVE是一个简单图，是一个简单图，则有：则有：如如a aijij1,1,则表示什么？则表示什么？(i,j(i,j 1,2,3,n)1,2,3,n)如对如对 i,ji,j 1,2,3,n,1,2,3,n,都有都有a aijij0 0，则表示什么？则表示什么？如对如对 i,ji,j 1,2,3,n,1,2,3,n,都有都有a aijij1(i1

32、(i j), j), a aiiii0 0，则表示，则表示什么？什么？如如G G是一个无向简单图是一个无向简单图, ,则对任意则对任意v vi i V V，都有：都有：47离散数学性质如G是一个有向简单图，则对任意viV，都有：48离散数学性质6)6)令令B B( (b bijij) )A A A AA A(a(aijij(2)(2) )n n n n，则有：则有：此时，此时，b bijij表示从表示从v vi i到到v vj j长度为长度为2 2的路数目，如的路数目，如b bijij0 0，则无，则无长度为长度为2 2的路，而的路，而b biiii给出了经过给出了经过v vi i的长度为的长

33、度为2 2的回路数目；的回路数目；7)7)令令C C( (c cijij) )A Am mA AA AAA( (a aijij(m)(m) )n n n n，则有：则有：此时，此时，c cijij表示从表示从v vi i到到v vj j长度为长度为m m的数目，如的数目，如c cijij0 0，则无长，则无长度为度为m m的路，而的路，而c ciiii给出了经过给出了经过v vi i的长度为的长度为m m的回路数目。的回路数目。49离散数学定理定理定定理理 设A(G)为图G的邻接矩阵，则(A(G)l中的i行j列元素等于G中联结vi与vj的长度为l的路的数目。证明证明 对l施归纳法当l =2时，

34、由上得知是显然成立。设命题对l = t成立，由故根据邻接矩阵的定义aik表示联结vi与vk长度为1的路的数目，而是联结vk与vj长度为t的路的数目，上式的每一项表示由vi经过一条边到vk，再由vk经过长度为l的路到vj的，总长度为t+1的路的数目。对所有的k求和，即是所有从vi到v的长度为t+1的路的数目，故命题对成立。50离散数学性质如下图，Vv1,v2,v3,v4,v5，其邻接矩阵A、A、A、A4如下：如下：上面图中结点的度数和两结点间长度为上面图中结点的度数和两结点间长度为k k的路的条数。的路的条数。51离散数学定理定理例例:给定一图G=V，E如图所示。求v1与v2之间长度为3的路数，

35、结点v1与v3之间长度为2的路数，在结点v2之间长度为4的回路数？52离散数学二、可达性矩阵二、可达性矩阵(i(i，j j1 1，2 2，3 3，n)n)则称矩阵则称矩阵P P为图为图G G的的可达性矩阵可达性矩阵。定义定义 设设G GVE(n(n，m)m)是一个简单图，是一个简单图，V Vvv1 1,v,v2 2,v,v3 3,v,vn n ，定义一个，定义一个n n阶方阵阶方阵P P(p(pijij) )n*nn*n，其中：，其中：53离散数学二、可达性矩阵 可达性矩阵的求法有两种：可达性矩阵的求法有两种：可达性矩阵的求法有两种：可达性矩阵的求法有两种： 1) 1) 计算矩阵计算矩阵 Bn

36、=A+ABn=A+A2 2+A+A3 3+ 令中不为零的元素等于令中不为零的元素等于1 1，为零的元素不变，为零的元素不变，得到得到P P。 见例题见例题1 1。 Bn=A+ABn=A+A2 2+A+A3 3+A+An n54离散数学例 ：例 ：求如下图所示的图形的可达性矩阵。55离散数学利用布尔求乘和布尔求和的运算直接求可达性矩阵利用布尔求乘和布尔求和的运算直接求可达性矩阵PAA(2)A(3).A(n)A(m)AAA.A (m1,2,3,n)若把邻接矩阵看作是结点集V上关系R的关系矩阵，则可达性矩阵P即为MR，因此可达性矩阵可以用Warshall算法计算2) 2) 利用布尔求乘和布尔求和的运

37、算直接求可达性矩阵利用布尔求乘和布尔求和的运算直接求可达性矩阵56离散数学例：例：利用邻接矩阵的布尔运算求可达性矩阵。57离散数学三：完全关联矩阵三：完全关联矩阵定定义义 给定无向图G，令v1,v2,vp和e1,e2,eq分别记为G的结点和边，则矩阵M(G)=(mij)，其中 称M(G)为完全关联矩阵。 58离散数学例：例：如对于图，可写完全关联矩阵： v1110011v2111000v3001101v4000110e1e2e3e4e5e6v500000059离散数学性质从关联矩阵中可以看出图形的一些性质：图中每一边关联两个结点，故M(G)的每一列 。每一行元素的和数对应于 。一行中的元素全为

38、0，其对应的结点为 。两个平行边其对应的两列相同。同一图当结点或边的编序不同，其对应M(G)仅有行序、列序的差别。 60离散数学定义定义定义定义 给定简单有向图G=V，E，V=v1,v2,vp，E=e1,e2,eq，pq阶矩阵M(G)=(mij)，其中 称M(G)为G的完全关联矩阵。 61离散数学性质从关联矩阵中可以看出图形的一些性质：(1)M(G)的每一列 。每一行元素”1”的个数对应于 ，”-1”的个数对应于 。一行中的元素全为0，其对应的结点为 。62离散数学例：例：如对于图，可写完全关联矩阵： 63离散数学边的合并边的合并 对图G的完全关联矩阵中的两个行相加定义如下：若记vi对应的行为

39、 ，将第i行与第j行相加，规定为：对有向图是指对应分量的加法运算，对无向图是指对应分量的模2的加法运算，把这种运算记作 64离散数学边的合并边的合并-关联矩阵的加法运算例：图 (a)中使v4和v5合并得到图 (b)。65离散数学边的合并边的合并 设图G的结点vi与结点vj合并得到图G，那么M(G)是将M(G)中的第i行与第j行相加而得到。因为若有关项中第r个对应分量有 ，则说明vi与vj两者之中只有一个结点是边er的端点，且将这两个结点合并后的结点vi,j仍是er的端点。若 ，则有两种情况：a)vi与vj都不是边er的端点，那么vi,j也不是er的端点。b)vi与vj都是边er的端点，那么合并

40、后在G中er成为vi,j的自回路，按规定应该被删去。 此外，在M(G)中若有某些列，其元素全为0，说明G中的一些结点合并后，消失了一些对应边 66离散数学定理定理定定理理 如果一个连通图G有r个结点，则其完全关联矩阵M(G)的秩为r-1，即rankM(G)=r-1。证明 这里对无向图进行证明。由于矩阵M(G)的每一列恰有两个1，若把M(G)的其它所有行加到最后一行上(模2加法)，得到矩阵，它的最后一行全为0，因为的秩与M(G)的秩相同，故M(G)的秩小于行数，即rankM(G)r-1。设M(G)的第一列对应边e，且e的端点为vi和vj，调整行序使第i行为第一行，这时M(G)的首列仅在第1行和第

41、j行为1，其余各元素均为0，再把第一行加到第j行上去则得到矩阵M(G)。其中M(G1)是M(G)删去第一行和第一列所得到的矩阵。67离散数学证明证明68离散数学证明（续）证明（续）证明证明由于M(G1)是G1的完全关联矩阵，而G1是由G的两个结点vi和vj合并而得到。由于G是连通的，故G1必为连通图，M(G1)也具有连通图完全关联矩阵的所有性质，故M(G1)没有全零的行。如果M(G1)的第一列全为零，则可将M(G1)的非零列与第一列对调，不影响完全关联矩阵的秩数。因此我们必可以通过调整行序和把一行加到另一行上这两种运算，使M(G1)的第一列首项元素为1，得到69离散数学证明（续）证明（续）证明

42、证明继续上述两种运算，并不改变矩阵的秩，经过r-1次，最后将M(G)变换成如下矩阵。显然M(r-1)(G)有一个(r-1)阶子阵，其行列式的值不为0，故M(r-1)(G)的秩至少为r-1。由和可知rankM(G)=r-1对于有向图的关联矩阵可以仿此证明证明。70离散数学矩阵与图的连通性矩阵与图的连通性无向线图G是连通图当且仅当它的可达性矩阵P的所有元素都均为1；有向线图G是强连通图当且仅当它的可达性矩阵P的所有元素都均为1；有向线图G是单侧连通图当且仅当它的可达性矩阵P及其转置矩阵PT经“布尔求和”运算后所得矩阵P1PPT中除对角线以外的其余元素均为1；有向线图G是弱连通图当且仅当它的邻接矩阵A及其转置矩阵AT经“布尔求和”运算后作为新的邻接矩阵BAAT而求出的可达性矩阵PB中所有元素均为1。71离散数学