[硕士论文精品]图的高阶限制边连通度

摘要图的边连通度和超边连通性常用来度量网络的可靠性，但是当两个图具有相同的边连通度和超边连通性时，就无法对其可靠性进行比较因此，为了更精确地度量网络可靠性，人们提出了”卜限制边连通度的概念设M是正整数，连通图G的边割S称为M限制边割，如果GS的每个连通分支都至少包含M个顶点；G中最小仇限制边割的基数称为图G的M一限制边连通度，记为A。G当M2时，入2G称为图G的限制边连通度，通常记为入7G如果KG存在，则称G是A仇一连通图目前，关于“P限制边连通度方面的研究，主要集中在讨论M限制边连通度的存在性及上界，计算特殊图类或网络的册限制边连通度，寻求分别具有极大“卜限制边连通度和较少最小M限制边割数的图类等方面令GMINI，期IXYG，LXLM，且AIX】连通1如果图G的竹P限制边割SFX，圄满足LXIM或IXLM，则称S是平凡的设入仇一连通图G满足K；GG，如果HG岛G，则称G是最优M限制边连通图，简称入M最优图；如果G的每个最小仇一限制边割都是平凡的，则称G是超级”P限制边连通图，简称超一AM连通图一般来说，AM一最优图和超K。连通图具有较高的可靠性本文共分五章，第一章综述竹P限制边连通度的应用背景及研究进展，介绍本文用到的一些基本概念，术语和记号，并概述本文的研究内容及获得的主要结果第二章主要研究满足A仇GG的一个一般充分条件已经证明，当M3时，H连通图G具有入MGG这一性质当仇4时，BONSMA等人指出不等式K，G知G一般不再成立欧见平于2007年证明阶大于等于N的儿一连通图G满足九G矗G本章我们通过研究满足入MG靠G的K。连通图所具有的结构性质，不仅易得欧见平的以上结论，而且还得到了如下结论当M5时，阶大于MM一1的入M一连通图G均满足入MG靠G最后，通过构造例子来说明我们给出的条件是最好的第三章主要研究图的最优限制边连通性给出并证明一般图，二部图，以及直径为2的图分别是最优图的充分条件，同时通过构造例子来说明这些条件不能被减弱本章得到的结论是对HELLWIG与VOLKMANN2004和2005年相应结论的改进，其中关于直径为2图的最优性结论是对王应前和李乔1999年结论的进一步推广第四章主要研究图的超级限制边连通性给出并证明一般图，二部图，无三角形图，以及直径为2的图分别是超一连通图的充分条件，并用例子说明这些条件是最好的本章所得的结论推广了王应前和李乔2001年的结论而关于直径为2图的超一HTTP/INFO3DOUCOM/论坛营销摘要兰州大学博T学位论文连通性，在不含三角形的条件下，我们得到的推论与王世英和林上为2007年的结论类似，并且推广了范英梅2003年的结论第五章主要研究图的入3一最优性和超一入3连通性首先讨论A3一最优与最优和超A7连通之间的关系然后给出并证明一般图，二部图，无三角形图，以及直径为2的图分别是入3一最优图和超A3连通图的充分条件，并通过构造例子来说明这些条件不能被减弱最后证明最小度62M的超入M连通非完全图所具有的一个结构性质G的最小度顶点集M的导出子图GM1不含完全子图玩一M1本章中，我们把欧见平2003年关于无三角形正则图的入3一最优性结论推广到一般图另外，关于直径为2图的A3一最优性和超入3连通性，我们所获得的结论推广了王应前2006年的相应结论通图关键词连通图，M限制边割，M一限制边连通度，AM割，入M最优图，超一入仇连HTTP/INFO3DOUCOM/论坛营销ABSTRACTUSUALLYTHEEDGECONNECTIVITYANDSUPEREDGECONNECTIVITYOFGRAPHSAREUSEDFORMEASURINGTHERELIABILITYOFNETWORKSHOWEVER，THESEPARAMETERSFAILTOCOMPARETHERELIABILITYOFGRAPHSWITHTHESAMEEDGECONNECTIVITYANDSUPEREDGECONNECTIVITYTHEREFOREINORDERTOMOREACCURATELYMEASURETHERELIABILITY,THECONCEPTMRESTRICTEDEDGECONNECTIVITYISPROPOSEDLETMBEAPOSITIVEINTEGERANEDGECUTSOFACONNECTEDGRAPHGISCALLEDALLMRESTRICTEDEDGECUT，IFEACHCOMPONENTOFGSCONTAINSATLEASTMVERTICESANDTHEMINIMUMCARDINALITYOFALLMRESTRICTEDEDGECUTSISCALLEDTHEMRESTRICTEDEDGECONNECTIVITYOFG，DENOTEDBYKGUSUALLY,WHENM2，A2GISCALLEDRESTRICTEDEDGECONNECTIVITYOFG，DENOTEDBYGGISCALLEDHLCONNECTEDIFAMGEXISTSATPRESENT，STUDIESONMRESTRICTEDEDGECONNECTIVITYMAINLYFOCUSONDISCUSSINGTHEEXISTENCEOFMRESTRICTEDEDGECONNECTIVITYANDITSUPPERBOUND，CALCULATINGTHEMRESTRICTEDEDGECONNECTIVITYOFSOMESPECIALGRAPHSORNETWORKS，ANDSEARCHINGFORGRAPHSWITHMAXIMALLYMRESTRICTEDEDGECONNECTIVITYANDFEWERMINIMUMMRESTRICTEDEDGECUTSLET岛GMINJX，X】IXYG，IXIM，ANDG【X】ISCONNECTEDANMRESTRICTEDEDGECUTSIX，X】ISCALLEDTRIVIALIFIXLMORI贾LMAK。一CONNECTEDGRAPHGWITHAMG矗GISSAIDTOBEOPTIMALLYMRESTRICTEDEDGECONNECTED，FORSHORTAMOPTIMAL，IF入MGG，ANDTOBESUPERMRESTRICTEDEDGECONNECTED，FORSHORTSUPERAM，IFEVERYMINIMUMMRESTRICTEDEDG争CUTOFGISTRIVIALGENERALLY,KNOPTIMAL黟APHSANDSUPERXM伊印HSHAVEHIGHERRELIABILITYTHISTHESISCONSISTSOFFIVECHAPTERSINCHAPTERL，ASURVEYONTHEAPPLICATIONBACKGROUNDANDTHERESEARCHADVANCEOFMRESTRICTEDEDGECONNECTIVITYOFGRAPHSAREGIVEN；THEN，SOMEDEFINITIONSANDNOTATIONSUSEDINTHISTHESISAREINTRODUCED；FINALLY,THEMAINRESULTSACQUIREDINTHISTHESISARELISTEDINCHAPTER2，AGENERALSUFFICIENTCONDITIONFORAGRAPHGSATISFYINGKG靠GISPRESENTEDPREVIOUSSTUDIESSHOWEDTHATAKCONNECTEDGRAPHGHASTHEPROPERTYHG厶GFORRN冬3，BUTFOR，7L4，BONSMAETA1POINTEDOUTTHATTHEINEQUALITYKIG靠GISNOLONGERTRUEINGENERAL，ANDIN2007OUSHOWEDTHATAKCONNECTEDGRAPHGWITHORDERATLEAST11HASTHEPROPERTYGGINTHISCHAPTER，BYCHARACTERIZINGSOMESTRUCTUREPROPERTIESOFAKCONNECTEDGRAPHGWITHKG靠G，WEOBTAINNOTONLYTHEABOVEOUSRESULTBUTTHERESULTTHATKCONNECTEDGRAPHGWITHORDERGREATERTHANMM1SATISFIESTHEINEQUALITYMHTTP/INFO3DOUCOM/论坛营销摘要兰州大学博士学位论文AMGGFORM5ATLAST，BYCONSTRUCTINGSOMEEXAMPLES，WETESTIFYTHATOURCONDITIONSAREBESTPOSSIBLEINCHAPTER3，THEOPTIMALLYRESTRICTEDEDGECONNECTIVITYOFGRAPHSISSTUDIEDSUFFICIENTCONDITIONSFORGENERALGR印11S，BIPARTITEGRAPHS，ANDFOR铲APLLSWITHDIAMETER2，TOBEHOPTIMALAREPRESENTED，RESPECTIVELY，ANDATTHESAMETIMEBYCONSTRUCTINGEXAMPLESTOILLUMINATETHATTHESECONDITIONSCANNOTBEWEAKENEDINADDITION，THERESULTSACQUIREDINTHISCHAPTERIMPROVETHEHELLWIGANDVOLKMANNSIN2004AND2005，ANDTHERESULTSFORGRAPHSWITHDIAMETER2GENERALIZETHEWANGANDLISIN1999INCHAPTER4，THESUPERRESTRICTEDEDGECONNECTIVITYOFGRAPHSISDISCUSSEDWEPRESENTSUFFICIENTCONDITIONSFORGENERALGRAPHS，BIPARTITEANDTRIANGLEFREEGRAPHS，ANDFORGRAPHSWITHDIAMETER2，TOBESUPERA7，ANDBYMEANSOFEXAMPLES，INDICATEOURRESULTSAREBESTPOSSIBLEINTHISCHAPTERTHERESULTSWEACQUIREDGENERALIZETHEWANGANDLISIN2001INADDITION，ASFARASTHESUPERH7CONNECTIVITYFORTRIANGLEFREEGRAPHSWITHDIAMETER2ISCONCERNED，WEOBTAINACOROLLARYSIMILARTOTHEWANGANDLINSRESULTIN2007，ANDGENERALIZETHEFANSIN2003INCHAPTER5，WEDISCUSSTHE入3一OPTIMALITYANDSUPERHACONNECTIVITYOFGRAPHSFIRSTLY,THERELATIONSBETWEENTHE入3一OPTIMAL，一OPTIMAL，ANDSUPERXAREDISCUSSEDTHEN，SUFFICIENTCONDITIONSFORGENERALGRAPHS，BIPARTITEGRAPHSANDTRIANGLEFREEGRAPHS，ANDFORGRAPHSWITHDIAMETER2，TOBE入3一OPTIMALANDSUPERHAAREPRESENTED，RESPECTIVELYALSOINTHISCHAPTERWECONSTRUCTEXAMPLESTOSHOWTHATTHESECONDITIONSCANNOTBEWEAKENEDFINALLY,THESTRUCTUREPROPERTYOFASUPERHMGRAPHGWITHMINIMUMDEGREE62MWHICHISNOTCOMPLETEGRAPHISOBTAINEDTHEINDUCEDSUBGRAPHGMOFMINIMUMDEGREEVERTICESSETMOFGRAPHGCONTAINSNOCOMPLETESUBGRAPH一M1INTHISCHAPTER，WEGENERALIZETHEOUSRESULTONTHE入3一OPTIMALITYOFTRIANGLEFREEREGULARGRAPHSTOGENERALGRAPLLSALSO，OURRESULTSGENERALIZETHEWANGSIN2006ONTHE入3一OPTIMALITYANDSUPERHACONNECTIVITYFORGR印HSWITHDIAMETER2KEYWORDSCONNECTEDGRAPH；MRESTRICTEDEDGECUT；MRESTRICTEDEDGECONNECTIVITY；入仇一CUT；KOPTIMALGRAPH；SUPERHMCONNECTEDGRAPHHTTP/INFO3DOUCOM/论坛营销原创性声明本人郑重声明本人所呈交的学位论文，是在导师的指导下独立进行研究所取得的成果。学位论文中凡引用他人已经发表或未发表的成果、数据、观点等，均已明确注明出处。除文中已经注明引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究成果做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。论文作者签名垫麴EL期星丛兰2HTTP/INFO3DOUCOM/论坛营销关于学位论文使用授权的声明本人在导师指导下所完成的论文及相关的职务作品，知识产权归属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定，同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版，允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相关的学术论文或成果时，第一署名单位仍然为兰州大学。保密论文在解密后应遵守此规定。论文作者签名JL赴导师签名幽日期幽HTTP/INFO3DOUCOM/论坛营销第一章引言本章首先综述本文研究问题的应用背景以及该领域的研究进展，然后介绍本文要用到的基本概念，术语和记号，最后介绍本文的研究内容及获得的主要结论11胁限制边连通度的应用背景及研究进展在对处理机互连网络的拓朴结构设计与分析中，人们通常把网络的拓朴结构模型化为图，其中图的顶点代表处理机，而一对处理机之间的直接通讯联系则用这对顶点之间的边来表示因此网络拓扑结构的性能可以通过图的性质和参数来度量在研究网络可靠性容错性时，经常考虑种被称为MOOR争SHANNON的网络模型【49，5叫它假定互连网络的结点非常可靠，永远不会失效，而结点之间的链接相互独立地以相等的概率P0，1失效于是在这种假定下，可用图的边连通度及边割数目来计算网络模型的可靠性设G就是这样一个互连网络模型，其中AG表示图G的边连通度，MIG表示图G的大小为I的边割数目，则G的可靠性RG，力表示为IEGIRG，P1一FMIG1一PLEGIIXG要准确地计算出G的可靠性，只需要计算出每个系数RA,GIAG，AG1，LEGI即可但是，早在1983年，PROVAN和BAU【61】就指出，计算出所有这些系数是NP困难问题于是，人们首先用边连通度来衡量网络的可靠性，并发现具有极大边连通度的图所对应的网络具有较高的可靠性关于图的极大边连通性，大量的文献研究了极大边连通图用度表示的充分条件，如CHARTRAND【14，LESNIAK【401，PLESNK和ZNALFI【60】，GOLDSMITH和WHITE131】，BOESCH和CHEN【9】，BOLLOB矗SF11，FIOL【28，SONEOKA等【671，DANKELMANN等【18，19，HEUWIG和VOLKMANN【351，VOLKMANN【72等分别给出了极大边连通图的一些ORE类型，或者用图的阶，最小度，或度序列等表示的充分条件ONEOKA等【66，671，PLESN【59，FFIBREGA和FIOL【23，24，25】等给出了极大边连通图用直径和围长表示的充分条件而WANG等【74，LIN等【44，MORIARTY和CHRISTOPHER【51】等分别在2003和2005年证明了围长为G，最小度石2的所有G一CAGE是极大边连通的为了较精确地度量网络可靠性，BAUER等人【7】于1981年提出了超级边连通的概念如果连通图G的每个最小边割都孤立一个顶点，则称图G是超级边连通的，简1HTTP/INFO3DOUCOM/论坛营销2第一章引言兰州大学博士学位论文称超边连通的随后，关于图的超边连通性的文献如雨后春笋般涌现出来，TINDELL【68】于1982年，BOESCH和TINDELL101于1984年分别刻画了边对称图和循环图的超边连通性，而BAUER等人81在1985年利用图G的超边连通性确定了可靠性多项式的前AG个系数MG，从而证明了极大边连通的和超边连通的网络有较好的局部可靠性，并证明了如何构建MAXAMINM图KELMANS【38】1972，LESNIAK【40】1974，FABREGA和FIOL【23】1989，FIOL等29】1990，FIOL【271992，SONEOKA【65】1992，VOLKMANNF7312003等分别给出了超边连通图用阶，直径，围长，最小度，或度序列等表示的充分条件，TINDELL【69】1996刻画了点传递图和CAYLEY图的超边连通性，CHEN等F15】2003研究了三类特殊网络的超边连通性，徐俊明和范英梅【86】2004研究了无向DEBRUIJN和KAUTZ网络的超边连通性，MARCOTE与BALBUENAF4612004，LIN等43】2006证明了围长为夕，最小度63的所有6，G一CAGE是超边连通的CHIUE和SHIEH【171999，杨超和徐俊明【8912007等讨论了图的卡氏积的极大边连通性和超边连通性另外，WANG和ZHANG【82】1997，DENG等【20】2004给出了构建MAXAMINMIIA，入1，2A一3图的方法于是，对于边连通度不等或者边连通度相等但最小边割数不相等的网络，它们的可靠性比较已经解决但是当两个不同网络的这两个参数均相同时，就无法比较其可靠性，而且在分析和应用这两个参数时都不言而喻的假定了系统的任何部分都可能同时失灵，也就是说对这些参数没有加任何限制，然而在大规模多处理器系统中，这种假设成立的可能性几乎为零为了弥补以上缺陷，也为了更精确地度量网络的可靠性，人们很自然的想到对图的边割集加上一些条件或限制，从而推广了经典边连通度的概念HARARY【32】于1983年首先提出条件连通度的概念，ESFAHANIAN和HAKIMIF211于1988年把条件更具体化，提出了限制边连通度的概念，而李乔良和李乔【41】于1998年提出了极大限制边连通图简称为最优图和超级限制边连通图简称为超入7连通图的概念更进一步，FHBREGA和FIOLF24，2511994，1996提出了M限制边割和M限制边连通度的概念；王应前F101，BONSMA等【131在2001“2002年研究了图的孓限制边割的存在性和限制边连通度的上界，并提出了极大3限制边连通图简称为入3最优图和超级孓限制边连通图简称为超一入3连通图的概念；王铭和李乔【79】证明了入3一最优图和超一K连通图具有较高的可靠性目前，这一领域的研究主要集中在M限制边割的存在性问题，M限制边连通度的优化问题包括寻求AMG的上界，极大M限制边连通图和超级胁限制边连通图的各种条件，计算或证明各种特殊图类或网络的M一限制边连通度和超级M限制边连通性等等关于这方面的文献很多F116，【13，16，【20126，【33。37，【39，41，42，45，47，48，【52581，【62，63，711，【75181，【84，85，87，88，F901104，我们这里不再详细介绍，参看第二章至第五章的引言HTTP/INFO3DOUCOM/论坛营销兰州大学博士学位论文12基本概念，术语和记号312基本概念，术语和记号本文所研究的图均为有限无向简单连通图设G是简单无向连通图，顶点集为YG，边集为EGG的项点数称为G的阶，用NG或IYGI表示，边数用IEGL表示对于顶点T，UYG，若E牡UEG，则称U和口在G中邻接或相邻，并称边E与牡关联顶点钍与口在G中最短路径的长度称为U与可的距离，记作站缸，口，经常简记为DU，秽G中所有两个顶点之间距离的最大值称为G的直径，记作DGG的围长GO是指G中最短圈的长度，若G中没有圈，则定义G的围长为无穷大对于顶点UYG，GU表示顶点钉在G中的邻点构成的集合，称为T，的开邻域；令小，GM0钉UU，称之为口的闭邻域；而用如I0“L记顶点T，在G中的度设XYG，我们记NX移NG0NX，支IV】G【秽】NX如果含义明确时，记号中的下标G可以省略，即用NV代替GU，用NV】代替GM，用DV代替站秒对于ETLVEG，令铅EDUDV一2，称为边E在G中的边度我们用6G表示G的最小度，用FGIILIN【白EEEG表示G的最小边度对XYG，AX】表示顶点集X在G的导出子图，XYGX对于G中两个不相交的顶点子集X和Y，Y1表示G中一个端点在X中，另一个端点在Y中的边所构成的集合，而I，明L表示G中一个端点在X中，另一个端点在Y中的边的条数经常把，圄简记为AX，L，圄L简记为IAX1设G和日是两个简单图，如果存在一个双射PVG_Y日，使得对任意的顶点T|，“YG，U口EG当且仅当口UP口E日，则称图G与H同构，记作G筌日设SEG，如果图GS不连通，则称S为G的一个边割，G中最小边割的基数称为G的边连通度，记为AG显然，AO6G如果AG6G，则称G是极大边连通图，也称G是K最优图如果G每个最小边割都孤立一个顶点，则称G是超级边连通图，简称超边连通图显然，如果G是超边连通图，则AO巧G设M是一正整数，SEO是连通图G的一个边割，如果GS的每个连通分支至少包含M个顶点，则称S为G的一个M限制边割，G中最小“P限制边割的基数称为G的M限制边连通度，记为AMG显然，ALGAG；A2G又称为G的限制边连通度，通常记为A7G如果连通图G存在“卜限制边割，则称G是K连通图显然，如果G是K连通图M2，则G也是K1连通图，并且K一1GKG设SIX，贾】是图G的一个M限制边割，如果ISIKG，则称S为G的一个入M割；如果IXI仇或I贾LM，则称FN限制边割S是平凡的显然，对于HTTP/INFO3DOUCOM/论坛营销4第一章引言兰州大学博士学位论文图G的任何AM一割S，图GS恰有两个连通分支这里，我们给出经常用来度量“卜限制边连通度入MG上界的参数G设M是一正整数，G是一连通图，令厶GMIN0XIXYG，LXIM，且GX】连通显然，TG6G，已GG称为G的最小边度下面，给出两个在网络优化中经常用到基本概念入M最优图和超一入M连通图设G是入M连通图并且满足入。G靠G，如果入MGG，则称G是极大M限制边连通图，又称G是最优M限制边连通图，简称入。最优图；如果G的每个A。割都是平凡的，则称G是超级M一限制边连通图，简称超AM连通图其中，入1最优图经常称为极大边连通图，A2一最优图经常记为A7最优图从定义很容易看出，超AM连通图必是AM一最优图，但其逆命题不成立，即入仇最优图不一定是超K连通图例如，当佗2M2时，伽长圈G成立入MG2岛G，所以是AM最优图，但显然不是超H连通图最后，我们给出本文常用的一些特殊图的记号表示N阶完全图，N表示二部划分顶点集基数分别为M和N的完全二部图完全二部图K1N又称为星图在【76】中，王应前定义了一个P，R一杠铃图P3，RP，它是把两个P阶完全图用矿条新边连接起来，使得其中的每个顶点的度均为P十7一1所得的图对于文中未加说明的图论术语和记号可参阅文献【12113本文的研究内容及主要结果本论文主要是关于计算机互连网络拓扑结构可靠性方面的几个重要度量参数A7和入3以及一般的M一限制边连通度K；的研究主要内容如下第二章主要研究M限制边连通度AM的上界问题WHITNEYF83，ESFAHANIAN和HAKIMIF21，BONSMA等【131及王应前和李乔【78分别证明了当M1，2，3时，入M一连通图G满足AMGG而当M4时，上述不等式不再完全成立【13】欧见平【54】证明了如果NG11，则A4连通图G成立沁G矗G我们第二章首先研究当M4时，满足入MGG的K连通图所具有的结构性质主要方法是先给定图G的任意一个入M割【S翻，以及一个使得G1连通并且满足I，X】IG的VA的M元子集X，然后通过讨论导出子图GYCL所有分支的阶数，各个分支与子图GF矧，G吲及G吲的结构关系，获得了图G所具有的结构性质，进而不仅得到了欧见平【54】的以上结论，同时还获得了对M5，不等式入MGG成立的一个一般充分条件，最后构造例子说明我们给出的条件是最好HTTP/INFO3DOUCOM/论坛营销兰州大学博士学位论文13本文的研究内容及主要结果5的第二章获得的主要结论如下定理221设GVE是K连通图，且KGG暇司是图G的一个A仇割XY，IXIM，AX】连通并且满足I，贾】L矗G，记导出子图G【圈的K个分支的顶点集分别为A，岛，Q则G具有以下性质AICFI仇一1，1，2，后；6XNSD且XNS谚；C对任意I，I1，2，七，如果IC；IM一1，则VU坛G，有IM，XGLLIE,，硐LL【C；，XUL，JI并且当等号成立时，G【YGUU】不包含阶至少为M的分支；D令仳X，RUQSG，如果UXNS玩蟛口一【UC；C雪Q，如果UXNS峙，IO如果存在顶点札X使得I玩IML，或者存在I满足LGIM一1，CINSD并且CINSD，则KM一2；E令JV，S雪DCJNS谚，CJA雪O，且【C，叫谚，1歹七，仇U诞，S雪G设图G满足讹X，均有LB。I仇一2，且IGLM一2G1，2，七如果存在TX，使得I玩U仇IM一1，则当M5时，LVLSM12；，当M5时，2MLVLMM一1；当M4时，8IVI10定理231设G是K一连通图A如果NG之11，则KG已G；B如果M5并且札G仇M一1，则入MG厶G第三章主要研究图的N最优性给出并证明一般图，二部图，以及直径为2的图分别是N最优图的充分条件，并构造例子说明这些条件是最好的主要结果如下定理321设G是A7连通图并且满足下面两个条件AG中任意一对距离为2的顶点霉与Y均满足DXDY2ING2J一3；BG中的每个三角形T均至少有一个顶点T，VT满足DVMG2J1则G是最优图定理331设G是连通二部图，LG4如果G中任意一对距离为2的顶点Z与均满足DZDY2【礼G24J1，HTTP/INFO3DOUCOM/论坛营销6第一章引言兰州大学博士学位论文则G是A7最优图推论333设G是连通二部图，6G3如果G中任意一对距离为2的顶点X与可均满足DXDY2LNG十24J1，则G是超边连通图定理343设G是A一连通图如果G中任意两个不相邻的顶点钆和U满足下面两个条件A当U和V均不位于G的任何三角形上时，有INUN口I1；B当U或U位于G的某个三角形上时，有LNUN钉I3则G是入7一最优图推论344设G是不合三角形的入7一连通图，DG2则G是入7一最优图以上结论分别是对HELLWIG和VOLKMANN2004年和2005年文章【33，35】中相应的结论改进，其中定理343和推论344推广了王应前和李乔【102】1999年的结论第四章主要研究图的超级限制边连通性目前已有的关于超一连通图用度或ORE类型表示的充分条件，基本上都只适用于直径为2的图，而对于一般图的相关结论还很少所以在第四章，我们给出并证明一般图，二部图，无三角形图，以及直径为2的图分别是超一入7连通图的充分条件，并构造例子说明这些条件是最好其主要结论如下定理421设G是连通图，NG4如果下面两个条件成立AG中任意一对距离为2的顶点Z与Y均满足DXDU2NG2JL；BG的任意一个三角形T中，至少存在一个顶点V满足DV【NA2J2则G是超入7连通图定理431设G是连通二部图，扎G4G中任意一对距离为2的顶点Z与均满足DXDU2【佗G24J3，则G是超一连通图定理433设G是不合三角形的入3一连通图，竹NG，D1D2如5是图G的度序列如果M警，_1互1【互NMAX15J2一熹“如一T，一1泓引一熹“则G是超一A，连通图推论434设G是连通的无三角形图，NG4如果G中至多有一个顶点Z不满足DZ【NG24J2，则G是超一A连通图HTTP/INFO3DOUCOM/论坛营销兰州大学博士学位论文13本文的研究内容及主要结果7定理44I设G是连通图，且不同构于集合澎见图44中的任何图如果G中任意两个不相邻的顶点TL和T，满足下面两个条件1当T与移均不位于G的任何三角形上，有LNUN御IL；2当TI或口位于图G的某个三角形上，有INUN“L4则G是超囊7连通图推论442设G是不含三角形的一连通图，DG2，且不同构于图44中的图风，日2，日3和完全二部图恐，NN4则G是超A7连通图推论443设G是不舍三角形的连通图，DG2，6A3，且不同构于图44中的图风则G是超一入7连通图其中定理441不仅改进了2001年王应前和李乔F103的结论，同时也是对2007年我们自己结论【64】的一个改进另外，推论442不仅改进了2003年范英梅【96】的结论，而且与王世英和林上为2007年【80】中的一个结论类似，但我们的结论适用范围更广一些第五章主要研究图的入3一最优性和超一A3连通性目前已有的关于如一最优图和超K连通图用度或ORE类型表示的充分条件仅适用于直径为2的图，而关于一般图的相应结论很少第五章我们把这方面的结论推广到一般图首先我们讨论A3一最优与一最优和超一连通之间的关系，然后给出并证明一般图，二部图，无三角形图，以及直径为2的图分别是入3一最优图和超一A3连通图的充分条件，并且构造例子说明这些条件是最好的最后，我们给出一般的超K连通图的一个必要条件，并用例子说明它不是充分条件第五章的主要结论如下定理522设G是砖最优图A如果6C4，则G是最优图；如果6C4，则G是超囊7连通图厶如果G是无三角形图，则当6C2时，G是X一最优图；当6C2时，G是超连通图定理53I设G是连通图，NG6如果G满足下面三个条件NVZ，YYG，当DZ，Y3时，DXD可2【NG12J一5；6VZ，剪YG，当DZ，Y2时，DXDY2【NG2J一1；CG的每个子图甄中，至少存在一个顶点U甄满足D“LNC2J2则G是砖最优图推论534设连通图G不含凰，NC6如果G满足下面两个条件OVZ，YYG，当DX，可3时，DZDY2【NC2J一5；B比，YYG，当DZ，可2时，DXDY2【NG2J一1则G是入3最优图HTTP/INFO3DOUCOM/论坛营销8第一章引言定理535设G是连通图，NV6如果G满足下面三个条件AVX，YYG，当DX，Y3时，DXDY22【NG2J一3；BVX，YYG，当DX，Y2时，DXDY2【NA2JL；CG的每个子图甄中，至少存在一个顶点钉K4满足DV【NA2J3则G是超一入3连通图推论536设连通图G不合K4，NV6如果G满足下面两个条件A比，YYG，当DX，Y3时，DXDY2【NA2J一3；BVX，YYG，当DX，Y2时，DXDY2LNG2J1则G是超入3连通图定理541设G是无三角形连通图，死G6如果至多有一个顶点ZVA不满足DXLG24J2，则G是入3一最优图定理542设G是无三角形连通图，NA10如果至多有一个顶点ZVA不满足DX【几G24J2，则G是超一A3连通图定理551设G是连通二部图，NA6如果对任意的顶点X，YYG，满足下面两个条件A当DZ，Y3时，DZDY2LNA24J一1；B当DZ，Y2时，DZDY2【礼G2AJ3则G是入3一最优图定理553设G是连通二部图，NG6如果对任意的顶点Z，YYG，满足下面两个条件A当DX，Y3时，DXDY2【诧G24J1；B当DZ，Y2时，DZDY2LNC24J5则G是超一砖连通图定理561设G是直径为2的入3一连通图如果G中任意两个不相邻的顶点T与U，满足下面三个条件1若U或秽位于图G的某个导出4长圈上，则INUNUI2；2若U或U位于图G的某个三角形上，则INUNUI3；3若U或钉位于图G的某个4阶完全子图甄上，则INUFI钐L5则G是A3一最优图推论562所有围长为5，直径为2，阶大于等于6的图都是入3最优图推论563设G是直径为2，不含三角形的入3连通图如果G中任意两个不相邻的顶点U和V，当U或UAT图G的某个4长圈上时，有LGUN“I2，则G是K最优图HTTP/INFO3DOUCOM/论坛营销兰州大学博士学位论文13。本文的研究内容及主要结果9定理564设G是连通图，礼G6，且不同构于集合9中的任何图见图58如果G中任意两个不相邻的顶点TL和口满足以下三个条件1ITI“1口I2；2若铭或钐位于图G的某个三角形上，有IGUN“I4；3若钍或T，位于图G的某个子图托上，有LGURLUL6则G是超一沁连通图推论565设连通图G不合三角形，凡G6，且不同构于图D阢，DW6，DWS及完全二部图鲍，住G一2见图58如果G中任意两个不相邻的顶点U和移均满足LGUN“2，则G是超一入3连通图推论506设G是无三角形连通图，6G5，NG6如果G中任意两个不相邻的顶点T和“均满足INUN口L2，则G是超一A3连通图推论567设连通图G不含子图尬，NA6，且不同构于集合9中的任何图见图5。8如果G中任意两个不相邻的顶点让和口满足以下两个条件1INUN“I22若U或钞位于图G的某个三角形上，有INUN移|4则G是超沁连通图推论568设连通图G不合子图甄，佗G。6，占G7如果G中任意两个不相邻的顶点孔和秒满足以下两个条件。1INUN”I22若让或U位于图G的某个三角形上，有INUN钉L4则G是超入3连通图定理571设M是正整数，G是非完全图的K连通图，AA62M如果G是超K连通图，则图G的最小度顶点集M的导出子图G【M不含完全子图KSM1其中定理541是把2003年欧见平【991关于正则图的相应结论推广到一般图上，而定理561和定理564分别推广了王应前2006年文章【761中给出的两个结论HTTP/INFO3DOUCOM/论坛营销第二章入MG锄G的一般充分条件在本章，我们首先综述关于入仇G上界方面的研究进展及一些主要结论，然后刻画满足K；GG的图所具有的一些结构性质，最后通过这些性质，我们得到了一个重要结论当M5时，只要NGMM一1，则K一连通图G一定满足入MG岛G并构造例子表明该条件是最好的，从而为K。的优化问题找到了理论依据21引言为了研究“卜限制边连通度的优化问题，首先要找到它的上界关于M3时AM的上界，WHITNEY83】早在1932年就证明了连通图G满足AG6G；ESFAHANIAN和HAKIMI【21】在1988年证明了N连通图G满足YG专G；BONSMA等F13】于2002年，王应前和李乔【78】于2005年各自证明了A3连通图G满足沁G6G对于M4，BONSMA等【13】指出不等式入MGG不再完全成立关于M4时K的上界，有以下结果。定理2111【101】设G是入4连通的K正则图则G矗G。2【54】设G是K一连通图如果NG11，列G矗G3【99】设G是K连通的K正则图K2则A5G6G4【99L设G是K连通的K一正则图如果GGM21，则入仇GG5【91】设G是连通图，TJG，NG21，N是正整数，GT是通过在新顶点让与N个完全图K的每个顶点T，之间加一条新边伽得到的图如果G不同构于图GT，则对于任意的MTL，G是K。一连通图，并且满足入MG靠G22满足KGG图的结构性质本节我们的主要方法是设M是正整数，G是入M一连通图，且满足KG靠G，FS，司是G的任意一个K割，XYG，IXLM，GX】连通并且满足I，圈I岛G我们讨论导出子图G2】的所有分支的阶数，各个分支与子图G】，GN及G同的结构关系，从而得出图G的一些结构性质下面，我们先引入BONSMA等人的一个结论引理221F13】设G是K连通图，AYG如果G【州和G【勾均包含一个至少1LHTTP/INFO3DOUCOM/论坛营销12第二章入MGG的般充分条件有M个顶点的分支，则HGI陋，五】1定理221设GVE是AM一连通图，且AMGG盼司是G的一个K割，XY，IXLM，CX】连通并且满足IIX，叉】IG，记导出子图C2】的七个分支的顶点集分别为A，岛，仇，则G具有以下性质NIGIM一1，I1，2，七；BXNS0且XNS0；C对任意I，I1，2，七，如果IGLM一1，则VU坛G，有IU，XULL概U】IL【G，XUL，J知并且当等号成立时，AIRGU乱】不包含阶至少为M的分支；D令UX，RUCJSC；，如果UXNSB。2TU兰。G，如果UXNS一【UCC雪G，如果UNCJ，柚O如果存在顶点钍X使得L风IM一1，或者存在I满足LGIM一1，GNSD并且GN雪0，则七M一2；E令JV，S，雪DGNSO，GN雪O，且【G，“】O，1歹七，仇UI，S，两G设图G满足VVX，均有I玩LM一2，且IGFM一2I1，2，后如果存在UX，使得I风UDUIM一1，则当M5时，LVIM12；，当M5时，2MIVLMM一1；当M4时，8IVI10证明O假定存在I，使得LGIM，由引理221，入MGSI，矧IG，这与AMG靠G矛盾因此，对任意的I，IGIM一1，I1，2，后。B若XNS0，则S贾由【S，司是G的一个入M一割知，CS】连通，并且ISIM，于是A2】包含了一个阶至少为M的分支，这与O矛盾，所以XNS0同理可证XN雪良CVI，若LAI仇一1，则对VU坛A，由G的定义，有AGUULI，司IL【G，让】F一J【G，XUL【U，X牡】J弁岛G一I盼，让】I一|【G，XUL心，XUIJI岛GHTTP/INFO3DOUCOM/论坛营销22满足入MGMG图的结构性质13因此，L阻，X叫II【G，ULL邑和ICJ，XTLL，并且由引理221和KG厶G知，当该不等式中等号成立时，G【YQUU】不包含阶至少为仇的分支D首先，假设存在顶点UX，使得L吼LML并且KM一1不失一般性，假设UXNS因为G【玩】和G同均连通，并且I雪IM，EHIJIN221，有KGLA风U钆LG一I【玩，叫I一I【G，X叫LI【TT，XULCJN且K叠岛G一七M一1G这与入仇G靠G矛盾，故KM一2其次，假定存在I满足LGIM一1，GNSD，且GN雪毋，但KM一1令TNXNSG，口NXN雪G，记包含于G旧并且与顶点钍邻接的A2】的分支数为TL。，包含于G同并且与顶点秒邻接的G防】的分支数为TLC则以下断言成立断言GCFU缸U鼠。】或GCFUUU风】包含一个阶至少为仇的连通分支不失一般性，假设GGU让U玩】包含阶至少为M的分支，则根据引理221，AMGLAGU乱UBUL厶G一L【C，叫IL【BU，叫L一LFC；，XULL【牡，XULON上KUG9岛G一KM一1靠G这与KG靠G矛盾，所以，K仇一2下面，我们用反证法证明上面的断言成立因为IGLM一1，由性质C有，IU，XULL之慨叫L|【Q，XULL1KUC1KTIC，JLIV，XVLLLIE,，秒】L临，XVLLI一一1K一J于是。L晚U坛陬M川例L玩LI坛【坛移MHTTP/INFO3DOUCOM/论坛营销14第二章。G厶G的一般充分条件I风LI【坛【U】口】IU。KU。KM一1；玩TOK【坛M让】钍II玩JINXNXVUUII玩LIXMU】|KVCKM一1因为GB,UNX【X【U】U】V】G【YGUUUBY】和CBUNX【坛MU】U】G【YGU札】U玩】，并且它们均连通，假设断言不成立，则在以上所有的不等式中，等号成立于是下面的结论18成立1IBULU。，I玩IVC，并且UVEG；2L坛【AK【叫WUIIGX【“】秒LKU。，L坛【坛M叫UILGXP】UIK一；3NXUUNXVX；否则，由G】的连通性和“勘EG知，存在顶点Y，使得，Y“NX【U】“】V或YNXGX【“】让】U，但Y粤GXUUNXV，这与2矛盾4VCK一1；否则，存在J0I，使得0N鼠D，且GN玩0于是根据2和3，G【玩U文M秽UCJ】与G玩U坛【U】UUG】中有一个连通，并且含有至少M个顶点，这与假设断言不成立矛盾5I坛UN坛UII坛乱II坛UL_I坛钍U坛UIO；6由1，2和5知，L【K钍】，NXVLUI1；7G防G】恰好包含M一2个单点分支；8I【G，“】|I盼，口】L1令WB牡，则G【正乙U、K【仳】VU叫】连通，并且I鼠UX【钍】钉U叫IM于是，靠GLABUUGX【叫口U【伽LG一I【BU，又【U】“】II【叫，又M郇】IL【G叫，文【秒】叫II【B。，坛M叫IIW，C伽】ILNX【叫U，NXM乱】I靠G一一LL一M一21岛G一1，矛盾至此，我们完成了D的证明E假设存在也XN