《图论及其在计算机科学中的应用》求取 ⇩

第一章 引论1

第一节 几个有名的图论问题1

第二节 什么是图？3

第三节 哥尼斯堡七桥问题的解5

习题11

第二章 通路和回路14

第一节 同构图14

第二节 子图15

第三节 边链、通路和回路16

第四节 连通图、非连通和成分20

第五节 欧拉图22

第六节 图的运算25

第七节 欧拉图的进一步讨论28

第八节 哈密尔顿通路和回路29

习题33

第三章 有向图36

第一节 什么是有向图？36

第二节 有向图的种类37

第三节 成对比较和竞赛38

第四节 在逻辑上的应用41

习题43

第四章 树44

第一节 树的概念和认识44

第二节 树的性质46

第三节 根树和二元树49

第四节 支撑树51

第五节 基本回路53

第六节 怎样找出所有的生成树54

习题57

第一节 割集58

第五章 割集和割点58

第二节 割集的性质59

第三节 图中所有的割集60

第四节 基本回路和割集62

习题64

第六章 图的矩阵表示65

第一节 关联矩阵65

第二节 回路矩阵68

第三节 基本回路矩阵和回路矩阵的秩70

第四节 割集矩阵71

第五节 Af、Bf和Cf之间的关系74

第六节 在开关网络中的应用76

第七节 邻接矩阵80

第八节 最小支撑树82

习题84

第七章 平面图86

第一节 公用设备问题86

第二节 平面图概念87

第三节 地图四色问题90

第四节 欧拉公式92

第五节 分块问题94

第六节 两个典型的非平面图96

第七节 五色定理99

习题103

第八章 最短通路算法104

第一节 最短通路问题104

第二节 Dijkstra算法105

第三节 任意两点间的最短通路109

习题114

第一节 二分图115

第九章 覆盖和匹配115

第二节 覆盖116

第三节 匹配118

第四节 匈牙利算法122

第五节 库恩-蒙克莱斯算法126

习题129

第十章 网络的最大流问题131

第一节 网络流的基本概念131

第二节 最大流基本定理134

第三节 标号法139

第四节 最小费用流问题145

习题149

第十一章 中国邮递员问题152

习题159

第十二章 旅行售货员问题161

第一节 TSP的表示161

第二节 分支和界限方法163

第三节 快速TSP算法167

习题169

参考文献170