足球比分直播

图上关于点不交子图的若干结果.pdf

返回
图上关于点不交子图的若干结果.pdf_第1页
第1页 / 共30页
图上关于点不交子图的若干结果.pdf_第2页
第2页 / 共30页
图上关于点不交子图的若干结果.pdf_第3页
第3页 / 共30页
图上关于点不交子图的若干结果.pdf_第4页
第4页 / 共30页
图上关于点不交子图的若干结果.pdf_第5页
第5页 / 共30页
点击查看更多>>
资源描述:
宁夏大学硕士学位论文 英文摘要AbstractGraph theory is a matllematics branch w曲a long history and has dcveloped r印idly in recent years.It is a subfieled m Comb.matorial mathematics.In 1736,Euler published t11e丘rSt anicle of野aph meo巧tos01ve the f细ous problem ofseven Bdges ofkonigsbe培.From the middle oftlle 19th cen机吼伊aph the·ory imo山e second stage ofd吖e1叩ment.D谢ng t11is period,a 1a增e number ofprobl锄s ofF印h t11eoryhave锄e唱ed,such as the map colored four-coIor probl锄,de、reloped eom“around the world”game ofH锄ilton issues.In the 20t11 centllry,witll血e d吖elopment of computer science,the eXteniVe applicationin mally filed draw more and more attemion仔om m础amatics field aJld o血er science矗eld.All graphs i11 t11is paper are considered only simple,flllite,undirected graplls wiⅡ1 no multiple e起es锄d no 100ps.Let G be a gr叩h,z肌d可are distinctVenices in G.A t11eta伊印h is the 11nion oftllI’eeintemally disjo衄pa山s that have the same t、;Iro distinct end vertices.A仃ee is an acyclic conllected gr印h.A sp糊ing廿lee is a gr印h which contains aIl Veitices ofG andtllis gr印h is atree.Let n and孔aret、lrospanning仃ees ofa gr印h G,i£for anytwo Vertices z,可ofG,me z一Ⅳpath in乃and死are intemally,恤en噩and正are two completely independent sp啪ing廿ees of G.A h啪iltonion cycles is a cyclewhich contains every vertex of G.In this p叩er,we mainly consider about the following problemdegeesum condition for two completely ind印endem sp锄ing廿.ees,me ex仃emal fhnction for three disjointtheta graphs.This p印er is divided into fbur chapters.h1 ch印terl,we in仃o“ce some notations and ternlinolo戥廿1e history and me progress of the problem of we snldy.In chapter 2,we consider the ex仃emal mnction for t11ree disjoint theta盯印hs.The main result is asfolIowingevery乒印h oforder礼≥12 aIld size at 1east max{『墨堡产],l三羔毫塑jcontains three disjointmeta铲aphs.In chapter 3,we conider t11e degee sum condition for铆o completely ind印eIldent spanning仃ees.The main result is as followinga伊印h of ordcr n≥7 has two conlpletely ind印endent sp锄ing廿ees,ifthe degree sum of锄y t、lro non-a由acent vertices in this黟印h is at 1east n.F1lnhenIlore,in the end of every ch印ters,we 1ist some problems for f11ture research and discussions.Key words D两oint meta graphs; complete indepelldent spallning廿℃es; 0re’s contion; Ex仃emalfhnction一II宁夏大学硕士学位论文 目 录目 录摘要.IABSTRACT英文摘要 .II主要符号对照表.Ⅳ第一章引言.11.1基本概念和术语.11.2问题的研究背景.21.3已有结论及本文的结果...3第二章存在三个点不交的口图的极值函数..72.1基本概念及术语.72.2主要引理及其证明..72.3主要定理1.3.9的证明..102.4可进一步讨论的问题..16第三章两个完全独立生成树存在的度和条件.173.1预备知识.173.2主要引理.173.3主要定理1.3.14的证明.183.4讨论...........27参考文献..28致谢30个人简介..3lIII宁夏大学硕十学位沦文 第章主要符号对照表GV EBⅥ,K,GyGEG占GdGuⅣGu盯2GG[u]%RGT2P『u]lujz产主要符号对照表顶点集为y边集为E的图顶点集为Ⅵ和K的二部图图G的顶点集图G的边集图G的最小度u在图G中的度乜在图G中的邻点集图G中不相邻的两个顶点的最小度和图G的通过U的导出子图礼个顶点的完全图几个顶点的路几个顶点的圈树路P的长度大于“的最小整数小于札的最大整数顶点戤的后继节点顶点孔的前驱节点宁夏大学硕士学位论文 第一章引言第一章 引言弟一早 与|一本章我们主要介绍本文中所用到的一些基本概念和术语,共分为三节,第一节介绍了基本概念和术语,第二节介绍了本文所研究问题的背景,第三节则介绍了本文的主要结果.1.1基本概念和术语我们首先介绍一些图论的基本术语,其他未说明的定义和术语参考文献[3].我们通常称不含圈和环的图为简单图.设GGyG,EG表示一个简单无向有限图,其中yG,EG分别表示图G的顶点集,边集,IyGI表示图G中包含的顶点的个数即图的阶数,lEGl表示图G中边的条数.设仳,“是图G中的两个顶点,如果euu是G的一条边,则称u,u是相邻的.此外,我们也说u,钉与e是相关联的,钆,钉分别为e的两个端点.G中与顶点札相关联的边的条数称为u在G中的度,我们用dG札表示.如果dGu0,则称u为孤立点.我们用ⅣGu来表示u在G中的邻点集,那么dGulⅣGuI.6G表示图G的最小度.只有一个顶点且无边的图定义为平凡图.边数为零的图称为空图.一个图,如果它的任意两个相异的顶点都是相邻的,则这个图定义为完全图.我们称图日是图G的子图,如果y日∈yG且E日∈EG.设日是G的子图,如果y日yG,则称日是图G的生成子图,也称为支撑子图.对图G的子图日,我们用G『y日1来表示日在G中的点导出子图.如果图G的子图集中的任意两个子图在G中都没有公共的顶点,则称这些子图是相互独立的或者点不交的.对于图G的两个点不交子图G1和G2,EGl,G2表示一个顶点在yG1中,另一个顶点在yG2中的边构成的集合.如果存在两个不交的子集Ⅵ和%,使得yGⅥu K,且G中的每条边的一个端点在Ⅵ中,另一个顶点在K中,则称图G为二部图或二分图.满足lⅥIm且I%In的二部图记为‰∥图G中的一个点边交替的序列称为途径,途径的点边都有可能重复,边不重的途径称为迹,顶点不重的迹则称为路,有礼个顶点n一1条边的路我们用R表示.其中,顶点用z1,z2,,zn来表示,边用%仇1i1,2,,礼来表示.设P1和P2是G的两条z一可路,如果他们除两个端点相同外,再无公共点,则称P1和P2是内不交的.p图定义为三条内不交的路的集合,这些路的起点和终点相同且起始点和终点这两个顶点是不同的两个顶点.起点和终点相同的路称为圈.有礼个顶点的圈记作G.3圈通常也称作三角形.长度为偶数的圈称为偶圈.包含了图G的所有顶点的圈称为哈密尔顿圈,包含哈密尔顿圈的图则称为哈密尔顿图.盯2G表示G中任意一对不相邻的顶点的最小宁夏大学硕士学位论文 第一章引言度和.如果G包含一条uu路,则称G中的两个顶点u,u是连通的.如果G中的任意两个顶点都是连通的,则称图G是连通图.连通无圈图称为树.树中度为1的顶点称为叶节点.G的连通无圈子图称为G的树分支.对连通图G中的顶点u,如果Gu是不连通的,则称u是G的割点.我们用G1,G2,,G。表示G一钊的几个连通分支.没有割点的连通图称为块.C表示图G的一个圈,Gf的弦是指GECI中连接C的两个顶点的一条边.一个圈被称为是弦圈如果它至少包含一条弦.点集z,,z2,,z。称为图G的一个独立集,如果它们中的任意两个顶点之间都没有边相连.图G的最大的独立集所包含的顶点的个数,叫做图G的独立数,我们一般用&G来表示.酊是通过从甄中恰好移除一条边所得到的图.除了上述基本概念和术语外,在每章必要时会给出一些特殊定义和术语,为方便阐述,有可能会重复某些定义.1.2问题的研究背景图论是组合数学的一个分支,与其他的数学分支都有着密切的联系.1736年欧拉研究并解决了著名的哥尼斯堡七桥问题,发表了图论的第一篇论文,他证明了这个问题是没有解的,并且将这个问题进行了推广,给出了对于一个给定的图可以以某种方式遍历的判定法则,也就是判断一个图是否是欧拉图的方法,这项工作使欧拉成为了图论的创始人.十九世纪中期关于图论的问题开始大量涌现,例如关于地图染色的四色问题、由“周游世界”游戏发展起来的哈密尔顿问题等.由于运筹学、计算机科学等领域的很多问题都可以转化为哈密尔顿问题,从而引起了广泛的注意和研究.1952年Dirac给出了判断哈密尔顿图的一个充分条件,即Dirac’s定理[1]如果图G是一个顶点数几≥3且使得对G中的每一个顶点u,dGu≥罟,则G是哈密尔顿图.1960年0ystein Ore给出了一个更一般的定理即0re’s定理【1]令G是一个顶点数n≥3的图.如果对G中的任意一对不相邻的顶点u,u,dG札dGu≥n,则G是哈密尔顿图.与此同时,出现了其他科学领域借助图去解决某些问题的成果,例如1847年德国的克希霍夫将树的概念和理论应用于工程技术的电网络方程组的研究中.1857年英国的凯莱提出了树的概念,并将其应用于有机化合物的分子结构的研究中.1936年匈牙利的数学家哥尼格写出了第一本图论专著有限图与无限图的理论,这也标志着图论开始成为一门独立的学科.近二十年来,随着科学技术的不断发展与进步,信息化和数字化也迅速发展,许多一2一宁夏大学硕士学位论文 第一章引言实际问题都可以建立适当的数学模型去解决,这促使人们对以图为结构的数字化技术更加关注,也使得图的理论,包括图的标号,图的控制和图的染色等成为了图论中发展最快的分支.而完全独立生成树特殊的判断条件也引起了学者的关注.Hasun啪a在[19]中提出了完全独立生成树的概念五和正是图G的两个生成树,如果对G中任意两个相异的顶点u,“,从u到口的路P1和P2在乃和正中是内不交的,则称矸和死是完全独立的.近年来,国内外学者发现完全独立生成树存在的条件和判断哈密尔顿图的条件几乎是平行的.在[14]中,T0m心撕证明了Dirac’s定理的度条件是两个完全独立生成树存在的充分条件;同时证明了2连通图的平方图有两个完全独立的生成树.这些条件也都是判断哈密尔顿图的充分条件.众所周知,目前已有很多判断哈密尔顿图的充分条件,那么研究这些条件可能会帮助研究者更广泛的去考虑完全独立生成树存在的问题,是不是判断哈密尔顿图的其他条件也是判断完全独立生成树存在的条件呢这个问题也是我们第三章所研究问题的意义.关于图上点不交子图的存在性研究也是图论的一个重要领域,而且利用度条件作为限制条件来研究点不交子图的存在性问题,目前已经得到了很多非常有意义的结果,可参考文献[2].本文的第二章,我们就研究的是图中包含指定个数的独立臼图问题,主要证明了高云澍和纪乃丹在[9]中提出的猜想,其尼3时的情况.该猜想为设尼是一个整数.任意阶数为礼边数至少为.,n,忌1的图包含尼个不交的目图,当,几,尼max{4七_1兰礼一4七1,l三gl二二堕羔墨竺二_三_兰二篓堑l二__生堕型I}.1.3已有结论及本文的结果第二章,我们主要研究了存在三个点不交的9图的极值函数,关于该问题,目前有以下结果Corr6di和Hajnal[5]中证明了关于不交圈存在性的一个结果.定理1.3.1[5】设惫是一个正整数,G是一个顶点数n≥3的图.如果6G≥2克,则G包含尼个不交的圈.W抽g[13]和Enomoto[7]证明了一个比定理1.3.1更强的结果如下.定理1.3.2[13]设尼是一个正整数,G是一个顶点数礼≥3尼的图.假设对G的任一对不相邻的顶点让,u,dGudG“≥4尼一1,则G包含尼个不交的圈.弦圈就是一个简单的臼图,但p图不一定是弦圈.显然,酊是阶数最小的口图且任意的臼图都包含一个偶圈.P6sa[12]证明了任意最小度至少为3的图包含一个弦圈.通过这些结果的启发,Finkel et a1.[6]和Chiba et a1.[3]分别得到了下面的结果.一3一宁夏大学硕士学位论文 第一章引言定理1.3.3[8]如果G是一个顶点数几≥4七且最小度JG≥3七的图,则G包含南个不交的弦圈.定理1.3。4[5]设r,s是两个非负整数且G是一个顶点数为n≥37 4s的图.假设对G中任意一对不相邻的顶点u和u,dGudGu≥4r6s一1,则G包含rs不交圈使得它们中的s个是弦圈.KawarabayaLshi[1 1]认为在一般的图中,最小度确保了酊的复制的存在,这被看做是不交的臼图的特定说明.定理1.3.5[1 1]设七是一个正整数,G是一个顶点数竹2 4七的图.如果占G≥f学],则G包含七个不交的酊的复制.在本文中,我们所做的研究是以高云澍和纪乃丹在[9]提出的猜想为基础,他们证明了该猜想尼2的情况.我们将证明七3的情况.猜想1.3.6【9】设惫是一个整数.任意阶数为n边数至少为,几,是1的图包含忌个不交的臼图,当,几,凫max{4矗i 1兰n~4克1,,l三塑∑二三丛墨竺二二上±{等∑二兰丛型j定理1.3.7[9]任意顶点数礼≥8,边数至少为,n的图包含两个不交的目图,如果,礼 如果n8如果n≥9注意高云澍和马丁在[10]中证明了下面的结果.定理1.3.8任意顶点数为竹≥12的边数至少为I些竽I的图包含三个点不交的日图.本文中我们将完全解决猜想1.3.6足3的情况.即定理1.3.9.定理1.3.9任意顶点数n≥12边数至少为 max{『半¨竿j的图包含三个点不交的目图.作为推论,我们还得到了另外一个结果推论1.3.10任意顶点数为n≥12边数至少为 max“半],I_掌j弱学宁夏大学硕士学位论文 第一章引言的图包含三个不交的偶长圈.第三章,我们主要考虑两个完全独立生成树存在的度和条件.完全独立生成树的概念是由HasuIl眦a[19]中提出的,同时他也证明了在七一连通线有向图的基础图中存在七个完全独立的生成树.Hasull啪a[20】中证明了在任意图中是否存在两个完全独立的生成树是ⅣP一完全的.因此关于完全独立生成树的存在性的研究趋势转向确定图族或者找出确保完全独立生成树存在的条件.在[20]中,HaSuIluma证明了任意的4一连通极大平面图包含两个完全独立的生成树,并且给出了寻找这样的树的线性算法.C.Morisaka和T.Hasun啪a在[21]中证明了在两个2一连通图的笛卡尔积图中存在两个完全独立的生成树.近年来,国内外学者发现完全独立生成树存在的条件和哈密尔顿图的条件几乎是平行的.众所周知,目前已有很多判断哈密尔顿图的充分条件,其中最经典的一个结果就是由Dirac[16]在1952年证明的.定理1.3.11Dirac’s定理,[16]如果G是一个顶点数礼≥3的图且6G≥≥,则G是哈密尔顿图.另外一个重要的结果是Ore在1960年证明的.定理1.3.12ore’s定理,[24]如果G是一个顶点数仇≥3的图且仃2G≥几,则G是哈密尔顿图.最近,Aral【i[14]中证明了在Dirac’条件下完全独立生成树的存在性并且提出了是否判断哈密尔顿图的其他己知的条件也是两个完全独立生成树存在的条件.这也是我们本章所研究的问题的目的.定理1.3.13时出’s定理,[14]如果G是一个顶点数礼≥7的图且6G≥罟,则G包含两个完全独立的生成树.在本章中通过不同于Ar撕[14]的证明,我们证明了0re’条件也是两个完全独立生成树存在的充分条件.即定理1.3.14.定理1.3.14如果G是一个顶点数仡≥7的图且仃2G≥n,则G包含两个完全独立的生成树.定理1.3.14的证明是独立于定理1-3.13的.不久前,FaIl et a1.[4】证明了一个顶点数礼8且盯2G≥礼的图包含两个完全独立的生成树,但是他们的证明是完全依赖于定理1.3.13,而我们的方法是通过构造以及不同于Fall et a1.[17]使用的技巧.利用与第三章类似的方法,Gao和Ji[18]证明了M00n和Moer’s[22】的判定哈密尔顿图的度条件也是二部图中两个完全独立生成树存在的充分条件.一气一宁夏大学硕士学位论文 第一章引言定理1.3.15[18】令Gx,y;E是一个二部图,并且顶点数IxIlyIn≥4.假设下列条件至少有一个被满足1JG≥孚.2对每对不相邻的顶点u∈x且“∈y满足dGudGu≥佗1.则G包含两个完全独立的生成树.6宁夏大学硕士学位论文 第二章存在三个点不交的口图的极值函数第二章 存在三个点不交的p图的极值函数本章我们主要讨论存在三个点不交的口图的极值函数.若无特殊说明,本章中的图均是指简单无向有限图.本章共分为三节.第一节介绍了基本概念及术语,第二节给出了所需引理及其证明,第三节给出了主要定理的证明.2.1基本概念及术语臼图定义为三条内不交的路的集合,这些路的起点和终点相同且起点和终点互异.设n是一个正整数,%表示有几个顶点的完全图.珩是通过从托中恰好移除一条边所得到的图.一个图集被称为是点不交的或者独立的,如果他们中的任意两个元素在G中都没有相同的顶点.在这章中,我们用不交来表示点不交.设Ⅵ,K是G的两个不交的顶点集,EⅥ,K表示G中一个顶点在Ⅵ中,另一个顶点在K中的边集,Ez,%,EⅥ,z分别表示Ez,K,EⅥ,z.R表示有n个顶点的路.C表示图G的一个圈,C的弦是指GEC的一条连接C的两个顶点的边.一个圈被称为是弦圈,如果它至少有一条弦.2.2主要引理及其证明为了后面证明的方便,我们给出了以下几个引理及其证明引理2.2.1 设G是一个顶点数为12,边数至少为57的图,则G包含三个不交的虹.证明利用反证法,假设G不包含三个不交的珩.如果6G≥8,则根据定理1.3.5,G 2 3酊,这与我们的假设矛盾.因此,我们可以假设6G≤7.设%∈yG并使得dG%6G.假设dG%1,则56IEGl57,这与题设IEGl≥57矛盾.因此dG“o≥2且IEG一{uol≥57一dG%.假设dGuo2且令u1,u2∈Ⅳ.Guo,则选择叫∈yG一{uo,u1,u2,显然[uo,u1,u2,叫]三酊且[yG一{%,u1,u2,叫]≥2酊,此时G三3酊,这与我们的假设矛盾.这意味着dGuo≥3.注意到G一.[“o].可以从K11中至多去掉5条边得到.假设[ⅣGuo]包含一条三长路,我们用B来表示.则B{uo】-包含一个子图Q 2酊.注意到IEGyQI≥577一109823,根据定理1.3.7,GyQ包含两个不交的酊的复制,它与Q是不交的,这意味着G 2 3酊,再次与我们的假设矛盾.因此ⅣGuo2 R.如果dGuo≥4则NGuo至少包含一条边,我们用ul乱2来表示.由于ⅣG一{“。让1nⅣG一伽乱2≠0,一7一
展开阅读全文
收藏
下载资源

加入会员免费下载





足球比分直播