• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

      2017-03-24 07:06:56靜,馬飛,姚
      關(guān)鍵詞:西北師范大學(xué)條路子集

      蘇 靜,馬 飛,姚 兵

      (西北師范大學(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

      猜你喜歡
      西北師范大學(xué)條路子集
      由一道有關(guān)集合的子集個數(shù)題引發(fā)的思考
      西北師范大學(xué)作品
      大眾文藝(2023年9期)2023-05-17 23:55:52
      這條路
      西北師范大學(xué)美術(shù)學(xué)院作品選登
      拓撲空間中緊致子集的性質(zhì)研究
      西北師范大學(xué)美術(shù)學(xué)院作品選登
      西北師范大學(xué)美術(shù)學(xué)院作品選登
      關(guān)于奇數(shù)階二元子集的分離序列
      這條路
      心聲歌刊(2018年6期)2018-01-24 00:56:12
      每一次愛情都只是愛情的子集
      都市麗人(2015年4期)2015-03-20 13:33:22
      武平县| 汽车| 东辽县| 怀安县| 高阳县| 清新县| 安阳市| 信宜市| 皋兰县| 辽阳市| 东城区| 梁山县| 松溪县| 台中县| 满城县| 肥东县| 定襄县| 西平县| 黔江区| 沧州市| 梨树县| 华亭县| 高邑县| 阿荣旗| 肇源县| 广饶县| 桐柏县| 中江县| 高阳县| 泽库县| 浙江省| 西丰县| 河东区| 大同市| 上栗县| 古田县| 滨海县| 本溪市| 深州市| 郎溪县| 岢岚县|