离散数学第七章第二节

1、1第7-2讲 图的连通性1. 路2. 连通的概念3. 删除结点和边与图的连通性4. 有向图的可达性5. 有向图的连通性6. 课堂练习7. 第7-2讲 作业21、路（1） 图论中的一个典型问题是从给定的结点出发图论中的一个典型问题是从给定的结点出发,沿着边连续移沿着边连续移动动,到达另一指定结点的问题。所经过的点边序列就形成了路到达另一指定结点的问题。所经过的点边序列就形成了路的概念。的概念。定义1 给定图给定图G=,设设v0, v1, v2,vn V， e1, e2, , em E，其中其中ei是关联结点是关联结点ei-1、 ei的边，的边，点边交替序列点边交替序列v0 e1v1 e2 v2

2、envn称为称为v0到到vn的路的路。v0和和vn分别称为该路的起点和终点。如分别称为该路的起点和终点。如果果v0=vn，称该路，称该路回路回路。 若路中各边均不相同，则称为若路中各边均不相同，则称为迹迹；若路中各；若路中各结点结点均不相同，均不相同，则称为则称为通路通路；若闭合通路中各；若闭合通路中各结点结点均不相同，则称为均不相同，则称为圈圈。例如右图中例如右图中：v1 e1v2 e5 v4e8v5 e7v3是迹，也是通路；是迹，也是通路； v2 e3v3 e4v2e6v5 e8v4 e5v2是回路；是回路； v2 e3v3 e7v5e6v2 是圈。是圈。31、路（2）定理1 在具有在具有

3、n n个结点的图中，如果从结点个结点的图中，如果从结点v vj j到到v vk k存在一条路，存在一条路，则从结点则从结点v vj j到到v vk k必存在一条不多于必存在一条不多于n-1n-1边的边的路。路。证明：设设从结点从结点v vj j到到v vk k存在一条路，存在一条路，该路的结点序列为该路的结点序列为vj vi vk。如果。如果该路有该路有m条边，则该路的结点序列中有条边，则该路的结点序列中有m+1个结点。个结点。 若若mn-1，则必，则必存在存在结点结点vs，它在该路中不止出现一次，可设该路的结它在该路中不止出现一次，可设该路的结点序列为点序列为vj vs vs vk。去掉。去

4、掉vs 到到 vs 之间这段路，则之间这段路，则vj vs vk仍然仍然是是v vj j到到v vk k的路，只不过路中边数已减少。的路，只不过路中边数已减少。 如果所得的这条路中的边如果所得的这条路中的边仍然大于仍然大于n-1，重复上述步骤，可得一条，重复上述步骤，可得一条v vj j到到v vk k的路且路中边数进一步减少。如此继续下去，最终的路且路中边数进一步减少。如此继续下去，最终可得一条可得一条v vj j到到v vk k且路中且路中边数不多于边数不多于n-1条边条边的路。的路。例如左图有例如左图有5个结点，个结点，v1e1v2 e3v3e4v2 e6v5 e8v4是图是图中中从从v

5、1到到v4路，它有路，它有5条边。去掉条边。去掉v2到到 v2 之间的路之间的路e3v3e4 v2 ，所得的路，所得的路v1e1v2 e6v5 e8v4仍然是从仍然是从v1到到v4路，其边数小于路，其边数小于5-1。42、连通的概念定义2 在无向图G中，如果从结点u到v存在一条路，则称结点u到v是连通的。 对无向图对无向图G= 而言，结点集合而言，结点集合V上的连通关系是等价上的连通关系是等价关系。该连通关系将结点集合作出一个划分，每个划分块连关系。该连通关系将结点集合作出一个划分，每个划分块连同它们所关联的边称为图同它们所关联的边称为图G的一个的一个连通分支连通分支。 定义3 若图图G G中

6、只有一个连通分支，则称中只有一个连通分支，则称图图G G是连通的是连通的。 右图所示图右图所示图G有有两个连通分支两个连通分支G1和和G253、删除结点和边与图的连通性(1)定义4 设无向图G=中，若有结点集V1V,使图G删除了V1的所有结点后所得的子图是不连通的,而删除了V1的任一真子集后所得的子图仍是连通的,则称V1是图G的点割集。如果某个结点构成一个点割集,则称该结点为割点。v 结点和边的删除结点和边的删除 在图中在图中删除结点删除结点v,就是将结点就是将结点v及及v所关联的边统统删除。所关联的边统统删除。 在图中在图中删除某边删除某边,则只须删除该边，而保留边所关联的结点。则只须删除该

7、边，而保留边所关联的结点。例：删除割点。删除割点。63、删除结点和边与图的连通性（2） 由定义5可知，连通度是为了产生一个不连通图所要删除结点的最少数目。那么，非连通图的连通度为0；存在割点的连通图的连通度为1；完全图Kn删除m(mn-1)个结点后仍是连通的，删除n-1个结点后成为仅有一个孤立结点的平凡图，故规定K(Kn)=n-1。定义5 非完全图G的点连通度点连通度( (简称连通度) )定义为： K(G)=min|Vi| Vi是点割集73、删除结点和边与图的连通性(3)定义6 设无向图G=为连通图，若有边集E1E,使图G删除了E1中的所有边后所得的子图是不连通的,而删除了E1的任一真子集后所

8、得的子图仍是连通的,则称E1是图G的边割集。如果某条边构成一个边割集,则称该边为割边(亦称为桥)。例：右图中，右图中，E E1 1=e=e1 1,e,e2 2 E E2 2=e=e1 1,e,e3 3,e,e5 5,e,e7 7 是边割集；是边割集；E E3 3=e=e8 8 是桥。是桥。84、有向图的可达性n 无向无向图的图的连通连通概念不能直接推广到有向图。概念不能直接推广到有向图。n 在有在有向向图图G=G=中，如果从结点中，如果从结点u u和和v v有一条路，则称从有一条路，则称从u u可达可达v v。n 如果如果u u可达可达v v，则，则u u、v v之间的最短路（之间的最短路（短

9、程线短程线）的长度称为）的长度称为结点u u、v v之间的之间的距离距离，记作，记作dd。 dd 0 0 dd=0=0 dd+ +dd dd如果从如果从u u到到v v不可达，则记不可达，则记d=d= 。 距离的概念也适用于无距离的概念也适用于无向向图图n 注意，因为是有注意，因为是有向向图，图，dd一般不等于一般不等于dd。n 将将D=maxd|u,vD=maxd|u,v G G 称为称为图图G G的直径的直径。n 可达性是有可达性是有向向图结点集上的二元关系，它是自反的和传递图结点集上的二元关系，它是自反的和传递的，但一般不是对称的。所以可达不是等价关系。的，但一般不是对称的。所以可达不是

10、等价关系。95、有向图的连通性（1）定义8 在简单有向图G中，任何一对结点间，如果至少从一个结点到另一个结点可达，则称该图是单侧连通的。如果图G中任何一对结点之间相互可达，则称图G是强连通的。如果在图G中略去边的方向视为无向图是连通的，则称图G是弱连通的。例：分析下列各有向图的连通性。例：分析下列各有向图的连通性。解：解：图图G G1 1是是强连通的；强连通的； G G2 2是是单侧连通的；单侧连通的； G G3 3是是弱连通的。弱连通的。105、有向图的连通性（2）定理4 一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个结点一次。证：充分性。充分性。如果如果图图G G中有一个回路

11、，它至少包含每个结点中有一个回路，它至少包含每个结点一次，则一次，则G G中任何两个结点相互可达，故图中任何两个结点相互可达，故图G G是强连通的。是强连通的。 必要性。必要性。如果有如果有向图向图G G是强连通的，则是强连通的，则G G中任何两个结点相中任何两个结点相互可达，故可从图中任一结点互可达，故可从图中任一结点v v出发，经由图中所有的结点，出发，经由图中所有的结点，再返回再返回v v，从而形成一个回路。，从而形成一个回路。115、有向图的连通性（3）定义9 在简单有向图G中，具有中，具有强连通性的最大子图称为强分图；具有具有单侧连通性的最大子图称为单侧分图；具有具有弱连通性的最大子

12、图称为弱分图。例如，下图右侧图中，包含结点例如，下图右侧图中，包含结点vv1 1,v,v2 2,v,v3 3,v,v4 4 的子图是强分的子图是强分图；仅包含一个孤立结点图；仅包含一个孤立结点v v5 5的子图也是强分图，但包含结点的子图也是强分图，但包含结点vv1 1,v,v2 2,v,v4 4 的子图不是强分图的子图不是强分图125、有向图的连通性（4）定理5 有向图G=的每个结点位于且只位于一个强分图中。证：设任意设任意v v V,令S是图图G G中所有与中所有与v v相互可达的结点集合，相互可达的结点集合，当然当然v S S。则则S是G G的一个强分图。因此，的一个强分图。因此，G G

13、的每个结点必位于的每个结点必位于一个强分图中。一个强分图中。 假设假设v v位于两个强分图位于两个强分图S S1 1和和S S2 2中，因中，因S S1 1中每个结点与中每个结点与v v相互可相互可达达, ,而而v v与与S S2 2中每个结点也相互可达中每个结点也相互可达, , 故故S S1 1和和S S2 2中任何一对结点中任何一对结点通过通过v v都是相互可达的。这与都是相互可达的。这与S S1 1和和S S2 2为强分图矛盾。故为强分图矛盾。故G G的的每每个结点位于且只位于一个强分图中。个结点位于且只位于一个强分图中。136 6、课堂练习课堂练习练习1 若无向图若无向图G G中恰有两

14、个奇数度结点中恰有两个奇数度结点u u和和v,v,则则u u、v v之间必有之间必有一条路。一条路。解：由由7-1定理定理2，任何图中，任何图中奇数度结点为奇数度结点为偶数个。所以偶数个。所以u、v必必位于位于G的同一连通分支中。的同一连通分支中。 从从u出发构造一条迹出发构造一条迹(边不重复的路边不重复的路)，方法是从，方法是从u出发经关联出发经关联u的一条边的一条边e1到达到达u1，若，若deg(u1)为偶数，则可经关联为偶数，则可经关联u1的一条的一条边边e2到达到达u2。如此继续，每边只取一次，直到一个。如此继续，每边只取一次，直到一个奇数度结点奇数度结点为止。如果该点是为止。如果该点是v v，则命题得证。如果该点仍是，则命题得证。如果该点仍是u u