图的方法

第1章 图的基本概念

1.1 图的概念

1.1.1 哥尼斯堡(K6nigsberg)七桥问题

1.1.2 图的概念

1.1.3 子图与补图

1.1.4 图与逻辑结构

习题1.1

1.2 结点的度数

1.2.1 结点的度数

1.2.2 完全图

习题1.2

1.3 图的连通性

1.3.1 路径与回路

1.3.2 无向图与有向图的连通性

习题1.3

1.4 图的矩阵表示

1.4.1 图的邻接矩阵

1.4.2 有向图的可达矩阵

1.4.3 赋权图的邻接矩阵

习题1.4

复习题

第2章 树

2.1 无向树

2.1.1 无向树的性质

2.1.2 生成树

2.1.3 最小生成树

习题2.1

2.2 有向树

2.2.1 有向树

2.2.2 根树

2.2.3 有序树

习题2.2

2.3 二叉树的应用

2.3.1 二叉树

2.3.2 前缀码

2.3.3 最优树与最优树的形成

2.3.4 遍历二叉树

习题2.3

复习题

第3章 特殊的图

3.1 欧拉图

3.1.1 欧拉图的充要条件

3.1.2 中国邮路问题

习题3.1

3.2 汉密尔顿图

3.2.1 汉密尔顿图及其充分条件

3.2.2 货郎担问题

习题3.2

3.3 二分图

3.3.1 二分图的定义

3.3.2 匹配

3.3.3 最大匹配及其求法

习题3.3

3.4 平面图

3.4.1 平面图的充要条件

3.4.2 欧拉定理及其推论

3.4.3 库拉托夫斯基定理

3.4.4 正多面体

习题3.4

复习题

第4章 图的简单应用

4.1 图的着色

习题4.1

4.2 最短路

4.2.1 狄克斯屈拉算法及其执行过程

4.2.2 最短路问题的应用

习题4.2

4.3 网络应用

4.3.1 AOV网与拓扑排序

4.3.2 AOE网与关键路径

4.3.3 网络最大流

习题4.3

复习题

附录

附录1 数学实验

附录2 参考答案

参考文献

《图的方法》是“高等数学模块化系列教材”之一，适用于计算机类各专业的专业基础课教材。《图的方法》计划课时为18课时，1学分。《图的方法》共分为四章：第1章介绍图的一些基本概念和基本性质；第2章讲述树的性质与应用；第3章介绍欧拉图、汉密尔顿图、二分图和平面图等一些具有特殊性质的图；第4章讲述图和网络的一些简单应用。每节后面都有练习题，每章后面附有复习题，帮助学生复习巩固所学知识。此外，《图的方法》最后附有数学试验和习题参考答案。《图的方法》各章均由王显金编写。