论文部分内容阅读
设G是一个无向简单图。G的一个独立集是由一些互不相邻的顶点构成的集合。G的控制集是G的一个顶点子集S使得V(G)S中的任意顶点都与S中的某一顶点相邻。图的（独立）控制集问题是图论研究的基本问题之一，可追溯到经典的“皇后问题”。此外，该问题也因具有较广泛的应用背景而受研究者的关注，例如计算机网络、人工智能等。研究图的（独立）控制集主要集中在两个基本问题:1.确定顶点数最少的（独立）控制集;2.（独立）控制集的计数问题。 本文主要内容: 1.通过改进“计算网格独立控制数的动态规划算法”，计算圆柱网格Cm，Pn和莫比乌斯网格Mm,n的独立控制数并给出相应的一个独立控制集; 2.确定了i（Cm，Pn）;当n=2或m=1，2，n≥1时，确定了i(Mm，n);当m＞2时，给出了i(Mm，2n)的递归不等式;其中i(G)表示图G的独立控制数; 3.研究两类仙人掌链(Cactus Chain)的独立控制集计数问题:确定了三角形链(3-Uniform Chain)的独立控制集的个数;确定了四边形平行链(4-UniformPara-Chain)和正交链(Ortho-Chain)独立控制集的个数并进而证明:平行链和正交链分别为四边形链中独立控制集的个数最少和最多的。