|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 计算机考研交流 』 (http://bbs.xml.org.cn/list.asp?boardid=67) ---- 离散数学(判定哈密顿图的充分必要条件) (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=71440) |
|
-- 作者：geng19861129 -- 发布时间：1/16/2009 12:28:00 PM -- 离散数学(判定哈密顿图的充分必要条件) 不知道是否已经有人研究出结果,书上说是目前没有一个简单的判定方法. google到几篇数学系论文,有通过邻接矩阵判断的,有通过递归定义方法进行分析的 请问大家,有没有人知道现在世界上时候已经有人研究出了判断一个图是否为哈密顿图的充分必要条件? 鄙人爱好图论,因此正在研究这个问题,希望有志同道合的人可以不吝赐教,说一下想法. |
|
-- 作者：geng19861129 -- 发布时间：1/16/2009 12:52:00 PM -- 本人对图论研究不是很深,因此有些名词也许不知道,所以自己定义几个名词便于本人阐述和大家理解. 定义1:设若某根树除根节点外(根节点唯一,必然没有兄弟节点)任何节点都没有兄弟节点,则称这种树为"线性树"(图形上是一个线性结构) 定义2:设F是一棵根树,v是F的任意叶节点,F中包含v的最大"线性树"为v在F中的"生成线性树",并称此生成线性树中靠近原图根节点的一端为“根端“，在原图中的叶节点成为“叶端“ 定义3:设G'是G的生成子图，若G'通过加上G中的若干边可以成为连通图，则称G'为在G中的可连通子图,并将G'加上最少边数后构成的连通图称为"最小可连通子图". 哈密顿图判定定理：设F是图G的任意一棵生成树,设F得所有的叶节点在F中的生成线性树组成图G1，易知G1的连通分支个数等于F的叶节点个数且G1是G的生成子图，则图G是哈密顿图当且仅存在这样的G1,当G1为G中的可连通子图，且G1中的叶端和根端均为G1在G中的最小可连通子图的割点。 证明比较容易，可以自行尝试。 因为思考尚未周全且表达能力有限，整个理论也许会有错，欢迎大家批判，我只是说说自己的想法而已。
[此贴子已经被作者于2009-1-16 14:30:45编辑过]
|
|
-- 作者：Chojin -- 发布时间：1/16/2009 1:34:00 PM -- 貌似用你的充要条件去判定哈密顿图还是个NP-Complete问题的 你要能提出一个多项式时间算法来判定哈密顿图才算解决了这个问题啊 |
|
-- 作者：geng19861129 -- 发布时间：1/16/2009 2:22:00 PM -- 我明白了,我的解法的最后找叶子节点之间的割点等问题是NP-compelte问题 正在思考...汗 我把最后G1的前面加了一个存在这样的G1,也许这样就不是NP-complete问题了? 谢谢指教
|
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
46.875ms |