离散数学 课件 6.5 汉密尔顿图

CHAPTER0606图论6.5汉密尔顿图目录CONTENTS01引言：汉密尔顿图的起源汉密尔顿的“周游世界”游戏及其在现实与理论中的应用价值。026.5.1汉密尔顿图的概念深入解析汉密尔顿路、汉密尔顿回路和汉密尔顿图的严格数学定义。036.5.2汉密尔顿图的判定方法系统学习判定汉密尔顿图的必要条件、充分条件，以及利用图的闭包进行判定的技巧。引言：汉密尔顿图的起源正十二面体模型（汉密尔顿周游世界游戏）🎮游戏背景1859年，爱尔兰数学家威廉·罗万·汉密尔顿发明了一个基于正十二面体的数学玩具，以此向朋友展示数学问题的趣味性。❓核心挑战在正十二面体的每个顶点代表一座“城市”，要求沿着边寻找一条闭合路线，能够访问图中的每一个顶点恰好一次，并最终返回起点。💡理论起源这个著名的“周游世界问题”成为了图论中重要概念——“汉密尔顿图”的起源，为后续研究图论中的回路问题奠定了基础。6.5.1汉密尔顿图的概念定义6.25：汉密尔顿路与汉密尔顿回路给定图G,若存在一条通路,经过图中每个结点一次且仅一次,称该通路为汉密尔顿路(Hamiltonpaths);若存在一条回路,经过图中每个结点一次且仅一次,称该回路为汉密尔顿回路(Hamiltoncircuits),具有汉密尔顿回路的图称为汉密尔顿图(Hamiltongraph)。汉密尔顿路它是经过图中所有结点的通路中，长度最短的通路。因为图中有n个结点，所以汉密尔顿路的长度为n-1。汉密尔顿回路它是经过图中所有结点的回路中，长度最短的回路。因为图中有n个结点，所以汉密尔顿回路的长度为n。特别规定为了理论上的完整性，在图论中，我们通常规定：平凡图（即仅有一个顶点的图）被定义为汉密尔顿图。图例分析：汉密尔顿图、路与非汉密尔顿图(a)汉密尔顿图存在汉密尔顿回路：

v₁→v₂→v₃→v₄→v₁(b)非汉密尔顿图存在汉密尔顿路v₁→v₂→v₅→v₄→v₃，

但不存在汉密尔顿回路(c)非汉密尔顿图既不存在汉密尔顿回路

也不存在汉密尔顿路。(d)汉密尔顿图结构满足条件，

存在一条包含所有顶点的汉密尔顿回路。(e)非汉密尔顿图图中存在汉密尔顿路，

但无法形成闭合的汉密尔顿回路。(f)非汉密尔顿图图的连通性或顶点分布导致,不存在任何汉密尔顿路。6.5.2汉密尔顿图的判定方法定理6.12：汉密尔顿图的必要条件若图G=<V,E>存在汉密尔顿回路,则对于集合V的每一个非空子集S，均有W(G-S)≤|S|。其中，W(G-S)表示从图G中删除子集S的所有结点及关联边后，所得子图的连通分支数量。定理直观解读从图G中删除任意非空子集S的结点后，剩下的子图被分割成的连通块数量，永远不能超过被“砍掉”的结点数量|S|。这意味着汉密尔顿图的连通性“足够好”。逻辑性质与应用这是一个必要非充分条件。它的主要价值在于：❌判定一个图不是汉密尔顿图，即找出反例S使得

W(G-S)>|S|。✅无法用它来直接证明一个图是汉密尔顿图。例题6.20：利用必要条件判断非汉密尔顿图问题描述试判断图6.43(a)是否为汉密尔顿图？我们利用汉密尔顿图的必要条件（定理6.12）来进行反证。推理与结论1.选取结点子集S={v₁,v₂}，即|S|=2。2.删除S后，子图G-S的连通分支数W(G-S)=33.由于W(G-S)>|S|，不满足必要条件，故结论为该图不是汉密尔顿图。图6.43：图G与删除S后的子图G-S彼得森图（PetersenGraph）：必要条件的局限性关键特性彼得森图满足不等式\(W(G-S)\leq|S|\)对于图中所有非空顶点子集\(S\)，这意味着它满足定理6.12所给出的必要条件。惊人的反例结论尽管满足上述必要条件，但经过严格的图论分析和验证，彼得森图并不是汉密尔顿图（即不存在经过每个顶点恰好一次的回路）。理论启示这有力地证明了：定理6.12的条件不是充分的。汉密尔顿图的判定问题远比欧拉图复杂，至今尚未找到简单的充要条件。定理6.13&6.14：存在汉密尔顿路/回路的充分条件定理6.13·存在汉密尔顿路的充分条件设图G=<V,E>是一个具有n个结点的简单图，若G中每一对不相邻的结点的度数之和大于等于n-1，则在G中存在一条汉密尔顿路。定理6.14·存在汉密尔顿回路的充分条件设图G=<V,E>是一个n阶简单图，若G中每一对不相邻的结点的度数之和大于等于n，则在G中存在一条汉密尔顿回路。关键性质：充分非必要条件

满足上述度数之和条件的图一定存在汉密尔顿路/回路，但反之不成立——即存在汉密尔顿路/回路的图，其结点度数之和未必满足上述要求。充分条件的局限性反例：n边形(n≥3)前提设定：考虑一个普通的n边形（如正六边形）。该图中每个顶点的度数均为2，因此任意两个不相邻顶点的度数之和为2+2=4。条件不满足：当边数n>5时（如n=6），顶点度数之和4<n-1(即5)。这意味着它不满足定理6.13的充分条件。事实结论：n边形显然存在汉密尔顿回路，它本身就是一个汉密尔顿图。逻辑结论与启示1.充分非必要条件：定理6.13和6.14给出的是判断汉密尔顿图的充分条件，而非必要条件。满足条件则“一定是”，但不满足条件并不代表“一定不是”。2.理论边界：这揭示了图论中判定汉密尔顿图的复杂性：目前尚未找到简单的充要条件，我们需要根据具体图的结构特征灵活分析。定义6.26：图的闭包（Closure）定义内容给定图G=<V,E>有n个结点,若将图G中度数之和至少是n的非邻接结点连接起来得图G',对图G'重复上述步骤,直到不再有这样的结点对存在为止,所得到的图,称为是原图G的闭包(Closure),记作C(G)。✦核心特性一个图的闭包是唯一的，与添加边的顺序无关。定理6.15：利用闭包判定汉密尔顿图定理核心表述当且仅当一个简单图G的闭包C(G)是汉密尔顿图时，这个简单图G是汉密尔顿图。判定策略与应用通过反复连接图G中度数之和足够大的非邻接顶点，逐步将G扩展为其闭包C(G)。若最终得到的闭包C(G)是汉密尔顿图（例如，C(G)是完全图），则可直接判定原图G也是汉密尔顿图。汉密尔顿图判定的现状计算复杂性壁垒汉密尔顿图的判定问题是图论与理论计算机科学中公认的NP-困难(NP-hard)问题。这意味着，在现有的经典计算模型下，不存在一个多项式时间的算法能够在所有情况下，快速判定任意一个图是否是汉密尔顿图。理论探索的困境尽管经过多年的研究，数学界已经提出了超过300个相关定理和充分条件，但遗憾的是，至今仍没有发现一个简单、通用的“充分必要”判别准则。寻找这样一个高效、普适的判定方法，依然是图论领域中一个极具挑战性的重大未解决问题。本节总结汉密尔顿图的概念▌定义

包含汉密尔顿回路的图，即在图中存在一条经过每个顶点恰好一次的回路。▌核心特征

在不重复访问顶点的前提下，完成对所有顶点的遍历并最终回到起点。判定方法体系1.必要条件(证伪)

公式:W(G-S)≤|S|。不满足此条件，则必不是汉密尔顿图。2.充分条件(证实)

利用度数和条件(Dirac/Ore定理)，满足即可判定为汉密尔顿图。3.闭包方法(间接判定)

通过逐步构造图的闭包，将复杂判定转化为简单完全图判定。计算复杂性NP-困难问题(NP-hard)

目前数学界尚未找到一个简洁、通用的充要条件来直接判定所有图。这意味着在大规模图数据中，汉密尔顿图的判定是一个计算上的难题，没有已知的高效算法。核心概念与定理汇总表汉密尔顿图具有汉密尔顿回路的图。定义6.25汉密尔顿路经过图中每个结点一次且仅一次的通路。定义6.25汉密尔顿回路经过图中每个结点一次且仅一次的回路。定义6.25必要条件对任意非空子集S，有