基于Q0-1规划模型用分枝定界法求解最大团问题

详细信息   全文下载|推荐本文 |

• 出版年：2008
• 作者：续晓欣；贾晓峰
• 单位1：中北大学应用数学系
• 出生年：1980
• 学历：硕士
• 职称：助教
• 语种：中文
• 作者关键词：最大团；Q0-1规划；分枝定界法；梯度
• 起始页：636
• 总页数：4
• 刊名：太原理工大学学报
• 是否内版：否
• 刊频：双月刊
• 创刊时间：1957
• 主管单位：山西省教育厅
• 主办单位：太原理工大学
• 主编：谢克昌
• 地址：太原市迎泽西大街新矿院路18号
• 邮编：030024
• 电子信箱：xuebao@tyut.edu.cn
• 网址：Http://www.xuebao.tyut.edu.cn
• 卷：39
• 期：6
• 期刊索取号：P806.6 132
• 数据库收录：《万方数据库——数字化期刊群》全文上网期刊；《中国核心期刊（遴选）数据库》收录期刊；中国科技论文统计源期刊中国科技核心期刊；中国学术期刊综合评价数据库(CAJCED)统计源期刊；中国期刊全文数据库(CJFD)全文收录期刊；《中文核心期刊要目总览》入编期刊；《中国数学文摘》数据源期刊；《中国物理文摘》数据源期刊；《中国无机分析化学文摘》数据源期刊；《中文科技期刊数据库》数据源期刊；《中国矿业文摘》数据库数据源期刊，矿业类核心期刊；美国化学文摘光盘版收录期刊；中国科学引文索引数据库数据源期刊；《中国知识资源总
• 核心期刊：《中国核心期刊（遴选）数据库》收录期刊；中国科技论文统计源期刊中国科技核心期刊；《中国矿业文摘》数据库数据源期刊，矿业类核心期刊

摘要

搜索图的最大团是经典的NP-难题。通过运用二次0-1规划模型（简称Q0-1规划模型）寻得最大团问题的解法，所用的分枝定界法建立在此模型之上。通过一个命题推导出图的最大团求解问题与一类特殊Q0-1规划的等价性，借助于求解一般Q0-1规划的分枝定界法推演出求最大团问题的分枝定界规则，从而将图论中的经典问题转化成代数问题加以解决，并给出实例说明该算法的有效性。