《图论及其应用》求取 ⇩

第一章 引论1

1 Konisberg桥问题(或Euler回路问题)1

2 路径问题2

3 应用举例6

4 Hamilton回路问题10

5 Ramsey问题11

习题12

第三章 基本概念13

1 图的概念13

2 同形14

3 点与边的关联关系15

4 道路与回路17

5 Euler回路17

6 Hamilton道路19

7 图的矩阵表示法22

2 例24

8 道路矩阵25

9 道路矩阵的Warshall算法27

10 强连通概念与递归概念29

习题31

第三章 树33

1 树的概念33

3 基本性质37

4 基本关联矩阵40

5 树的数目41

6 内向树与外向树46

7 二元树50

8 Huffman树52

9 搜索树55

10 DFS算法56

11 旅行商问题59

12 最佳匹配问题62

习题65

第四章 最佳路径问题67

1 最佳路径问题67

2 求最短路径的Dijkstra算法68

3 最短树问题70

4 最短树的Kruskal算法72

5 求任意两点间的最短距离73

6 求任意两点距离的Warshall算法77

7 关键路径法78

1 平面图81

2 Euler公式81

习题81

第五章 平面图81

3 极大平面图82

4 Kuratowski图83

5 Kuratowski定理84

6 对偶图88

7 五色问题90

8 Minty引理91

习题92

第六章 电路网络93

1 回路矩阵93

2 回路矩阵的若干性质95

3 基本关联矩阵Bk与基本回路矩阵C？的关系97

4 割集矩阵99

5 克希荷夫定律103

6 电路问题104

7 状态变量法理论基础106

8 状态变量法107

9 状态变量法举例114

10 若干特殊性形127

11 图论在电路中的其它应用137

习题144

第七章 图与代数方程组145

1 矩阵的Cates图145

2 代数方程组与Mason信号流图146

3 图的运算147

4 行列式的展开法151

5 代数方程组的Coates解法153

6 Mason公式154

7 Mason公式的证明158

习题165

第八章 匹配理论167

1 基本概念167

2 关于匹配的基本定理169

3 Hall定理170

4 匈牙利算法与例170

5 Konig定理172

6 最佳匹配173

7 最佳匹配的算法与例177

习题181

1 网络流问题与最大流182

第九章 运输网络与开关网络182

2 割切183

3 Ford-Fulkerson最大流与最小割切定理185

4 标号法186

5 开关函数190

6 传输矩阵与连接矩阵191

7 简单接触网络的实现和算法192

习题200

第十章 图的算法201

1 图的连通性判断201

2 树的生成202

3 Minty算法和Mayeda-Seshu算法207

4 DFS算法的基本思想212

5 无向图的DFS算法213

6 有向图的DFS算法215

7 图的块划分216

8 强连通块的划分220

第十一章 色数问题225

1 问题的提出225

3 独立集概念及其应用227

4 求极大独立集的布尔代数算法229

5 支配集232

6 色数的一种求法233

7 色数多项式235

2 色数及其性质236

8 应用举例237

习题238