连通图中边控制树的存在性

来源 :福州大学 | 被引量 : 0次 | 上传用户:pptcowboy
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的哈密顿问题是指在图中寻找一个包含所有顶点的圈,它是图论重要研究课题之一。对图G的子图H,若G的每个点(或每条边)要么在H中,要么和H中某个点相邻,则称H为G的控制子图(或边控制子图)。1965年,Harary和Nash-Williams证明了“线图L(G)是哈密顿的当且仅当G有一个控制的欧拉子图”。1986年,Thomassen提出了下面的猜想:每个四连通的线图是哈密顿的,这个猜想引起了学者们广泛的研究并得到了许多相关的结果。本文主要讨论控制子图,如果图G存在两棵边不相交的树T1,T2使得T1为支撑树,T2为边控制树,则可以证明G 一定包含一个控制闭迹,从而G的线图一定是哈密顿图。由于4-连通线图对应到原图为本质4-边连通图。因此研究本质4-边连通图中的边控制树存在性就十分有意义。本文旨在研究边不相交的边控制树存在性问题。分别给出了存在两棵边不相交的边控制树的充分条件和必要条件,从而可以得出本质5-边连通图在一定条件下存在两棵边不相交的控制树,并且证明存在无限多本质4-边连通图都不包含两棵边不相交的控制树。本文分为四章:第一章给出图论中与本文相关的一些基本概念,同时介绍Thomassen猜想的研究现状及边控制树的研究背景以及本文的主要结论。第二章主要研究一般图的控制树存在性问题,给出了存在两棵边不相交的控制树的充分条件和必要条件。第三章研究本质k-边连通图中边控制树存在性问题,证明了本质5-边连通图在一定条件下存在两棵边不相交的边控制树,同时给出了无限多不存在两棵边不相交的边控制树的本质4-边连通图。第四章主要介绍一些本论文的后续研究工作。
其他文献
自2002年美国颁布SOX法案后,我国着手完善内部控制规范。先于2008年颁布了《企业内部控制基本规范》,紧接着2010年,审计署等五部委联合发布了包括评价指引、应用指引和审计指
石墨烯(graphene)是一种典型的二维材料,由于其在光学、电学和机械学等方面的特性,从2004年在实验室被发现至今,一直是科学研究的热点。随着研究的深入,石墨烯的生长方法已经
近年来,压力问题已经成了社会工作众多问题中重要的、需要引起注意的问题,引起了社会各界的广泛关注,并且学者们也开始逐渐将注意力转移到压力问题的研究领域。在煤矿企业中,
随着社会和国民经济的快速发展,对煤炭资源需求量的增加,煤矿资源的大量开采已经导致地下形成了大范围的采空区。采空区导致覆岩及地表沉陷,将对地面建筑物造成不同程度的破
隧道内交通目标的准确提取,是隧道异常事件检测的关键。而在隧道场景中监控设备存在抖动,使得提取的车辆目标畸形、行人目标与背景连通,严重干扰了交通目标的有效提取。同时
设{Xn,n≥ 1}是一列L1随机变量,{Yn,n ≥ 1}是一列相互独立的非负随机变量且独立于Xi(i=1,2,…).令Tn =∑i=1 n XiYi,n ≥ 1,则当{Xn,n≥1}是零均值PA序列时,{Tn,n≥ 1}是一
最近几十年,癌症已经成为威胁人类健康最重要的疾病之一,精确、可靠的肿瘤识别对癌症诊断以及治疗至关重要,而应用数据挖掘技术获取肿瘤数据潜在信息是研究肿瘤发生、发展、
近年来,以碳纳米管为基础的三维结构如阵列、泡沫、微球以及空间网络等的研究得到人们的广泛关注,其中尤其以球状结构的研究最为吸引人。本文通过实验室自行构建的液滴基微流
论文为解决山东掖县镁矿菱镁矿尾矿堆积难题,以菱镁矿尾矿、熟石灰、γ-Al203为原料,尝试合成含镁铝尖晶石的胶凝材料,研究材料的结构和性能,通过正交实验确定尾矿的最佳掺量
合作博弈是研究在合作过程中达成联盟与分配利益的理论依据.由于实际合作博弈的需求,多目标合作博弈成为当前合作博弈研究领域的热点.为了研究多目标合作博弈的分配解,学者们