K₄                                                   K₅                                                    K₆

        从K₆中每个顶点减去一条边，得到下图。     

       该图是可平面的。4TSP可以出现在平面图上。

参考资料：
[1] Travelling salesman problem  （TSP，旅行商问题，又译为旅行推销员问题、货郎担问题）
http://en.wikipedia.org/wiki/Travelling_salesman_problem

[2] Complete graph   （完全图）
http://en.wikipedia.org/wiki/Complete_graph

[3] Hamiltonian path
http://en.wikipedia.org/wiki/Hamiltonian_cycle

[4] Kuratowski graph  （库拉托斯基面图）
http://eom.springer.de/K/k056020.htm

[5] Graph, planar （平面图）
http://eom.springer.de/g/g044990.htm

[6] “P对NP（P versus NP, P vs NP）”问题的描述、难度、可能的答案http://bbs.sciencenet.cn/forum.php?mod=viewthread&tid=266338

转载本文请联系原作者获取授权，同时请注明本文来自杨正瓴科学网博客。

链接地址：https://wap.sciencenet.cn/blog-107667-475002.html?mobile=1

收藏

分享