本书系统阐述图论与算法图论的基本概念、理论、算法及其应用，建立图的重要矩阵与线性空间，论述了计算复杂度理论中的NP完全性理论和著名的一些NPC问题等内容。本书适用于高等院校数学、计算机科学、信息与网络等专业的大学生与研究生，以及科研工作者与图论爱好者。

　　图论是离散数学的骨干分支，离散数学则是计算机科学技术与网络信息科学的理论基础。多年来，为了实现高速计算的目的，数学促进了计算机科学的形成与发展。例如图灵机的数学理论为计算机的诞生打下了基础；另一方面，随着计算机科学在社会发展中作用的日益提升，它又反过来促进数学的发展。例如1976年，伊利诺大学的Appel和Haken用计算机证明了四色猜想成立。我国著名数学家吴文俊、张景中等用计算机进行了几何定理的机器证明，发展出一套成熟的机器证明的新理论与新方法。离散数学，特别是图论，近年来如异军突起般蓬勃发展，实乃数学与计算机科学交互作用的范例。图论与计算机科学结盟解决了有关离散事物的结构与关系当中定性与定量的各种优化问题。在信息科学与网络技术迅猛发展的时代背景之下，接受图论教育与进行图论研究成了众多相关的青年科学家与工程师的强烈追求。图论自身的美好形象，诸如它的强有力的逻辑，漂亮的图形，高明的数学技巧等等，也对每个爱好科学的年轻人产生了挥之不去的诱惑，在高等学校的教学当中，图论课成了广大大学生和研究生争相选修的最受欢迎的热门课程之一。
　　学习图论，除了能使我们采用它的成果与方法之外，同样重要的是它能培养我们思考问题与解决问题的能力。图论中的问题，看似通俗简单，却往往含有非平凡的难度，每个学习研究图论的人在它面前必须全力以赴、严肃认真地思考问题，有时百思方得其解，有时则是百思仍不得其解的！

第一章 图
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问题
习题
习题解答与提示
参考文献

　　当时数学界并未对欧拉解决七桥问题的意义有足够的认识，甚至仅仅视其为一个数学游戏而已，图论诞生后并未及时获得足够的发展。1936年，匈牙利数学家柯尼希（Konig）出版《有限图与无限图理论》，这是图论的第一部专著，它总结了图论200年的成果，是图论发展的第一座里程碑。此后，图论进入发展与突破的快车道，又经过半个多世纪的发展，现已成长为数学科学的一个独立的重要学科。它的分支很多，例如图论、算法图论、极值图论、网络图论、代数图论、随机图论、模糊图论、超图论等等。由于现代科技尤其是大型计算机的迅猛发展，使图论大有用武之地，无论是数学、物理、化学、天文、地理、生物等基础科学，还是信息、交通、战争、经济乃至社会科学的众多问题，都可以应用图论方法予以解决。图论又是计算机科学最重要的基础之一。
　　1976年世界上发生了不少大事，其中有一件是美国数学家Appel和Haken在Koch的协作之下，用计算机证明了图论难题——四色猜想（4CC）：
　　任何地图，用四种颜色，可以把每国领土染上一种颜色，使邻国异色。
　　4CC的提法和内容十分简朴，以至于可以向随便一个人（哪怕他不识字）在几分钟之内讲清楚。1852年英国的一个大学生格思里（Guthrie）向他的老师德·摩根（DeMorgan）请教这个问题。德·摩根是当时十分有名的数学家，他不能判断这个猜想是否成立，于是很快在数学界流传开来。