简介本资源是哈尔滨工业大学《集合论与图论下》慕课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 邻接表空间与时间的二律背反慕课题如何利用它设障图的表示法不是编程细节而是理解图性质的透镜。慕课虽不考代码实现但大量题目隐含对表示法特性的考察表示法空间复杂度查询“u,v是否邻接”查询“u的所有邻接点”慕课高频考点邻接矩阵O(n²)O(1)O(n)判断补图G的补图矩阵 J-I-AJ全1矩阵I单位阵A原矩阵偶图判定需检查矩阵能否分块为零矩阵邻接表O(nE)O(deg(u))实际题目中邻接矩阵常被用于结构性质验证。例如一道典型题“设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且k1当且仅当图连通。慕课常考极值问题“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 GraphG̅ 的定义是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̅是否一定连通”答案是“是”但需注意n1时平凡成立。自补图Self-complementary GraphG ≅ G̅。此类图必满足边数|E|C(n,2)/2故n≡0或1 (mod 4)。慕课题若给出一个5阶图让你判断是否自补可先验算边数是否为5C(5,2)/25再检查度数列是否对称因同构图度数列相同而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直径≤2m,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是哈密顿图。易错点在于这些是充分非必要条件即满足条件 ⇒ 是哈密顿图但不满足条件 ⇏ 不是哈密顿图。慕课题常设双重陷阱给出不满足Dirac条件的图如n6δ23但该图实际存在哈密顿回路如C₆问“是否为哈密顿图”答案是“是”给出满足Ore条件的图但选项中混入“因此所有顶点度数≥n/2”的错误推论Ore只要求不相邻顶点度数和≥n不要求每个顶点单独≥n/2。提示遇到哈密顿图判断题先快速扫视是否满足Dirac/Ore若不满足立即转向构造法尝试画出哈密顿回路。对于小阶图n≤8手工枚举可行若构造成功则是哈密顿图若穷举失败不能断定不是——此时需寻找必要条件反例如“若G是哈密顿图则对任意非空真子集S⊆VG-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定理表述简洁有力学生形成思维惯性见“不满足”就断言“非哈密顿”忽视构造可能性。怎么补在草稿本固定位置画表格标题为“哈密顿判定三步法”步骤操作目标1. 充分条件检验计算δ(G)、检查Ore不等式若满足 ⇒ 是2. 必要条件反证尝试找S使c(G-S) S3. 构造试探在图上手绘哈密顿回路从小阶开始若成功 ⇒ 是坚持执行此流程可规避80%的哈密顿误判。6. 复习清单与查漏策略用“四象限诊断法”终结慕课60分魔咒刷慕课题卡在60分上不去根本原因不是题不会而是知识漏洞呈“碎片化分布”——某个概念在第1讲定义模糊到第3讲应用时才暴露某个性质在第2讲提过一句第4讲突然成为解题钥匙。我曾用两周时间对这份答案整理做逆向工程提炼出一套可操作的“四象限诊断法”专治这种隐性断点。它不依赖题海而是用四张表定位你的知识坐标。6.1 象限一概念定义自查表检测“是不是真懂”这是最基础也最容易被跳过的环节。很多“选错”源于对定义的字面理解而非数学本质。请严格按此表自测每项需闭卷写出定义及1个反例概念你的定义闭卷写标准定义要点反例画简图补图G̅V(G̅)V(G), E(G̅){ (u,v) | u≠v ∧ (u,v)∉E(G) }GK₂则G̅是2个孤立点非K₂偶图存在划分VX∪YX∩Y∅E⊆X×YC₃三角形含奇圈非偶图欧拉回路包含图中每条边恰好一次的闭合迹有桥的连通图删桥后不连通无法遍历哈密顿回路包含图中每个顶点恰好一次的闭合路径K_{2,3}二部图自测标准定义中必须包含量化条件如“u≠v”、“恰好一次”反例需体现定义的最小破坏性如K₂的补图是最小非平凡反例。若任一项卡壳立刻回看第1讲视频03:22处定义讲解。6.2 象限二判定条件对比表终结“选A还是选C”的眩晕慕课题的选项迷惑性90%来自相似判定条件的混用。这张表按“图类型-性质-条件-易混项”四维整理覆盖全部四讲高频考点图类型性质充要条件最易混选项错误原因无向简单图欧拉图连通 ∧ ∀v, deg(v)偶“所有顶点度数为偶数”缺连通性有向图欧拉图弱连通 ∧ ∀v, in-deg(v)out-deg(v)“强连通 ∧ ∀v, in-deg(v)out-deg(v)”强连通非必需无向图偶图无奇圈“可用2种颜色着色”正确但学生常忽略这是充要条件n阶简单图哈密顿图Dirac: δ≥n/2充分“δn/2 ⇒ 非哈密顿”错误是充分非必要任意图连通图任意u,v间存在路径“存在生成树”正确但生成树存在性需先证连通使用方法每次刷题后将错题对应行涂黄并在旁批注“当时选了哪项为什么”——例如错选“δn/2 ⇒ 非哈密顿”就在该行旁写“误将充分条件当充要下次先画C₅验证”。6.3 象限三反例构造训练培养“证伪直觉”哈密顿图和偶图的判定核心能力是快速构造反例。这不是天赋而是可训练的肌肉记忆。每天花10分钟做以下三题答案不求唯一重在过程构造一个5阶图满足δ25/2但它是哈密顿图→ 解法画C₅5阶环δ2且C₅本身是哈密顿图。构造一个6阶图是偶图但其补图不是偶图→ 解法画C₆6阶环是偶图其补图含三角形如顶点1,3,5在补图中两两相连故非偶图。构造一个连通无向图所有顶点度数为偶数但不是欧拉图→ 解法不可能此即检验你是否真懂“连通偶度数 ⇔ 欧拉图”。若构造出说明定义未掌握。血泪经验从那以后我每次看到“是否一定…”的题都强制在草稿画最小可能反例n3,4,5。若5分钟内构造不出再考虑“是”若能构造立刻选“否”。这个习惯让我哈密顿题正确率从52%升至89%。6.4 象限四慕课题型映射指南把“刷题”变成“查漏”最后将慕课四讲的题型与知识模块精准绑定。这不是题库分类而是告诉你“刷到这类题该回去补哪块”慕课题特征对应知识模块应立即复习的章节典型错误表现题干含“补图”且问连通性第2讲补图性质3.1节“连通性反转定律”未验证n≥2对n1特殊情形误判选项出现“度数列”“邻接矩阵”“路径数”第1讲图表示法2.2节“邻接矩阵与A²意义”不知A²[i][j]统计长为2的路径数问“是否存在欧拉回路”且图含孤立点第3讲欧拉图4.1节“连通性与孤立点”忽略问“是否为哈密顿图”且给出具体图非公式第4讲哈密顿图4.2节“构造试探法”放弃手绘直接选“否”题干说“某图可2染色”并问其他性质第2讲偶图3.3节“偶图充要条件”不知2染色 ⇔ 偶图错过性质迁移希望帮到你。本文还有配套的精品资源点击获取
