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