图的连通支配集构造算法研究

连通支配集是图的支配理论中一个比较新的领域，关于图的连通支配集的构造算法研究在无线网络应用技术中有着广泛的应用。确定一个图的最小连通支配集是NPC问题，即使是对结构相对简单、有相应构造规则的图，其构造问题也十分复杂。本项目研究广义Petersen图等图类的连通支配集的构造问题。通过理论分析和计算所研究的图类的最小连通支配集上下界；然后利用计算机构造和搜索，将所研究的图类分成几个子类来分别考虑。重点研究满足最小支配集下界的子类，利用这类图的全局性质和局部性质，将其连通支配集划分为规则结构模式与非规则结构模式，建立相应的模式库。在此基础上，研究不同参数下规则结构模式的构成规律，探讨不同参数下的非规则结构模式是否存在统一的形式。通过研究规则结构模式和非规则结构模式的组合性质给出所研究图类的连通支配集构造算法。本项目研究提供了构造图的连通支配集的一个新思路，为无线网络技术提供理论和应用基础。

图的连通支配集及其构造算法的设计问题是近年来的图论领域和无线网络技术研究热点之一。图的连通支配集因其结构上的特点使得其在无线网络骨干网设计和路由算法设计中有着广泛的应用价值。本项目主要研究规则图的最小连通支配集构造问题，其中主要包括广义Petersen图、循环图及相关的正则图类。同时研究一般网络结构下的连通支配集构造算法问题，包括复杂网络结构下的连通支配集构造和其他相关问题。项目执行期间，我们取得了一些成果：. （1）在k=3,5,7条件下，n为奇数的广义Petersen图P(n,k)的最小连通支配集结构，在顶点数充分大的条件下，具有类似的循环结构。我们猜测对任意k，这个结论都是正确的。如果这个结论成立的话，我们对任意的n，k为奇数的广义Petersen图P(n,k)的最小连通支配集结构可以给出一个统一的构造方式。. （2）通过研究四正则循环图的最小连通支配集结构，我们得到当k=2,3,4时，四正则循环图Cn(1,k)的最小连通支配集结构。利用类似的方法研究了四正则循环图的最小连通支配数的上下界，可以得到当k充分大时，四正则循环图的最小连通支配集的大小近似于顶点数的1/3。. （3）给出了两类Snark图--Goldberg图和花图的最小连通支配集结构。这两类图都是三正则图，其最小支配集结构表现出的性质和广义Petersen图有类似之处，这为我们研究一般三正则图的最小连通支配集提供了有利的参考。. （4）我们也研究了和连通支配集相关的受限支配集问题，尤其是图的[1,2]-支配集问题。我们给出了广义Petersen图的最小[1,2]-支配数的界，设计了构造树的最小[1,2]-支配集的近似算法，给出了连通[1,2]-支配集的概念，并研究了它和连通支配集、[1,2]-支配集的关系。. （5）鉴于真实网络往往是介于规则图和随机图之间的复杂网络，我们对复杂网络的相关问题也做了大量研究，对节点重要性、链路预测等问题给出了一些结论。在对复杂网络研究过程中，我们发现网络的社团结构对其连通支配集的构造有一定的作用，我们设计了基于社团结构的网络连通支配集构造算法，现在正在进行模拟数据实验和真实网络数据实验验证过程中。