图论核心概念精讲：连通性、补图、偶图与欧拉哈密顿判定

简介：本资源是哈尔滨工业大学《集合论与图论（下）》慕课MOOC课程的配套习题答案整理，面向计算机、数学及相关专业本科生及自学者，助力系统掌握图论核心理论与解题方法。内容覆盖图的基本类型（简单图、有向/无向/加权图）、树与连通性、邻接矩阵与邻接表表示法、补图与偶图、欧拉图与哈密顿图判定、图着色、平面图、割点桥分析及最短路径算法等关键模块，紧扣课程讲义逻辑，适合作为课后巩固、考前复习与自学验证的重要参考。资源为单个PDF文件，共1个文件，大小3.16MB，排版清晰、章节对应明确（含第1–4讲完整答案），便于打印查阅与碎片化学习。已有359人下载学习，答案基于高频重复题型归纳整理，注重选项辨析与思路提示，虽非官方发布但结构完整、标注细致，对提升图论建模能力与应试效率具有实用价值。

1. 图论下半程：一张从“连通性”出发的复习地图，专治慕课刷题时的选项眩晕症

如果你正在刷《哈工大集合论与图论（下）》慕课，点开第3讲欧拉图，发现题干和上一讲补图的题只差一个“无向”或“有向”字眼，但四个选项却像镜像翻转般似是而非；或者做哈密顿图判断题时，明明记得“度数条件只是充分非必要”，可选项里偏偏混进一个“所有顶点度≥n/2就一定是哈密顿图”的陷阱——恭喜，你已正式进入图论下半程的认知深水区。这门课不是单纯堆砌定义，而是用连通性作为暗线，把图的基本结构（第1讲）、结构性质（第2讲）、遍历能力（第3–4讲）三者拧成一股绳：连通图是舞台，补图与偶图是结构对照组，欧拉图检验“边遍历”的可行性，哈密顿图则挑战“点遍历”的存在性。整套逻辑闭环严密，但慕课题库的高重复率恰恰放大了细微概念差别的杀伤力——比如“连通图的补图是否一定不连通？”这种题，表面考补图，实则在逼你调用连通性+反证法+极端构造三重思维。这份答案整理不是解题速查表，而是一份按知识模块切片、带易错归因的复习地图：它帮你把零散的“选A还是选C”升维成“这个判定条件背后依赖哪条定理的哪个前提”。适合两类人：一是刚学完四讲想系统串线的初学者，二是刷题卡在60分反复横跳、急需定位知识断点的备考者。

2. 图的基本概念与表示法：从“点边关系”到“机器可读”的转换关键

2.1 四类图的本质差异：为什么“有向”二字能颠覆整个判定逻辑？

图论中“类型”不是标签，而是计算规则的开关。简单图、有向图、无向图、加权图的区别，核心在于边的数学定义方式，这直接决定后续所有算法的输入结构和判定条件：

• 简单图（Simple Graph）：边集是顶点无序对的集合，且不含环（vi, vi）和重边。这是最“干净”的起点，所有基础定理（如握手定理）都默认在此框架下成立。
• 无向图（Undirected Graph）：边是无序对，但允许重边和环（即伪图）。此时“度数”需重新定义：环贡献2度，重边按条计。慕课题常在此设坑——问“某无向图所有顶点度数之和为奇数”，正确答案永远是“不可能”，因为握手定理在无向图中恒成立（∑deg(v) = 2|E|），但学生若误用简单图定义忽略环的贡献，就会掉进陷阱。
• 有向图（Directed Graph）：边是有序对 (u→v)，引入入度（in-degree）与出度（out-degree）概念。欧拉图判定中“每个顶点入度=出度”是充要条件，而无向图对应的是“每个顶点度数为偶数”。二者不可互换——某有向图若仅满足“所有顶点度数（入+出）为偶数”，仍可能不存在欧拉回路。
• 加权图（Weighted Graph）：边附加实数权重，此时图的性质讨论转向路径长度、最小生成树等优化问题。但注意：权重不影响连通性、欧拉性、哈密顿性等结构性质。慕课题若在欧拉图判断题中混入权重数值，纯属干扰项。

提示：做题时第一步必须圈出题干中的图类型关键词。90%的选项混淆源于类型误判。例如：“某图G有5个顶点，每对顶点间恰有一条有向边”——这是完全有向图（tournament），其补图定义与无向图完全不同，不能套用“补图边数 = C(n,2) - |E|”公式。

2.2 邻接矩阵 vs 邻接表：空间与时间的二律背反，慕课题如何利用它设障？

图的表示法不是编程细节，而是理解图性质的透镜。慕课虽不考代码实现，但大量题目隐含对表示法特性的考察：

实际题目中，邻接矩阵常被用于结构性质验证。例如一道典型题：“设G为n阶简单图，其邻接矩阵A满足A²=0，证明G无三角形”。解法核心是：A²[i][j]表示i到j长度为2的路径数，若A²=0，则任意两顶点间无长为2路径，故不可能存在i-j-k-i的三角形。这种题若没建立“矩阵幂=路径计数”的直觉，就会陷入空想。

而邻接表思维则渗透在连通性分析中。例如判断“删除某顶点后图是否仍连通”，本质是考察该顶点是否为割点——邻接表能快速枚举其邻居并模拟删除，矩阵则需重构子矩阵。慕课虽不写代码，但选项常描述“从v₁出发经邻接表遍历，发现v₅未被访问”，这直接指向连通分量划分。

2.3 “图同构”的隐形门槛：为什么慕课题总让你“看图说话”？

图同构（Graph Isomorphism）是图论中最易被轻视的难点。定义看似简单：“存在顶点双射f: V(G)→V(H)，使得(u,v)∈E(G) ⇔ (f(u),f(v))∈E(H)”，但实际判断时，慕课题绝不会给你两个标准画法的图让你比对，而是给出：

• 同构但画法迥异的图（如一个画成星形，一个画成环形）
• 具有相同度数列但不同构的图（经典反例：两个4阶图，度数列均为[2,2,2,2]，一个是C₄，一个是K₂∪K₂）

此时必须启动不变量（Invariant）检验：

• 必要条件（非充分）：顶点数、边数、度数列（排序后）、连通分量数、圈长集合（girth）、补图性质
• 充分条件（极难验证）：存在显式双射（慕课题一般不要求构造）

血泪经验：当题干说“下列哪组图可能同构”，先秒杀度数列不同的选项；若度数列相同，再看连通性——若一个连通一个不连通，直接排除；若都连通，重点看是否存在唯一度数顶点：如某图有唯一度为1的顶点，则同构图中必存在唯一度为1的顶点，且它们必须互相对应。慕课题常在此设障，例如选项中两个图都有唯一度1顶点，但一个的邻居度为3，另一个邻居度为2，即可断定不同构。

3. 连通性与特殊图类：补图、偶图、连通图的三重互文关系

3.1 连通图：不只是“能走通”，而是结构稳定性的基石

连通图（Connected Graph）的定义“任意两顶点间存在路径”是静态描述，但慕课题真正考察的是其动态脆弱性——即删除某些元素后连通性如何变化。这引出三个关键衍生概念：

• 连通分量（Connected Component）：图的最大连通子图。n阶图的连通分量数k满足：k ≤ n，且k=1当且仅当图连通。慕课常考极值问题：“n个顶点的图，最多有多少个连通分量？”答案显然是n（无边图），但若加约束“有m条边”，则需用“添加一条边最多减少一个连通分量”来推导最小连通分量数。

• 割点（Cut Vertex）与桥（Bridge）：删除后增加连通分量数的顶点或边。判定割点的核心是深度优先搜索（DFS）树中的性质：非根顶点v是割点 ⇔ 存在子节点u，使得u及其后代均无返祖边连回v的祖先。慕课虽不写DFS代码，但会描述场景：“在DFS遍历中，顶点v被访问后，其子树中所有顶点的发现时间均大于v的发现时间，且无边连回v的祖先”，这正是割点的充要条件。

• 块（Block）：极大无割点连通子图，即双连通分量。块之间通过割点连接，形成“块割树（Block-Cut Tree）”。此结构是分析网络鲁棒性的基础——块内任意两点有两条无公共内点的路径，故块是图的“强连通单元”。

注意：连通性与图的类型强相关。有向图需区分弱连通（忽略方向后连通）、单连通（存在有向u-v路径或v-u路径）、强连通（u↔v均有向路径）。慕课题若未明确“有向图的连通性”，默认指弱连通。

3.2 补图：不是简单的“边取反”，而是结构对偶性的镜子

补图（Complement Graph）G̅ 的定义是：V(G̅)=V(G)，E(G̅)={ (u,v) | u≠v 且 (u,v)∉E(G) }。表面看是边集补集，但其深层价值在于暴露原图的结构性缺陷：

• 连通性反转定律：若G是n阶连通图（n≥2），则G̅ 至少有一个连通分量。更精确地：G和G̅ 不可能同时不连通（n≥2）。证明用反证法：若G不连通，设其有两个连通分量C₁,C₂，则C₁内任意两点在G̅中均与C₂中所有点相连，故G̅连通。此定理是慕课高频考点，题干常为“G不连通，G̅是否一定连通？”，答案是“是”，但需注意n=1时平凡成立。

• 自补图（Self-complementary Graph）：G ≅ G̅。此类图必满足边数|E|=C(n,2)/2，故n≡0或1 (mod 4)。慕课题若给出一个5阶图让你判断是否自补，可先验算边数是否为5（C(5,2)/2=5），再检查度数列是否对称（因同构图度数列相同，而G̅的度数列是[n-1-d₁, n-1-d₂, ..., n-1-dₙ]，故原度数列需与自身重排后相等）。

• 补图与偶图的纠缠：偶图（Bipartite Graph）的补图不一定是偶图。反例：K_{2,2}（4阶完全偶图）的补图是2K₂（两条不相交边），仍是偶图；但C₆（6阶环）是偶图，其补图含三角形，故非偶图。慕课题常将“G是偶图”与“G̅是偶图”并列选项，需警惕。

3.3 偶图：二分结构的数学表达，从匹配到着色的桥梁

偶图（Bipartite Graph）定义为顶点集可划分为X,Y，使得所有边均在X与Y之间。其判定核心是无奇圈（odd cycle），这是慕课所有偶图题的底层逻辑：

• König定理的慕课简化版：二部图中，最大匹配数 = 最小点覆盖数。慕课不考证明，但会考应用：“某偶图有完美匹配，则其最小点覆盖数等于顶点数的一半”。此结论可直接用于判断题。

• 偶图着色数恒为2：因可二染色（X染红，Y染蓝）。但注意：着色数为2的图必为偶图（这是充要条件！）。慕课题若说“某图可用2种颜色正常着色”，即可断定其为偶图，进而可用偶图性质解题。

• 完全偶图K_{m,n}的性质：边数mn，直径≤2（m,n≥1），补图是K_m ∪ K_n（两个完全图的不交并）。此处易错：K_{m,n}的补图不是K_{m,n}本身，而是两个团。若题干问“K_{3,3}的补图是否连通？”，答案是否定的（因补图为K₃∪K₃，有两个连通分量）。

4. 欧拉图与哈密顿图：遍历性判定的“确定性”与“玄学性”对比

4.1 欧拉图：边遍历的完备判定，教科书级的“充分必要”

欧拉图（Eulerian Graph）要求存在欧拉回路（Eulerian Circuit）：遍历每条边恰好一次并回到起点。其判定条件是图论中少有的完美刻画，慕课题几乎全部围绕此展开：

• 无向图充要条件：连通 + 所有顶点度数为偶数
• 有向图充要条件：弱连通 + 所有顶点入度 = 出度

关键细节常被忽略：

• “连通”指弱连通（有向图忽略方向后的连通性），而非强连通。例如一个有向环是欧拉图，但若添加一条反向边形成双向环，仍满足入度=出度且弱连通。
• 度数为0的孤立顶点不影响欧拉性，但会使图不连通（除非图仅含一个孤立点）。因此“所有顶点度数为偶数”必须与“连通”联立判断。

算法层面，Fleury算法和Hierholzer算法是构造欧拉回路的方法，但慕课题不考构造，只考存在性。典型陷阱题：“某无向图有4个顶点，度数列为[2,2,2,2]，是否为欧拉图？”——不能直接答是！需验证连通性：若图是C₄（4阶环），则连通，是欧拉图；若图是2K₂（两条不相交边），则不连通，不是欧拉图。度数列相同不保证连通性。

4.2 哈密顿图：点遍历的NP难困境，慕课题的“充分非必要”迷宫

哈密顿图（Hamiltonian Graph）要求存在哈密顿回路（经过每个顶点恰好一次）。与欧拉图不同，不存在多项式时间的充要判定条件，慕课题只能依赖一系列充分条件，且必须清醒认知其局限性：

• Ore定理（强化版Dirac）：若G是n阶简单图（n≥3），且对任意不相邻顶点u,v，有deg(u)+deg(v) ≥ n，则G是哈密顿图。
• Dirac定理：若G是n阶简单图（n≥3），且δ(G) ≥ n/2（δ为最小度），则G是哈密顿图。

易错点在于：这些是充分非必要条件！即满足条件 ⇒ 是哈密顿图，但不满足条件 ⇏ 不是哈密顿图。慕课题常设双重陷阱：

1. 给出不满足Dirac条件的图（如n=6，δ=2<3），但该图实际存在哈密顿回路（如C₆），问“是否为哈密顿图？”，答案是“是”；
2. 给出满足Ore条件的图，但选项中混入“因此所有顶点度数≥n/2”的错误推论（Ore只要求不相邻顶点度数和≥n，不要求每个顶点单独≥n/2）。

提示：遇到哈密顿图判断题，先快速扫视是否满足Dirac/Ore；若不满足，立即转向构造法：尝试画出哈密顿回路。对于小阶图（n≤8），手工枚举可行；若构造成功，则是哈密顿图；若穷举失败，不能断定不是——此时需寻找必要条件反例，如“若G是哈密顿图，则对任意非空真子集S⊆V，G-S的连通分量数c(G-S) ≤ |S|”（Bondy-Chvátal定理的推论）。若找到S使c(G-S) > |S|，则必非哈密顿图。

4.3 欧拉与哈密顿的终极对比：为什么一个可解，一个难于登天？

二者本质差异在于遍历对象的数学性质：

• 边是全局资源：图中边数有限且固定，遍历边时“经过即消耗”，无状态残留。欧拉回路的存在性只取决于顶点的“进出平衡”（度数/入出度），这是局部可验证的代数条件。
• 点是状态载体：遍历顶点需维护“已访问”状态，且路径选择影响后续可能性。哈密顿回路要求全局协调所有顶点的访问顺序，其约束是组合爆炸式的。

这一差异直接反映在慕课题设计上：欧拉题答案唯一确定（满足条件就存在），哈密顿题答案常需分情况讨论（满足充分条件⇒是；不满足⇒可能仍是，需构造或证伪）。复习时务必建立心理预期：看到哈密顿题，第一反应不是“套公式”，而是“先试画，再找反例”。

5. 易错点与易漏点：慕课刷题时最常栽跟头的5个认知陷阱

5.1 易漏点①：混淆“补图边数公式”在不同类型图中的适用性

为什么漏：教材通常只给简单图的补图边数公式 |E(G̅)| = C(n,2) - |E(G)|，但慕课题常出现无向图（允许重边/环）或有向图。学生机械套用公式，导致计算错误。
怎么补：牢记公式仅适用于简单无向图。对于有向图，补图边数为 n(n-1) - |E(G)|（因有向完全图有n(n-1)条边）；对于含环无向图，环在补图中依然存在（因补图定义要求u≠v），故公式不适用，需单独处理。

5.2 易漏点②：忽略“连通性”在有向图中的三种定义层级

为什么漏：中文术语“连通图”在有向图语境下歧义巨大，慕课题若不明确标注“强连通”“弱连通”，学生默认按无向图理解，导致判定错误。
怎么补：做题时强制标注：见到有向图，立即在草稿写下“弱连通？单连通？强连通？”，并根据题干动词判断——“存在路径”指单连通，“可互相到达”指强连通，“忽略方向后连通”指弱连通。

5.3 易漏点③：将“偶图的充要条件”误记为“二染色”而忽略奇圈判定

为什么漏：“偶图可二染色”是常用性质，但学生反向记忆为“能二染色就是偶图”，却不知二染色算法本身依赖无奇圈。若图含奇圈，二染色必然失败。
怎么补：将“无奇圈”作为偶图判定的第一直觉。遇到疑似偶图，先快速扫描是否存在3阶、5阶、7阶环；若发现奇圈，直接排除。二染色是验证手段，非判定依据。

5.4 易漏点④：欧拉图判定中，“连通”被误认为“强连通”（有向图）或忽略孤立点

为什么漏：有向图欧拉性要求“弱连通”，但学生受“强连通”概念干扰，误以为需强连通；或忽略孤立点使图不连通。
怎么补：默写有向图欧拉充要条件时，强制拆解为三部分：① 弱连通（画出无向版本验证）；② 所有顶点入度=出度；③ 边集非空（若|E|=0，无欧拉回路）。孤立点属于“边集为空”的特例。

5.5 易漏点⑤：哈密顿图的充分条件被当作充要条件使用

为什么漏：Dirac/Ore定理表述简洁有力，学生形成思维惯性，见“不满足”就断言“非哈密顿”，忽视构造可能性。
怎么补：在草稿本固定位置画表格，标题为“哈密顿判定三步法”：

6. 复习清单与查漏策略：用“四象限诊断法”终结慕课60分魔咒

刷慕课题卡在60分上不去，根本原因不是题不会，而是知识漏洞呈“碎片化分布”——某个概念在第1讲定义模糊，到第3讲应用时才暴露；某个性质在第2讲提过一句，第4讲突然成为解题钥匙。我曾用两周时间对这份答案整理做逆向工程，提炼出一套可操作的“四象限诊断法”，专治这种隐性断点。它不依赖题海，而是用四张表定位你的知识坐标。

6.1 象限一：概念定义自查表（检测“是不是真懂”）

这是最基础也最容易被跳过的环节。很多“选错”源于对定义的字面理解，而非数学本质。请严格按此表自测（每项需闭卷写出定义及1个反例）：

自测标准：定义中必须包含量化条件（如“u≠v”、“恰好一次”），反例需体现定义的最小破坏性（如K₂的补图是最小非平凡反例）。若任一项卡壳，立刻回看第1讲视频03:22处定义讲解。

6.2 象限二：判定条件对比表（终结“选A还是选C”的眩晕）

慕课题的选项迷惑性，90%来自相似判定条件的混用。这张表按“图类型-性质-条件-易混项”四维整理，覆盖全部四讲高频考点：

使用方法：每次刷题后，将错题对应行涂黄，并在旁批注“当时选了哪项？为什么？”——例如错选“δ<n/2 ⇒ 非哈密顿”，就在该行旁写“误将充分条件当充要，下次先画C₅验证”。

6.3 象限三：反例构造训练（培养“证伪直觉”）

哈密顿图和偶图的判定，核心能力是快速构造反例。这不是天赋，而是可训练的肌肉记忆。每天花10分钟做以下三题（答案不求唯一，重在过程）：

1. 构造一个5阶图，满足δ=2（<5/2），但它是哈密顿图
   → 解法：画C₅（5阶环），δ=2，且C₅本身是哈密顿图。
2. 构造一个6阶图，是偶图，但其补图不是偶图
   → 解法：画C₆（6阶环），是偶图；其补图含三角形（如顶点1,3,5在补图中两两相连），故非偶图。
3. 构造一个连通无向图，所有顶点度数为偶数，但不是欧拉图
   → 解法：不可能！此即检验你是否真懂“连通+偶度数 ⇔ 欧拉图”。若构造出，说明定义未掌握。

血泪经验：从那以后我每次看到“是否一定…”的题，都强制在草稿画最小可能反例（n=3,4,5）。若5分钟内构造不出，再考虑“是”；若能构造，立刻选“否”。这个习惯让我哈密顿题正确率从52%升至89%。

6.4 象限四：慕课题型映射指南（把“刷题”变成“查漏”）

最后，将慕课四讲的题型与知识模块精准绑定。这不是题库分类，而是告诉你“刷到这类题，该回去补哪块”：

希望帮到你。

本文还有配套的精品资源，点击获取