求最大完全子图的启发式着色算法.pdfVIP

　第 12 卷 第 2 期 滁 州 学 院 学 报 Vol . 12 N o . 2 　 　20 10 年 4 月 J OU RNAL O F CHU ZHOU UN IV ERSI T Y Ap r . 20 10 　 求最大完全子图的启发式着色算法 李建新1 ,2 ( 1. 宿州学院 计算机科学与技术系 ,人工智能与数据挖掘研究室 , 安徽 宿州 234000 ; 2 . 合肥工业大学 计算机与信息学院 , 安徽 合肥 230009) 摘 　要 :本文提出了一种求最大完全子图的启发式着色算法. 该算法通过为顶点着色将已知无向图划分为极大 完全子图的并集 ,再根据各极大完全子图中顶点的多少选取最大完全子图. 随后为提高算法执行效率 ,又对该 算法提出了一种精简措施. 最后将该算法运用于一集成电路测试数据编码压缩实验中 ,证明了该算法对求解最 大完全子图的有效性. 关键词 :最大完全子图;极大完全子图;启发式算法 ;着色算法 中图分类号 : O 157 . 6 　　　文献标识码 :A 　　　文章编号 (20 10) 0 　引言 位 ,相容压缩是将测试集中相容的测试向量合并为一个向 ( ) 最大完全子图 maximum complet ed sub - grap h 问题 量. 为追求最大压缩率 ,需寻求测试集中的极大相容类 ,这 是图论中的一个经典组合优化问题 ,也是一类 N P 完全问 个问题可映射为图论中的极大完全子图问题 ,并且可通过 题 ,对它的研究具有很大的理论和实用价值 ,该问题在实 为顶点着色分类的方法划分各个极大相容类 ,进一步研究 ( 践中被广泛应用于市场分析 、方案选择 、管理决策 、故障诊 可将该方法演化为求极大完全子图 great complet ed sub - 断、数据压缩等不同领域. 目前国内外对最大完全子图问 grap h) 的一般算法 , 进而也就得到了求最大完全子 图的 ( 题的求解有广泛的研究 ,大致可分为确定性算法 exact al 算法. ) [ 1] ( ) [2 - 6 ] 2 　相关概念 gorit hm 和启发式 heuri stic algorit hm 算法两大 类. 确定性算法在求解顶点数相对较少 、密度相对较低的 [7 ] ( ) ( 定义 1 通常把二元序组 V , E , 称为图. 记为 : G 图时尚为有效 , 随着研究的深入 ,遇到的问题复杂度越来 ) ( ) ( )