4TSP与平面图(笔记) 仿照SAT( k SAT),这里称无向简单图顶点度数为 k 的TSP为 k TSP。 显然,2TSP只有一个Hamilton cycle,并且一定是平面图,因为它不包含 Kuratowski图 K 5 或 K 3,3 。 4TSP,“最小的图是 K 5 ”,这个看法正确吗? 假如正确,则 4 TSP一定不在平面图上吗? K 4 K 5 K 6 从 K 6 中每个顶点减去一条边,得到下图。 该图是可平面的。 4TSP可以出现在平面图上。 参考资料: Travelling salesman problem (TSP,旅行商问题,又译为旅行推销员问题、货郎担问题) http://en.wikipedia.org/wiki/Travelling_salesman_problem Complete graph (完全图) http://en.wikipedia.org/wiki/Complete_graph Hamiltonian path http://en.wikipedia.org/wiki/Hamiltonian_cycle Kuratowski graph (库拉托斯基面图) http://eom.springer.de/K/k056020.htm Graph, planar (平面图) http://eom.springer.de/g/g044990.htm “P对NP(P versus NP, P vs NP)”问题的描述、难度、可能的答案 http://bbs.sciencenet.cn/forum.php?mod=viewthreadtid=266338