您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

山东大学学报（理学版） ›› 2015, Vol. 50 ›› Issue (12): 130-136.doi: 10.6040/j.issn.1671-9352.0.2014.567

• 论文 • 上一篇    

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

尹杰杰   

  1. 海南大学信息科学技术学院应用数学系, 海南 海口 570228
  • 收稿日期:2014-12-22 修回日期:2015-11-18 出版日期:2015-12-20 发布日期:2015-12-23
  • 作者简介:尹杰杰(1990-),男,硕士研究生,研究方向为计算代数.E-mail:15120644019@163.com
  • 基金资助:
    国家自然科学基金资助项目(10971044)

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

YIN Jie-jie   

  1. Department of Applied Mathematics of Information and Technology College, Hainan University, Haikou 570228, Hainan, China
  • Received:2014-12-22 Revised:2015-11-18 Online:2015-12-20 Published:2015-12-23

PDF (PC)

1842

摘要： 对于具有n个顶点的简单连通图G,首先证明了求解G的所有支配集等价于求解一个多元多项式方程组的所有0-1解; 其次,对于任一正整数k<n, 证明了这一多项式方程组模型可改进为求解G中具有k个顶点的支配集(即k-支配集)的多项式方程组模型,并使用Grbner 基给出求解方法, 从而得到求G的极小支配集和支配数的一个可行途径。 通过实例验证了这一代数计算方法的有效性。

关键词: k-支配集, Grbner基, 支配数, 图, 极小支配集

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.

Key words: k-dominating set, Grbner basis, minimal dominating set, dominating number, Graph

中图分类号: 

  • O157. 5
[1] ADAMS W, LOUSTAUNAUS P. An introduction to Grbner bases[M]. Washington, D C: American Mathematical Society, 1994:118-276.
[2] Sk Md Abu Nayeem, PAL Madhumangal. Genetic algorithmic approach to find the maximum weight independent set of a graph[J]. Journal of Applied Mathematics and Computing, 2007, 25(1):217-219.
[3] 熊雪玮,赵志琴. 图的k-独立集与Grbner 基求解[J].工程数学学报,2012, 29(5):696-702. XIONG Xuewei, ZHAO Zhiqing. Solving the k-independent sets of graph by Grbner basis[J]. Chinese Journal Engineering Mathematics, 2012, 29(5):696-702.
[4] 熊雪玮.几个图论问题的多项式建模与Grbner 基求解[M]. 海口:海南大学出版社,2012. XIONG Xuewei. The polynomial modeling and Grbner basis solving of several problems in graph theory[M]. Haikou: Hainan University Press, 2012.
[5] MARGULIES S, HICKS I V. An algebraic exploration of dominating sets and Vizing's conjecture[J]. The Electronic Journal of Combinatorics, 2012, 19(2):1-30.
[6] MNUK M. Representing graph properties by polynomial ideals[M]. New York: Computer Algebra in Scientific Computing, 2001:431-444.
[7] BONDY J A, MURTY U S R. Graph theory [M]. Berlin: Springer, 2008: 78-156.
[8] 殷剑宏,吴开亚. 图论及其算法[M]. 合肥:中国科学技术大学出版社,2003:179-185. YIN Jianhong,WU Kaiya. Graph theory and algorithms[M]. Hefei:University of Science and Technology of China Press, 2003:179-185.
[1] 汤步洲,胡晗. 电力安全知识图谱构建技术与应用[J]. 《山东大学学报(理学版)》, 2026, 61(5): 18-26.
[2] 张鲁宁,王景升. 基于自适应残差动态融合图注意力网络的交通速度预测[J]. 《山东大学学报(理学版)》, 2026, 61(5): 90-101.
[3] 白月蓉,魏宗田,王德莉. 基于多火源燃烧连通度的网络抗毁性分析[J]. 《山东大学学报(理学版)》, 2026, 61(4): 102-108.
[4] 王智玄,庞继芳,王智强,宋鹏,李茹. 融合长短期兴趣的属性增强临时群组推荐算法[J]. 《山东大学学报(理学版)》, 2026, 61(3): 54-65.
[5] 杨滨,孙建楠,曹恩国,李子川,周志立. 基于显著性特征的海报设计侵权检测分析[J]. 《山东大学学报(理学版)》, 2026, 61(3): 11-19.
[6] 姚勋祥,刘培培,徐英城,范清兰,包芳勋,张云峰. 基于多重分形优化的图像超分辨率重建[J]. 《山东大学学报(理学版)》, 2026, 61(3): 96-110.
[7] 王军涛,黄强. 基于一般重叠函数的模糊数学形态学边缘检测方法[J]. 《山东大学学报(理学版)》, 2026, 61(1): 36-48.
[8] 仲尚,马丽,刘文哲,李雨豪. 融合多尺度注意力机制和改进特征融合的轻量化水面小目标检测模型[J]. 《山东大学学报(理学版)》, 2026, 61(1): 15-25.
[9] 王江,李敬文,高鑫,孙亮晶. 若干联图的邻点可约全标号[J]. 《山东大学学报(理学版)》, 2025, 60(8): 57-67.
[10] 王辉,刘蒙蒙. 三圈图的Mostar指标的下界[J]. 《山东大学学报(理学版)》, 2025, 60(8): 68-77.
[11] 武晓军,陈怡丹,郝耀军,宋长伟,何德清. 具有标签流形和动态图约束的多标签特征选择[J]. 《山东大学学报(理学版)》, 2025, 60(7): 69-83.
[12] 吴辛尧,徐计. 基于图互信息池化的分层图表示学习[J]. 《山东大学学报(理学版)》, 2025, 60(7): 84-93.
[13] 钱文彬,彭嘉豪,蔡星星. 基于邻域粒度与三支决策的知识表示学习方法[J]. 《山东大学学报(理学版)》, 2025, 60(7): 94-103.
[14] 任艳栏,谢云丽. 丛代数换位图具有非离开面性的G -系统证明[J]. 《山东大学学报(理学版)》, 2025, 60(5): 79-86.
[15] 梁娟,张晋珠,崔亮. 具有交叉扩散的植被模型的稀疏最优控制[J]. 《山东大学学报(理学版)》, 2025, 60(4): 29-39.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发