课程信息#

• 课程名称：图论与算法（Graph Theory and Algorithms, GTA）
• 主讲教师：程龚 教授
• 授课对象：计算机相关专业本科生和研究生
• 主要教材：《图论与算法》，程龚编著，清华大学出版社（免费发放纸质版，直至教材面市）
• 考核方式：平时成绩40% + 期末开卷考试60%
• 前导课程：离散数学、数据结构
• 联系方式：QQ群号663740856
• 上机地点：基础实验楼乙124

课程简介#

人与人之间的社交关系、生态环境中的食物链、互联网中路由器之间的连接，人们的日常生活中有许多这样的图和网络，影响着生活的方方面面。社交关系是否丰富、食物链是否稳定、路由器的连接有多强的容错性，要回答这些问题，需要从数学的角度将这些图和网络恰当地表示出来，在此基础上，采用合适的方式对问题进行建模，最终找到算法加以解决。这些实际需求推动了图论的发展。

事实上，图论是研究图和网络的数学分支，它将集合元素间的二元关系表示为由顶点和边组成的数学结构，研究这些结构的各种性质。图论中有许多易懂难解的问题，充满思想性和技巧性，十分适合训练学生的逻辑思维，并进一步提高算法设计与分析能力。图论中的典型模型和算法，不仅为学生进一步学习组合优化等提供基础支撑，也能在众多领域中找到应用范例，从而为未来的学习研究提供一种有力的工具。

教学周历#

• 第01周：图的基本概念
• 第02周：连通和遍历
• 第03周：上机编程（连通和割点）
• 第04周：圈和遍历
• 第05周：连通度
• 第06周：上机编程（欧拉迹和块）
• 第07周：匹配
• 第08周：赋权图和有向图
• 第09周：上机编程（最大匹配和最大流）
• 第10周：论文报告
  • 论文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
• 第11周：独立、覆盖和支配
• 第12周：染色
• 第13周：平面
• 第14周：上机编程（可平面性）
• 第15周：期末考试
• 第16周：端午停课