(54)--6.2 哈密顿图离散数学离散数学.ppt

《(54)--6.2 哈密顿图离散数学离散数学.ppt》由会员分享，可在线阅读，更多相关《(54)--6.2 哈密顿图离散数学离散数学.ppt（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、哈密顿图英国数学家哈密顿（William Rowan Hamilton）发明的“周游世界”游戏：用一个正十二面体的20个结点代表世界上20个大城市，30条棱表示这些城市之间的交通线路。要求游戏者从任意一个城市（即结点）出发，沿棱行走经过每个城市一次且只经过一次，最终返回出发地。1、“周游世界”游戏周游世界的路线是不唯一的。1、“周游世界”游戏n经过图中每个经过图中每个结点一次且仅一次结点一次且仅一次的通路的通路/回路，称为回路，称为哈哈密密顿通路顿通路/回路回路。存在存在哈密顿回路哈密顿回路的图称为的图称为哈密顿图哈密顿图。存在存在哈密顿哈密顿通通路路而不存在哈密顿而不存在哈密顿回路回路的图称

2、为的图称为半半哈密顿图哈密顿图。dbaecdbaecdbaecf具有哈密顿通路，但具有哈密顿通路，但不是哈密顿图不是哈密顿图具有哈密顿回路，具有哈密顿回路，是是哈密顿图哈密顿图无哈密顿通路，无哈密顿通路，无无哈密顿回路哈密顿回路2、哈密顿通路与哈密顿回路设无向图设无向图 G=是哈密顿图，是哈密顿图，V1 是是 V 的任意非空真子集，的任意非空真子集，则则p(G V1)|V1|。dbaecfabV1=a p(G V1)=2|V1|=1 不满足必要条件不满足必要条件V1=a，b p(G V1)=3|V1|=2 不满足必要条件不满足必要条件彼得森图，对于任意非空结彼得森图，对于任意非空结点真子集，点

3、真子集，p(G V1)|V1|，但不是哈密顿图。但不是哈密顿图。3、哈密顿图存在的必要条件设 G=是n阶简单图，n 3。（1）若对G中任意一对不相邻的结点u、vV，都有d(u)+d(v)n-1，则G中必有哈密顿通路。（2）若对G中任意一对不相邻的结点u、vV，都有d(u)+d(v)n，则G必是哈密顿图。n 2时，完全图Kn 和有向完全图是哈密顿图。4、哈密顿图的充分条件例：某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，那么服务员能否将他们安排在同一张圆桌就坐，使得每个人都能与两边的人交谈？请用图论中的原理来解释原因。答：依题意，可做出一个包含8个结点的图G。这样问题就变成了图G中是否存在哈密顿回路。由每人至少与其余7人中的4人有共同语言，可知图中任意两个结点度数的和至少是8，所以图G是哈密顿图，存在哈密顿回路，即该问题的答案是肯定的。4、哈密顿图的充分条件THANKYOU