您的位置:山东大学 -> 科技期刊社 -> 《山东大学学报(理学版)》

山东大学学报(理学版) ›› 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

摘要: 对于具有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]. 山东大学学报(理学版), 2018, 53(9): 1-11.
[2] 寇艳芳,陈祥恩,王治文. K1,3,p K1,4,p的点可区别的IE-全染色及一般全染色[J]. 山东大学学报(理学版), 2018, 53(8): 53-60.
[3] 刘小花,马海成. Q形图的匹配能序及Hosoya指标排序[J]. 山东大学学报(理学版), 2018, 53(8): 61-65.
[4] 刘华,叶勇,魏玉梅,杨鹏,马明,冶建华,马娅磊. 一类离散宿主-寄生物模型动态研究[J]. 山东大学学报(理学版), 2018, 53(7): 30-38.
[5] 高瑞梅,初颖. Weyl构形An-1Bn之间的构形的自由性[J]. 山东大学学报(理学版), 2018, 53(6): 70-75.
[6] 朱林. A4型箭图的可分单态射表示和RSS等价[J]. 山东大学学报(理学版), 2018, 53(2): 1-8.
[7] 李美莲,邓青英. 平图的transition多项式的Maple计算[J]. 山东大学学报(理学版), 2018, 53(10): 27-34.
[8] 房启明,张莉. 无4-圈和5-圈的平面图的k-frugal列表染色[J]. 山东大学学报(理学版), 2018, 53(10): 35-41.
[9] 孙泽锐,王继军,李国祥,夏国恩. 基于插值图像的可逆信息隐藏算法[J]. 山东大学学报(理学版), 2018, 53(1): 46-52.
[10] 齐平, 王福成, 王必晴. 一种基于图模型的可信云资源调度算法[J]. 山东大学学报(理学版), 2018, 53(1): 63-74.
[11] 王凯,洪宇,邱盈盈,王剑,姚建民,周国栋. 一种查询意图边界检测方法研究[J]. 山东大学学报(理学版), 2017, 52(9): 13-18.
[12] 王晓丽,王慧娟,刘彬. 最大度为7的平面图全染色[J]. 山东大学学报(理学版), 2017, 52(8): 100-106.
[13] 潘文华,徐常青. 一类稀疏图的邻和可区别边色数[J]. 山东大学学报(理学版), 2017, 52(8): 94-99.
[14] 王霞,张茜,李俊余,刘庆凤. 基于粗糙集的三元概念分析[J]. 山东大学学报(理学版), 2017, 52(7): 37-43.
[15] 张聪,裴家欢,黄锴宇,黄德根,殷章志. 基于语义图优化算法的中文微博观点摘要研究[J]. 山东大学学报(理学版), 2017, 52(7): 59-65.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!