图的某些控制参数的计算

论文摘要

经过几十年的发展,图的控制参数理论已经成为图论中非常活跃的研究领域之一.基于不同的实际背景,人们提出了许多控制参数.控制参数理论快速发展的主要原因是：图的控制参数理论与组合优化、理论计算机科学、社会科学等学科有着密切关系；图的控制参数理论可直接应用于设施选址、监视系统、通信网络等现实问题中.目前,关于图的控制参数的研究主要集中在算法及复杂性研究、界、极值图刻画、精确值计算等方面.本文考察了图的控制数、符号控制数、减控制数、符号全控制数、减全控制数、配对控制数、混合控制数、符号混合控制数、k-距离控制数以及k-步长控制数等控制参数,主要从算法复杂性和精确值计算两个方面对这些参数进行了研究.所做的主要工作如下：·在第二章,主要研究了符号控制数、减控制数、符号全控制数、减全控制数、配对控制数等常见控制参数,求出了这些控制参数在某些特殊图类上的精确值.在本章的最后一节,还证明了控制数问题在最大度不超过4的平面二部图上是NP-完全的. （有关结果已在《Utilitas Mathematica》发表一篇,录用一篇）.·在第三章,较系统地研究了图的混合控制问题的算法复杂性.我们给出了求树的混合控制数的两个多项式时间算法,并论证了在分裂图上求解这一问题是NP-完全的. （有关结果己在《Theoretical Computer Science》发表）.·在第四章,主要研究了图的符号混合控制问题.吕新忠[76]提出了这一概念并给出了路和圈的符号混合控制数的值,我们证明了该问题在平面图上是NP-完全的,并给出了完全图和完全二部图的符号混合控制数的精确值. （有关结果已投稿）.·在第五章,主要研究了图的距离控制和步长控制问题.首先给出了求树的2-步长控制数的一个线性时间算法,然后类似地给出了求树的k-距离控制数的一个新的线性时间算法. （有关结果已投稿）.

论文目录

• 摘要
• Abstract
• 第一章 绪论
• §1.1 引言
• §1.2 基本概念
• §1.3 本文的主要工作
• 第二章 图的几种常见控制参数研究
• §2.1 引言
• §2.2 完全多部图的几个常见控制参数的值
• §2.2.1 符号控制数和减控制数
• §2.2.2 符号全控制数和减全控制数
• §2.3 两个完全图的Kronccker积的几个常见控制参数的值
• §2.3.1 几个控制参数值
• §2.3.2 几个全控制参数的值
• §2.4 图的上定位控制数
• §2.5 控制数问题的一个NP-完全结果
• 第三章 图的混合控制
• §3.1 引言
• §3.2 求树的混合控制数的两种多项式时间算法
• §3.2.1 将树的混合控制问题转化为强弦图的控制问题
• §3.2.2 树的混合控制问题的标号算法
• §3.3 混合控制问题的一个NP-完全结果
• 第四章 图的符号混合控制
• §4.1 引言
• §4.2 完全图的符号混合控制数
• §4.3 完全二部图的符号混合控制数
• §4.4 符号混合控制问题的一个NP-完全结果
• 第五章 图的步长控制和距离控制
• §5.1 引言
• §5.2 2-步长控制问题在树上的一个线性时间算法
• §5.3 k-距离控制问题在树上的一个标号算法
• 研究展望
• 参考文献
• 作者攻读博士学位期间完成的论文
• 作者在攻读博士学位期间参加的课题
• 致谢