树图上k-控制问题和块图上2-控制问题的算法研究

摘要

在过去的三十多年里,随着计算机科学的迅速发展,图论也得到了飞速发展,而图论中发展最快的领域也许就是控制数理论的研究.控制数理论能够快速发展的主要原因是它在现实世界中,例如编码理论,计算机科学,通信网络,监视系统和社会网络等理论与实践中有着广泛而深刻的应用背景.对于一个正整数k,k-控制问题就是寻找满足下列条件拥有最小点数的集合D:即不在集合D中的任意点,至少需要被点集D中k个点所控制,G中所有满足该条件的集合的最小势叫做无向图G的k-控制数.
　　对于图G=（V,E）,每个点带有二维标号M（v）=（t（v）,k（v））,其中k（v）的取值范围是k（v）∈{0,1,2…,k},t（v）∈{B,R}.这种标号定义下的k-混合控制问题就是要找到一个包含所有t（v）=R的集合D使得所有不在D中的点至少被D中k（v）个点所控制.
　　换句话说,图G=（V,E）的一个k-混合控制集D就是点集V中满足下列两个条件的子集:（MD1）如果t（v）=R,那么v∈D（MD2）对于所有不在D中的点v,|NG（v）∩D|≥k（v）所有k-混合控制集的最小势是该图的k-混合控制数,记作rkM（G）.具有最小k-混合控制数的集合称为该图的最小k-混合控制集.在图的控制数理论研究中,算法研究是一个十分活跃的研究方向,其中一项重要工作是在特殊图类上寻找控制数及其相关参数的有效算法,树图和块图是两类著名的特殊图类,它形成弦图和完美图的子类,它们在解决很多现实问题中有重要作用,由于树图和块图具有良好的结构性质,因此许多N P-完全的控制数及其相关参数问题限制在树图和块图上都是多项式时间可解的.
　　本文我们主要研究了两类控制参数（k-控制和k-混合控制）的算法问题,以下是本文的主要结果:（1）本文给出计算树图上最小k-混合控制数的线性时间算法,并证明了算法的正确性.同时该算法可被推广用于找出树上最小k-控制集.（2）本文给出计算块图上最小2-混合控制数的线性时间算法,并证明了算法的正确性.同时该算法可被推广用于找出块图上最小2-控制集.（3）本文证明在二部图以及分裂图上k-控制数问题是N P-完全的.

目录

摘要

ABSTRACT

第一章 概述

§1.1 引言

§1.2 定义和概念

第二章 各类控制数问题算法的研究

§2.1 控制数的标号算法

§2.2 控制数的动态规划算法

§2.3 控制数的原始-对偶算法

第三章 k-控制集的NP-完全性质

第四章 树上k-混合控制数的算法

第五章 块图上2-混合控制数的算法

参考文献

致谢