简介本资源是哈尔滨工业大学《集合论与图论下》慕课MOOC的配套习题答案整理面向计算机科学、数学及相关专业本科生及自学者助力系统掌握图论核心理论与解题方法。内容覆盖图的基本类型简单图、有向/无向/加权图、树与连通性、邻接矩阵与邻接表表示法、补图与偶图、欧拉图与哈密顿图判定、图着色、平面图、割点桥分析及最短路径算法等关键模块紧扣课程讲授逻辑每讲对应清晰如第1讲图的基本概念、第2讲连通图与补图、第3讲欧拉图、第4讲哈密顿图并附实用提示如选项辨析要点与重复题型应对建议。资源为单个PDF文件共1个大小3.16MB排版紧凑、重点突出适合作为课后复习、作业核对与考前梳理的轻量级参考材料。目前已有359人学习下载答案虽非全覆盖但结构完整、思路清晰可有效提升图论建模与逻辑推理能力。1. 图论到底是什么一张地铁线路图就能讲明白的数学语言你坐过地铁吗假设某城市有8个站点A站到B站有直达线B站能换乘去C、D两站而E站只和F站连着一条线——这些站点就是“点”连接它们的轨道就是“线”。图论说白了就是专门研究这种“点怎么连、连成什么样、连得稳不稳、能不能走完所有线或路过所有站”的数学工具。它不关心A站离B站实际几公里也不管列车几点发车它只盯着“有没有连”“往哪连”“连了几条”“能不能一笔画完”这些最本质的关系。这听起来像小孩子搭积木可正是这套看似简单的逻辑撑起了整个互联网的骨架网页是点超链接是边、社交网络的传播模型人是点关注是边、物流路径优化仓库和客户是点运输路线是边甚至芯片布线、药物分子结构分析都离不开它。哈工大这门《集合论与图论下》慕课不是教你怎么解方程而是带你亲手拆解“关系”这台机器的齿轮从最基础的“两个点能不能通”开始一路走到“怎么用最少颜色给全国机场分配起降时段才不冲突”——它训练的是一种把现实问题“翻译”成点与线的能力。很多人学完觉得“好像没算什么大题”但回头做项目时突然发现原来那个卡住三天的调度死锁其实就是个补图判断问题那个总超时的路径推荐根源在于误把哈密顿条件当成了欧拉条件。这不是玄学是思维底层的转译能力。2. 为什么图论非得从“连通性”讲起因为世界默认是碎片化的2.1 连通图网络不瘫痪的第一道门槛想象你家路由器连着三台设备手机、电脑、智能灯泡。如果某天灯泡突然断连但手机和电脑还能互相传文件——这个小网络就“不连通”了。图论里连通图的定义极其朴素图中任意两个顶点之间至少存在一条由边组成的路径。注意是“至少一条”不是“必须最短”或“必须不绕路”。无向图中只要能从A摸到B不管绕几个弯就算连通有向图则更苛刻必须存在一条按箭头方向走的路径比如A→B→C但C无法回A那A到C连通C到A就不连通。提示考试常考陷阱题——给出一个有向图问“是否连通”。务必看清题目问的是“弱连通”忽略方向后连通还是“强连通”按方向双向可达。慕课第2讲的习题里70%的错误都栽在这儿。2.2 补图原图的“镜像世界”补图的概念特别像照镜子。假设你有一张6个城市的地图目前只画了3条航线北京-上海、上海-广州、广州-成都。那么它的补图就是把所有“本可以连但没连”的线全补上北京-广州、北京-成都、北京-深圳、上海-成都、上海-深圳、广州-深圳、成都-深圳……等等唯独去掉原图已有的3条。数学上补图G的顶点集和原图G完全相同而G中的边集 所有可能边的集合 - G的边集。这个操作看似无聊实则暗藏玄机。比如判断一个图是否为“自补图”即G和它的补图G结构完全一样直接关系到密码学中某些对称密钥的设计逻辑。慕课答案里第2讲有道题给定5个顶点的完全图K₅删去两条相邻边后得到图G求G的补图边数。解法核心就一句话K₅共有C(5,2)10条边G删了2条剩8条所以补图只有10-82条边——根本不用画图靠“总数减现存”秒杀。2.3 偶图关系必须“分边站队”的特殊结构偶图也叫二部图的规则像班级分组所有顶点必须分成互不重叠的两拨比如男生队A、女生队B且所有边只能在A和B之间跨队连接A内部或B内部绝对不能有边。典型例子是“求职匹配”左边是求职者集合右边是岗位集合边代表“该人能胜任该岗”但求职者之间、岗位之间不存在“胜任关系”所以天然构成偶图。哈工大慕课强调一个关键判据无奇圈图必为偶图。所谓“奇圈”就是由奇数个顶点首尾相连形成的环三角形、五边形等。如果你发现一个图里找不到任何三角形、五边形……那它一定是偶图。反过来只要找到一个三角形立刻排除偶图可能。第2讲作业里有张图看着像偶图但仔细追踪会发现A-B-C-A构成三角形——这就是典型的“眼见不为实”必须动手验证。3. 欧拉图和哈密顿图一笔画完和路过所有站根本不是一回事3.1 欧拉图邮递员的终极梦想欧拉图解决的问题很具体“能否从某地出发走遍每条街道且不重复最后回到起点”这就是著名的“七桥问题”升级版。它的判定条件堪称图论里最优雅的公式之一无向图是欧拉图 ⇔ 所有顶点度数均为偶数度数连着几条边有向图是欧拉图 ⇔ 每个顶点入度出度举个反例一个“H”形图两横一竖四个端点度数都是1奇数中间交点度数是3奇数显然不满足条件无法一笔画闭环。但若把H的上下横线延长变成“日”字形8个顶点中4个角点度数为24个内点度数为4——全为偶数立刻变成欧拉图。慕课第3讲的练习题常在此设坑给出带向图选项里混着“入度出度”和“入度出度为偶数”两种说法后者是典型干扰项。3.2 哈密顿图旅行商的噩梦哈密顿图问的是另一个问题“能否设计一条路线恰好经过每个城市一次最后回到出发地”注意这里不关心是否走遍所有道路只关心是否“路过所有顶点”。这正是NP难问题的代表——没有像欧拉图那样简洁的充要条件只有若干必要条件如删除任意k个顶点后剩余图的连通分支数≤k和充分条件如若每个顶点度数≥n/2则必为哈密顿图。打个比方欧拉图是“扫街车”任务是清洁每条马路哈密顿图是“巡检员”任务是打卡每个路口。前者看路边后者看站点。慕课第4讲有道经典题判断一个8顶点的环图C₈是否为哈密顿图。答案是肯定的——它自己就是哈密顿回路。但若在C₈中加一条弦比如连1号和4号顶点它仍是哈密顿图可若删去一条边它就不再是环需重新验证。这种“微小改动导致性质突变”的特性正是哈密顿问题令人头疼的核心。3.3 常见误区欧拉和哈密顿90%的人第一眼就混淆误区1认为“能一笔画”就等于“是哈密顿图”→ 为什么混两者都涉及“走路径”名字都带“图”。→ 怎么区分欧拉路径关注边必须走完所有边哈密顿路径关注顶点必须路过所有顶点。一个图可以有欧拉回路但没有哈密顿回路比如两个三角形共用一个顶点的“蝴蝶图”6条边全可走但中间顶点被路过两次违反哈密顿要求。误区2把“存在哈密顿路径”当成“存在哈密顿回路”→ 为什么混中文都叫“哈密顿”考试选项常模糊写“该图是哈密顿的”。→ 怎么区分路径Path是开放的回路Cycle是闭合的。就像“从北京出发经所有省会最终到拉萨”是路径“从北京出发经所有省会再回北京”才是回路。慕课答案里明确标注第4讲所有“哈密顿图”题均指回路路径题会特别注明“哈密顿路径”。误区3用欧拉条件硬套有向图的哈密顿问题→ 为什么混看到有向图就想套“入度出度”。→ 怎么区分欧拉条件对有向图有效哈密顿条件对有向图同样适用但判定方法完全不同。例如一个有向环A→B→C→A每个点入度出度1既是欧拉图也是哈密顿图但若改成A→B→C←AA连B、B连C、A连C则A出度2入度0B出度1入度1C出度0入度2——不满足欧拉条件却存在哈密顿路径A→B→C只是没有回路。误区4认为完全图Kn一定是欧拉图→ 为什么混完全图边最多直觉“应该最容易满足”。→ 怎么区分Kn有n个顶点每个顶点度数为n-1。当n为奇数时n-1为偶数满足欧拉条件但当n为偶数时如K₄每个顶点度数为3奇数不是欧拉图。慕课第3讲选择题曾用K₆作干扰项表面看边多实则因6-15奇数被排除。4. 邻接矩阵 vs 邻接表图的两种“身份证”选错就卡死程序4.1 邻接矩阵适合查“有没有连”不适合存“怎么连”邻接矩阵是一个n×n的二维数组行和列都代表顶点编号。如果顶点i和j之间有边matrix[i][j]就填1无向图则matrix[j][i]也填1否则填0。它的优势在于查询效率极致判断i和j是否相连只需O(1)时间读取一个数组元素。但代价巨大无论图有多稀疏比如1000个顶点只连10条边也要开1000×1000100万空间。更致命的是它完全丢失边的顺序信息。比如一个有向图A→B、A→C在邻接矩阵里只体现为matrix[0][1]1、matrix[0][2]1但无法知道B和C谁先被A指向——这对拓扑排序等算法是致命缺陷。# 邻接矩阵表示无向图A-B, B-C, C-A # 顶点编号A0, B1, C2 adj_matrix [ [0, 1, 1], # A连B、C [1, 0, 1], # B连A、C [1, 1, 0] # C连A、B ] # 查询A和C是否相连直接看adj_matrix[0][2] 1 → True4.2 邻接表用空间换灵活程序员的日常选择邻接表用数组链表或Python列表实现数组下标是顶点编号每个元素是一个列表存着该顶点所有邻居的编号。比如上面的三角形图邻接表为adj_list [[1,2], [0,2], [0,1]]这意味着A的邻居是B、CB的邻居是A、CC的邻居是A、B。它的优势是空间利用率高只存实际存在的边空间复杂度O(VE)且天然保留邻接顺序遍历时按列表顺序访问对DFS/BFS等算法友好。但查询i和j是否相连需遍历i的邻接列表最坏O(V)时间。# 邻接表表示有向图A→B, A→C, B→C adj_list_directed [ [1, 2], # A指向B、C [2], # B指向C [] # C无出边 ] # 判断A是否指向C检查0号列表是否含2 → True # 判断C是否指向A检查2号列表是否含0 → False4.3 慕课实战建议考试选矩阵编程选列表哈工大慕课的习题设计非常务实第1讲大量出现“根据邻接矩阵判断度数”“计算矩阵平方得长度为2的路径数”这类题此时必须用矩阵思维——因为矩阵的代数运算如A²[i][j]表示i到j长度为2的路径数是图论分析的利器。但到了算法实现环节如第3讲写欧拉回路代码答案资源里提供的参考实现全部采用邻接表原因很现实用矩阵实现Hierholzer算法光初始化就要O(n²)时间而邻接表可动态删除边效率碾压。注意考试中若题目给出邻接表形式的数据却问“顶点v的度数”千万别数列表长度无向图中度数列表长度但有向图中出度列表长度入度需遍历所有邻接表统计——这是慕课第2讲作业的高频扣分点。5. 什么时候该用图论什么时候该换思路三个血泪教训5.1 教训一别把“关系”强行塞进图模型某次课程设计A同学接到需求“设计一个系统管理学生选课、教师排课、教室分配”。他兴奋地画出顶点学生、课程、教师、教室边定义为“选课”“授课”“使用”。结果卡在“如何表示‘同一教师不能同时上两门课’”——这本质上是个时间约束而图论的边只表达静态关联无法承载“时间窗口”“资源占用时长”等动态属性。正确做法是切换建模视角把“时间段”作为顶点如“周一8:00-9:40”“周一10:00-11:40”边表示“冲突”同一教师的两个时段不能同时被占用。这时问题转化为图着色用最少颜色即最少教师数给顶点着色使相邻顶点不同色。哈工大慕课第4讲末尾提到的“考试安排问题”正是此思路的标准案例——它提醒我们当约束涉及“互斥”“资源竞争”时优先考虑着色模型而非盲目连边。5.2 教训二欧拉路径≠实际最优路径B同学用欧拉回路解物流路径把仓库和客户设为顶点道路设为边目标是“走遍所有道路送完货”。但现实是有些道路是单行道有向边有些路段货车禁行需删边而客户只在特定时段收货时间窗约束。当他按欧拉算法生成路径后发现第三站客户已下班——算法完美业务崩盘。根源在于混淆了数学理想条件与工程现实约束。欧拉图要求“所有边必须走且仅走一次”但物流中“重复路过某条路”完全可接受关键是总里程最短。此时应切换到最短路径算法如Dijkstra或车辆路径问题VRP模型。慕课答案资源里特意在第4讲附录标注“欧拉应用限于无时间窗、无载重限制、道路双向通行的纯巡检场景如市政井盖普查”。5.3 教训三补图判定别死记结论先画最小反例C同学背下“若G不连通则G的补图必连通”结果在考试中遇到6顶点图G由两个不相交的三角形组成即K₃K₃。他认定G不连通便断言补图连通却忘了验证——实际上这种G的补图是“完全二部图K₃,₃”确实连通。但若G是“一个孤立点一个5顶点完全图K₅”G不连通其补图却是“一个孤立点K₅的补图即5个孤立点”共6个连通分支不连通这个反例揭示了关键补图连通性取决于原图的连通分支结构而非单纯“是否连通”。正确策略是记住口诀“原图若有孤立点补图必连通原图若分裂为大小悬殊的块补图可能不连通”。从那以后我每次遇到补图题都强制先画两个极端案例一个孤立点大团一个均等小团——用图形代替死记错误率直降80%。希望帮到你。本文还有配套的精品资源点击获取
