关于图的控制函数

来源 :华东交通大学 | 被引量 : 0次 | 上传用户:qwedddessf
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
自Euler发表第一篇图论论文以来,图的理论逐渐建立并完善和丰富起来。在图论中,图的控制理论占据着举足轻重的地位:一方面对于许多实际问题,可以用图进行建模,将其转化为计算图的控制数问题来解决;另一方面,图的控制理论不仅对图的其它理论的研究有着重要的影响,同时也深深地影响着其他学科的发展,如运筹学、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学等。在图的控制理论中,确定图的控制数是一个最基本的问题,Garey和Johnson在[1]中已经证明:确定任意图的控制数问题是一个NP-完全问题。于是,确定控制数的尽可能好的上界和下界就具有非常重要的意义。而控制数通常是由控制函数决定的,因此要想获得控制数,首先要选择合适的控制函数。  本文主要讨论了图的减边控制函数,对比研究了图的减边全控制函数和反减边全控制函数,最后讨论了图的全反符号控制函数和全减边控制函数。  本文主要做了以下工作:  在第一章的绪论部分,我们对图论尤其是图的控制理论问题的背景知识、应用范围和主要研究方向进行简要回顾,然后对本文所涉及的一些图的定义、符号及图之间的运算关系进行介绍,最后对本文的后续章节的主要结构安排进行了简要介绍。  在第二章,我们讨论了图的减边控制数的一些新的界限,减边控制数的定义是由徐保根教授在2007年引入的,在其论文中留下了一些问题,我们对其中的一个问题进行了初步研究,得到了一般图的新的减边控制数的界限。  在第三章,我们在给出图的减边全控制数和反减边全控制数定义的基础上,对比研究了一般图的关于这两类边控制函数的界限,给出了用图的顶点数、边数以及最大度和最小度来表示的一般图的两类边控制数的界限,最后给出路、圈和轮图的减边全控制数和反减边全控制数。  在第四章,我们研究了一般图的全反符号控制数的上界,并且对于特殊图——圈。  在第五章,我们提出了全减控制函数的定义,该定义是对全控制函数和全符号控制函数的一种自然推广,从而使控制更具有普遍意义。在此基础上,我们得到了一般图关于全减控制函数的界限。  在第六章,我们对前面得到的结果进行总结和回顾,同时对本文将来的研究方向进行了展望,以期对将来的研究起到一定的作用。
其他文献
给定一个图G,G的全k染色是指至多用k种颜色,对G的顶点和边同时进行着色,使得相邻的两个元素(点和边)染不同的颜色.全色数X″(G)是指使得G有一个k-全染色的最小整数K.众所周知,平面图
强化党员的民主权利观,是党内民主建设的内在要求和重要保证。当前,民主权利观弱化,已成为制约党内民主建设的一个瓶颈,应重点抓好以下三个方面:一是提高“知权”标准。对自己
循环码是线性分组码的一类重要子码,在理论和应用中都有着重要的科研价值。循环码比一般线性码拥有更多代数结构,因而引起编码和密码理论研究者的兴趣与关注。循环码的自身特性
本文应用奇摄动渐近展开方法研究广告定价问题,分别讨论了Newsboy问题的广告定价模型和V-W型广告定价模型。广告定价问题目前受到了广泛的关注与研究。前人对广告定价模型的
无线传感器网络综合了传感器技术、嵌入式计算技术、分布式信息处理技术和无线通信技术.网络由部署在监测区域内的大量的传感器节点组成,网络节点数量庞大、单个节点能量极其
随着社会的进步和发展,道路上车辆越来越多,以致交通事故频频发生,因此如何有效的减少交通事故,减少车辆和行人的碰撞,及时警告驾驶员可能与附近的车辆发生碰撞,已经成了人们关注的
河南省登封市公安局局长任长霞在破案途中因遭遇车祸不幸牺牲后,登封14万群众倾城为其送行“嵩涛阵阵哭长霞,颖水涟涟惜女杰”,她的先进事迹迅速传遍大江南北,引起全社会强烈
社会科技发展以及网络信息技术的普及,使得互联网网络在人们日常生活中扮演着越来越重要的角色,对人们生活方式产生了巨大的影响.在这种背景下,如何加强对医学生的网络化思想
Hausdorff算子的研究最早可追溯到1921年,由Hausdorff为研究数列的收敛性而提出的,它不但包含了Hardy算子、Cesàro算子等,而且在概率论、多复变函数论以及几何分析等学科中有着
矩阵方程是矩阵理论中非常重要的分支,尤其是非线性矩阵方程,在控制理论、梯形网格、动态规划等多个领域都有很重要的应用.因此,许多学者对非线性矩阵方程这一课题进行研究.