图论导引

第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 Turdn定理

练习题

第8章 有向图

8.1 有向图的概念

8.2 有向图的矩阵

8.3 竞赛图

练习题

第9章 网络流

9.1 流的基本概念

9.2 最大流最小割定理

9.3 求最大流的标号法

9.4 整数流

练习题

第10章 随机图

10.1 随机图的概念

10.2 期望

10.3 方差

练习题

参考文献

《图论导引》系统讨论了图论的基本理论与方法，给出了一些基本算法及应用.书中除了包含树、欧拉图与汉密尔顿图、匹配、平面图、着色、Ramsey数、有向图、网络流等内容外，为了读者更深层次地思考，还介绍了通常一般图论书不包括的双圈覆盖、整数流、随机图等内容。
　　《图论导引》的特点就是包括大量的实际例子.在大部分章节的开头都以实际应用为引例，引出本部分所讲内容，然后对所关联的知识点逐渐展开讨论，采用问题式教学的编写模式，目的是激发学生学习图论的积极性。
　　《图论导引》既可作为大学数学、信息与计算科学、计算机类等许多专业高年级本科生的图论教材，也可作为低年级研究生的图论教材或参考书。