1、第二节第二节 图的道路与连通图的道路与连通一、无向图的道路一、无向图的道路1。定义定义：图：图G中由结点和边交替构成的序列中由结点和边交替构成的序列p=v0e1v1e2v2.ekvk 称为由称为由v0到到vk的一条的一条道道路路，其中每条，其中每条ei和和vi-1及及vi关联。关联。v0称为道路称为道路 p的的起点起点，vk称为道路称为道路 p的的终终点点。p中的边数中的边数k称为称为道路的长度道路的长度。只由一个结点构成的道路称为只由一个结点构成的道路称为零道路零道路。例例：下图中下图中 p1=v1e1v1e2v2e2v1e5v4e8v3e6v2 p2=v1e2v2e6v3e8v4e5v1e
2、4v3e9v5 p3=v1e5v4e8v3e6v2 （简记为：（简记为：p3=v1v4v3v2）p4=v6 都是道路都是道路。v1v2v3v4v6v5e9e10e12e8e7e2e4e5e6e3e1e112。道路的分类：。道路的分类：迹迹：任何满足道路定义的道路：任何满足道路定义的道路。简单道路简单道路：边不重复出现的道路。：边不重复出现的道路。基本道路基本道路：结点不重复出现的道路。：结点不重复出现的道路。例例：上图中，：上图中，p1是迹，是迹，p2是简单道路，是简单道路，p3是基本道路，是基本道路，p4是零道路。是零道路。3。回路回路：起点和终点相同的道路。：起点和终点相同的道路。边不重复
3、出现的回路称为边不重复出现的回路称为简单回路简单回路。结点不重复出现的回路称为结点不重复出现的回路称为圈圈。例例：下图中，：下图中，c1是一般回路，是一般回路，c2是简单是简单回路，回路，c3是圈。是圈。例例：下图中：下图中 c1=v1e1v1e2v2e7v4e8v3e4v1e3v2e2v1 c2=v1e1v1e2v2e3v1e5v4e8v3e4v1 c3=v1e5v4e10v6e12v5e9v3e4v1 （c3可简记为：可简记为：c3=v1v4v6v5v3v1）都是）都是回回路。路。c1是一般回路，是一般回路，c2是简单回路，是简单回路，c3是圈。是圈。v1v2v3v4v6v5e9e10e1
4、2e8e7e2e4e5e6e3e1e114。定理定理：设：设G是是n阶图，如果存在从结点阶图，如果存在从结点u到到 v的道路，则必存在长度不超过的道路，则必存在长度不超过n-1的道路的道路。证明要点证明要点：如果结点：如果结点u到到v的道路的道路 p的长度的长度 超过超过n-1，则，则 p中至少有中至少有n+1个结点，因而个结点，因而 道路中至少有一个结点出现两次，如道路中至少有一个结点出现两次，如 viei.v1，则去掉，则去掉ei.vi后仍是结点后仍是结点u到到v的的 道路，但是道路长度至少短道路，但是道路长度至少短1。重复这一。重复这一 过程，即得所需结论。过程，即得所需结论。二、无向图
5、的连通问题二、无向图的连通问题1。定义定义:如果存在从结点如果存在从结点u到结点到结点v的道路，则称的道路，则称u到到v是是连通连通的的。结点集结点集V上的上的“连通连通”关系具有性质：自反、对称、关系具有性质：自反、对称、传递。传递。2。如果图。如果图G中任何两个结点都是连通的，则称中任何两个结点都是连通的，则称G是是连通图连通图。3。图。图G中的极大连通子图称为图中的极大连通子图称为图G的的支支，图图G的的支数支数记为记为(G)。图图G连通当且仅当连通当且仅当(G)=1。例例：下图中：下图中(G)=3。v1v6v4v7v5v2v3v84。连通图连通图G=(V,E)的点割集定义：设的点割集定
6、义：设S V，如果，如果 (G-S)1，则称，则称S是是G的一个的一个点割集点割集。S是是G的一个点割集，而的一个点割集，而S的任何真子集都不是点割集时，的任何真子集都不是点割集时，称称S是是G的一个的一个基本点割集基本点割集。如如 S1=v2，v5，S2=v2，v6,S3=v2，v7，S4=v3，v5,S5=v4 由单个结点（如由单个结点（如u）构成的点割集简称为）构成的点割集简称为割点割点。v1v6v4v7v5v2v3定理定理 结点结点u是图是图G的割点当且仅当存在两结点的割点当且仅当存在两结点v和和w，使，使v到到w的任何道路都经过的任何道路都经过u。证明要点证明要点：“”,当当u是割点
7、时，则是割点时，则G u至少有至少有2支，支，从这从这2支中各选一个结点即可。支中各选一个结点即可。“”,反之，如果反之，如果 v到到 w的任何道路都经过的任何道路都经过 u，则去掉，则去掉 u后后，v和和 w各在各在 G u的的 1支中，即支中，即u是割点。是割点。5。连通图连通图G=(V,E)的边割集定义：设的边割集定义：设F E，如果，如果(G-F)1，则称，则称F是是G的一个的一个边割集边割集。F是是G的一个边割集，而的一个边割集，而F的任何真子集都不是边割集时，的任何真子集都不是边割集时，称称 F是是G的一个的一个基本边割集基本边割集。如如F1=v2v3，v3v7，F2=v2v3，v
8、5v7,F3=v1v4，F4=v2v4，v2v6，v5v6,F5=v4v6，v2v6，v2v5，v3v7 由单条边（如由单条边（如uv）构成的边割集简称为）构成的边割集简称为割边割边。v1v6v4v5v2v3v7定理定理 边边e是图是图G的割边当且仅当的割边当且仅当 e 不在不在G的任何回的任何回路上。路上。证明要点证明要点：“”:当当e是割边时，则是割边时，则G e有有2支，支，因而因而e 不在不在G的任何回路上。的任何回路上。“”:反之，如果反之，如果 e不在任何回路上，则去掉不在任何回路上，则去掉 e 后，后，e 关联的两个结点各在关联的两个结点各在 G e的的 1支中，即支中，即 e
9、是割是割边。边。6.图的连通度图的连通度(限无环图限无环图G)(1)点连通度点连通度:记为记为(G),定义为定义为最小基本点割集基数最小基本点割集基数,当当G Kn(G)n 1,当当G Kn例如下图中例如下图中,(G)2v1v6v4v5v2v3v7v8(2)边连通度边连通度:记为记为(G),定义为定义为最小基本边割集基数最小基本边割集基数,当当G K1(G)0,当当G K1例如下图中例如下图中,(G)2,(G)2v1v6v4v5v2v3v7v8练习练习:求下列图的求下列图的(G),(G),和和(G)=2(G)=2=2(G)=2(G)=2=2(G)=2(G)=3=4(3)连通度定理连通度定理:(
10、G)(G)证明要点证明要点:首先首先,每个结点关联的边构成一个边割集每个结点关联的边构成一个边割集,于是于是(G).下面证明下面证明(G)(G)：首先注意对每个基本边割集首先注意对每个基本边割集F，(G-F)=2；其次设；其次设F含含(G)条边，条边，G-F的的2支为支为G1和和G2，若，若G不是二部图，不是二部图，则去掉这支中与则去掉这支中与F关联的全部结点即可；若关联的全部结点即可；若G是二是二部图，则交替删去这部图，则交替删去这2支中与支中与F关联的结点即可。关联的结点即可。四、有向图的道路四、有向图的道路 1。定义定义：如果图：如果图G中由结点和边交替构成的序列中由结点和边交替构成的序
11、列 p=v0e1v1e2v2.ekvk,满足其中每条满足其中每条 ei 是是 vi-1的出边和的出边和 vi 的的入边，则称入边，则称 p为由为由 v0到到 vk 的一条的一条有向道路有向道路。在下图中，一些有向道路在下图中，一些有向道路 p1=v1v4v2v1v3v5v4 p2=v3v2v1v3v5v4v2 p3=v5v4v2v1v3v1v2v3v4v52。有向道路的分类：。有向道路的分类：有向迹有向迹：任何满足定义的有向道路：任何满足定义的有向道路。有向简单道路有向简单道路：边不重复的有向道路。：边不重复的有向道路。有向基本道路有向基本道路：结点不重复的有向道路。：结点不重复的有向道路。3
12、。有向回路有向回路：起点和终点相同的有向道路。：起点和终点相同的有向道路。边不重复的有向回路称为边不重复的有向回路称为有向简单回路有向简单回路。结点不重复的有向回路称为结点不重复的有向回路称为有向圈有向圈，在下图中，一些有向回路在下图中，一些有向回路 p1=v1v4v2v1v3v5v4v2v1 p2=v3v2v1v3v5v4v3 p3=v5v4v2v1v3v5v1v2v3v4v5五、五、有向图的连通问题有向图的连通问题 1。如果存在从结点。如果存在从结点u到结点到结点v的有向道路，则称的有向道路，则称u可达可达v。结点集结点集V上的上的“可达可达”关系具有性质：自反、关系具有性质：自反、传递。
13、传递。定理：如果在定理：如果在n阶有向图中结点阶有向图中结点u可达可达v，则必存，则必存在从结点在从结点u到结点到结点v的长度不超过的长度不超过n-1的有向道路。的有向道路。2。有向图。有向图G的连通有如下三个层次：的连通有如下三个层次：强连通图强连通图：任何一对不同结点都相互可达。：任何一对不同结点都相互可达。单向连通图单向连通图：任何一对不同结点间，至少从一个结点可：任何一对不同结点间，至少从一个结点可达另一个结点。达另一个结点。弱连通图弱连通图：不看边的方向时是连通的。：不看边的方向时是连通的。abcd单向连通单向连通弱连通弱连通abcdabcd强连通强连通3。强连通的性质。强连通的性质
14、死锁问题的强连通背景死锁问题的强连通背景定理定理:有向图有向图G是强连通图当且仅当存在一条包含所有结是强连通图当且仅当存在一条包含所有结点的有向回路点的有向回路。证明要点证明要点：当：当G强连通时强连通时,据定义可依次构造道路据定义可依次构造道路 v1v2 v3 vn v1,反过来是明显的反过来是明显的.定义：有向图定义：有向图G的极大强连通子图称为的极大强连通子图称为强分图强分图。例：下面有个强分图例：下面有个强分图:G(v2,v3,v4),G(v5,v6)G(v1)v1v2v5v3v4v6定理：每个结点都只位于一个强分图中。定理：每个结点都只位于一个强分图中。证明要点证明要点：强连通是结点
15、集合上：强连通是结点集合上的一个等价关系，的一个等价关系，由每个等价类诱导的子图是一个由每个等价类诱导的子图是一个强分图强分图 作业：作业：习题习题9。2 1、2、5(吴子华吴子华)or习题十习题十 15、16、19(冯伟森冯伟森)附加题附加题1：证明：证明 1的图必含回路，反之成立吗？的图必含回路，反之成立吗？附加题附加题2：证明连通图的：证明连通图的1 度结点不是割点。度结点不是割点。第三节第三节 图的矩阵表示图的矩阵表示一、邻接矩阵一、邻接矩阵 1。设。设G=(V,E)是有向简单图是有向简单图,其中其中 V=v1,v2,.,vn,定义矩阵定义矩阵A=(ai j)n n如下如下:1 如果如
16、果(vi,vj)E ai j=0 如果如果(vi,vj)E 称称A为为G的的邻接矩阵邻接矩阵.下面有向图对应的邻接矩阵是下面有向图对应的邻接矩阵是 v1 v2 v3 v4 v5 v1 0 0 1 1 0 v2 1 0 1 1 0 A =v3 0 0 0 0 1 v4 0 0 1 0 0 v5 0 0 0 1 0 v1v2v5v3v4 2。邻接矩阵的性质：。邻接矩阵的性质：邻接矩阵等价地描述了有向图的信息。邻接矩阵等价地描述了有向图的信息。矩阵行和等于结点出度，列和等于入度。矩阵行和等于结点出度，列和等于入度。设设A2=(a(2)i j)，则，则 a(2)i j=1 k n(ai kakj)a(
17、2)i j 0当且仅当至少存在当且仅当至少存在ai k=1且且 akj=1，也，也就是存在从就是存在从vi到到vj的长度为的长度为2的有向道路。因此的有向道路。因此 a(2)i j 的值表达了的值表达了从从vi到到vj的长度为的长度为2的有向道路的有向道路数目数目。例如，对于前面的邻结矩阵例如，对于前面的邻结矩阵 v1 v2 v3 v4 v5 v1 0 0 1 0 1 v2 0 0 2 1 1 A2=v3 0 0 0 1 0 v4 0 0 0 0 1 v5 0 0 1 0 0 从中可以看出，存在一条从从中可以看出，存在一条从v1到到v3的长度为的长度为2的道路，的道路，2条从条从v2到到v3的
18、长度为的长度为2的道路，的道路，1条从条从v4到到v5的长度为的长度为2的道路，的道路，不存在从不存在从v5到到v2的长度为的长度为2的道路等等。的道路等等。v1v2v5v3v4 v1 v2 v3 v4 v5 v1 0 0 0 1 1 v2 0 0 1 1 2 A3=v3 0 0 1 0 0 v4 0 0 0 1 0 v5 0 0 0 0 1 v1v2v5v3v4 类似地，可以构造类似地，可以构造 0 0 1 1 0 0 0 1 2 1 A4=0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 可对照图找出长度为可对照图找出长度为4的有向道路的有向道路.设设Am=(a(m)i j)，那
19、么那么a(m)i j 的值表达了的值表达了从从vi 到到vj长度为长度为m的有向道路数目的有向道路数目。a(m)i i 的值表达了通过的值表达了通过vi的长度为的长度为m的有向回路数目。的有向回路数目。3。可达矩阵。可达矩阵 设设G=(V,E)是有向简单图是有向简单图,其中其中 V=v1,v2,.,vn,定义矩阵定义矩阵P=(pi j)n n如下如下:1 vi非平凡可达非平凡可达 vj pi j=0 其它其它 称称P为为G的的可达矩阵可达矩阵.可达矩阵可达矩阵P可通过邻结矩阵可通过邻结矩阵A求得，求得，方法之一是计算矩阵和：方法之一是计算矩阵和：B=A+A2+.+An-1 然后，令然后，令pi
20、 j=1当且仅当当且仅当bi j 0。例如，由前面的例子可得例如，由前面的例子可得 B=A+A2+A3+A4 0 0 3 3 2 1 0 5 5 4 =0 0 1 1 2 0 0 2 1 1 0 0 1 2 1 其中每个非其中每个非0的的bi j表达了表达了vi到到vj 的长度不超过的长度不超过4的道路数目，的道路数目，若若 bi j=0，表明不存在从表明不存在从vi到到vj 的非平凡道路。的非平凡道路。v1v2v5v3v4由矩阵由矩阵B直接可导出下面的可达矩阵：直接可导出下面的可达矩阵：0 0 1 1 1 1 0 1 1 1 P=0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 可
21、达矩阵也可以利用可达矩阵也可以利用Warshall算法求得。算法求得。v1v2v5v3v44。由可达矩阵构造图的强分图。由可达矩阵构造图的强分图 令令Q=P PT=(qi j)n n，其中，其中 1 i=j qi j=pi j pji i j 那么，在矩阵那么，在矩阵Q中第中第k行中元素行中元素1对应列对应列的结点，构成图的一个强分图。的结点，构成图的一个强分图。例例：根据前面例子得到的可达矩阵，可得：根据前面例子得到的可达矩阵，可得 0 0 1 1 1 0 1 0 0 0 1 0 1 1 1 0 0 0 0 0 P PT=0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1
22、 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 =0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 从第从第1行知道，行知道，v1单独在一个强分图中单独在一个强分图中；从第；从第2行知道，行知道，v2单独在一个强分图中单独在一个强分图中；从第；从第3、4、5行知道，行知道，v3、v4、v5共同构成一个强分图共同构成一个强分图。由此可见，该图有由此可见，该图有3个强分图，它们分别包个强分图，它们分别包含结点子集含结点子集v1、v2、v3，v4，v5。可由下图验证。可由下图验证。v1v2v5v3v4二、关联矩阵二、关联矩阵 1。定义定义：设设G=
23、(V,E)是有向简单图是有向简单图,其中其中 V=v1,v2,.,vn,E=e1,e2,.,em,定义矩阵定义矩阵M=(mi j)n m如下如下:1 如果如果ej是是vi的出边的出边 mi j=-1 如果如果ej是是vi的入边的入边 0 其它其它 称称M为为G的的关联矩阵关联矩阵.例例：下面有向图对应的关联矩阵如下：下面有向图对应的关联矩阵如下：e1 e2 e3 e4 e5 e6 e7 e8 v1 -1 1 1 0 0 0 0 0 v2 1 0 0 1 1 0 0 0 M=v3 0 0 -1 0 0 -1 1 0 v4 0 -1 0 -1 0 1 0 -1 v5 0 0 0 0 -1 0 -1 1 v1v2v5v3v4e1e2e3e5e4e6e7e82。关联矩阵的性质：。关联矩阵的性质：关联矩阵等价地描述了有向图的信息。关联矩阵等价地描述了有向图的信息。矩阵每行中矩阵每行中1的个数等于对应结点出度，的个数等于对应结点出度，-1的个数等的个数等于结点的入度。于结点的入度。矩阵每列恰有一个矩阵每列恰有一个1和和-1。作业：作业：习题习题9。3 3(吴子华吴子华)or习题十习题十 30(冯伟森冯伟森)
