确定Ramsey数下界值的随机算法

摘要

文[1—2]借助于计算机得到了几个Ramsey数的下界值,但由于计算机确定Ramsey数的下界值往往需要判断多达指数级的各种情况,因此所需的计算时间常使人难以接受.本文提出了一种确定Ramsey数r(k,l)下界值的随机算法,该算法试图随机而有针对性地构造一个有n个顶点的简单图G,使G中既无k个顶点的团又无l个顶点的独立集。