甘肃科技
甘肅科技
감숙과기
GANSU SCIENCE AND TECHNOLOGY
2014年
19期
14-18
,共5页
极大团问题%图着色%极大独立集
極大糰問題%圖著色%極大獨立集
겁대단문제%도착색%겁대독립집
极大团问题是图论中一个经典的组合优化问题,也是一类NP完全问题,在国际上已有广泛的研究.作者在对其他现有极大团求解算法进行研究之后,设计了一种基于图着色思想的极大团求解算法.基本思想是通过不同的方式对随机图的相应补图进行顶点着色,寻找出所有顶点的极大独立集.而后返回到原图之中找出极大团,并且通过比较删减寻找到随机图的所有极大团.
極大糰問題是圖論中一箇經典的組閤優化問題,也是一類NP完全問題,在國際上已有廣汎的研究.作者在對其他現有極大糰求解算法進行研究之後,設計瞭一種基于圖著色思想的極大糰求解算法.基本思想是通過不同的方式對隨機圖的相應補圖進行頂點著色,尋找齣所有頂點的極大獨立集.而後返迴到原圖之中找齣極大糰,併且通過比較刪減尋找到隨機圖的所有極大糰.
겁대단문제시도론중일개경전적조합우화문제,야시일류NP완전문제,재국제상이유엄범적연구.작자재대기타현유겁대단구해산법진행연구지후,설계료일충기우도착색사상적겁대단구해산법.기본사상시통과불동적방식대수궤도적상응보도진행정점착색,심조출소유정점적겁대독립집.이후반회도원도지중조출겁대단,병차통과비교산감심조도수궤도적소유겁대단.
