畢業(yè)論文2連通4,2圖中的圈以及含有hamilton圈的一個充分條件的再證明

1、1畢業(yè)論文題目：目：2連通連通[42]圖中的圈以及含有圖中的圈以及含有Hamilton圈的一個充分條件的再證明圈的一個充分條件的再證明學院：院：數(shù)學與信息科學學院數(shù)學與信息科學學院專業(yè)：業(yè)：數(shù)學與應用數(shù)學數(shù)學與應用數(shù)學畢業(yè)年限：畢業(yè)年限：2012屆學生姓名：學生姓名：…………3Abstract:Abstract:GraphTheybegan200yearsagoEulerpublishedthefirstpaperongraphthey

2、in1736heusedgraphtheytosolvetheKonigsbergSevenBridges.theHamiltonproblemisaveryimptantactiveresearchtopicingraphtheyIn1857IrishmathematicianHamiltonputfwardaproblem:“whatisthenecessarysufficientconditionwhenaconnectedgra

3、phhasaHamiltoncycle.”HoweverithasnotbeensolveduntilnowAtthesametimebasedonHamiltonproblemaresearchonnaturesofcyclesingraphhasbeencarriedout.Thesenaturesarehamiltonicitypancyclicityextensibilityetc.Themaincontentofthispap

4、erconsistsofthreeparts:inthefirstpartintroducessomeoftheconceptstermssymbolscoveredinthearticletheresearchbackgroundtheexistingresultsinthesecondpartwediscussedthecyclesin2connected[42]graphsinthethirdpartwediscussedasuf

5、ficientconditionfthegraphcontainsHamiltoncycle.KeyKeywds:wds:[st]graphconnectivitysverticesconnectedgraphfullycycleextensibilitythelongestcycleHamiltoncycleindependencenumber1預備知識[12]1.1符號概念介紹本文考慮的圖是有限、無向、簡單圖文中所使用的記號和術(shù)語約

6、定如下:設(shè)G=(V(G)E(G))是一個圖V(G)、E(G)分別表示G的頂點集和邊集.|G|=|V(G)|表示G中頂點的數(shù)目稱為G的階|E(G)|表示G中邊的數(shù)目對頂點集V1V2…VmV(G)用G[V1V2…Vm]表示G中由V1V2?…Vm導出的子圖對v∈V(G)及G的子圖H記NH(v)=u∈V(H):uv∈E(G)NG(v)簡記為N(v)dH(v)=|NH(v)|稱圖G中點v的度dG(v)也簡記為d(v).用δ△分別表示圖G中頂點的最