图的k-支配集与Grobner基求解  

Solving the algebraic model of k-dominating sets of graph by Grobner basis

作　　者：尹杰杰[1] 

机构地区：[1]海南大学信息科学技术学院应用数学系,海南海口570228

出　　处：《山东大学学报（理学版）》2015年第12期130-136,共7页Journal of Shandong University(Natural Science)

基　　金：国家自然科学基金资助项目(10971044)

摘　　要：对于具有n个顶点的简单连通图G,首先证明了求解G的所有支配集等价于求解一个多元多项式方程组的所有0-1解;其次,对于任一正整数k<n,证明了这一多项式方程组模型可改进为求解G中具有k个顶点的支配集(即k-支配集)的多项式方程组模型,并使用Gr¨obner基给出求解方法,从而得到求G的极小支配集和支配数的一个可行途径。通过实例验证了这一代数计算方法的有效性。Let G be a simple connected graph of n vertices. It is shown that finding all dominating sets of G is equivalent to finding all 0-1 solutions of a system of multivariate polynomial equations; furthermore,it is shown that this polynomial equation model can be modified to give a polynomial equation model for finding dominating sets of k vertices（ i. e. k-dominating sets） of G,and that such a model can be solved by using the Grbner basis method. Consequently,a feasible way of finding minimal dominating sets and the dominating number of G is obtained. The numerical example is presented to illustrate the effectiveness of this algebraic computational method.

关 键 词：图 k-支配集 极小支配集 支配数 GROBNER基 

分 类 号：O157.5[理学—数学]