电子科技大学图论期末通关指南（杨春老师考点精析+历年真题实战）
1. 杨春老师图论课程核心考点解析
杨春老师的图论课程在电子科技大学一直以"重点突出、逻辑清晰"著称。根据历年学生反馈和课堂笔记，我把老师反复强调的核心知识点整理为以下四大板块：
图的基本概念与性质这部分看似简单，却是考试中概念判断题的主要来源。需要重点掌握：
- 握手定理及其推论（所有顶点度数之和等于边数的两倍）
- 图的同构判定条件（不变量比较法）
- 欧拉图与哈密顿图的充要条件（特别注意老师强调的Ore定理和Dirac定理）
树与生成树是每年必考的大题模块。杨老师特别爱考：
- 最小生成树的Kruskal和Prim算法（要求能完整写出算法步骤并分析时间复杂度）
- 二叉树的性质（叶子节点数=度为2的节点数+1）
- 最优二叉树（Huffman树）的构建过程（近三年考了两次）
平面图与着色是学生普遍觉得困难的部分。需要吃透：
- 欧拉公式及其应用（计算最大平面图的边数）
- 库拉托夫斯基定理的判定方法（K5和K3,3的细分）
- 顶点着色数的计算方法（重点掌握Brooks定理）
匹配与网络流虽然难度较大，但考试占比不低：
- 二分图匹配（匈牙利算法的具体步骤）
- 最大流最小割定理（Ford-Fulkerson方法的标号过程）
- 网络单纯形法的基本思想（老师近两年新增的考点）
2. 历年真题高频题型与解题套路
分析近五年的期末试卷，我发现有几种题型几乎每年都会以不同形式出现：
2.1 概念证明题
这类题目通常占20-30分，主要考察对定理的理解。比如2021年考过： "证明：对于任何简单图G，至少有两个顶点的度数相同" 解题关键是用反证法+鸽巢原理，这是杨老师课上反复强调的经典组合。
2.2 算法应用题
最小生成树和最短路径算法每年必考一题。2020年的真题就很典型： "给出带权图，要求：(1)用Prim算法求最小生成树(2)用Dijkstra算法求v1到各顶点最短路径" 建议准备时：
- 熟记两种算法的表格写法
- 注意区分Prim和Dijkstra的松弛操作区别
- 准备时间复杂度分析的标准答案模板
2.3 综合计算题
平面图判定和着色问题常组合出题。比如2019年考题： "判断给定图是否为平面图，若是则给出平面嵌入，若不是说明原因并计算其交叉数" 应对策略：
- 先检查边数是否超过3n-6（n≥3）
- 再用库拉托夫斯基定理逐步删除边和顶点
- 着色时先用最大度数估算，再用贪心算法验证
3. 期末冲刺复习方法论
3.1 三阶段复习法
根据多位高分学长经验，最后两周建议这样安排：
第一阶段（5天）：知识体系构建
- 按章节整理思维导图（推荐XMind）
- 对每个定理自己推导一遍（如欧拉公式的证明）
- 整理易混淆概念对比表（如欧拉迹vs哈密顿圈）
第二阶段（7天）：真题实战训练
- 按年份倒序做近5年真题
- 严格计时（选择/填空控制在30分钟内）
- 对错题用红笔标注错误原因
第三阶段（2天）：考点查漏补缺
- 重点复习错题本
- 记忆常用结论（如n阶完全图的边数）
- 模拟考场环境做一套押题卷
3.2 考场时间分配技巧
根据试卷结构，我建议：
- 选择题（15题×2分）：控制在25分钟内
- 填空题（10空×3分）：20分钟
- 证明题（2题×10分）：30分钟
- 计算题（2题×15分）：35分钟
- 最后留10分钟检查
特别注意：遇到5分钟没思路的题先跳过，所有题目第一问尽量都答（通常很简单）
4. 必备公式与结论速查
4.1 图论基本公式
| 公式名称 | 表达式 | 适用条件 |
|---|---|---|
| 握手定理 | ∑deg(v)=2E | 所有无向图 |
| 欧拉公式 | n-m+f=2 | 连通平面图 |
| 树边数公式 | m=n-1 | 任何树图 |
| 完全图边数 | m=n(n-1)/2 | Kn图 |
4.2 常用算法复杂度
# 常见算法时间复杂度速查 algorithms = { "DFS/BFS": "O(n+m)", "Prim（邻接矩阵）": "O(n^2)", "Kruskal": "O(m log m)", "Dijkstra（二叉堆）": "O((n+m) log n)", "Floyd-Warshall": "O(n^3)", "匈牙利算法": "O(nm)" }4.3 易错点警示
概念混淆：
- 欧拉图要求所有边遍历一次
- 哈密顿图要求所有顶点遍历一次
计算失误：
- 平面图边数上限是3n-6（n≥3）
- 完全二分图Km,n的边数是mn
证明疏漏：
- 使用数学归纳法时要写明基例和归纳步骤
- 反证法需要明确假设和矛盾点
考前最后一天，建议把这份指南快速过一遍，重点记忆标红内容。记得带上量角器和直尺（画图题可能用到），保持平常心应对考试。去年有位学长就是按这个方法复习，最终考了93分。