山东大学学报（理学版） ›› 2015, Vol. 50 ›› Issue (12): 130-136.doi: 10.6040/j.issn.1671-9352.0.2014.567
• 论文 • 上一篇
尹杰杰
YIN Jie-jie
摘要： 对于具有n个顶点的简单连通图G,首先证明了求解G的所有支配集等价于求解一个多元多项式方程组的所有0-1解; 其次,对于任一正整数k<n, 证明了这一多项式方程组模型可改进为求解G中具有k个顶点的支配集(即k-支配集)的多项式方程组模型,并使用Grbner 基给出求解方法, 从而得到求G的极小支配集和支配数的一个可行途径。 通过实例验证了这一代数计算方法的有效性。
中图分类号:
| [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-1和Bn之间的构形的自由性[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. |
|
||
