图论

第一章图

1.1从哥尼斯堡七桥问题谈起

1.2图的基本概念

1.3轨道和圈

*1.4Brouwer不动点定理

1.5求最短轨长度的算法

*1.6图上博弈

习题

第二章树

2.1树的定义与性质

2.2生成树的个数

2.3求生成树的算法

2.4求最优树的算法

2.5有序二元树

2.6n顶有序编码二元树的数目

*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.6Ramsey数

习题

第六章Euler图和Hamilton图

6.1Euler图

6.2中国邮递员问题

6.3Hamilton图

习题

第七章有向图

7.1弱连通、单连通与强连通

7.2循环赛图、有向轨和王

7.3有向Hamilton图

习题

第八章最大流的算法

8.12F算法

*8.2Dinic分层算法

8.3有上下界网络最大流的算法

8.4有供需要求的网络流算法

8.5关于PERT的两个问题

习题

第九章连通度

9.1顶连通度

9.2边连通度

*9.3一种边数最少的κ连通图

习题

第十章图的线性空间与矩阵

10.1图的线性空间

10.2图矩阵

10.3开关网络

习题

第十一章图论中的NPC问题

11.1问题、实例和算法的时间复杂度

11.2Turing机和NPC

11.3满足问题和Cook定理

11.4图论中的一些NPC问题

习题

习题解答与提示

参考文献

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