《国论及其应用》求取 ⇩

目录1

第一章 引论1

§1 K？nisberg桥问题（或Euler回路问题）1

§2 路径问题2

§3 应用举例6

§4 Hamilton回路问题10

§5 Ramsey问题11

习题12

第二章 基本概念13

§1 图的概念13

§2 同形14

§3 点与边的关联关系15

§5 Euler回路17

§4 道路与回路17

§6 Hamilton道路19

§7 图的矩阵表示法22

§8 道路矩阵25

§9 道路矩阵的Warshall算法27

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

习题31

第三章 树33

§1 树的概念33

§2 例34

§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

习题80

第五章 平面图81

§1 平面图81

§2 Euler公式81

§3 极大平面图82

§4 Kuratowski图83

§5 Kuratowski定理84

§6 对偶图88

§7 五色问题90

§8 Minty引理91

习题92

第六章 电路网络93

§1 回路矩阵93

§2 回路矩阵的若干性质95

§3 基本关联矩阵Bk与基本回路矩阵Cf的关系97

§4 割集矩阵99

§5 克希荷夫定律103

§6 电路问题104

§7 状态变量法理论基础106

§8 状态变量法107

§9 状态变量法举例114

§10 若干特殊情形127

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

习题144

第七章 图与代数方程组145

§1 矩阵的Coates图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

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

§1 网络流问题与最大流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

§2 色数及其性质226

§3 独立集概念及其应用227

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

§5 支配集232

§6 色数的一种求法233

§7 色数多项式235

§8 应用举例237

习题238