图论课程主页


南京大学计算机科学与技术系

图论介绍


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

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

课程信息


教师:程龚 副教授
授课对象:主要面向计算机专业二、三年级本科生,以及研究生
教材:《图论与网络流理论》,高随祥,高等教育出版社
主要参考书:《图论导引》第2版,Douglas B. West,机械工业出版社
考核方式:平时成绩40%,期末闭卷考试60%
前导课程:离散数学 (必须先修),算法设计与分析 (建议先修)

教学周历


  1. 图的基本概念 (1.1, 1.5, 1.6)
  2. 割点、割边和连通度 (2.1, 2.2)
  3. k-连通图 (2.3, 2.4)
  4. 匹配的概念 (3.1, 3.2)
  5. 最大匹配算法 (增广路算法、Hopcroft-Karp算法;Edmonds算法)
  6. 中国邮递员问题和旅行商问题 (4.2, 4.4)
  7. 支配集、点独立集和点覆盖集 (5.1)
  8. 边独立集和边覆盖集 (5.2)
  9. 平面图的概念 (7.1, 7.2, 7.4)
  10. 可平面图的判断 (7.3;DMP算法)
  11. 边染色和点染色 (6.1, 6.2, 6.5)
  12. 平面图的面染色和有向图 (7.7, 8.1, 8.2, 8.3, 8.5)
  13. 网络流 (9.1, 9.2)
  14. 习题讲解
  15. 图论的应用 (讨论课)
  16. 期末考试

教师与助教


本课程由程龚副教授主讲,学生可以通过如下方式联系:

办公室电子邮件
程龚南京大学仙林校区计算机科学技术楼309室gcheng@nju.edu.cn
助教:谷雨南京大学仙林校区计算机科学技术楼413室
助教:刘达欣南京大学仙林校区计算机科学技术楼811室
助教:刘庆霞南京大学仙林校区计算机科学技术楼811室
助教(OJ):丁文韬南京大学仙林校区计算机科学技术楼811室

更多资源