图划分及相关问题研究

来源 :中国科学院大学 | 被引量 : 0次 | 上传用户:daocaoren666666
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图论起源于著名的七桥问题,以图为研究对象来刻画事物之间的二元关系.自二十世纪六十年代以来,计算机的迅速发展,有力地推动了图论的发展,使图论成为近年来较为活跃的数学分支之一.目前,图论已经广泛应用于计算机科学、生物学、网络科学、信息论、化学、控制论、博弈论等领域.  本文主要研究图划分及相关的因子理论和生成树问题.  本文第一章介绍了本文工作的研究背景以及论文的内容与安排.  本文第二章主要研究了图和超图的公平划分问题.划分是指将一个图或超图的顶点集划分成若干个不相交的子集,使得划分满足子集之间的某些限制条件.比较典型的是同时优化多个量的划分问题,即公平划分问题.划分问题是一个经典的组合优化问题,具有广泛的应用,如超大规模集成电路设计(VLSI)、布线问题、聚类问题等,是图论研究中的一个热点和难点问题.  本文第二章针对Bollobás和Scott所提出的一个超图公平划分问题的猜想,给出了边的阶数不超过3的超图存在某种公平划分的一个结果,首次研究了该猜想的含有3-边的超图情形,是Bollobás-Scott猜想的一个重要进展.  本文的第三章主要研究图的因子理论.图的因子理论是图论的一个重要分支,在图论的研究中受到了极大的关注.很多问题都涉及图的因子和因子分解,如编码设计,计算机网络的文件传输等问题.  图的因子问题分为两大类,分别是:度因子问题和连通分支因子问题.如果一个因子是用度来描述的,则称该因子为度因子.如果一个因子是用连通分支来描述的,则称该因子为连通分支因子.  图的度因子理论研究从1891年Petersen的有关正则图的1-因子开始,经历了k-因子,f-因子,[a,b]-因子,[g,f]-因子等越来越一般情形的研究,取得了比较丰富的研究成果.  连通分支因子理论是由M.Kano提出的,在1993年他提出了一些关于连通分支因子的问题和猜想,促进了连通分支因子理论研究的发展.目前关于连通分支因子的结果,已经有了圈因子、路因子和星因子的存在性的结果,其他某些特殊图类所组成的连通分支因子还有很多值得研究的问题.  本文第三章讨论了连通分支因子问题,解决了Kano等人所提出的关于星类因子的猜想,是对Kano等人的星因子的结果的推广,得到了一个更强的结论.  本文第四章研究了图的与Hamilton性质有关的生成树的存在性问题.图的生成树是图论中的重要概念之一,在实际生活中有许多重要的应用,如通信网络设计、管道铺设、道路系统设计等.在结构图论的研究中,我们关注的是图的生成树特征问题,它的产生和发展与著名的Hamilton问题密切相关,是结构图论中的一个重要研究课题.  从生成树的观点来看,图的Hamilton路是恰有两个叶子的生成树,同时也是最大度为2的生成树.那么,图中Hamilton路的存在性问题就可以推广为如下问题:给出图中存在至多k个叶子的生成树,或者图中存在最大度不超过k的生成树等一系列问题的充分条件.  目前关于图的与Hamilton性质相关的生成树特征问题的研究,主要是从参数的角度出发进行刻画.具体来说,就是用独立数、连通度、不相邻点的度和等条件,讨论图中存在具有某些特殊性质的生成树的充分条件,比如具有如下特殊性质的生成树:(1)至多k个叶子的生成树;(2)最大度不超过k的生成树;(3)去掉所有叶子后,最大度不超过k的生成树;(4)去掉所有叶子后,至多k个叶子的生成树;(5)可以在m距离之内控制图中所有点且至多k个叶子的树.关于前两种树的研究结果比较丰富,后三种树是近年来研究的热点,我们主要关注的是在什么样的条件下,图中会存在后三种树.  本文第四章用不相邻点的度和条件给出了图中存在生成树满足去掉所有叶子后的茎至多有k个叶子的一个充分条件,并且给出了一个极值图类说明所给出的界是紧的.  本文第五章是总结与展望,包括本文主要内容、主要贡献以及进一步的研究展望.
其他文献
谱峰校正是基于核磁共振的代谢组学数据预处理过程中的一个重要环节,谱峰校正效果直接影响后续的多变量统计分析.核磁共振谱图中常见的谱峰形状有单峰,二重峰,三重峰,多重峰
当前,评价一堂成功的美术课,首要的一点是看授课教师的教学方法和艺术,能不能使学生们对所接受的新知识具有浓厚的兴趣感、极大的热情和好奇心.因此,广大的初中美术教师在教
学位
本文主要研究代数、微分多项式系统的零点分解算法.将代数或微分多项式系统的零点集合分解为由三角列表示的纯维代数簇或微分代数簇是符号计算的一个核心算法.在本文中,我们从
学位
第一章,列举了度量空间上概率测度弱收敛的一些基本结果,这些结果都是以后的论述和证明中所必需的.第二章,完整地叙述并证明了取值于Polish空间的Skorohod空间D[O.T]上概率测
针对高光谱遥感图像的小目标检测问题,提出了一种基于自适应参数支持向量机(SVM)的检测方法。采用主成分分析(PCA)法对高光谱遥感图像进行降维,降低数据冗余度;之后通过无监