%0 Journal Article
%T 图的k-支配集与Grbner基求解<br>Solving the algebraic model of k-dominating sets of graph by Grbner basis
%A 尹杰杰
%J 山东大学学报（理学版）
%D 2015
%R 10.6040/j.issn.1671-9352.0.2014.567
%X 摘要： 对于具有n个顶点的简单连通图G,首先证明了求解G的所有支配集等价于求解一个多元多项式方程组的所有0-1解; 其次,对于任一正整数k<n, 证明了这一多项式方程组模型可改进为求解G中具有k个顶点的支配集(即k-支配集)的多项式方程组模型,并使用Grbner 基给出求解方法, 从而得到求G的极小支配集和支配数的一个可行途径。 通过实例验证了这一代数计算方法的有效性。<br>Abstract: 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 Grbner 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 &lt
%K em&gt
%K k&lt
%K /em&gt
%K -支配集
%K Grbner基
%K 支配数
%K 图
%K 极小支配集
%K &lt
%K br&gt
%K &lt
%K em&gt
%K k-&lt
%K /em&gt
%K dominating set
%K Grbner basis
%K minimal dominating set
%K dominating number
%K Graph
%U http://lxbwk.njournal.sdu.edu.cn/CN/10.6040/j.issn.1671-9352.0.2014.567