论文部分内容阅读
本文给出一种求解任一具有礼个顶点的有限图G的极大独立集和独立数的代数计算方法．该方法是通过将求解G的极大独立集问题加强为对每个1≤k≤n求解G的k一独立集问题来给出的．首先证明了G中k-独立集的存在性等价于一个多元多项式方程组的解的存在性，使得可以通过使用多项式理想的GrSbner来判断所得方程组解的存在性并进一步求解方程组．由于k-独立集存在时只有有限多个，得到的GrSbner基构成的方程组是很容易求解的三角形方程组，G的极大独立集和独立数在求解最多n个方程组即可得到．最后，通过实例验证了代数计算方法的