10.3969/j.issn.1005-3085.2012.05.011
图的 k-独立集与 Gr¨obner 基求解?
本文给出一种求解任一具有 n 个顶点的有限图 G 的极大独立集和独立数的代数计算方法.该方法是通过将求解 G 的极大独立集问题加强为对每个1≤ k ≤ n 求解 G 的 k-独立集问题来给出的.首先证明了 G 中 k-独立集的存在性等价于一个多元多项式方程组的解的存在性,使得可以通过使用多项式理想的 Gr¨obner 来判断所得方程组解的存在性并进一步求解方程组.由于 k-独立集存在时只有有限多个,得到的 Gr¨obner 基构成的方程组是很容易求解的三角形方程组,G 的极大独立集和独立数在求解最多 n 个方程组即可得到.最后,通过实例验证了代数计算方法的有效性.
图、k-独立集、极大独立集、Gr¨obner 基
O157.5(代数、数论、组合理论)
2012-11-06(万方平台首次上网日期,不代表论文的发表时间)
共7页
696-702