《21世纪高等院校教材：图论》系统阐述图论与算法图论的基本概念、理论、算法及其应用，建立图的重要矩阵与线性空间，论述计算复杂度理论中的NP完全性理论和的一些NPC问题等。《21世纪高等院校教材：图论》概念明确、立论严谨，语言流畅生动，注重算法分析及其有效性；内容全面深入，可读与可教性强，是一部理想的图论基础性著作。
目录
- 章 图
- 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 有供需要求的网络流算法
- 习题
- 第九章 连通度
- 9.1 顶连通度
- 9.2 边连通度
- 9.3 一种边数少的k连通图
- 习题
- 第十章 图的线性空间与矩阵
- 10.1 图的线性空间
- 1O.2 图矩阵
- 习题
- 第十一章 图论中的NPC问题
- 11.1 问题、实例和算法的时间复杂度
- 11.2 Turing机和NPC
- 11.3 满足问题和Cook定理
- 11.4 图论中的一些NPC问题
- 习题
- 习题解答与提示
- 参考文献
