图包含指定长度圈和泛弧问题的研究

《图包含指定长度圈和泛弧问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、山东大学博士学位论文图包含指定长度的圈和泛弧问题的研究姓名：邹青松申请学位级别：博士专业：运筹学与控制论指导教师：李国君20111028图包含指定长度的圈和泛弧问题的研究邹青松山东大学数学学院，山东，济南，250100指导教师：李国君教授中文摘要图论的研究已有200多年的历史．图论起源于1736年Euler发表的一篇论文，他用图论的方法解决了哥尼斯堡(KSnigsberg)七桥问题．自二十世纪六十年代以来，图论得到迅速发展，涌现了大量结果．图论中有很多著名问题，如欧拉图问题，哈密顿圈问题，中国邮递员问题，四色定

2、理等．应用图论来解决运筹学，物理学，化学，生物学，计算机网络，信息论和博弈论等学科问题，已经显示出极大的优越性．图论作为离散数学和组合数学的一个重要分支，受到了各方面的普遍重视．本文只考虑简单、有限图，这些图不包含环和重边，并且只有有限个顶点和边．设G是一个顶点数为n的图，日是一个顶点数为h的图，其中n和h是正整数．图论中的包装问题是指，在图G中找到尽可能多的点不相交的同构与日的子图．图G的z卜因子是图G的—个子图，它由h／^J个同构与日的子图组成．特别地，图G的拓因子指的是图G中的缸正则子图，其中k是正整数．

3、在日常生活中，很多优化问题和网络问题，诸如编码设计，积木设计，生物DNA分子结构分析，进度表等关于运筹和网络设计问题都涉及到图的因子和因子分解．本文主要研究2一因子问题．一个圈称为b圈，如果它恰好包含七个顶点；类似地，一条路称为肛路，如果它恰好包含七个顶点．图中包含每个顶点的圈，称为图的哈密顿圈．显然，一个哈密顿圈可以被看成是仅有一个分支的2．因子．1952年，G．Dirac给出了图包含哈密顿圈的最小度条件．1960年，0．Ore给出了图包含哈密顿圈的最小度和条件．这两个结果可被认为是2一因子问题的先驱．对于一

4、个给定的图，山东大学博士学位论文找到2．因子存在性的条件是很困难的．常用的技巧是先找出一个顶点数目极小的包装，然后扩充成为2．因子．本文研究了图论中的几个问题，具体地，我们研究了图中点不相交的子图(主要是圈和路)及2．因子的存在性问题，有向图中泛弧的存在性问题．图的点不相交圈问题可以概括为：最小度(或者度和)满足什么条件时，图包含一个2．因子?进一步地，从这些条件中，我们能否确定2．因子中圈的数目或者圈的长度?上述问题是极值图论中的基本问题．本文中，我们利用最小度与最小度和条件研究了图包含缸圈、每圈和8．圈的问

5、题．一条弧e称为有向图D的泛弧，如果对于任意的点z6V(D)，存在一个包含弧e和点z的圈．显然，如果有向图包含一个哈密顿圈，则哈密顿圈的每一条弧都是泛弧．我们利用最小度条件研究了强连通多部竞赛图和圈连通多部竞赛图包含泛弧的问题．全文共分为五章．在第一章中，我们给出了一个简短而完整的引言．首先我们列出了本文中会用到的所有术语和符号，然后我们介绍了图中点不相交的子图和指定长度的圈的研究背景和进展．紧接着，我们介绍了有向图中泛弧问题的研究进展．最后，我们列出了本文的主要结果．在第二章中，我们给出了图包含点不相交4．圈

6、的度条件．首先我们定义两类图：M(后1，k2)=K4,1+2UK4k2+a和N(kl，岛)=K4,1+1UK4七,+3，其中七l，也是非负整数．设G是一个无爪图，顶点数为IGJ_4七，其中k是—个正整数．如果图G的最小度和观(G)至少为4七一2，我们证明了图G包含k一1个点不相交的4-圈和一条4．路，使得所有这些圈和路是点不相交的，除非G同构与U(kl，乜)或N(k1，如)，其中七l≥0，‰≥0，七1+乜=k一1．我们给出反例，说明了结论的度条件是最好的，而且无爪图的要求是必需的．紧接着，我们给出了二部图包含缸

7、圈的度条件．设G=(Ⅵ，K；E)是一个二部图，满足IKl=IKI=2k，其中k>0是一个正整数．假设对于任意的o∈Ⅵ，鲈∈K，甜gE(G)，d(z)+d(y)≥3k，我们证明了G包含k个点不相交的垂圈．在第三章中，我们研究了二部图包含点不相交昏圈的问题．设G=(H，％；E)是一个二部图，满足IⅥJ_IKI=3k，其中七是一个正整数．我们首先利用最小度条件证明了，如果最小度大于等于2七，则图G或者包含七个点不相交的6-圈，或者包含七一1个点不相交的6-圈和一个乒圈，它n山东大学博士学位论文们点不相交．紧接着，我们

8、探讨了二部图包含点不相交6-圈的度和条件．设G=(Ⅵ，K；E)是—个二部图，满足lⅥI．I％I=3k，其中k是—个正整数．我们证明了，如果对于任意的z∈Ⅵ，Y∈％，xy舞E(G)，d(x)+d(可)≥4k一1，则图G有一个支撑子图包含k一1个点不相交的6-圈和一条6-路，它们彼此点不相交；如果k>2，并且对于任意的z∈Ⅵ，Y∈K，xygE(G)，d扛)+d(秒)≥4k，则图G有一个支撑