图的支配问题是近年来图论中一个比较活跃的研究领域。图的支配数问题是其中一类重要问题,它在网络设计中有许多实际应用。比如在一个通讯网络的一些节点上放置发射器,要求每个发射器的节点一定和某个发射器的节点有一个直接的通讯线路。如何选择节点,使得放置的发射器的数目最小,这就是一个支配数问题。计算图的支配数问题属于Np-完全问题,因此至今只有少数图的支配数被找到并证明。本文利用计算图的支配数算法计算出n比较小的时候广义Petersen图P（n,2）和循环图C（n;{1,4}）的支配数,并构造出n比较小的时候这两类图的支配集,从中找出规律,推出任意n情况下的支配集,从而确定出广义Petersen图p（n,2）和循环图C（n;{1,4}）的支配数上界。同时通过计算机计算得的结果,本文给出了广义Petersen图P（n,2）和循环图C（n;{1,4}）的支配数的定理。为了证明所给出的定理,本文引入了重复支配数的概念,将证明最小支配数转化为证明重复支配数的问题。通过一系列的引理证明,最终成功证明出了广义Petersen图P（n,2）的支配数为循环图C（n;{1,4}）的支配数为其中
本文来源: https://www.lw50.cn/article/8ce38d47f7db1d92d0f672df.html