!!课程信息
* 课程名称:图论与算法(Graph Theory and Algorithms, __GTA__)
* 主讲教师:[程龚|程龚] 教授
* 授课对象:计算机相关专业本科生和研究生
* 主要教材:《图论与算法》,程龚编著,清华大学出版社
* 考核方式:平时成绩40% + 期末开卷考试60%
* 前导课程:离散数学、数据结构
* 联系方式:QQ群号663740856
* 上机地点:基础实验楼乙125

!!课程简介

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

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

!!教学周历
* 第01周:[图的基本概念|GTA/1.pdf]
* 第02周:[连通和遍历|GTA/2.pdf]
* 第03周:上机编程(连通和割点)
* 第04周:[圈和遍历|GTA/3.pdf]
* 第05周:[连通度|GTA/4.pdf]
* 第06周:上机编程(欧拉迹和块)
* 第07周:[匹配|GTA/5.pdf]
* 第08周:[赋权图和有向图|GTA/6-7.pdf]
* 第09周:上机编程(最大匹配和最大流)
* 第10周:论文报告
** 论文1,学号后2位 % 4 = 1:[Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling|https://doi.org/10.1145/2463676.2465315]
** 论文2,学号后2位 % 4 = 2:[Fast Shortest-Path Distance Queries on Road Networks by Pruned Highway Labeling|https://doi.org/10.1137/1.9781611973198.14]
** 论文3,学号后2位 % 4 = 3:[Dinitz' Algorithm: The Original Version and Even's Version|https://doi.org/10.1007/11685654_10]
** 论文4,学号后2位 % 4 = 0:[A New Approach to the Maximum-Flow Problem|https://doi.org/10.1145/48014.61051]
** 论文5,所有人可选:[Keyword Search over Knowledge Graphs via Static and Dynamic Hub Labelings|https://doi.org/10.1145/3366423.3380110]
* 第11周:[独立、覆盖和支配|GTA/8.pdf]
* 第12周:[染色|GTA/9.pdf]
* 第13周:[平面|GTA/10.pdf]
* 第14周:上机编程(可平面性)
* 第15周:期末考试
* 第16周:端午停课