[讨论] 4TSP与平面图（笔记）
已有 5169 次阅读
2011-8-14 10:57
|系统分类:科研笔记|
Graph, TSP, 平面图, planar, Kuratowski
[讨论] 4TSP与平面图（笔记）
仿照SAT（kSAT），这里称无向简单图顶点度数为k的TSP为kTSP。
显然，2TSP只有一个Hamilton cycle，并且一定是平面图，因为它不包含Kuratowski图K5或K3,3。
4TSP，“最小的图是K5”，这个看法正确吗？
假如正确，则4TSP一定不在平面图上吗？
K4 K5 K6
从K6中每个顶点减去一条边，得到下图。
该图是可平面的。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://blog.sciencenet.cn/blog-107667-475002.html
上一篇：
2011暑假傻拍（12）：杂烩（树上鸟、嫩芽、桃、敬业字、树顽强）下一篇：
[请问] “科学网”博主里的职业中医，都有谁？谢谢！
