蘇 靜，馬 飛，姚 兵

(西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 蘭州 730070)

2-連通圖的一些等價(jià)定義

蘇 靜，馬 飛，姚 兵

(西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 蘭州 730070)

通過(guò)從不同角度深入理解并挖掘 2-連通圖的本質(zhì)特征，給出了多種關(guān)于 2-連通圖的等價(jià)性命題.從最長(zhǎng)圈及收縮點(diǎn)對(duì)等方面出發(fā)，提出了新的有關(guān) 2-連通圖的命題，并證明了其相互間的等價(jià)性.

2-連通圖；耳分解；扇；路；圈

1 預(yù)備知識(shí)

眾所周知，連通圖在通信網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等網(wǎng)絡(luò)研究中有著廣泛的應(yīng)用.[1-2]例如，人們希望一個(gè)完善的通信網(wǎng)絡(luò)不會(huì)因?yàn)槟承┙Y(jié)點(diǎn)的損壞而癱瘓，即希望所有可能的信息傳輸線路構(gòu)成的圖能夠保持連通.[3-5]因此，對(duì)連通圖的深入研究不僅是數(shù)學(xué)理論的需要，更是為實(shí)際網(wǎng)絡(luò)結(jié)構(gòu)提供可靠的理論依據(jù)和可行的技術(shù)手段的需要.

關(guān)于2-連通圖的充分必要條件可以在諸多文獻(xiàn)中看到.West[6]給出了2-連通圖的8種等價(jià)性命題.Bondy和Murty[7]也給出了關(guān)于2-連通圖特征的3種等價(jià)性命題.這些相互等價(jià)的定義均從不同的角度來(lái)刻畫2-連通圖.本文挖掘并整理了有關(guān)2-連通圖的若干充分必要條件，又從圖的收縮運(yùn)算以及圈結(jié)果等角度出發(fā)，給出了新的命題，同時(shí)為已有命題和新命題的等價(jià)性證明做了簡(jiǎn)化和統(tǒng)一性工作.

定義1[7]若圖G的頂點(diǎn)子集V′使得圖G-V′不連通，則稱V′為G的頂點(diǎn)割.k-頂點(diǎn)割是指有k個(gè)頂點(diǎn)的頂點(diǎn)割.圖G的所有k-頂點(diǎn)割中最小的k稱為G的連通度.若G的連通度大于或等于k，則稱G為k-連通圖.

定義2[6]圖G的一個(gè)耳朵是指G中內(nèi)部頂點(diǎn)的度均為2的極大路.圖G的耳分解是滿足下面條件的分解C0，P1，…，Pk：C0是一個(gè)圈；當(dāng)i≥1時(shí)，Pi是G的子圖C0∪P1∪…∪Pi的一個(gè)耳朵.

定義3[6]對(duì)圖G的一個(gè)頂點(diǎn)x和一個(gè)頂點(diǎn)子集U，(x，U)-扇是指從x到U的每個(gè)頂點(diǎn)的路所構(gòu)成的集合，且此集合中任意2條路在圖G中只有一個(gè)公共的頂點(diǎn)x.

按照定義2，一條邊也是一個(gè)耳朵.文獻(xiàn)[7]定義沒(méi)有割點(diǎn)的連通圖為塊.圖的極小邊割稱為鍵.一條路的非起、終點(diǎn)的頂點(diǎn)叫做這條路的內(nèi)部頂點(diǎn).圖G中的一族路稱為內(nèi)部不相交的，如果G中沒(méi)有這樣的頂點(diǎn)，它是這族路當(dāng)中一條以上路的內(nèi)部頂點(diǎn).圖G的一個(gè)頂點(diǎn)子集S稱為連通集合，如果圖G有一個(gè)連通子圖H，使得V(H)=S.

2 結(jié)論及證明

定理1 設(shè)圖G為至少有4個(gè)頂點(diǎn)的圖，則下面命題相互等價(jià)：

(1)圖G是2-連通圖；[7]

(2)對(duì)任意2個(gè)頂點(diǎn)u，v∈V(G)，圖G中至少存在2條內(nèi)部不相交的(u，v)-路；[7]

(3)圖G中的任意2個(gè)頂點(diǎn)都位于同一個(gè)圈上；[7]

(4)將G中的路uwv換成邊uv后得到的圖是2-連通圖，其中w是2-度頂點(diǎn)；

(5)在G中添加一個(gè)新頂點(diǎn)w，并將w與G中2個(gè)不同的頂點(diǎn)u，v分別相連得到的圖是2-連通圖；

(6)對(duì)于圖G的具有至少2個(gè)頂點(diǎn)的子集U和子集U外的一個(gè)頂點(diǎn)x，圖G有一個(gè)(x，U)-扇；[6]

(7)圖G的任意一個(gè)頂點(diǎn)和任意一條邊都位于同一個(gè)圈上；[6]

(8)圖G的任意頂點(diǎn)要么在G的最長(zhǎng)圈C上，要么在一條起、終點(diǎn)均在C上的路中；

(9)圖G的任意2條邊都位于同一個(gè)圈上；[6]

(10)對(duì)每一對(duì)滿足|X|，|Y|≥2的不相交頂點(diǎn)子集X和Y，圖G含有2條完全不相交的路，使得每條路的起點(diǎn)在X中，終點(diǎn)在Y中，且這2條路的內(nèi)部頂點(diǎn)均不在X和Y中；[6]

(11)對(duì)于圖G的任意2個(gè)頂點(diǎn)u，v和任意的邊e，圖G有包含邊e的(u，v)-路；[8]

(12)對(duì)于圖G的任意3個(gè)頂點(diǎn)u，v，w，圖G有包含頂點(diǎn)w的(u，v)-路；[8]

(13)圖G有耳分解，并且G的每個(gè)圈均是某個(gè)耳分解的起始圈；[8]

(14)對(duì)于圖G的任意3個(gè)頂點(diǎn)u，v，w，圖G有不包含頂點(diǎn)w的(u，v)-路；[8]

(15)圖G的任意2條邊都在圖G的同一個(gè)鍵中.[9]

當(dāng)d(u，v)=1時(shí)，因圖G是2-連通的，故邊uv不是圖G的割邊.于是邊uv一定被包含在某個(gè)圈中，即圖G-uv中的(u，v)-路與邊uv構(gòu)成的(u，v)-路內(nèi)部不相交，命題(2)得證.

當(dāng)d(u，v)=k>1時(shí)，令w是某條最短(u，v)-路位于v之前的頂點(diǎn)，有d(u，w)=k-1.由歸納假設(shè)，G中有內(nèi)部不相交的(u，w)-路P和Q.由于圖G是2-連通的，故G-w是連通的，進(jìn)而圖G含有一條(u，v)-路R.如果R與P，Q中的某一個(gè)無(wú)內(nèi)部交點(diǎn)，則證明完畢；若路R與2條路P和Q都相交，設(shè)z是路R上最后一個(gè)(v之前)屬于P∪Q的頂點(diǎn)，不妨設(shè)z∈V(P)，即得到內(nèi)部不相交的(u，v)-路，其中一條由路P的一部分(從u到z)和路R的一部分(z到v)組成，另一條由路Q和邊wv組成.

圖2 (u1，v1)-路與(u2，v2)-路有一個(gè)公共的頂點(diǎn)

圖3 兩條路有多個(gè)交點(diǎn)的情形

對(duì)圖G的任意2個(gè)頂點(diǎn)x和y，若圖G-{x，y}是連通的，則稱縮點(diǎn)對(duì)圖G·{x，y}是對(duì)圖G實(shí)施了一次保連通點(diǎn)收縮運(yùn)算.

定理2 圖G是2-連通圖，當(dāng)且僅當(dāng)對(duì)圖G可以實(shí)施一系列保連通點(diǎn)收縮運(yùn)算，將圖G收縮到4個(gè)頂點(diǎn)的2-連通圖C4，C4+e和K4(如圖4所示)中的一個(gè).

圖4 全部4個(gè)頂點(diǎn)的2-連通圖

證明 充分性證明是顯然的，只要從收縮到最后的C4，或C4+e，或K4原路返回到圖G，且每一個(gè)返回步驟產(chǎn)生的圖都是2-連通圖.

必要性.若保連通點(diǎn)收縮運(yùn)算產(chǎn)生的圖G-{x，y}有割點(diǎn)w，即圖G-{x，y}至少有2個(gè)分支H1和H2，使得收縮2個(gè)頂點(diǎn)x和y后的新頂點(diǎn){x，y}在分支H1中.但圖H2在圖G中是一個(gè)孤立的分支，這與圖G是2-連通圖沖突.從而證明了保連通點(diǎn)收縮運(yùn)算產(chǎn)生的圖仍然是2-連通圖.當(dāng)收縮到4個(gè)頂點(diǎn)的圖G*時(shí)，易知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] 高隨祥.圖論與網(wǎng)絡(luò)流理論[M].北京：高等教育出版社，2009：1-298.

[9] REINHARD DIESTEL.圖論[M].于青林，王濤，王光輝，譯.北京：高等教育出版社，2013：1-370.

(責(zé)任編輯：李亞軍)

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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61163054，61363060，61662066).

蘇靜(1993—)，女，碩士，主要從事圖的標(biāo)號(hào)及復(fù)雜網(wǎng)絡(luò)研究；通信作者：姚兵(1956—)，男，教授，主要從事圖著色與標(biāo)號(hào)以及復(fù)雜網(wǎng)絡(luò)研究.

O 157.5 [學(xué)科代碼] 110·7470

A