应用图论PDF电子书下载

第一章 图的基本概念 1

1.1 引言 1

1.2 图的概念 2

1.2.1 图的定义 2

1.2.2 顶点的度 3

1.2.3 图的同构 4

1.3 子图 5

1.4 路与连通 7

1.4.1 路与圈 7

1.4.2 连通性 8

1.4.3 二分图的一个特征 8

1.5 有向图 9

1.5.1 基本概念 10

1.5.2 存在有向路和有向圈的条件 11

1.5.3 不存在有向圈的条件 11

习题一 13

第二章 树与割集 15

2.1 树及其性质 15

2.1.1 树的定义 15

2.2.2 树的特征 15

2.2 生成树 17

2.2.1 生成树 17

2.2.2 生成树的构造 17

2.2.3 基本圈 18

2.2.4 生成树的数目 18

2.3 割集 21

2.3.1 割集 21

2.3.2 割集的性质 21

2.3.3 割集的环和 22

2.3.4 基本割集 23

2.3.5 割点 24

2.4.1 （点）连通度 25

2.4 图的连通度 25

2.4.2 边连通度 26

2.5 最优生成树 27

2.6 单向树 29

2.6.1 单向树 29

2.6.2 有序树 30

2.6.3 Huffman树 32

习题二 35

第三章 图的矩阵表示 36

3.1 关联矩阵 36

3.1.1 无向图的关联矩阵 36

3.1.2 有向图的关联矩阵 40

3.2 邻接矩阵 41

3.2.1 无向图的邻接矩阵 42

3.2.2 有向图的邻接矩阵 44

3.3.1 无向图的圈矩阵 45

3.3 圈矩阵 45

3.3.2 有向图的回路矩阵 48

3.4 割集矩阵 50

3.4.1 无向图的割集矩阵 50

3.4.2 有向图的割集矩阵 52

习题三 54

第四章 搜索技术与分枝定界法 56

4.1 搜索技术 56

4.1.1 深探法DFS 57

4.1.2 广探法BFS 59

4.1.3 α-β搜索法 59

4.2 分枝定界法 61

第五章 最短路问题 67

5.1 解最短路问题的基本方法 67

5.1.1 从一个始点v1到一个终点vn的最短路问题 67

5.1.2 求任意两顶点间的最短路问题 70

5.2.2 具有负权的有向图中的最短路 73

5.2 具有负权有向图中的最短路 73

5.2.1 赋权有向图中的最短路 73

5.3 K最短路问题 75

5.3.1 双向扫视算法基础 75

5.3.2 双向扫视算法过程 76

5.3.3 算法原理 77

习题五 82

第六章 可行遍性 83

6.1 Euler图 83

6.2 中国邮递员问题 84

6.2.1 Euler图中的最优环游 85

6.2.2 非Euler图中的最优环游 86

6.3 Hamilton图 88

6.4 旅行售货员问题 90

6.4.1 调整Hamilton圈以得到近似最优解 91

6.4.2 分枝定界法确定精确最优解 92

习题六 96

第七章 平面图 98

7.1 平面图的概念 98

7.1.1 平面图 98

7.1.2 Euler公式 99

7.1.3 极大平面图 100

7.2 图的平面性检测 102

7.2.1 Kuratowski图 102

7.2.2 平面性检测 103

7.3 对偶图 105

7.4 五色定理与四色猜想 108

习题七 110

第八章 着色、匹配与覆盖 112

8.1 色数问题 112

8.1.1 色数及其性质 112

8.1.2 色数的一种求法 113

8.1.3 色数多项式 115

8.2 匹配、覆盖及独立集 117

8.2.1 匹配 117

8.2.2 覆盖与独立集 118

8.3 二分图的匹配和覆盖 119

8.3.1 Hall定理 119

8.3.2 匹配与覆盖的关系 121

8.3.3 匈牙利算法 122

8.4 人员分派问题 124

8.4.1 人员分派问题 124

8.4.2 最优分派问题 124

习题八 128

第九章 网络流问题与选址问题 130

9.1 基本概念和定理 130

9.1.1 网络的流 130

9.1.2 割 132

9.1.3 最大流最小割定理 133

9.2 解最大流问题的标号法 135

9.3 多端最大流问题 138

9.4 选址问题 143

9.4.1 单服务设施问题 143

9.4.2 一般选址问题 148

习题九 152

第十章 流图与代数方程组 153

10.1 Mason信号流图 153

10.1.1 信号流图 153

10.1.2 线性方程组的Mason信号流图表示 153

10.1.3 信号流图的运算规则 155

10.2 Mason公式 158

10.3 矩阵与Coate流图 160

习题十 165

参考书目 166