哈密顿图,一直是NP完全问题的最优试金石（下面二十几本世界名著佐证这句话或参考邀请海南琼州大学给他的当年毕业博士就有已担任国务院副秘书长等几个部长级领导做报告的宁大师在这页倒数第2、3段所说）：

1、海南琼州大学的导师柳柏濂教授去合作几年的威斯康星大学的博士Michael R. Garey（其第1篇于1972年发于贝尔实验室杂志-至2000年的单位仍贝尔实验室-曾是世界第一的贝尔实验室领导层的除主席外最重要的Treasurer），与David S. Johnson 1979年的英文版在1987年由北京大学3个前辈翻译出版为603页的中文版的《Computers and Intractability: A Guide to the Theory of NP-Completeness计算机和难解性:NP 完全性理论导引》一书并它的被引仅这里就8万次，是最具影响的集大成著作如此中英文版我都有来多次读反复读(李国杰的第4-5段说它,最近的3详解).

这书最先的1.1和1.2节只说巡回售货员问题（即权最小哈密顿圈问题），其后正式说“NP完全问题”的1.5节说 “An outline of the book”之前说The foundations for the theory of NP-completeness were laid in a paper of Stephen A. Cook, presented in 1971, entitled "The complexity of theorem proving procedures" (Cook, 1971). Cook suggested that other problems in NP might share with the satisfiability problems this property of being the "hardest" member of NP. Subsequently, Richard Karp presented a collention of results(Karp, 1972) proving that indeed the decision problem versions of many well-known combinatorial problems, including the treveling salesman problem（旅行商问题）, are just as "hard" as the satisfiability problems. Since then a wide variety of other problems have been proved equivalent in difficulty to these problems, and this equivalence class, consisting of the "hardest" problems in NP；还有开始讲NP类的2.3节以旅行商问题开头并一直多次讲（旅行商是权最小哈密顿圈，只唯一说它可见哈密顿圈是NP完全问题的最优试金石；就如这里第1节只唯一说最具NP代表性的旅行商）。下面见作者说这书是为计算机科学和组合数学研究生写的教科书。并最先讲哈密顿图--足见哈密顿图是P=?NP的最优试金石。

2-1、《自动机理论、语言和计算导论》1979年第2版，作者John E. Hopcroft，Jeffrey D. Ullman（这2个作者都已获得计算机诺贝尔奖图灵奖），第十三章“难解性问题”， 13.1节的第一段说“确定的多项式时间内能识别的语言，构成一个重要的类，记作P”。显然好理解，这段没有举例； 13.1节的第二段说“有一些重要问题，看来似乎不在P中，却有有效的非确定算法，我们用NP来表示它。哈密顿圈问题是一个例子，该问题是：在一个图中是否存在一个哈密顿圈？看来不象是有一个确定的多项式时间算法，它能识别具有哈密顿圈的图。然而，却有一个非确定算法，猜测在圈的边，然后验证它们是否真的构成一个哈密顿圈； 13.1节的第三段说“P和NP的区别类似于下述区别，即有效地寻找一个命题（诸如“这个图有一个哈密顿圈”等）的证明和有效地验证一个证明（亦即检查一个具体圈是否哈密顿圈）之间的区别”。第一个例子就讲哈密顿图--足见哈密顿图是P=?NP的最优试金石。

2-2、《自动机理论、语言和计算导论》第3版（这版除第2版的2诺奖得主作者John E.Hopcroft，Jeffrey D.Ullman外，第3版再加入曾是世界第一企业Google的两个老板Larry Page和Sergey Brin的顾问Rajeev Motwani-也是他俩的博士导师），第十章“难解问题”，10.1节“P类和NP类”，10.1.1“可在多项式时间内解答的问题”-即P类问题，10.1.2“例子：克鲁斯卡算法”-P类问题的典型算法，10.1.3“非确定多项式时间”-它对应NP类，10.1.4“例子：货郎问题”-货郎问题就是哈密顿图问题的子问题。第一个例子就讲哈密顿图--足见哈密顿图是P=?NP的最优试金石。（10.1.5“多项式时间归约”，10.1.6“NP完全问题”的定理10.5“若某个NP完全问题属于P，则P=NP”等都是很基本的概念和定理）。

3-1、高度评价海南琼州大学是世界一流水平的我国哈密顿图第一个开拓者刘振宏大师翻译1988年出版的唯一和多年来一直是世界首富的比尔·盖茨合作科学论文的美国三院院士Christos H. Papadimitriou的世界名著《组合最优化：算法和复杂性》的第十五章“NP-完备问题”15.1“引言”，15.2“一个最优化问题的三种提法”的例 15.1 “n个城市的货郎问题…”（注：巡回售货员、旅行推销员、旅行商、货郎问题都是权最小哈密顿图，而例 15.1表明是这章的第一个例子，足见哈密顿图是P=?NP的最优试金石）；

还有第十六章“再论NP-完备问题”，16.1节依次讲5个主题：哈密顿圈、哈密顿圈的余、货郎问题的余、连通性的余、线性不等式组。

3-2、这里国务院副总理方毅在人民大会堂会见美国加利福尼亚大学圣地亚哥分校计算机科学系主任胡德强教授（数学大师项武忠院士和夫人只是陪衬，胡德强英文名是Te Chiang Hu确是加利福尼亚大学圣地亚哥分校教授）独撰1982年出版的世界名著《Combinatorial algorithms组合算法》第8章“NP-Complete problems”的前3节没有说到任何NP类，§8.4标题就是这章的标题“NP-Complete problems”并开头第1句起就说“The Hamiltonian circuit problem哈密顿圈问题asks if there is …”第2句是“The traveling salesman problem旅行商问题aska if there is …”如此第3句是“An algorithm for the traveling salesman problem can be used for solving the Hamiltonian circuit problem, since we can transform the Hamiltonian circuit problem to the traveling salesman problem as follows.…”；

3-3、华中科技大学学术委员会副主席也是居于高度评价海南琼州大学是国际一流的林诒勋教授之后的这页最后段的中国排序学会副会长陈荣秋教授独撰1987年出版的《排序的理论与方法》的第五章“关于计算复杂性”说“Dantzig等人曾把旅行推销员问题转化为具有负边长的最短路问题”-旅行推销员问题是权最小哈密顿圈问题-排序问题有许多NP问题可仍需要哈密顿图主导；

4、《计算理论基础》1981年第1版，2个作者是哈佛学院院长Harry R. Lewis，唯一和比尔·盖茨合作科学论文的美国三院院士Christos H. Papadimitriou，第6章“计算复杂性”，6.1节“P类”，6.2节“若干问题”，6.2.1“Euler图和哈密顿图”，这节说“不难看出Euler图属于P类”，而对于哈密顿图，这节做了很多陈述之后，最后说“不幸的是做了所有简单的改进和加速之后，它仍不是多项式的”。6.4节“NP类”，这节第三段说“上一节我们见过一批似乎不属于P类的问题，哈密顿图、旅行商问题等”，旅行商问题也是哈密顿图问题的子问题。可见第一个例子就讲哈密顿图--足见哈密顿图是P=?NP的最优试金石。

5-1、这里第2段说：撰写“数据结构”圣经的海南琼州大学的导师柳柏濂教授去合作几年的威斯康星大学的博士E. Horowitz大师的《计算机算法基础》被北京大学用作“教材或参考书”的第1、第2本书等我国许多书都说“我们查阅了国外流行的数种教材，发现多数教材杂面向设计方面不是重视不够就是处理不甚恰当，而只有Ellis Horowitz和Sartaj Sahni合著的“Fundamentals of Computer Algorithms”一书比较集中地反映了以上观点”（1978年出版）的第11章“NP-Hard and NP-Complete problems: NP-难度和NP-完全的问题”开头11.1节说“The second group contains problems whose best known algorithms are nonpolynomial. Examples we have seen include the traveling salesperson and the knapsack problem for which the best algorithms given in this text have a complexity O(n²2ⁿ) and O(2^n/2) respectively第二类问题则包括那些迄今已知的最好算法所需时间是非多项式的问题。例如旅行推销员和背包问题，本书前面已指出它们的时间复杂度分别是O(n²2ⁿ) and O(2^n/2)”（traveling salesperson常译为旅行推销员、旅行商、货郎等，都是权最小哈密顿图，而这章最先讲它且它的时间复杂度极大-因此哈密顿图是P=?NP的最优试金石）。

5-2、《计算机算法的设计与分析》1974年第1版，这是很经典的至今仍被世界各国主要大学用作蓝本的世界名著，作者是Alfred Aho和2个计算机诺贝尔奖得主John Hopcroft，Jeffrey Ullman合撰，第10章“NP完全问题”的10.1节之前的引言说“非确定多项式时间完全问题（简称“NP完全”问题），这类问题包括许多“典型的”组合数学问题，如旅行商问题、哈密顿圈问题、整数线性规划问题，以及所有已证明和这一类问题“等价的”问题”，并旅行商也是权最小哈密顿图，可见哈密顿图--NP完全问题的最优试金石。

5-3、计算机诺贝尔奖得主Ronald L. Rivest和C. E. Leiserson以及Cormen等在1990年出版的《Introduction to algorithms算法导论》的“NP完全性”这章开头的2个例是最长路径和哈密顿圈（图的最长路径就是哈密顿路）

5-4、以色列国家科学院院长David Harel在1987年出版的《Algorithmics. The spirit of computing算法学:计算的精髓》的“Inefficiency and intractability”这章的“Path-finding problems”只用粗字标旅行商和哈密顿路图-此前各章节没有粗字标任何NP问题

5-5、Google副总裁Udi Manber在1989年出版的《Introduction to algorithms. A creative approach算法引论:一种创造性方法》

关于“计算机算法设计与分析”-还可参考这里更多书籍-它们也主要如此以哈密顿图为主导。

6-1、在图论组合书籍方面，如北京大学前辈才子王树禾教授1990年出版的《图论及其算法》一书，第271页在给出定义1（即P的定义）后，接着说“有许多问题，我们虽然尚不知其有无多项式算法，但给出一些附加信息，则可以在多项式时间内由图灵机加以解决。例如图是否哈密顿图？众所周知，这个问题是个难解问题，但若给出图的一个圈，则在多项式时间内可以验证它是否哈密顿圈”。其后给出定义2（即NP的定义），再接着说“显然，PÍNP。但P=NP是否成立？这是一个尚未解决而其意义十分之深远的问题”---关于如何的“意义十分之深远”，可参考这页第二部分很多国外大师的论文之陈述。

6-2，和上面高度评价海南琼州大学是世界一流水平的我国哈密顿图第一个开拓者刘振宏大师合作多本书籍的这里第1的山东大学计算机学会第二届常务理事长马绍汉（第一届正理事长转而担任他的秘书长）在1988年出版的《图论算法》一书的第八章“NP-完全性理论”的8.1节“问题的可解性及有效算法”-这是P类问题，8.2节“NP类”-这节的图论就唯一只举哈密顿图例子和讲解哈密顿图。

6-3，国际数学联盟秘书长德国科学院院长Martin Grtschel，国际数学联盟主席匈牙利科学院院长Laszlo Lovasz和Alexander Schrijver大师合撰1988年出版的《Geometric Algorithms and Combinatorial Optimization几何算法与组合最优化》的第1章就已讲讲P类、NP类以及NP难度、NP完全问题等的并也以哈密顿图、旅行商问题为主导，如1.1节标题是“Complexity theory: P and NP”并这节也是这章第1页只讲哈密顿圈问题，接着第2页又讲旅行商问题（就是这页第5之一书）

6-4，哈佛大学王浩院士的博士Shimon Even独撰1979年出版的《图论算法》的第9章“The theory of NP-completeness”的9.1“Introduction”-那肯定先讲多项式时间算法问题即P类问题，9.2“The NP class of decision problems”-即NP类虽讲到素数但只是带过而几乎全是以哈密顿图为主导；第10章“NP-complete graph problems”-10.2节是“Hamilton paths and circuits哈密顿路图和哈密顿圈”（10.2节占4页而10.1节仅1页半）可见哈密顿图为主导。

6-5，1993年图灵奖得主Juris Hartmanis的博士Edward M. Reingold，Jürg Nievergelt和博士论文做哈密顿树图的Narsingh Deo合撰的《组合数学算法》的第9章是讲P类、NP类以及NP难度、NP完全问题等的并也以哈密顿图、旅行商问题为主导。

附：我从广州回来海南贫困重灾区后出版的一些书籍也很不错可参考：如1、唯一和多年来一直是世界首富的比尔·盖茨合作科学论文的美国三院院士Christos H. Papadimitriou独撰1994年出版的《Computational Complexity计算复杂性》；2、高度评价海南琼州大学是国际一流的林诒勋教授等翻译的这里第3的Bernhard Korte大师和其博士Jens Vygen于2000年合撰出版的《Combinatorial Optimization: Theory and Algorithms组合最优化：理论与算法》；3、麻省理工学院的科学学院院长Michael Sipser独撰1997年出版的《Introduction to the Theory of Computation计算理论导引》；4、1997年当选院士的张勇传和其夫人瞿继恂合撰1994年出版的《组合最优化：计算机算法和复杂性》的第九章“整数线性规划与NP问题”开头第2段说“整数线性规划又是NP困难问题中最有代表性的问题，如前一章所分析指出的，可适定性问题，货郎问题，最大团问题，一般排序问题，哈密顿路图等一批难题都可以多项式转化为整数线性规划”；5、张立昂独撰1996年出版的《可计算性与计算复杂性导引》；6、美国工程院院士William J. Cook主撰的1998年出版的《Combinatorial optimization组合最优化》，最近7、堵丁柱等的《计算复杂性导论》，8、S. Dasgupta，C. Papadimitriou，U. Vazirani的《Algorithms算法》，特别是9、Jon Kleinberg, Éva Tardos合撰的《Algorithm Design》很受推崇，等等。

总之，就如这里香港数学会理事长高度评价海南琼州大学的哈密顿图具有世界领先水平的第四章“未来数学家的挑战”的第1节说“NP问题的代表问题之一是Traveling salesman problem”（注：Traveling salesman problem就是权最小哈密顿图问题），而且这整个第1节只唯一说这一个NP问题（上面以色列科学院院长在“Is P equal to NP ?”节说在计算机科学“It is definitely the most intriguing这绝对是最有趣的”）。

直到最近图同构才成为另一个关注点（它对相关问题有很大作用，也对P=？NP问题看似有些点促进--但起码根本算不上对P=？NP问题有较实质进展性作用，因而哈密顿图仍居主导地位）：Mathematician claims breakthrough in complexity theory（http://news.sciencemag.org/math/2015/11/mathematician-claims-breakthrough-complexity-theory ）。

即最近，美国芝加哥大学数学和计算机科学系教授Laszlo Babai和他的博士生John Wilmes合作，似乎很有希望得到图同构问题的拟多项式时间算法，即运行时间大约是vO(log v), 该时间复杂度比多项式时间高，但比一般的NP-完全问题的指数时间低得多，比原先的exp(√(vlog v))时间算法，大大改进了。这提醒我们图同构问题可能不是NP-完全问题。这结果如果被证实为正确的话，它将被评估为近几年里计算机科学的重大突破)。

关于图同构-综合些的资料可参考郝志峰校长指导的侯爱民的博士论文“哈密顿环与图同构问题的理论研究及算法设计”--这篇博士论文的参考文献中前4个是书第5个是海南琼州大学的论文（这篇博士论文的共5个关键词依次是：NP问题；哈密顿圈；图同构；判定条件；判定算法。可见其紧扣这页主题），在中国知网还见郝建强、靳伟、商慧亮的几篇图同构的博士论文--可他们的都与NP问题无关（这个侯爱民1989年在天津大学硕士研究生毕业之前已和天津大学前辈教授王镭、张连芳教授合作发表论文“机器人智能故障安全系统”，《微小型计算机开发与应用》，1988年第4期。以前的大多数研究生要毕业很久都难正式发表一篇论文）。