2-連通圖的一些等價定義

蘇 靜，馬 飛，姚 兵

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

2-連通圖的一些等價定義

蘇 靜，馬 飛，姚 兵

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

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

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

1 預(yù)備知識

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

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

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

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

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

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

2 結(jié)論及證明

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

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

(2)對任意2個頂點u，v∈V(G)，圖G中至少存在2條內(nèi)部不相交的(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條路的內(nèi)部頂點均不在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構(gòu)成的(u，v)-路內(nèi)部不相交，命題(2)得證.

當d(u，v)=k>1時，令w是某條最短(u，v)-路位于v之前的頂點，有d(u，w)=k-1.由歸納假設(shè)，G中有內(nèi)部不相交的(u，w)-路P和Q.由于圖G是2-連通的，故G-w是連通的，進而圖G含有一條(u，v)-路R.如果R與P，Q中的某一個無內(nèi)部交點，則證明完畢；若路R與2條路P和Q都相交，設(shè)z是路R上最后一個(v之前)屬于P∪Q的頂點，不妨設(shè)z∈V(P)，即得到內(nèi)部不相交的(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，且每一個返回步驟產(chǎn)生的圖都是2-連通圖.

必要性.若保連通點收縮運算產(chǎn)生的圖G-{x，y}有割點w，即圖G-{x，y}至少有2個分支H1和H2，使得收縮2個頂點x和y后的新頂點{x，y}在分支H1中.但圖H2在圖G中是一個孤立的分支，這與圖G是2-連通圖沖突.從而證明了保連通點收縮運算產(chǎn)生的圖仍然是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] 高隨祥.圖論與網(wǎng)絡(luò)流理論[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

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

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

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

A