图论讲义第2章-连通性.docx

《图论讲义第2章-连通性.docx》由会员分享，可在线阅读，更多相关《图论讲义第2章-连通性.docx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论讲义第2章-连通性第二章图的连通性在第一章中已经定义连通图是任二顶点间都有路相连的图。对于连通图，其连通的程度也有高有低。例如，下列三个图都是连通图。对于图G1，删除一条边或一个顶点便可使其变得不连通；而对于图G2，至少需要删除两条边才能使其不连通，可以以删除一个顶点使其不连通；对于图G3，要毁坏其连通性，则至少需要删除三条边或三个顶点。本章主要讨论怎样通过图的顶点集、边集和不交的路集合的构造性质来获知图的连通性程度。通过研究割边和割点来刻画1连通图的特性；定义连通度和边连通度来度量连通图连通程度的高低；通过不交路构造和元素的共圈性质来反映图的2连通和k连通性。2.1割点和割边定义2.1.

2、1设)(GVv，假如)()(GwvGw?，则称v为G的一个割点。注：该定义与某些著作中的定义有所不同，主要是在环边的顶点能否算作割点上有区别。例如，下列图中u,v两点是其割点。定理2.1.1假如点v是简单图G的一个割点，则边集E(G)可划分为两个非空子集1E和2E，使得1EG和2EG恰好有一个公共顶点v。证实留作习题。推论2.1.1对连通图G，顶点v是G的割点当且仅当vG?不连通。定理2.1.2设v是树T的顶点，则v是T的割点当且仅当1)(vd。证实：必要性：设v是T的割点，下面用反证法证实1)(vd。若0)(=vd，则1KT?，显然v不是割点。若1)(=vd，则vT?是有1)(?vT条边的无

3、圈图，故是树。进而)(1)(TwvTw=?。因而v不是割点。以上均与条件矛盾。充分性：设1)(vd，则v至少有两个邻点u,w。路uvw是T中一条),(wu路。因T是树，uvw是T中唯一的),(wu路，进而)(1)(TwvTw=?。故v是割点。证毕。推论2.1.2每个非平凡无环连通图至少有两个顶点不是割点。证实：设T是G的生成树，则T至少有两个叶子u,v，由上一定理知，u,v都不是T的割点，即1)()(=?TwuTw。由于uT?是图uG?的生成树，故)(1)()()(GwTwuTwuGw=?=?，因而u不是G的割点。同理v也不是G的割点。证毕。定理2.1.3设v是连通图G的一个顶点，则下列命题等

4、价：1v是G的割点；2存在)(,GVwu，使得vwu,且v在每条),(wu路上；3存在)(vGV的一个划分：)(vGVWU=，=WU，使得对Uu?和Ww?，v在每条),(wu路上。证实：1?3因v是割点，故vG?至少有两个连通分支1G、2G。令)(1GVU=而)()(1vGVGVW=，则对Uu?和Ww?，u、w分别属于vG?的不同的连通分支。可见G中所有的),(wu路必经过v否则vG?中仍有),(wu路，这与u、w分别属于vG?的不同的连通分支矛盾。3?2显然。2?1若v在每条),(wu路上，则vG?中不存在),(wu路，即vG?不连通，故v是G的割点。证毕。定义2.1.2设)(GEe，假如)

5、()(GweGw?，则称e为G的一条割边。例如下列图中，边uv，边wu都是其割边。定理2.1.4边e是G的割边当且仅当e不在G的任何圈中。证实：证其逆否命题：e不是割边当且仅当e含在G的某个圈中。必要性：设e=xy不是割边。假定e位于G的某个连通分支1G中，则eG?1仍连通。故在eG?1中有),(yx路P，P+e便构成1G中一个含有e的圈。充分性：设e含在G的某个圈C中，而C含于某连通分支1G中，则eG?1仍连通。故)()(GweGw=?，这讲明e不是割边。证毕。定理2.1.5一个连通图是树当且仅当它的每条边都是割边。证实：连通图G是树?G无圈?任何边e不含在圈中?任何边e是G的割边。证毕。定

6、理2.1.6设e是连通图G的一条边，则下列命题等价：1e是G的割边；2e不在G的任何圈上；3存在)(,GVvu，使得e在每条),(vu路上；4存在)(GV的一个划分：)(GVWU=，=WU，使得对Uu?和Ww?，e在每条),(wu路上。证实：1?2定理2.1.4已证。1?4?3?1的证实与定理2.1.3的证实类似。2.2连通度和边连通度定义2.2.1对图G，若V(G)的子集V使得)()(GwVGw?，则称V为图G的一个顶点割集。含有k个顶点的顶点割集称为k顶点割集。注：1割点是1顶点割集。2完全图没有顶点割集。定义2.2.2图G的连通度定义为()min|GVV=是连通图G的顶点割集。十分地，完

7、全图的连通度定义为1)(?=K,空图的连通度定义为0,不连通图的连通度定义为0。注：(1)若G是平凡图，则0)(=G。(2)使得)(|GV=的顶点割集V称为G的最小顶点割集。(3)若kG)(，则称G为k连通的。(4)按上述定义，图G是k连通的，当且仅当G的最小点割集至少含k个顶点，当且仅当G中没有k?1点割集，当且仅当从G中任意去掉k?1个顶点后，所剩图仍连通。(5)根据k连通的定义，若图G是k连通的，则它也是k?1连通、k?2连通、1连通的。因而，所有非平凡连通图都是1连通的。定义2.2.3对图G，若E(G)的子集E使得)()(GwEGw?，则称E为图G的一个边割集。含有k条边的边割集称为k

8、边割集。注：(1)对非平凡图G，若E是一个边割集，则EG不连通。(2)一条割边构成一个1边割集。(3)设)(GVS?，)(GVS?，SS,，记号,SS表示一端在S中另一端在S中的所有边的集合。对图G的每个边割集E，必存在非空的)(GVS?，使得,SS是G的一个边割集，其中SVS=。定义2.2.4图G的边连通度定义为()min|GEE=是连通图G的边割集。完全图的边连通度定义为1)(?=K，空图的边连通度定义为0，不连通图的边连通度定义为0。注：(1)对平凡图G，0)(=G。(2)是含有割边的连通图，则1)(=G。(3)使得)(|GE=的边割集E称为G的最小边割集。(4)若kG)(，则称G为k边

9、连通的。(5)按上述定义，图G是k边连通的，当且仅当G的最小边割集至少含k条边，当且仅当G中没有k?1边割集，当且仅当从G中任意去掉k?1条边后，所剩图仍连通。(6)根据k边连通的定义，若图G是k边连通的，则它也是k?1边连通、k?2边连通、1边连通的。因而，所有非平凡连通图都是1边连通的。例如，下列图中，G1是连通的且有割点和割边，因而是1连通的和1边连通的；G2的最小点割集含1个点，最小边割集含2条边，故它是1连通的和2边连通的；G3的最小点割集和最小边割集分别含2个点和2条边，因而是2连通的和2边连通的；G4的最小点割集和最小边割集分别含3个点和3条边，因而是3连通的和3边连通的。定理2

10、.2.1)()()(GGG。证实：先证)()(GG。对图的边连通度()G作数学归纳法。对()G1的图G，若2GK=，则显然()11G=?=；若2GK，则G至少含三个点。设e=uv是G的一条割边，则u或v必是割点，故()G=1。总之，此时()G=()G1。假设对所有k=的图，都有，则对()1Gk=+的图G，设E是它的一个1k+边割集。任取边()euvEG=，则Ee?是Ge?的最小边割集，故()Gek?=。由归纳假设，()()GeGe?。取Ge?的最小点割集T，则|()()TGeGek=?=，且Tu构成G的最小点割集。故()|11()GTuTkG=+=。归纳完成。再证)()(GG。设=)(vd。删

11、去与v关联的条边后，G变成不连通图，故这条边构成G的一个边割集。因而)()(GG。证毕。下列图G1是一个2,3=和4=的图，G2是一个1,2=和3=的图。G2G3G1G2定理2.2.2对具有个顶点条边的连通图G，有2()G?。证实：因()2()vVGdv=，故2，由定理2.2.1，2。由于是整数，因而2?。证毕。定理2.2.3设G是一个简单图，k是一个自然数，若2()2kG+?，则G是k连通的。证实：用反证法。假设G不是k连通的，则G的连通度k120()1()Gdu?+(G)120()1()Gdu?+可见(G)=。证毕。推论2.2.2设非空简单图G中任二不相邻顶点u和v都知足()()1dudv

12、+?，则(G)(G)=。证实：若G中任意两点都相邻，则G是完全图，(G)1(G)=?=，结论成立。若G中有不相邻顶点，则diam2G。但由于任二不相邻顶点u和v都知足()()1dudv+?，即任二不相邻顶点u和v都有公共的邻点。因而又有diam2G。进而diam2G=。由定理2.2.4便得(G)(G)=。证毕。根据推论2.2.2，下面的结论是显然的。推论2.2.3设G是一个简单图，若1()2G?，则(G)(G)=。固然直径为2的图能使得边连通度到达上界，但其点连通度仍然可能很小。例如下列图的直径为2，其连通度只要1。2.32-连通图的性质定义2.3.1无割点的连通图称为一个块(block)。设

13、G是一个图，H是G的一个子图，若H本身是一个块且它是G中具有此性质的极大子图，则称H是图G的一个块。下面是块及图的块的例子。块含4个块的图注：至少有三个顶点的图是块当且仅当它是2连通图。若只要两个顶点，则有反例，例如2K是个块，但不是2连通的。关于2连通图块，有下列重要结论。定理2.3.1(Whitney,1932)3的图G是2连通图块当且仅当G中任二顶点共圈。证实：充分性：设G中任二顶点在同一圈上，欲证G是2连通的。对)(GVw?，任取)(,wGVvu?。由条件，u,v在G中共处于某个圈C上。若Cw?，则在wG中u,v仍在圈C上；若Cw，则wG?中u,v在路wC?上。总之u,v在wG?中有路

14、相连。由u,v的任意性，wG?是连通图，故w不是G的割点。再由w的任意性知，G无割点，即G是2连通的。必要性：设G是2连通图，欲证任二顶点u,v都在同一圈上。对距离),(vud作归纳法。1),(=vud时，因2，故G中无割边，uvG?仍连通。因而uvG?中存在一条),(vu路1P。这表明在G中u,v都在圈uvP+1上。假定kvud路与边xy构成一个圈，它含有u及边e；设Cy?。由Whitney定理,x不是割点。故存在不含x的),(yu路P，令w是P上从y出发第一个与C公共的顶点，则C上x-u-w段P上),(yw段xy构成一个含u和e=xy的圈。3?4：与2?3类似可证。4?5：设G中任二边共圈

15、。对)(,GVvu?及)(GEe?，假如uve=，结论显然成立；假如u或v之一是e的端点，比方u是e的端点而v的一个邻点是w，则e与边wv共圈，故显然有),(vu路含有边e。下面假定u和v都不是e的端点。因任二边共圈显然任二点共圈，故由2?3知u与e共圈，v也与e共圈。设这二圈分别是1C和2C。若2Cu或1Cv，则结论成立；若2Cu?且1Cv?，则如下构作含e的),(vu路：从u出发沿1C到达1C与2C的第一个公共顶点w，再从w出发沿2C含e的部分到达v，即可。5?6：对)(,GVwvu?，设与w相关联的一条边为e。由5，存在),(vu路含有边e，于是含有w。6?7：对)(,GVwvu?，存在

16、),(wu路P含有顶点v，则P的从u到v的一段不含有w。7?1：由于对)(GVw?及)(,GVvu?，存在),(vu路不含有顶点w，故w不是割点。由w的任意性，G无割点。进而G是块。证毕。2.4Menger定理上节的Whitney定理表明，对一个图G，G的最小点割集含至少2个点当且仅当G中任意两点间都有至少2条内部点不交的路，即“分离G中任意两点所需删除的最少顶点数和这两点间内部点不交路的最大条数要么都大于等于2，要么都不超过2。这涉及到图的连通性能的两个度量：删除顶点时图保持连通的能力和顶点间不交途径的重数。Whitney定理讲明对2连通图这两种连通性度量是等价的。下列Menger定理显示，

17、这一结论对任意k连通图都成立。设G是一个简单图，x,y是G中任二不同顶点。假如从G中删去一组顶点后不再有(x,y)路则称这组顶点分离x和y，而称这组顶点为一个(x,y)分离集。G中含点数最少的(x,y)分离集称为最小(x,y)分离集，其顶点数称为G的(x,y)分离数，记为s(x,y)。此外，将G中两两内部点不交的(x,y)路的最大条数记为r(x,y)。定理2.4.1Menger,1927对任意图G，设x,y是G中两个不相邻顶点，则G中分离x,y所需的最少顶点数等于G中两两内部点不交的(x,y)路的最大条数，即s(x,y)=r(x,y)。证实：首先，对任意图G和G中任意两个不相邻顶点x,y，显然

18、有s(x,y)r(x,y)。下面用反证法证实对任意图G和G中任意两个不相邻顶点x,y，s(x,y)r(x,y)。假设结论不真。则存在图G和G中两个不相邻顶点x,y，使得s(x,y)r(x,y)。取G为具有这种性质的所有图中顶点数最少并且边数最少的一个，即：对具有上述性质的任何一个图H，要么(G)(H)r(x,y)0，可知G是连通图。假如s(x,y)=1，则必须r(x,y)=0,这与G是连通图矛盾。因而s(x,y)1。2对G的任二异于x,y的相邻顶点u和v，存在G的顶点子集U，知足|U|(,)1sxy=?且Uu和Uv都是G的(x,y)分离集。事实上，设e=uv，H=G?e。H的(x,y)分离数s

19、H(x,y)s(x,y)?1，(?)否则存在H的(x,y)分离集R使得|R|s(x,y)?2，则Ru是G的(x,y)分离集，且只含s(x,y)?1个点，这与G的(x,y)分离数为s(x,y)矛盾。另一方面，由于s(x,y)r(x,y)，H中两两内部点不交的(x,y)路的条数(,)Hrxyr(x,y)s(x,y)?1。(?)由G的最小性可知，H中的(x,y)分离数等于H中两两内部点不交的(x,y)路的最大条数，即sH(x,y)=(,)Hrxy。结合(?)式和(?)式，知sH(x,y)=(,)Hrxy=s(x,y)?1。设U是H的一个最小(x,y)分离集，由于H与G只相差一条边e=uv，易见Uu和

20、Uv都是G的(x,y)分离集。3用(),()GGNxNy表示x和y在G中邻点的集合，则()()GGNxNy=。事实上，假设()()GGNxNy，则u?()()GGNxNy。设HGu=?。由G的最小性，H中(x,y)分离数等于H中两两内部点不交的(x,y)路的最大条数。与上述2的证实类似可知，图H的(x,y)分离数sH(x,y)=s(x,y)?1，故H中存在s(x,y)?1条两两内部点不交的(x,y)路。显然它们和路xuy一起构成G的s(x,y)条两两内部点不交的(x,y)路。这与G的取法矛盾。4记k=s(x,y)。假如12,kWwww=是G的一个最小(x,y)分离集，则()GWNx?或者()G

21、WNy?。事实上，设Gx、Gy为图GW?中分别包含x和y的连通分支，用1G表示由(G)xVW在G中导出的子图，2G表示由(G)yVW在G中导出的子图。显然12(G)(G)VVW=。假如1(G)1k=+，则(G)xVx=，此时结论显然成立。同理，2(G)1k=+时结论成立。下面假设1(G)2k+，且2(G)2k+。给1G添加一个新顶点v*，将它与1G中属于W的每个顶点都连新边，这样获得的图记为1G?。若1G?中存在(x,v*)分离集S知足|S|1，故U。由结论4，1Uv()GNx?或者1Uv()GNy?，但由于1()xvEG及结论，可知U()GNx?，且U?()GNy；同样，由结论4，2Uv()GNx?或者2Uv()GNy?，但上面已知U()GNx?，由结论可知必定2Uv()GNx?，进而2()GvNx。这与P是G的最短(x,y)路矛盾。证毕。由Menger定理可得到Whitney定理的如下推广推论2.4.11+k的图G是k连通图当且仅当G中任二顶点至少被k条两两内部无公共顶点的路所连。证实：必要性：用反证法。设G是k连通图。假定G中存在两个顶点x,y，它们之间两两内部无公共顶点的路最多只要m条， m