图论及其在计算机科学中的应用PDF电子书下载

第一章 引论 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