求真分享 http://blog.sciencenet.cn/u/zlyang 求真务实

博文

[讨论] 4TSP与平面图(笔记)

已有 3204 次阅读 2011-8-14 10:57 |系统分类:科研笔记|关键词:TSP,,平面图,planar,Graph,Kuratowski| Graph, TSP, 平面图, planar, Kuratowski

[讨论] 4TSP与平面图(笔记)
 
 
 
        仿照SAT(kSAT),这里称无向简单图顶点度数为k的TSP为kTSP。
        显然,2TSP只有一个Hamilton cycle,并且一定是平面图,因为它不包含Kuratowski图K5K3,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



http://blog.sciencenet.cn/blog-107667-475002.html

上一篇:2011暑假傻拍(12):杂烩(树上鸟、嫩芽、桃、敬业字、树顽强)
下一篇:饶毅教授的Taiwan China建议有理!

1 丁甜

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2018-12-18 23:01

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部