第1章 图的基本概念

1.1图的发展简史

1.2图的概念

1.3顶点的度

1.4连通性

1.5图的矩阵表示

1.6图的最短路问题

练习题

第2章 树

2.1树和森林的概念

2.2树的结构及Cayley公式

2.2.1树的结构

2.2.2 Cayley公式

2.3图上的树

2.4深探树和广探树

2.5最优树

练习题

第3章 欧拉图和汉密尔顿图

3.1欧拉图

3.2汉密尔顿图

3.3中国邮递员问题

3.4货郎担问题

练习题

第4章 匹配与因子分解

4.1二部图的匹配

4.2因子分解

4.3匈牙利算法

4.4最优分派问题

练习题

第5章 平面图

5.1欧拉公式

5.2库拉托斯基定理、对偶图

5.3平面性判别算法

5.4图的曲面嵌入

5.4.1唯一平面嵌入

5.4.2曲面嵌入的基本概念和性质

练习题

第6章 着色

6.1顶点着色

6.2边着色

6.3图的顺序着色算法

6.4色多项式

6.5图的双圈覆盖

6.5.1偶子图的概念和性质

6.5.2双圈覆盖

练习题

第7章 Ramsey数

7.1图的Ramsey数

7.2 Turan定理

练习题

第8章 有向图

8.1有向图的概念

8.2有向图的矩阵

8.3竞赛图

练习题

第9章 网络流

9.1流的基本概念

9.2最大流最小割定理

9.3求最大流的标号法

9.4整数流

练习题

第10章 随机图

10.1随机图的概念

10.2期望

10.3方差

练习题

参考文献