以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  [原创]He,He 离散大本，P138-139中定理8.7及推论1后有 ( * )及( * * )  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=56770)

--  作者：cpkug
--  发布时间：12/15/2007 10:45:00 AM

--  [原创]He,He 离散大本，P138-139中定理8.7及推论1后有 ( * )及( * * )
大家来看看这个：

定理8.7 设G 是n(n >= 2) 阶无向简单图，若对于G 中任意不相邻的顶点vi, vj 均有
                                   d(vi) + d(vj) >= n - 1                                  ( * )
则G 中存在哈密顿通路.

推论1 设G 是n(n >= 3) 阶无向简单图，若对于G 中任意不相邻的顶点vi, vj 均有
                                  d(vi) + d(vj) >= n                                        ( * * )
则G 中存在哈密顿回路，从而G 是哈密顿图.

这是表示这两个结论很重要吗？还是有什么其它含义，大家来说说吧！


--  作者：Logician
--  发布时间：12/15/2007 2:06:00 PM

--  
印象中这两个结论是最早找到的一批关于“哈密顿通/回路”存在性的充分条件。
由于“H-回路”问题很难，没有简单的充要条件，所以它引起了不少图论研究者的兴趣。（由于“H-回路”问题是NP-Complete的，所以它在算法/计算理论领域也有很重要的价值）
在这种情况下，各种H-回路存在的充分条件和必要条件都可以看成是从某个侧面刻画了H-图的性质，从而可能会对我们真正地理解H-图有所帮助。
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 27.344ms