《图论基础教程》求取 ⇩

目录1

导言1

第一章　图的基本概念17

§1·1　图是什么17

§1·2　图的定义22

§1·3　子图24

§1·4　路26

第一章习题28

第二章　树29

§2·1　基本概念29

§2·2　部分树33

§2·3　最小部分树35

第二章习题41

第三章　最短路问题42

§3·1　第一类最短路问题43

§3·2　距离表——第二类最短路问题46

§3·3　第一类选址问题——使最大服务路程达到最小49

§3·4　第二类选址问题——使运输量达到最52

小52

第三章习题56

第四章　有向图58

§4·1　有向图的定义58

§4·2　有根图与有根树61

§4·3　有根图与有根部分树64

§4·4　最小有向部分树的算法68

第四章习题75

第五章　运输网路77

§5·1　网络流图与最大流77

§5·2　割切81

§5·3　最大流与最小割切定理83

§5·4　寻求最大流的标号法86

第五章习题92

第六章　匹配94

§6·1　匹配的定义95

§6·2　偶图与其上的最大匹配算法96

§6·3　交错链与增长链100

§6·4　交错树104

§6·5　带花的树107

§6·6　一般图的最大匹配算法111

第六章习题117

第七章　可行遍性问题119

§7·1　一笔画与欧拉巡回119

§7·2　欧拉路与欧拉回路的Fteury算法124

§7·3　中国邮递员问题125

§7·4　哈密尔顿问题129

§7·5　旅行推销员问题130

第七章习题136

第八章　图的可平面性140

§8·1　图的平面嵌入141

§8·2　欧拉公式144

§8·3　平面性的检查148

§8·4　平面的实现153

第八章习题166

第九章　图的边染色与点染色168

§9·1　图的边染色168

§9·2　图的顶点染色171

§9·3　点色数的一个求法173

§9·4　印刷电路板的分层问题176

第九章习题178

§10·1　有向图的关联矩阵179

的部分树的计数179

第十章　有向图的关联矩阵与连通图中179

§10·2　基本关联矩阵182

§10·3　部分树的计数定理184

§10·4　有根部分树的计数定理188

§10·5　无向图的部分树的计数196

第十章习题198

附录—Binet—Cauchy定理198

参考书目202