随机图的哈密尔顿回路实验研究

作     者：梅俊杰 刘蕻 许欢 王以松 MEI Jun-jie;LIU Hong;XU Huan;WANG Yi-song

作者机构：贵州大学计算机科学与信息学院贵州贵阳550025 

基　　金：国家自然科学基金带函数的回答集程序设计研究与实现(60963009) 

出 版 物：《贵州大学学报（自然科学版）》 (Journal of Guizhou University:Natural Sciences)

年 卷 期：2013年第30卷第3期

页      码：77-81页

摘      要：哈密尔顿回路问题是图论的经典NP-难解问题之一,在计算机科学中被广泛用作测试用例以测试算法/系统的有效性,包括可满足性(SAT)、回答集程序设计(ASP)以及约束可满足问题(CSP)等。在本文中,我们通过ASP实验研究了40到100个节点(步长为10)随机图的哈密尔顿回路存在性、不存在性、以及难于计算等的分布情况,结果表明它们都具有一定的规律。这不仅对随机图的哈密尔顿回路本身是有益的探索,也为生成随机图哈密尔顿测试用例提供了有益的指导。

主 题 词：哈密尔顿回路 随机图 回答集程序设计 

学科分类：081203[081203] 08[工学] 0835[0835] 0812[工学-测绘类] 

D　O　I：10.3969/j.issn.1000-5269.2013.03.018

馆 藏 号：203719654...