基于分辨函数的极大团搜索算法  

Discernibility Function-based Algorithm for Finding All Maximal Cliques

作　　者：黄治国[1] 李娜[2] 

机构地区：[1]河南工程学院软件学院,郑州451191 [2]中南民族大学计算机科学学院,武汉430074

出　　处：《计算机科学》2014年第4期248-251,共4页Computer Science

基　　金：国家自然科学基金项目(61300127);河南工程学院博士基金项目(D2013003)资助

摘　　要：寻找极大团是几何图论极为重要的基础研究问题之一。将分辨函数模型与极大团性质结合,定义了顶点的极大团分辨函数、顶点关于某顶点子集的布尔映射函数,得到了一些与极大团相关的重要性质与定理,证明了图的极大团搜索问题可快捷自然地转换为相对简单的分辨函数表达式约束,为设计极大团搜索算法提供了一种有效的理论依据与求解途径。进而引入约简树构造方法设计了基于分辨函数的极大团搜索算法,最后通过给定无向连通图实例说明了算法的可行性与有效性。Finding maximal clique of a graph is a fundamental problem in graph theory.By combining discernibility function with maximal clique,the discernibility function of maximal clique over the vertex and the Boolean mapping function of the vertex with respect to any vertex set were defined,and some characteristics and theorems relative to maximal clique were obtained,then a fact was proved that the problem of finding all maximal cliques in a graph can be naturally expressed as relatively simple constraints of discernibility function expression.Furthermore,discernibility function-based algorithm was designed for finding all maximal cliques in a graph by introducing the method of reduction tree constructing.The theoretical derivation and simulation instance show that this algorithm is feasible and effective in practice.

关 键 词：图论 极大团 分辨函数 约简树构造 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]