几类图的控制参数的理论与算法

论文摘要

近三十多年来，随着计算机科学和网络通讯技术的飞速发展，图论研究也呈现出异常活跃的趋势，而控制数理论也许是其中发展最快的领域．图的控制数理论作为图论的一个重要研究方向，在相关学科领域，例如计算机科学、通讯网络、编码理论、运筹学以及社会学等领域具有广泛的应用．目前，关于图的控制数理论研究主要集中在四个方面：（1）各类控制参数的界的确定，相互之间关系的研究，以及控制参数与图的其他参数，如色数的关系研究；（2）各类控制参数计算复杂性的研究及其算法的设计；（3）函数控制数及其相关课题的研究；（4）控制数理论在相关学科中的应用研究． 本文所做的工作主要包括以下五部分： 第一，我们确定了一般连通图及无爪立方图上电力控制数的准确上界，并对达到其上界的极值图进行了刻画（有关结果已被《Discrete Mathematics》录用）；并分别讨论了外平面图及一般平面图上电力控制数的界（有关结果已被《Journal of Shanghai University》录用）． 第二，我们研究了两类新的控制函数：负边控制函数和负星控制函数；确定了负边控制数的界，并对达到其上界的阶数为偶数的极值图进行了刻画；并且讨论了这两类控制参数与其他控制参数的关系（有关结果已被《Ars Combinatoria》录用）． 第三，我们对达到图的2-距离控制数已知上界的极值图进行了完全刻画． 第四，我们给出了二部置换图上无圈控制集的线性时间算法，并研究了三种情况下直线簇上区间图的最小连通控制集算法（有关结果已发表在《上海大学学报（自然科学版）》）． 第五，我们构造了具有最小可能边数且最小度为κ的任意大的无限唯一κ-可着色图类（有关结果已被《Journal of Shanghai University》录用）．

论文目录

• 摘要
• Abstract
• 第一章 引言
• §1.1 图的控制数理论的产生与应用
• §1.2 本文的主要工作
• 第二章 基本概念和记号
• §2.1 基本定义及记号
• §2.2 一些基本控制集的概念
• 第三章 图的电力控制数
• §3.1 电力控制数的应用背景及基本概念
• §3.2 连通图的电力控制数
• §3.3 无爪立方图的电力控制数
• §3.4 平面图的电力控制数
• 第四章 图的函数控制数
• §4.1 控制函数的基本概念和应用背景
• §4.2 负边控制函数
• 第五章 图的2-距离控制数
• §5.1 2-距离控制数的基本概念
• 2（G）=「p／3」的连通图'>§5.2 γ₂（G）=「p／3」的连通图
• §5.2.1 预备定理
• 2（G）=「p／3」的连通图'>§5.2.2 γ₂（G）=「p／3」的连通图
• 第六章 图的控制集在特殊图上的算法
• §6.1 二部置换图的无圈控制集算法
• §6.1.1 基本概念和记号
• §6.1.2 二部置换图的无圈控制集算法
• §6.2 直线簇上区间图的最小连通控制集
• §6.2.1 基本概念和记号
• §6.2.2 直线簇上区间图的最小连通控制集
• 第七章 一个着色问题
• §7.1 着色问题的基本概念
• §7.2 具有最少可能边数的唯一k-可着色图
• 参考文献
• 作者攻读博士学位期间公开发表的论文
• 致谢
• 博硕士学位论文同意发表声明
• 发表意见书