图的最小半全控制集

摘要

图的控制问题是图论的一个重要研究领域.为了解决计算机网络以及物流仓储等实际应用中出现的问题，衍生了出不同的控制集.本文主要研究图的半全控制数.它是介于控制数与全控制数之间的重要控制参数.
　　在笛卡尔乘积图中，各种控制问题的研究一直很活跃.我们通过分块法给出了圆柱格子图Pk□cn(2≤k≤5)的半全控制数；通过证明性质和数学归纳法给出了完全格子图Pk□Pn(2　　另外，我们研究了毛虫树和蜘蛛树的最小半全控制集问题.设计了毛虫树的半全控制数的算法，并且给出了蜘蛛树的半全控制数.其中讨论的蜘蛛树有：病态的蜘蛛树，健全的蜘蛛树，κ-扩展星形树等.
　　随着计算机网络的发展，单位圆盘图在很多领域都有应用.它为广播网，无线传感网络以及计算几何学中的一些问题提供了图论模型.最后，对单位圆盘图的最小半全控制集问题，我们设计了一个基于极大独立集的5-近似算法和一个基于2-分离集簇的PTAS算法.

目录

第一个书签之前