本书系统阐述图论与算法图论的基本概念、理论、算法及其应用，建立图的重要矩阵与线性空间，论述计算复杂度理论中的NP完全性理论和著名的一些NPC问题等。

本书概念明确，立论严谨，语言流畅生动，注重算法分析及其有效性；内容全面深入，可读与可教性强，是一部理想的图论基础性著作。

本书系统阐述图论与算法图论的基本概念、理论、算法及其应用，建立图的重要矩阵与线性空间，论述计算复杂度理论中的NP完全性理论和著名的一些NPC问题等。

本书概念明确，立论严谨，语言流畅生动，注重算法分析及其有效性；内容全面深入，可读与可教性强，是一部理想的图论基础性著作。

本书读者对象为高等院校数学、计算机科学、信息与网络等专业的大学生与研究生，以及科研工作者与图论爱好者。

第一章 图

 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问题

 习题

习题解答与提示

参考文献