哈密尔顿图范更华.ppt

2004年11月 计算机系软件教研室 中国地质大学计算机系软件教研室  第11讲 哈密尔顿图 Hamilton Graph 主讲人 薛思清 中国地质大学(武汉)计算机学院 主要内容 1 哈密尔顿图 2 哈密尔顿图判定定理 3 建模：哈密尔顿图应用(下节课讨论) 重点难点：哈密尔顿图判定定理 11.1 哈密尔顿图 几个问题 在一个大城市，有很多取款机，那么，如何制定出一个最优的路线，使运钞车过每个提款机一次就能运送完钱钞？ ?货郎担问题 ?旅行商人问题 (Traveling Salesman Problem ,TSP) 优化算法——近似解?演化算法 11.1 哈密尔顿图 几个问题 在一个大城市，有很多取款机，那么，如何制定出一个最优的路线，使运钞车过每个提款机一次就能运送完钱钞？ ?货郎担问题?旅行商人问题(TSP) 考虑在七天内安排七门课程的考试，要求同一位教师所任教的两门课程考试不安排在接连的两天里，如果教师所担任的课程都不多于四门，则是否存在满足上述要求的考试安排方案？ ?时间表问题 国际象棋的跳马是否可以遍历其棋盘，即从任一格出发跳到每一格仅一次并最后回到出发的棋盘格子？ 在一个至少有5人出席的圆桌会议上（会议需要举行多次），为达到充分交流的目的，会议主持者希望每次会议每人两侧的人均与前次不同，这是否可行？请应用图论知识进行论证。 周游世界问题 11.1 哈密尔顿图 问题 1859年爱尔兰数学家威廉·哈密尔顿（Sir William Hamilton）发明了一个小游戏玩具：一个木刻的正十二面体，每面系正五角形，三面交于一角，共有20个角，每角标有世界上一个重要城市。哈密尔顿提出一个问题：要求沿正十二面体的边寻找一条路通过20个城市，而每个城市只通过一次，最后返回原地。哈密尔顿将此问题称为周游世界问题。游 戏) 求解 抽象为图论问题 哈密尔顿给出了肯定回答，该问题的解是存在的 11.1 哈密尔顿图 11.1 哈密尔顿图 2002年“离散数学与计算机科学研究中心”在福州大学成立 范更华教授获2005年度国家自然科学奖二等奖 ——研究主题：哈密尔顿圈及圈覆盖理论 ——“范定理” ( “范条件”、“范类型”) 11.1 哈密尔顿图 范更华：歪打正著学了图论 灵光一闪发现定理 ——科学中国人（2005）年度人物 哈密尔顿圈问题是图论最古老的研究课题之一，是至今未解决的世界难题，在许多领域有着重要应用。经过多年艰苦攻克，范更华的这一项目在这一问题的研究上开辟 了一条新的途径，证明若图中每对距离为2的点中有一点的度数至少是图的点数的一半，则该图存在哈密尔顿圈。了此成果引发了大量后续工作，以“范定理”、“范 条件”、“范类型”被广泛引用而出现于多种国际权威学术刊物，并作为定理出现在国外的教科书中。 ——新华网 2006.1.10 11.1 哈密尔顿图 哈密尔顿回路(H-回路): 一条经过图G中的每一个结点恰好一次的回路(环) ?哈密尔顿图(Hamilton Graph, H-图): 具有哈密尔顿回路的图 哈密尔顿路(H-路): 一条经过图G中的每一个结点恰好一次的路(通路) ?半哈密尔顿图 11.1 哈密尔顿图 11.1 哈密尔顿图 哈密尔顿图性质 若图G=(V，E) 具有哈密尔顿回路，则对于结点集V的每一个非空子集S均有ω(G－S)≤|S|成立。其中ω(G－S)是G－S中连通分支数。 ——哈密尔顿图的必要条件 ——也是判定非哈密尔顿图的充分条件 11.1 哈密尔顿图 8×8马图(能否遍历??是否是H图?) 11.1 哈密尔顿图 4×4马图 5×5马图 11.2 哈密尔顿图判定定理(充分条件) 设图G为具有n(n≥3)个结点的简单无向图， 1 如果G的每一对(不相邻)结点的度数之和都不小于n–1，那么G中有一条哈密尔顿通路； 2 如果G的每一对(不相邻)结点的度数之和不小于n，那么G为一哈密尔顿图。 11.2 哈密尔顿图判定定理 判定定理1的证明 首先，G是连通的? 若G有两个或更多互不连通的分图，设一个分图有n1个结点，任取一个结点v1，设另一个分图有n2个结点，任取一个结点v2， 由 d(v1)≤n1－1，d(v2)≤n2－1， 有 d(v1)+ d(v2) ≤n1+ n2－2＜n－1， 这表明与题设矛盾，故G必连通。 11.2 哈密尔顿图判定定理 其次，G有哈密尔顿通路？