离散数学 2：图论
学会用图描述关系，掌握连通性、特殊图与生成树
课程介绍
图是描述事物之间关系最强的数学模型：社交网络、地铁线路、知识图谱本质上都是图。这门课从哥尼斯堡七桥问题讲起，配合大量图示和例题，带你学习图的定义与表示、度数与握手定理、通路回路与连通性，以及欧拉图、哈密顿图、二部图、平面图等特殊图，最后掌握树的性质与两种最小生成树算法。学完后你能用图论语言建模实际问题，为学习图搜索、最短路径等图算法打下理论基础，适合计算机专业学生和算法学习者。
学完你将能够
- 掌握图、顶点、边、度等基本概念
- 用邻接矩阵与邻接表表示图
- 运用握手定理并判定图的连通性
- 判别欧拉图、哈密顿图与二部图
- 了解平面图、欧拉公式与图的着色
- 掌握克鲁斯卡尔与普里姆最小生成树算法
课程大纲
第1章 图的基本概念 6 个要点
- 从哥尼斯堡七桥问题认识图
- 有向图、无向图与顶点度数
- 握手定理及其应用
- 完全图、正则图、子图与补图
- 图的同构判定
- 邻接矩阵、关联矩阵与邻接表
第2章 图的连通性 5 个要点
- 通路、回路及其分类
- 可达性与无向图连通分支
- 强连通、单向连通与弱连通
- 点割集、边割集与连通度
- 最短路径问题简介
第3章 特殊图 6 个要点
- 欧拉图的定义、判定与应用
- 哈密顿图的定义与必要条件
- 二部图、完全二部图与匹配
- 平面图与欧拉公式
- 库拉托夫斯基定理
- 对偶图与图的着色
第4章 生成树 6 个要点
- 树的定义与等价性质
- 生成树的概念与存在性
- 最小生成树问题
- 克鲁斯卡尔算法
- 普里姆算法的步骤
- 根树、有序树与二叉树