二部图的控制参数研究

来源 :中国科学技术大学 | 被引量 : 0次 | 上传用户:ljn3125678
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
控制是图论中的重要概念,由于它在计算机科学,化学等的广泛应用,对图的各类控制参数以及对控制参数与其它参数之间关系的研究已成为图论研究中一个非常重要的领域.本文主要研究两种控制数(控制数和成对控制数)与图的边数极值之间的关系.   本文分为三部分.在第一部分,首先我们介绍了图论的历史背景和现实中的应用,接着我们给出了图论的一些基本概念;在第二部分,首先我们给出了有关控制的一些概念,其次我们给出了有关控制参数与边数极值的主要结论.从主要结论中我们知道,当k>3时,边数等于1/4(n-k+2)2的二部图中必含孤立点,而我们在电路板制作和资源分配等问题中常会遇到连通二部图和成对控制与边数极值的情况,于是对连通二部图的控制数与边数极值的研究和对二部图的成对控制数与边数极值的研究都是很有意义的.在第三部分第一节我们主要研究就是连通二部图的控制数与边数极值问题,在这一节中我们给出了当连通二部图的控制数k(≥4)给定时,边数的上界为「1/4(n-k)2+(n-k)」,且这个界是紧的;在第二节我们主要研究成对控制数和边数极值问题,在这一节中,我们给出了当二部图的成对控制数k(>2)给定时,边数的上界为1/4((n-k/2)2+2(n-k/2)),且这个界是紧的.
其他文献
本学位论文主要考察了子群的几类嵌入性质对有限群类构造的影响.不仅得到了可解群、p-超可解群等饱和群系及广义超中心的结构的细致刻画,而且还揭示了某些非可解群类的构造.全
在论文中,我们主要考虑了具有源项和粘弹性项的波动方程的解的爆破和衰减性质.   首先,我们研究具有源项的粘弹性方程在一定条件下,甚至是初始能量趋于零时,解在有限时间内爆
随着多媒体技术、网络技术以及数字设备技术的迅速发展,如何有效的检索所需要的图像信息是急需要解决的问题。基于内容的图像检索技术就是这种背景和应用需求下产生的。尽管
随着计算机技术与视频监控和技术的发展,对运动目标的识别与跟踪已成为一个重要研究领域。本文基于这一研究,就运动目标的背景提取,运动目标物体识别与运动目标物体跟踪这三个方
在深空探测任务中,由于通信距离极远,使得地面站接收到的信号极其微弱,传输时延大大增加。尤其是对于未来更远探测距离的深空任务,已经无法使用点对点链路的传输方式。为了确保深
学位