公开(公告)号：CN107832471A

公开(公告)日：2018-03-23

申请号：CN201711232637.3

申请日：2017-11-30

申请人： 河南科技大学

发明人： 闫永义 ,  岳菊梅 ,  范波 ,  马建伟 ,  付主木 ,  李晓强 ,  刘磊波 ,  宋晓娜 ,  刘剑锋

IPC分类号： G06F17/30

CPC分类号： G06F17/30958

摘要： 搜寻并获取图的所有独立集的方法，对图中的任意顶点赋予一个特征向量，再利用半张量积方法将所有的特征向量转化为与对应顶点子集相对应的向量。该方法包括以下五个步骤：1）根据目标图直接写出其邻接矩阵；2）计算图的独立集矩阵；3）判断独立集矩阵是否包含“所有元素都等于0的列”，如果否，则算法结束，该图无独立集；如果是，构造决策集合；4）对于决策集合中的每一个元素，通过求解一组线性方程就可以求得一个独立集；5）循环执行上述步骤4，直到每个元素都执行一遍。本发明克服了现有基于计算机编程的算法所存在的不足，能够搜索出任意图的所有独立集，有很好的理论和工程应用前景。