|
|||||
|
|
| 图的k-独立集与Grbner基求解 | |
| 作者姓名： | 熊雪玮 赵志琴 |
| 作者单位： | 海南大学信息科学技术学院应用数学系;中山大学新华学院经济与贸易系 |
| 基金项目： | 国家自然科学基金(10971044)~~ |
| 摘 要： | 本文给出一种求解任一具有n个顶点的有限图G的极大独立集和独立数的代数计算方法.该方法是通过将求解G的极大独立集问题加强为对每个1≤k≤n求解G的k-独立集问题来给出的.首先证明了G中k-独立集的存在性等价于一个多元多项式方程组的解的存在性,使得可以通过使用多项式理想的Grbner来判断所得方程组解的存在性并进一步求解方程组.由于k-独立集存在时只有有限多个,得到的Grbner基构成的方程组是很容易求解的三角形方程组,G的极大独立集和独立数在求解最多n个方程组即可得到.最后,通过实例验证了代数计算方法的有效性. |
| 关 键 词： | 图 k-独立集 极大独立集 Grbner基 |
| 本文献已被 CNKI 等数据库收录！ | |