关于Hamilton Path

来源: 于 2010-04-14 02:32:48 [博客] [旧帖] [给我悄悄话] 本文已被阅读：次

1. 这道题真的是Hamilton Path的问题吗？，不是首尾相连呀。 有可能更难，有可能更容易。把从1到N的自然数，组成N位数，要相邻的两个数不互质，可以组成多少个数？

2. P与ＮＰ的问题是指计算量，是计算的问题，不用编程算就不可能用理论验证吗？

３.　有没有特殊性质的问题，Hamilton Path不是ＮＰ－complete的