图论与网络最优化算法

第1章图与网络的基本概念1.1绪论1.2一些基本概念1.3图的矩阵表示1.4图在计算机中的存储1.5算法及其计算复杂性习题1

第2章树2.1路径与连通2.2有向图的连通性2.3图的搜索2.4树及其性质2.5生成树算法2.6有向树习题2

第3章连通性3.1连通度3.2割边、割集、割点3.3块与块划分3.4可靠网络的设计习题3

第4章路径算法4.1最短路径问题4.2最短路径问题的一些扩展4.3最优路径4.4关键路径4.5最短路径算法的应用习题4

第5章匹配5.1匹配的概念5.2匹配基本定理、5.3二部图的最大匹配5.4二部图的最大权匹配5.5一般图的最大匹配5.6一般图的最大权匹配5.7匹配的应用习题5

第6章行遍性问题6.1欧拉图6.2中国邮递员问题6.3有向欧拉图6.4中国邮递员问题的应用与推广6.5哈米尔顿图6.6有向哈米尔顿图6.7哈米尔顿圈的寻迹6.8流动推销员问题6.9TSP的近似算法6.10TsP的分枝定界法6.11旅行推销员问题的应用习题6

第7章平面图7.1平面图的概念7.2欧拉公式7.3平面图的对偶图7.4库拉托夫斯基定理7.5可平面性算法7.6图的交叉和厚度习题7

第8章图的着色8.1边色数8.2时间表问题8.3支配集与独立集8.4支配数、覆盖数和独立数的计算8.5支配集与独立集的应用8.6点色数8.7色多项式8.8色数的应用和算法习题8

第9章网络流问题9.1流与截集9.2最大流最小截集定理9.3ford和fulkerson标记法9.4Dinits法9.5最大流问题的应用与推广9.6最小费用流9.7有向图的中国邮递员问题习题9参考文献