文献类型：期刊文章

作　　者：熊雪玮[1] 赵志琴[2]

机构地区：[1]海南大学信息科学技术学院应用数学系,海口570228 [2]中山大学新华学院经济与贸易系,广州510520

出　　处：《工程数学学报》

基　　金：国家自然科学基金(10971044)~~

年　　份：2012

卷　　号：29

期　　号：5

起止页码：696-702

语　　种：中文

收录情况：AJ、BDHX、BDHX2011、CSCD、CSCD2011_2012、JST、MR、RCCSE、SCOPUS、ZGKJHX、ZMATH、核心刊

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

关 键 词：图  k-独立集  极大独立集 Grbner基  

分 类 号：O157.5[数学类]