课程概述

     随着计算机科学技术的迅速发展，作为支撑学科的离散数学正变得越来越重要。图论作为提供一种离散数学模型的应用数学学科得到了迅速发展。应用图论及其方法来解决运筹学、物理、化学、生物学、计算机科学、网络理论、信息论、社会科学以及经济管理等方面的问题已显示出了极大的优越性。同时，图论自身所取得的很大进展与它与其他数学学科，如代数学、拓扑学、概率论、数论等的紧密联系，起到了相互促进的作用。计算机科学技术的发展所产生的各种理论问题的研究需要采用现代数学中的不同理论和方法，图论是其中最典型的一种理论。因此，图论课程的教学在国内外不同层次的阶段都受到高度重视，成为了应用数学、运筹学与控制论、优化理论和计算机科学技术以及相关专业的重要课程。
      图论的内容比较广泛，作为图论教学的内容包括图的基本概念、树、连通度、图的遍历、图的着色理论、匹配、平面图、图论算法及网络等。通过本课程的学习，要求学生对图论中的基本概念和术语、基本定理及证明方法和技巧有较好的理解和掌握，对图论与计算机科学等其他学科之间的关系有一定了解，为后续相关课程的学习和进行深入地研究工作奠定良好的基础。

证书要求

本课程成绩满分100分。由以下部分构成：

考核环节

所占分值

考核与评价细则

对应课程目标

1.随堂测试

72分

每讲6道测验题，每题1分

课程目标3

课程目标4

2.讨论话题

8分

回答回帖，每个回帖1分，超过8个回帖得8分

课程目标3

课程目标4

3.网上期末考试

20分

期末考试共10题，每题2分

课程目标1

课程目标2

课程最终成绩 = 1+2+3


预备知识

数学分析、线性代数

授课大纲

第1讲 图的基本概念

1.1 课前准备-图论

1.2 简史

1.3 图

1.4 图的表示

1.5 图模型

1.6 子图

1.7 度

1.8 正则图

1.9 同构

1.10 邻接矩阵

1.11 邻接表

第1讲测验

第2讲 树、割集

2.1 树的定义

2.2 树的性质

2.3 极小连通图

2.4 树的中心

2.5 生成树

2.6 最小生成树

2.7 割点

2.8 割点的性质

第2讲测验

第3讲 连通度

3.1 路、圈

3.2 连通图

3.3 背景

3.4 顶点连通度和边连通度

3.5 顶点连通度和边连通度的关系

3.6 n连通

第3讲测验

第4讲 欧拉图

4.1 欧拉图、欧拉定理

4.2 欧拉定理的扩展

第4讲测验

第5讲 哈密顿图

5.1 背景

5.2 哈密顿图

5.3 哈密顿图判定的必要条件

5.4 哈密顿图判定的充分条件

第5讲测验

第6讲 匹配问题

6.1 独立集

6.2 偶图的匹配

6.3 偶图匹配的条件

第6讲测验

第7讲图兰定理

7.1 图兰定理

7.2极图理论

第7讲测验

第8讲 图的顶点着色问题

8.1 图的顶点着色

8.2 色数的上、下界

8.3 四色定理 vs 五色定理

第8讲测验

第9讲 平面图

9.1 背景

9.2 平面图的定义

9.3 欧拉公式

9.4 例题

9.5 非哈密顿平面图

第9讲测验

第10讲 有向图的基本概念

10.1 有向图的表示

10.2 有向图中顶点的度

10.3 有向完全图

10.4 有向图的同构

10.5 有向路、有向圈

第10讲测验

第11讲 网络流

11.1 网络流问题

第11讲测验

参考资料

1.《图论》， J.A.Bondy,U.S.R.Murty编，吴望名等译，科学出版社，1984年

2.《Graph Theory》，R.Diestel编，Springer-Verlag出版社，2003年

3.《Modern Graph Theory》，B.Bollobas编，2000年