图的 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