离散数学第七章第二节

第7-2讲图的连通性1.路2.连通的概念3.

删除结点和边与图的连通性4.有向图的可达性5.有向图的连通性6.课堂练习7.第7-2讲作业11、路（1）图论中的一个典型问题是从给定的结点出发,沿着边连续移动,到达另一指定结点的问题。所经过的点边序列就形成了路的概念。定义1

给定图G=<V,E>,设v0,v1,v2,…vnV，e1,e2,…,emE，其中ei是关联结点ei-1、ei的边，点边交替序列v0

e1v1e2v2…envn称为v0到vn的路。v0和vn分别称为该路的起点和终点。如果v0=vn，称该路回路。若路中各边均不相同，则称为迹；若路中各结点均不相同，则称为通路；若闭合通路中各结点均不相同，则称为圈。例如右图中：v1

e1v2e5v4e8v5e7v3是迹，也是通路；v2

e3v3e4v2e6v5e8v4e5v2是回路；v2

e3v3e7v5e6v2是圈。21、路（2）定理1

在具有n个结点的图中，如果从结点vj到vk存在一条路，则从结点vj到vk必存在一条不多于n-1边的路。证明：设从结点vj到vk存在一条路，该路的结点序列为vj…vi…vk。如果该路有m条边，则该路的结点序列中有m+1个结点。若m>n-1，则必存在结点vs，它在该路中不止出现一次，可设该路的结点序列为vj…vs…vs…vk。去掉vs到vs之间这段路，则vj…vs…vk仍然是vj到vk的路，只不过路中边数已减少。如果所得的这条路中的边仍然大于n-1，重复上述步骤，可得一条vj到vk的路且路中边数进一步减少。如此继续下去，最终可得一条vj到vk且路中边数不多于n-1条边的路。例如左图有5个结点，v1e1v2e3v3e4v2e6v5e8v4是图中从v1到v4路，它有5条边。去掉v2到

v2之间的路e3v3e4v2，所得的路v1e1v2e6v5e8v4仍然是从v1到v4路，其边数小于5-1。32、连通的概念定义2

在无向图G中，如果从结点u到v存在一条路，则称结点u到v是连通的。

对无向图G=<V,E>而言，结点集合V上的连通关系是等价关系。该连通关系将结点集合作出一个划分，每个划分块连同它们所关联的边称为图G的一个连通分支。

定义3若图G中只有一个连通分支，则称图G是连通的。

右图所示图G有两个连通分支G1和G243、删除结点和边与图的连通性(1)定义4

设无向图G=<V,E>中，若有结点集V1V,使图G删除了V1的所有结点后所得的子图是不连通的,而删除了V1的任一真子集后所得的子图仍是连通的,则称V1是图G的点割集。如果某个结点构成一个点割集,则称该结点为割点。结点和边的删除在图中删除结点v,就是将结点v及v所关联的边统统删除。在图中删除某边,则只须删除该边，而保留边所关联的结点。例：删除割点。53、删除结点和边与图的连通性（2）由定义5可知，连通度是为了产生一个不连通图所要删除结点的最少数目。那么，非连通图的连通度为0；存在割点的连通图的连通度为1；完全图Kn删除m(m<n-1)个结点后仍是连通的，删除n-1个结点后成为仅有一个孤立结点的平凡图，故规定K(Kn)=n-1。定义5非完全图G的点连通度(简称连通度)定义为：K(G)=min{|Vi||Vi是点割集}63、删除结点和边与图的连通性(3)定义6

设无向图G=<V,E>为连通图，若有边集E1E,使图G删除了E1中的所有边后所得的子图是不连通的,而删除了E1的任一真子集后所得的子图仍是连通的,则称E1是图G的边割集。如果某条边构成一个边割集,则称该边为割边(亦称为桥)。例：右图中，E1={e1,e2}E2={e1,e3,e5,e7}是边割集；E3={e8}是桥。74、有向图的可达性

无向图的连通概念不能直接推广到有向图。

在有向图G=<V,E>中，如果从结点u和v有一条路，则称从u可达v。如果u可达v，则u、v之间的最短路（短程线）的长度称为结点u、v之间的距离，记作d<u,v>。

d<u,v>0

d<u,u>=0

d<u,v>+d<v,w>d<u,w>如果从u到v不可达，则记d<u,v>=。

距离的概念也适用于无向图

注意，因为是有向图，d<u,v>一般不等于d<v,u>。将D=max{d<u,v>|u,vG}称为图G的直径。可达性是有向图结点集上的二元关系，它是自反的和传递的，但一般不是对称的。所以可达不是等价关系。85、有向图的连通性（1）定义8在简单有向图G中，任何一对结点间，如果至少从一个结点到另一个结点可达，则称该图是单侧连通的。如果图G中任何一对结点之间相互可达，则称图G是强连通的。如果在图G中略去边的方向视为无向图是连通的，则称图G是弱连通的。例：分析下列各有向图的连通性。解：图G1是强连通的；G2是单侧连通的；G3是弱连通的。95、有向图的连通性（2）定理4一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个结点一次。证：充分性。如果图G中有一个回路，它至少包含每个结点一次，则G中任何两个结点相互可达，故图G是强连通的。

必要性。如果有向图G是强连通的，则G中任何两个结点相互可达，故可从图中任一结点v出发，经由图中所有的结点，再返回v，从而形成一个回路。105、有向图的连通性（3）定义9在简单有向图G中，具有强连通性的最大子图称为强分图；具有单侧连通性的最大子图称为单侧分图；具有弱连通性的最大子图称为弱分图。例如，下图右侧图中，包含结点{v1,v2,v3,v4}的子图是强分图；仅包含一个孤立结点v5的子图也是强分图，但包含结点{v1,v2,v4}的子图不是强分图115、有向图的连通性（4）定理5有向图G=<V,E>的每个结点位于且只位于一个强分图中。证：设任意vV,令S是图G中所有与v相互可达的结点集合，当然vS。则S是G的一个强分图。因此，G的每个结点必位于一个强分图中。假设v位于两个强分图S1和S2中，因S1中每个结点与v相互可达,而v与S2中每个结点也相互可达,故S1和S2中任何一对结点通过v都是相互可达的。这与S1和S2为强分图矛盾。故G的每个结点位于且只位于一个强分图中。126、课堂练习练习1若无向图G中恰有两个奇数度结点u和v,则u、v之间必有一条路。解：由7-1定理2，任何图中奇数度结点为偶数个。所以u、v必位于G的同一连通分支中。从u出发构造一条迹(边不重复的路)，方法是从u出发经关联u的一条边e1到达u1，若deg(u1)为偶数，则可经关联u1的一条边e2到达u2。如此继续，每边只取一次，直到一个