课程信息#
- 课程名称:图论与算法(Graph Theory and Algorithms, GTA)
- 主讲教师:程龚 教授
- 授课对象:计算机相关专业本科生和研究生
- 教材教辅:
- 教材:《图论与算法(第1卷):基础入门》,程龚编著,免费发放纸质版
- 参考书:《图论与网络流理论》,高随祥编著,高等教育出版社
- 参考书:《图论导引(原书第2版)》,Douglas B. West著,机械工业出版社
- 考核方式:平时成绩40% + 期末开卷考试60%
- 前导课程:离散数学、数据结构
- 联系方式:QQ群号765549967
课程简介#
人与人之间的社交关系、生态环境中的食物链、互联网中路由器之间的连接,人们的日常生活中有许多这样的图和网络,影响着生活的方方面面。社交关系是否丰富、食物链是否稳定、路由器的连接有多强的容错性,要回答这些问题,需要从数学的角度将这些图和网络恰当地表示出来,在此基础上,采用合适的方式对问题进行建模,最终找到算法加以解决。这些实际需求推动了图论的发展。
事实上,图论是研究图和网络的数学分支,它将集合元素间的二元关系表示为由顶点和边组成的数学结构,研究这些结构的各种性质。图论中有许多易懂难解的问题,充满思想性和技巧性,十分适合训练学生的逻辑思维,并进一步提高算法设计与分析能力。图论中的典型模型和算法,不仅为学生进一步学习组合优化等提供基础支撑,也能在众多领域中找到应用范例,从而为未来的学习研究提供一种有力的工具。
教学周历#
- 第01周:图的基本概念
- 第02周:停课(延期考试)
- 第03周:连通和遍历
- 第04周:上机编程(连通和割点)
- 第05周:圈和遍历
- 第06周:连通度
- 第07周:上机编程(欧拉迹)
- 第08周:匹配
- 第09周:赋权图和有向图
- 第10周:上机编程(最大匹配和最大流)
- 第11周:独立、覆盖和支配
- 第12周:停课(五一放假)
- 第13周:论文报告
- 论文1,学号后2位 % 4 = 1:Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling
- 论文2,学号后2位 % 4 = 2:Fast Shortest-Path Distance Queries on Road Networks by Pruned Highway Labeling
- 论文3,学号后2位 % 4 = 3:Dinitz' Algorithm: The Original Version and Even's Version
- 论文4,学号后2位 % 4 = 0:A New Approach to the Maximum-Flow Problem
- 论文5,所有人可选:Keyword Search over Knowledge Graphs via Static and Dynamic Hub Labelings
- 第14周:染色
- 第15周:平面
- 第16周:上机编程(可平面性)
- 第17周:期末考试