一个实用的检验K_(n)(3,p)的算法  

A Practical Algorithm on Verifying K_(n)(3,p)

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

机构地区：[1]内蒙古财经学院计算中心,内蒙古呼和浩特010051 [2]内蒙古大学计算机学院,内蒙古呼和浩特010021

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

摘　　要：设 Kn是 n个顶点的完全图 .若对 Kn 的每条边着以红色或蓝色 ,并且图中既不包含红色团 K3也不包含蓝色团 Kp,这样就得到一个二色边图 Kn,同时将这种染色所得的图记为 Kn( 3,p) .把使 Kn( 3,p)成立的最大值记为 R( 3,p) ,R( 3,p) =r( 3,p) -1 ,r( 3,p)是 Ramsey数 .本文给出一个实用的算法 ,可以对给定连通图检验 Kn( 3,p)Let K n be the complete graph with order n. If two colors red and blue are assigned to the edges of K n, and there is neither clique K 3 whose edges are all red nor clique K p whose edges are all blue. so a 2 edge coloring graph K n has been obtained, such a 2 edge coloring graph is denoted K n(3,p). The maximum value of n for K n(3,p) is written as R(3,p), obviously R(3,p)=r(3,p)-1, where r(3,p) is the Ramsey numer. In our works, we give a practical algorithm to verifying K n(3,p) for a given connected graph.

关 键 词：独立集 极大独立集 最大独立集 RAMSEY数 

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