图的路划分问题

来源 :云南大学 | 被引量 : 0次 | 上传用户:easelin
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
判断一个图是否有哈密顿路的问题是图论中的一个经典问题,而判断一个图是否能被划分成一些给定数目路的并问题是哈密顿路问题的一个重要推广,后者被称为点不交路的划分问题。路的划分问题在现实中有着许多的应用。而这个问题在一般图中都是NP-完备的,一个可能解决这个问题的方法就是找出哈密顿路或者路划分存在的充分性条件。   本文将对图中路划分存在性问题展开讨论,重点讨论2-连通图和二部图中路划分存在的充分性条件,主要是引入了邻域并型的条件来解决这个问题。   本文的研究内容及成果主要包括下面几章:   第一章:回顾了问题的由来,理论的形成,给出了到目前为止的一些研究成果。   第二章:对文中所出现的定义、概念和符号等给出了说明。   第三章:给出2-连通图中路划分存在的一个充分性条件及其证明。   第四章:给出二部图中路划分存在的一个充分性条件及其证明。   第五章:给出相关结论及未来研究的方向。   
其他文献
模型修正问题出现于上世纪90年代初,作为机械系统建设和维护的一个重要工具。关于二次模型修正问题的研究是如今重要的国际前沿问题。近年来,国内外关于二次模型修正问题的研究已经取得了大量的研究成果,但仍有许多问题有待更深入的研究,比如在特定条件下如何保持系数矩阵正定、物理连接性等。针对实对称二次模型,发展模型修正问题新的直接方法和高效的优化技术,使得二次模型的修正既能够保持原始二次模型结构,又满足无溢出
在捕获与再捕获问题中,我们感兴趣的通常是对研究群体的总体数目的估计。在本文中,我们依次对三个不同的捕获-再捕获/移出模型进行研究,在各自的假设条件下得到了对群体数目的估
随着城市配电网的网络化程度的不断提高,凭借人们的经验已经不能很好地改造和管理配电网。而在整个配电网地规划和管理中,人们不断地在其整体统一规划和先模块式规划再分解协调
本文以研究军人保险制度中的风险管理体系为主要内容,对于将金融风险管理的基本原理应用于军人保险制度进行了初步的尝试,特别分析了当前我国军人保险制度中的主要风险方面,以及
本文在前人的基础上进一步讨论了E凸集和E凸函数的性质,以此为基础和工具,首次给出了E凸函数的次微分,并对E凸函数的次微分进行了较深入的探讨。E凸函数的次微分是全文章的核心
曲面重建(SurfaceReconstruction)是指通过已知的曲面的部分信息将原曲面重建出来。曲面重建被广泛应用于计算机视觉和图像处理等多个领域。在过去的二十年里,许多重建算法被
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
期刊
无线射频识别(RFID)是一项新兴的无接触自动识别技术。作为物联网的关键技术之一,RFID产业潜力巨大,应用范围遍及制造、物流、医疗、运输、零售、国防等。然而,随着RFID应用的普及
身份认证和密钥交换是不安全分布网络通讯的中心问题。口令认证协议就是利用短的、容易记住的口令,实现身份认证和密钥交换。在本文中,首先设计了对称和非对称的两个口令认证和
k-路问题和k-树问题是两类组合优化问题。由于其与实际联系的紧密性,这两类问题更易引起广大研究工作者的关注。到目前为止,已得到了一些的理论研究成果,为实际应用奠定了理论基