第1讲 图的基本概念

1.1 课前准备-图论

1.2 简史

1.3 图

1.4 图的表示

1.5 图模型

1.6 子图

1.7 度

1.8 正则图

1.9 同构

课件

第1讲测验

第2讲 连通图、补图、偶图

2.1 路、圈

2.2 连通图

2.3 判定是否连通

2.4 几类证明方法

2.5 判定是否有圈

2.6 关于路和圈的一个定理

2.7 补图

2.8 双图

2.9 图兰定理

2.10 极图理论

第2讲测验

第3讲 欧拉图

3.1 欧拉图、欧拉定理

3.2 欧拉定理的扩展

第3讲测验

第4讲 哈密顿图

4.1 背景

4.2 哈密顿图

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

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

第４讲测验

第5讲 图的表示、带权图

5.1 邻接矩阵

5.2 邻接表

5.3 关联矩阵

5.4 图解

5.5 带权图

第5讲测验

第6讲 树、割集

6.1 树的定义

6.2 树的性质

6.3 极小连通图

6.4 树的中心

6.5 生成树

6.6 最小生成树

6.7 割点

6.8 割点的性质

第6讲测验

第7讲 图的连通度

7.1 背景

7.2 顶点连通度和边连通度

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

7.4 n连通

7.5 明格尔定理

7.6 柯尼希定理

7.7 网络流问题

第7讲测验

第8讲 匹配问题

8.1 独立集

8.2 偶图的匹配

8.3 偶图匹配的条件

8.4 相异代表系

第8讲测验

第9讲 平面图

9.1 背景

9.2 平面图的定义

9.3 欧拉公式

9.4 例题

9.5 非哈密顿平面图

9.6 库拉托夫斯基定理

第9讲测验

第10讲 图的顶点着色问题

10.1 图的顶点着色

10.2 色数的上、下界

10.3 四色定理 vs 五色定理

第10讲测验

第11讲 有向图的基本概念

11.5 有向路、有向圈

11.6 邻接矩阵

11.1 有向图的表示

11.2 有向图中顶点的度

11.3 有向完全图

11.4 有向图的同构

第11讲测验

第12讲 有根树、有序树、比赛图

12.1 有根树、有序树

12.2 比赛图

第12讲测验