概述
一、问题的提出
哈密尔顿图起源于一种游戏，它是由英国数学家哈密尔顿
于1859年提出的“周游世界游戏”，它用一个正十二面体的20个顶点代替20个城市(图(1))，这个正十二面体同构于一个平面图(图(2))，要求沿着正十二面体的棱，从一个城市出发，经过每个城市恰好一次，然后回到出发点，这个游戏曾风靡一时，它有若干个解，称为哈密尔顿图。
二、哈密尔顿图
哈密尔顿通路——通过图中每个顶点一次且仅一次的通路。
哈密尔顿回路——通过图中每个顶点一次且仅一次的回路。
哈密尔顿图——存在哈密尔顿回路的图。
三、判定
遗憾的是至今尚未找到一个判别哈密尔顿回路和通路的充分必要条件。虽然有些充分非必要，或必要非充分条件，但在大部分情况下，还是采用尝试的办法。
最后
以上就是沉默皮皮虾为你收集整理的哈密尔顿图的全部内容，希望文章能够帮你解决哈密尔顿图所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复