课程信息#
- 课程名称：图论与算法（Graph Theory and Algorithms, GTA）
- 主讲教师：程龚 教授/博导
- 授课对象：计算机相关专业本科生和研究生
- 教材教辅：
- 主要教材：《图论与算法（第一卷）：基础入门》，程龚编著，免费发放纸质版
- 辅助教材：《图论与网络流理论》，高随祥编著，高等教育出版社
- 主参考书：《图论导引（原书第2版）》，Douglas B. West著，机械工业出版社
- 考核方式：平时成绩40% + 期末开卷考试60%
- 前导课程：离散数学、数据结构
- 联系方式：QQ群号xxx
课程简介#
人与人之间的社交关系、生态环境中的食物链、互联网中路由器之间的连接，人们的日常生活中有许多这样的图和网络，影响着生活的方方面面。社交关系是否丰富、食物链是否稳定、路由器的连接有多强的容错性，要回答这些问题，需要从数学的角度将这些图和网络恰当地表示出来，在此基础上，采用合适的方式对问题进行建模，最终找到算法加以解决。这些实际需求推动了图论的发展。
事实上，图论是研究图和网络的数学分支，它将集合元素间的二元关系表示为由顶点和边组成的数学结构，研究这些结构的各种性质。图论中有许多易懂难解的问题，充满思想性和技巧性，十分适合训练学生的逻辑思维，并进一步提高算法设计与分析能力。图论中的典型模型和算法，不仅为学生进一步学习组合优化等提供基础支撑，也能在众多领域中找到应用范例，从而为未来的学习研究提供一种有力的工具。
教学周历#
- 第01次课：图的基本概念
- 第02次课：连通和遍历
- 第03次课：上机编程（割点和割边）
- 第04次课：圈和遍历
- 第05次课：连通度
- 第06次课：上机编程（欧拉迹）
- 第07次课：匹配
- 第08次课：网络
- 第09次课：上机编程（最大匹配和最大流）
- 第10次课：上台报告（图论与算法的研究）
- 第11次课：边的独立、覆盖和支配
- 第12次课：顶点的独立、覆盖和支配
- 第13次课：染色
- 第14次课：平面性
- 第15次课：平面图的染色
- 第16次课：期末考试