顶点序下图的支配集算法

摘要：

文中将粗糙集理论中的属性序引入到图论中,研究顶点序下图的支配集问题.首先,在图的顶点集上定义一个全序关系,称为顶点序.然后,利用顶点序定义一个二元等价关系,得到图中所有顶点闭邻接集的一个划分.最后,基于该划分设计了一种顶点序下图的极小支配集算法.同时,证明了该算法在给定顶点序下求解极小支配集的完备性和唯一性,并通过实例分析验证了所提算法的正确性和有效性.

关键词：支配集、顶点序、算法完备性、算法唯一性

所属期刊栏目：47

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金项目;重庆市科委项目

在线出版日期：2020-12-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：444-448