2-连通图的一些等价定义

苏 静，马 飞，姚 兵

(西北师范大学数学与统计学院，甘肃 兰州 730070)

2-连通图的一些等价定义

苏 静，马 飞，姚 兵

(西北师范大学数学与统计学院，甘肃 兰州 730070)

通过从不同角度深入理解并挖掘 2-连通图的本质特征，给出了多种关于 2-连通图的等价性命题.从最长圈及收缩点对等方面出发，提出了新的有关 2-连通图的命题，并证明了其相互间的等价性.

2-连通图；耳分解；扇；路；圈

1 预备知识

众所周知，连通图在通信网络、社交网络、交通网络等网络研究中有着广泛的应用.[1-2]例如，人们希望一个完善的通信网络不会因为某些结点的损坏而瘫痪，即希望所有可能的信息传输线路构成的图能够保持连通.[3-5]因此，对连通图的深入研究不仅是数学理论的需要，更是为实际网络结构提供可靠的理论依据和可行的技术手段的需要.

关于2-连通图的充分必要条件可以在诸多文献中看到.West[6]给出了2-连通图的8种等价性命题.Bondy和Murty[7]也给出了关于2-连通图特征的3种等价性命题.这些相互等价的定义均从不同的角度来刻画2-连通图.本文挖掘并整理了有关2-连通图的若干充分必要条件，又从图的收缩运算以及圈结果等角度出发，给出了新的命题，同时为已有命题和新命题的等价性证明做了简化和统一性工作.

定义1[7]若图G的顶点子集V′使得图G-V′不连通，则称V′为G的顶点割.k-顶点割是指有k个顶点的顶点割.图G的所有k-顶点割中最小的k称为G的连通度.若G的连通度大于或等于k，则称G为k-连通图.

定义2[6]图G的一个耳朵是指G中内部顶点的度均为2的极大路.图G的耳分解是满足下面条件的分解C0，P1，…，Pk：C0是一个圈；当i≥1时，Pi是G的子图C0∪P1∪…∪Pi的一个耳朵.

定义3[6]对图G的一个顶点x和一个顶点子集U，(x，U)-扇是指从x到U的每个顶点的路所构成的集合，且此集合中任意2条路在图G中只有一个公共的顶点x.

按照定义2，一条边也是一个耳朵.文献[7]定义没有割点的连通图为块.图的极小边割称为键.一条路的非起、终点的顶点叫做这条路的内部顶点.图G中的一族路称为内部不相交的，如果G中没有这样的顶点，它是这族路当中一条以上路的内部顶点.图G的一个顶点子集S称为连通集合，如果图G有一个连通子图H，使得V(H)=S.

2 结论及证明

定理1 设图G为至少有4个顶点的图，则下面命题相互等价：

(1)图G是2-连通图；[7]

(2)对任意2个顶点u，v∈V(G)，图G中至少存在2条内部不相交的(u，v)-路；[7]

(3)图G中的任意2个顶点都位于同一个圈上；[7]

(4)将G中的路uwv换成边uv后得到的图是2-连通图，其中w是2-度顶点；

(5)在G中添加一个新顶点w，并将w与G中2个不同的顶点u，v分别相连得到的图是2-连通图；

(6)对于图G的具有至少2个顶点的子集U和子集U外的一个顶点x，图G有一个(x，U)-扇；[6]

(7)图G的任意一个顶点和任意一条边都位于同一个圈上；[6]

(8)图G的任意顶点要么在G的最长圈C上，要么在一条起、终点均在C上的路中；

(9)图G的任意2条边都位于同一个圈上；[6]

(10)对每一对满足|X|，|Y|≥2的不相交顶点子集X和Y，图G含有2条完全不相交的路，使得每条路的起点在X中，终点在Y中，且这2条路的内部顶点均不在X和Y中；[6]

(11)对于图G的任意2个顶点u，v和任意的边e，图G有包含边e的(u，v)-路；[8]

(12)对于图G的任意3个顶点u，v，w，图G有包含顶点w的(u，v)-路；[8]

(13)图G有耳分解，并且G的每个圈均是某个耳分解的起始圈；[8]

(14)对于图G的任意3个顶点u，v，w，图G有不包含顶点w的(u，v)-路；[8]

(15)图G的任意2条边都在图G的同一个键中.[9]

当d(u，v)=1时，因图G是2-连通的，故边uv不是图G的割边.于是边uv一定被包含在某个圈中，即图G-uv中的(u，v)-路与边uv构成的(u，v)-路内部不相交，命题(2)得证.

当d(u，v)=k>1时，令w是某条最短(u，v)-路位于v之前的顶点，有d(u，w)=k-1.由归纳假设，G中有内部不相交的(u，w)-路P和Q.由于图G是2-连通的，故G-w是连通的，进而图G含有一条(u，v)-路R.如果R与P，Q中的某一个无内部交点，则证明完毕；若路R与2条路P和Q都相交，设z是路R上最后一个(v之前)属于P∪Q的顶点，不妨设z∈V(P)，即得到内部不相交的(u，v)-路，其中一条由路P的一部分(从u到z)和路R的一部分(z到v)组成，另一条由路Q和边wv组成.

图2 (u1，v1)-路与(u2，v2)-路有一个公共的顶点

图3 两条路有多个交点的情形

对图G的任意2个顶点x和y，若图G-{x，y}是连通的，则称缩点对图G·{x，y}是对图G实施了一次保连通点收缩运算.

定理2 图G是2-连通图，当且仅当对图G可以实施一系列保连通点收缩运算，将图G收缩到4个顶点的2-连通图C4，C4+e和K4(如图4所示)中的一个.

图4 全部4个顶点的2-连通图

证明 充分性证明是显然的，只要从收缩到最后的C4，或C4+e，或K4原路返回到图G，且每一个返回步骤产生的图都是2-连通图.

必要性.若保连通点收缩运算产生的图G-{x，y}有割点w，即图G-{x，y}至少有2个分支H1和H2，使得收缩2个顶点x和y后的新顶点{x，y}在分支H1中.但图H2在图G中是一个孤立的分支，这与图G是2-连通图冲突.从而证明了保连通点收缩运算产生的图仍然是2-连通图.当收缩到4个顶点的图G*时，易知G*∈{C4，C4+e，K4}.

[1] PAOLO CRUCITTI，VITO LATORA，MASSIMO MARCHIORI，et al.Error and attacktolerance of complex networks[J].Physica A，2004，340：388-394.

[2] KRAPIVSKY P L，REDNER S，LEYVRAZ F.Connectivity of growing random networks[J].Phys Rev Lett，2000，85：4629-4632.

[3] YAO BING，YANG CHAO，YAO MING，et al.Graphs as models of scale-free networks[J].Applied Mechanics and Materials，380/381/382/383/384：2720-2723.

[4] YAO BING，WANG HONG YU，YAO MING，et al.On the collapse of graphs related to scale-free networks[J].International Conference on Information Science and Technology，2013：738-743.

[5] YAO BING，LIU XIA，ZHANG WAN JIA，et al.Applying graph theory to the internet of things[J].IEEE International Conference on High Performance Computing and Communications，2013：2354-2361.

[6] DOUGLAS B W.Introduction to graph theory[M].2nd ed.Berkeley：Pearson，2006：81-287.

[7] BONDY J A，MURTY U S R.Graph theory with applications[M].New York：North Holland，1976：47-138.

[8] 高随祥.图论与网络流理论[M].北京：高等教育出版社，2009：1-298.

[9] REINHARD DIESTEL.图论[M].于青林，王涛，王光辉，译.北京：高等教育出版社，2013：1-370.

(责任编辑：李亚军)

Probing equivalent definitions of 2-connected graphs

SU Jing，MA Fei，YAO Bing

(College of Mathematics and Statistics，Northwest Normal University，Lanzhou 730070，China)

By digging more properties of 2-connected graphs from different aspects，some equivalent propositions of 2-connected graphs are given.Furthermore，several new equivalent propositions of 2-connected graphs are proposed by longest circles and graph contraction operation，and the equivalent proofs between the propositions are derived.

2-connected graph；ear decomposition；fan；path；cycle

1000-1832(2017)01-0033-05

10.16163/j.cnki.22-1123/n.2017.01.007

2015-10-28

国家自然科学基金资助项目(61163054，61363060，61662066).

苏静(1993—)，女，硕士，主要从事图的标号及复杂网络研究；通信作者：姚兵(1956—)，男，教授，主要从事图着色与标号以及复杂网络研究.

O 157.5 [学科代码] 110·7470

A