哈密尔顿图,离散数学图论南京大学计算机科学与技术系,内容提要,哈密尔顿通路哈密尔顿回路哈密尔顿图的必要条件哈密尔顿图的充分条件哈密尔顿图的应用竞赛图与有向哈密尔顿通路,沿着正十二面体的棱寻找一条旅行路线,通过每个顶点恰好一次又回到出发点.(Hamilton1857),周游世界的游戏,G中Hamilton通路包含G中所有顶点通路上各顶点不重复G中Hamilton回路包含G中所有顶点除了起点与终点相同之外，通路上各顶点不重复。Hamilton回路与Hamilton通路Hamilton通路问题可转化为Hamilton回路问题G*K1,Hamilton通路/回路,Hamilton回路的基本特性,Hamilton回路:无重复地遍历图中诸点,Euler回路:无重复地遍历图中诸边.若图G中有一顶点的度为1,则无Hamilton回路.设图G中有一顶点的度大于2,若有Hamilton回路,则只用其中的两条边.若图中有n个顶点,则Hamilton回路恰有n条边.注：Hamilton回路问题主要针对简单图。,Hamilton回路的存在性问题,Kn(n3)有Hamilton回路,一个基本的必要条件,如果图
