普通高等教育“十一五”国家级规划教材：图论（第2版）

　　第一章  图
　　1.1  从哥尼斯堡七桥问题谈起
　　1.2  图的基本概念
　　1.3  轨道和圈
　　*1.4  Brouwer不动点定理
　　1.5  求最短轨长度的算法
　　*1.6  图上博弈
　　习题
　　第二章  树
　　2.1  树的定义与性质
　　2.2  生成树的个数
　　2.3  求生成树的算法
　　2.4  求最优树的算法
　　2.5  有序二元树
　　2.6  n顶有序编码二元树的数目
　　*2.7  最佳追捕问题
　　习题
　　第三章  平面图
　　3.1  平面图及其平面嵌入
　　3.2  平面图Euler公式
　　3.3  极大平面图
　　3.4  平面图的充要条件
　　*3.5  平面嵌入的灌木生长算法
　　习题
　　第四章  匹配理论及其应用
　　4.1  匹配与许配
　　4.2  匹配定理
　　4.3  匹配的应用
　　4.4  图的因子分解
　　习题
　　第五章  着色理论
　　5.1  图的边着色
　　5.2  图的顶着色
　　*5.3  四色猜想为真的机器证明
　　5.4  颜色多项式
　　5.5  独立集
　　5.6  Ramsey数
　　习题
　　第六章  Euler图和Hamilton图
　　6.1  Euler图
　　6.2  中国邮递员问题
　　6.3  Hamilton图
　　习题
　　第七章  有向图
　　7.1  弱连通、单连通与强连通
　　7.2  循环赛图、有向轨和王
　　7.3  有向Hamilton图
　　习题
　　第八章  最大流的算法
　　8.1  2F算法
　　*8.2  Dinic分层算法
　　8.3  有上下界网络最大流的算法
　　8.4  有供需要求的网络流算法
　　8.5  关于PERT的两个问题
　　习题
　　第九章连通度
　　9.1  顶连通度
　　9.2  边连通度
　　*9.3  一种边数最少的κ连通图
　　习题
　　第十章  图的线性空间与矩阵
　　10.1  图的线性空间
　　10.2  图矩阵
　　10.3  开关网络
　　习题
　　第十一章  图论中的NPC问题
　　11.1  问题、实例和算法的时间复杂度
　　11.2  Turing机和NPC
　　11.3  满足问题和Cook定理
　　11.4  图论中的一些NPC问题
　　习题
　　习题解答与提示
　　参考文献

　　《图论(第2版)》系统阐述图论与算法图论的基本概念、理论、算法及其应用，建立图的重要矩阵与线性空间，论述计算复杂度理论中的NP完全性理论和著名的一些NPC问题等。《图论(第2版)》概念明确，立论严谨，语言流畅生动，注重算法分析及其有效性；内容全面深入，可读与可教性强，是一部理想的图论基础性著作。
　　《图论(第2版)》读者对象为高等院校数学、计算机科学、信息与网络等专业的大学生与研究生，以及科研工作者与图论爱好者。