如何判断哈密顿图_哈密顿图的必要条件.doc
《如何判断哈密顿图_哈密顿图的必要条件.doc》由会员分享,可在线阅读,更多相关《如何判断哈密顿图_哈密顿图的必要条件.doc(2页珍藏版)》请在三一文库上搜索。
1、如何判断哈密顿图_哈密顿图的必要条件一、哈密顿图定义概念哈密顿通路(回路)与哈密顿图(Hamilton图)通过图G的每个结点一次,且仅一次的通路(回路),就是哈密顿通路(回路)。存在哈密顿回路的图就是哈密顿图。1.哈密顿通路设G=V,E为一图(无向图或有向图).G中经过每个顶点一次且仅一次的通路称作哈密顿通路2.哈密顿回路G中经过每个顶点一次且仅一次的回路称作哈密顿回路3.哈密顿图若G中存在哈密顿回路,则称它是哈密顿图4.定义详解:(1)存在哈密顿通路(回路)的图一定是连通图;(2)哈密顿通路是初级通路,哈密顿回路是初级回路;(3)若G中存在哈密顿回路,则它一定存在哈密顿通路,反之不真(4)只
2、有哈密顿通路,无哈密顿回路的图不交哈密顿图;与欧拉图的情形不同,到目前为止还未找到判断一个图是否是哈密顿图的非平凡的充要条件。事实上这是图论中尚未解决的主要问题之一。哈密顿图有很多充分条件,例如,(1)若图的最小度不小于顶点数的一半,则图是哈密顿图;(2)若图中每一对不相邻的顶点的度数之和不小于顶点数,则图是哈密顿图。另外,还有很多用度序列、度和、图的坚韧度等参数给出的充分条件。三、哈密顿图的充分条件和必要条件定理1:设无向图G是哈密顿图,V1是V的任意的非空子集,则其中,p(G-V1)为从G中删除V1(删除V1中各顶点及关联的边)后所得到的图的连通分支,|V1|为V1集合中包含的顶点个数。【
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 如何 判断 哈密 必要条件
链接地址:https://www.31doc.com/p-3421846.html