數(shù)學與應用數(shù)學畢業(yè)論文-2-連通[4_2]-圖中的圈以及含有Hamilton圈的一個充分條件的再證明.doc

1畢業(yè)論文題目：2-連通4,2-圖中的圈以及含有Hamilton圈的一個充分條件的再證明學院：數(shù)學與信息科學學院專業(yè)：數(shù)學與應用數(shù)學畢業(yè)年限：2012屆學生姓名：學號：指導教師：22-連通4,2-圖中的圈以及含有Hamilton圈的一個充分條件的再證明摘要：圖論(GraphTheory)的研究開始于200多年前,關于圖論的第一篇論文是1736年Euler發(fā)表的,他用圖論的方法解決了格尼斯堡(Konigsberg)七橋問題.圖的Hamilton問題是圖論中一個十分重要且又十分活躍的研究課題,1857年,愛爾蘭數(shù)學家哈密頓提出:一個連通圖有哈密頓圈的充要條件是什么?這樣一個問題.但是這個問題至今仍未能解決,以Hamilton問題為出發(fā)點發(fā)展起了對圖的圈性質(zhì)的研究,這些性質(zhì)主要包括Hamilton性、泛圈性、完全圈可擴性等.本文的主要內(nèi)容包括三個部分:在第一部分中主要介紹了文章中所涉及的一些概念、術語符號和本文的研究背景及已有的結(jié)果；在第二部分中討論2-連通4,2-圖中的圈；在第三部分中討論了圖中含有Hamilton圈的一個充分條件.關鍵詞：s,t-圖；連通度；s-點連通圖；完全圈可擴性；最長圈；Hamilton圈；獨立數(shù)中圖分類號:O157.5TheCyclesin2-connected4,2-graphsandanotherproofofasufficientconditionforthegraphcontainingHamiltoncyclesAbstract:GraphTheorybegan200yearsago,Eulerpublishedthefirstpaperongraphtheoryin1736,heusedgraphtheorytosolvetheKonigsbergSevenBridges.theHamiltonproblemisaveryimportantandactiveresearchtopicingraphtheory,In1857,IrishmathematicianHamiltonputforwardaproblem:“whatisthenecessaryandsufficientconditionwhenaconnectedgraphhasaHamiltoncycle.”However,ithasnotbeensolveduntilnow,AtthesametimebasedonHamiltonproblem,aresearchonnaturesofcyclesingraphhasbeencarriedout.Thesenaturesarehamiltonicity,pancyclicity,extensibilityetc.Themaincontentofthispaperconsistsofthreeparts:inthefirstpartintroducessomeoftheconceptstermssymbolscoveredinthearticle,andtheresearchbackgroundandtheexistingresults；inthesecondpartwediscussedthecyclesin2-connected4,2-graphs；inthethirdpartwediscussedasufficientconditionforthegraphcontainsHamiltoncycle.Keywords:s,t-graph；connectivity；s-verticesconnectedgraph；fullycycleextensibility；thelongestcycle；Hamiltoncycle；independencenumber31預備知識1-21.1符號概念介紹本文考慮的圖是有限、無向、簡單圖,文中所使用的記號和術語約定如下:設G=(V(G),E(G)是一個圖,V(G)、E(G)分別表示G的頂點集和邊集.|G|=|V(G)|表示G中頂點的數(shù)目,稱為G的階,|E(G)|表示G中邊的數(shù)目；對頂點集V1,V2,VmV(G),用GV1,V2,Vm表示G中由V1,V2,Vm導出的子圖；對vV(G)及G的子圖H,記NH(v)=uV(H):uvE(G),NG(v)簡記為N(v)；dH(v)=|NH(v)|稱圖G中點v的度,dG(v)也簡記為d(v).用,分別表示圖G中頂點的最小度和最大度,即:=mind(v):vV(G),=maxd(v):vV(G)；定義圖G的連通度K(G)為使圖G不連通所要刪去的頂點的最小數(shù)目,對任意的kK(G),稱G為k-連通的；對V(G)的子集S、T,令E(S,T)=stE(G):sS,tT；設C=V1V2VrV1,是G的一個圈,Vi,VjV(C),用Vi-1和Vi+1分別表示C上的點Vi-1和Vi+1,Vi-1和Vi+1也分別簡記成Vi-和Vi+；用ViCVj和ViC_Vj(1Ijr)分別表示C上的路ViVi+1Vj和ViVi-1Vj.；|C|=|V(C)|稱為圈C的長度,若C的長度為r,則稱C為G的一個r-圈；G中經(jīng)過G的每個頂點恰一次的路叫做G的的Hamilton路,同樣地G中經(jīng)過G的每個頂點恰一次的圈叫做G的Hamilton圈；如果一個圖G中存在一個Hamilton圈,則稱G為Hamilton的；如果圖G的任意兩個頂點之間都有一條Hamilton路,則稱G為Hamilton連通的；對一個有n個頂點的圖G,如果對任意的k(3kn),G都有長度為k的圈,則稱G為泛圈圖；如果圖G滿足:(1)G的每一個頂點都在一個3-圈上；(2)對G中任意一個圈C,只要|C|S|的獨立集S,G的最大獨立集的頂點數(shù)稱為G的獨立數(shù),記為(G).22-連通4,2-圖中的圈32.1關于s,t-圖有下述性質(zhì)與結(jié)果:性質(zhì)2.1.1s,t-圖必是s,t-1-圖.性質(zhì)2.1.2s,t-圖必是s+1,t-圖.性質(zhì)2.1.3s,t-圖必是s+1,t+1-圖.定理2.1.1設G是4,2-圖,則:(a)G是連通的當且僅當G同構(gòu)于K1,3或者G有Hamilton路.(b)G是2-連通的當且僅當G同構(gòu)于K2,3或者G同構(gòu)于K1,1,3或者G有Hamilton圈.2.2主要結(jié)果下邊的定理2.2.1是本文要證明的主要結(jié)果,顯然定理2.2.1要比定理2.1.1中(b)的結(jié)果更好.定理2.2.1設G是2-連通4,2-圖,C是G中滿足|V(C)|V(G)|的任一圈,則或者G中有(|C|+1)-圈,或者G同構(gòu)于K2,3,K1,1,3,F1,F2,F3,F4,F5.其中F1,F2,F3,F4,F5如下圖:圖F1圖F2圖F35圖F4圖F52.3定理2.2.1的證明4證明設圖G滿足定理條件,C是G的一個圈,且|V(C)|4則任取xV(H),有|NC(x)|=1.證明若|NC(x)|2,取v1,v2NC(x)(v1v2),由論斷1:v1v2E(C).因為|C|4,所以|v1+Cv2-|,|v2+Cv1-|必有一個2.不妨設:|v2+Cv1-|2,考慮Gx,v2-,v2+,v1-,由論斷1:xv1-,xv2-,xv2+,v1-v2-E(C)；由G是4,2-圖,必有v2-v2+E(G).若v2-2=v1,則G中有(|C|+1)-圈C=v1xv2v2-v2+Cv1,矛盾！所以v2-2v1.考慮Gx,v2-2,v2+,v1-,由論斷1:xv1-,xv2+E(G),又xv2-2E(G),否則G中有(|C|+1)-圈C=v2-2xv2v2-v2+Cv2-2,矛盾！又v1-v2-2E(G),否則G中有(|C|+1)-圈C=v1-v2-2C_v1xv2v2-v2+Cv1-,矛盾！由G是4,2-圖:必有v2-2,v2+E(G).如此考慮下去可得:任意vV(v1+Cv2-),有vv2+E(G),特別地v1+,v2+E(G),這與論斷1矛盾！論斷3設H1,H2是G-C的兩個分支,則NC(H1)NC(H2)=.證明若NC(H1)NC(H2),取vNC(H1)NC(H2),則有x1v,x1vE(G),其中x1V(H1),x2V(H2),考慮Gx1,x2,v-,v+,由論斷1:x1v-,x1v+,x2v-,x2v+E(G),這與G是4,2-圖矛盾！論斷4對G的任一分支H,|H|2,則H與C間必有兩條獨立邊.6證明此結(jié)論顯然.以下分3種情形完成定理的證明:情形1|C|4取G-C的一個分支H,由論斷2知任取xV(H),有NC(x)=1,又因為G是2-連通的,所以|NC(H)|2,所以H與C間必有兩條獨立邊.設:x1v1,x2v2E(V(H),V(C),其中x1,x2V(H)(x1x2),v1,v2V(C)(v1v2),若v1v2E(C),由于|C|4,所以|v1+Cv1-|,|v2+Cv1-|必有一個2.不妨設:|v2+Cv1-|2考慮Gx1,x2,v1+,v2+2,由論斷2知x1v1+,x1v2+2,x2v1+,x2v2+2E(G),則由G是4,2-圖知必有x1x2,v1+v2+2E(G),則G中有(|C|+1)-圈C=v1+v2+2Cv1x1x2v2C_v1-,矛盾！所以v1v2E(C).考慮Gx1,x2,v1-,v2+,由論斷2知x1v1-,x1v2+,x2v1-,x2v2+E(G),則由G是4,2-圖知必有x1x2,v1-v2+E(G)考慮Gx1,x2,v1-2,v2+2,由上述討論可得v1-2v2+2E(G).如此下去可得:v1-iv2+iE(G),i=1,2,(|C|/2)-1.若|C|為奇數(shù),則G中有(|C|+1)-圈C=x1v1C_v1-(|C|/2-1)v2+(|C|/2-1)C_v2x2x1,矛盾！若|C|為偶數(shù)且|C|8,考慮Gx1,x2,v1-,v1-3,由論斷2知:x1v1-,x1v1-3,x2v1-,x2v1-3E(G)則由G是4,2-圖知必有x1x2,v1-v1-3E(G),則G有(|C|+1)-圈C=x1v1v1-v1-3C_v2x2x1,矛盾！若|C|=6,考慮Gx1,x2,v1-,v2+2,由論斷2知x1v1-,x1v2+2,x2v1-,x2v2+2E(G),則由G是4,2-圖知必有x1x2,v1-v2+2E(G),則G有7-圈C=x1v1v1-v2+2v2+v2x2x1,矛盾！情形2|C|=3設C=v1v2v3v1,G-C的分支數(shù)2,取G-C的任意兩個分支H1,H2,因為G是2-連通的,所以|NC(Hi)|2,i=1,2.又注意到|C|=3,可知NCH1NCH2,這與推論3矛盾！因此G-C只能有一個分支,設此分支為H,|H|=1或2.則易見G有4-圈,此為矛盾！所以|H|3；由|C|=3及|NC(H)|2知H與C間必有兩條獨立邊取兩條這樣的獨立邊,不妨設為x1v1,x2v2E(V(H),V(C),其中x1,x2V(H),且x1x2,則x1x2E(G)(否則G有4-圈),對任意的xV(H),有xv3E(G),若xx1,x2,則結(jié)論顯然,設xx1,x2,若xv3E(G),考慮Gx,x1,x2,v3,由論斷1知x1v3,x2v3E(G),由,有x1x2E(G),又x1xE(G)(否則G有4-圈),7同理x2xE(G),對任意的xV(H),有xx1,xx2E(G),考慮Gx,x1,x2,v3,由論斷1知x1v3,x2v3E(G),又由有x1x2,xv3E(G),由G是4,2-圖知必有xx1,xx2E(G)；若|H|4,取x3,x4V(H)x1,x2,由知x3,x4均與x1,x2相鄰,則G有4-圈,此為矛盾！由此說明|H|=3,即G同構(gòu)于F1.情形3|C|=4注意到對G的任一分支H,均有|NC(H)|2且|C|=4,結(jié)合論斷3可知G-C至多有2個分支,取G-C的一個分支H,若|H|2,由論斷4知H與C間必有2條獨立邊,取兩條這樣的獨立邊,設x1v1,x2v2E(V(H),V(C),其中x1,x2V(H)(x1x2),v1,v2V(C)(v1v2),若v1v2E(C),考慮Gx1,x2,v1-,v2-,由論斷1知x1v1-,x1v2-,x2v1-,x2v2-E(G),又x1x2E(G)(否則G有5-圈),這與G是4,2-圖矛盾！所以v1v2E(C)子情形3.1|H|3取xV(H)x1,x2,顯然x不能與x1,x2同時相鄰,否則G有4-圈,不妨設xx2E(G),令Cv1,v2=v3,v4,即C=v1v2v3v4v1,所以有xv3E(G),xv4E(G)；若xv3E(G),考慮Gx,x1,v2,v4,由論斷1知x1v2,x1v4,xv2,xv4E(G),xx1E(G),這與G是4,2-圖矛盾！若xv4E(G),考慮Gx,x2,v1,v3,由論斷1知x2v1,x2v3,xv1,xv3E(G),由G是4,2-圖知xx2,v1v3E(G),則G有5-圈C=xx2v2v3v4x,此為矛盾！考慮Gx,x1,v3,v4,由假設及論斷1得xx1,x1v4E(G),又因為及G是4,2-圖,則x1v3E(G),若v2v4E(G)則G有5-圈C=v1x1v3v2v4v1,此為矛盾！所以v2