首页 | 本学科首页   官方微博 | 高级检索  
     检索      

一个查找二色Ramsey图中可能存在的自由边的算法
引用本文:斯勤夫,段禅伦.一个查找二色Ramsey图中可能存在的自由边的算法[J].内蒙古大学学报(自然科学版),2001,32(5):590-592.
作者姓名:斯勤夫  段禅伦
作者单位:1. 内蒙古财经学院计算机信息管理系
2. 内蒙古大学计算机学院
摘    要:Kn(s,t)定义为一个正整数n,同时存在一个由二色边构成简单完成图Kn,使得Kn中既不存在单色完全子图Ks和单色子完全子图Kt,在Ramsey图Kn(s,t)中一条自由边定义为,即使单独改变这条边的颜色,所得到的新图仍是一个二色Ramsey图Kn(s,t)。本基于作在献2]中给出的算法,提出一个新算法,该算法可以找出一个给定Ramsey图Kn(s,t)中的所有可能的自由边,并简要分析了其时间复杂性。对于一个已有的Ramsey图Kn(,s,t),利用该算法可能找出其他Ramsey图Kn(s,t)。

关 键 词:Ramsey数  二色Ramsey图  自由边  二色边  查找算法  简单完全图
文章编号:1000-1638(2001)05-0590-03
修稿时间:2001年6月11日

An Algorithm on Searching Possible Free Edges in a 2-coloring Ramsey Graph
SI Qin fu ,DUAN Chan lun.An Algorithm on Searching Possible Free Edges in a 2-coloring Ramsey Graph[J].Acta Scientiarum Naturalium Universitatis Neimongol,2001,32(5):590-592.
Authors:SI Qin fu  DUAN Chan lun
Institution:SI Qin fu 1,DUAN Chan lun 2
Abstract:
Keywords:Ramsey number  Ramsey graph  free edge
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号