关于Ramsey图:一个递归型查找图中所有给定元素个数独立集的算法  

On Ramsey Graph: A Recursive Algorithm on Finding all Independent Sets with Given Size

作　　者：斯勤夫[1] 段禅伦[2] 许文昌[1] 

机构地区：[1]内蒙古财经学院计算机信息管理系,内蒙古呼和浩特010051 [2]内蒙古大学计算机学院,内蒙古呼和浩特010021

出　　处：《内蒙古大学学报（自然科学版）》2002年第6期702-702,共1页Journal of Inner Mongolia University：Natural Science Edition

基　　金：内蒙古自然科学基金资助项目 ( 2 0 0 1 0 90 1 -0 2 )

摘　　要：改进了作者在文献〔1〕中给出的算法 ,给出一个速度较快的新算法 ,对一个可能的 ( s,t,n) -Ramsey图 ,该算法可以找出其中所有给定元素个数的独立集 ,进而可以检验该图是否是一个 ( s,t,n) -Ramsey图 .For a simple undirected graph, a recursive algorithm on finding independent set with given size is presented in this paper based on our previous works. When a (s,t,n) graph is a candidate Ramsey graph of s clique free and t independent free, our algorithm is fast on verifying whether the graph is a (s,t,n) graph or not.

关 键 词：RAMSEY图 递归型查找图 给定元素 独立集 (s t n)-图 (s t n)-Ramsey图 图论 

分 类 号：O175.5[理学—数学]