本书是一本有一定学术参考价值的理工科研究生教学用书。它是根据作者多年从事研究生图论教学的经验，并结合国内外优秀教材的长处和图论的新近发展状况编写而成。全书共十章，分别讨论图的基本概念、树、图的连通度、Enler图与Hamilton图、匹配与因子分解、平面图、图的着色、Ramsey定理、有向图以及代数图论中的一些内容。其内容详尽，既有基本内容，又有提高内容；不仅较为全面地介绍了图论中的一些基本概念，基本理论和基本方法，而且还反映了近期图论及其应用中的一些研究课题和结论。
本书论证简明，叙述清晰，内容深入浅出，循序渐进，便于教学。书中还配有较多数量的典型例题和习题，既可作为研究生教学用书，也可作为本科高年级学生的教材以及有关科技工作者的参考书。
- 目录
- 前辅文
- 第一章 图的基本概念
- §1.1 图和简单图
- §1.2 子图与图的运算
- §1.3 路与图的连通性
- §1.4 最短路及其算法
- §1.5 图的代数表示及其特征
- §1.6 极图
- §1.7 交图与团图
- 习题1
- 第二章 树
- §2.1 树的概念与性质
- §2.2 树的中心与形心
- §2.3 生成树
- §2.4 最小生成树
- 习题2
- 第三章 图的连通度
- §3.1 割边,割点和块
- §3.2 连通度
- §3.3 应用
- §3.4 图的宽距离和宽直径
- 习题3
- 第四章 Euler图与Hamilton图
- §4.1 Euler图
- §4.2 高效率计算机鼓轮的设计
- §4.3 中国邮递员问题
- §4.4 Hamilton图
- §4.5 度极大非Hamilton图
- §4.6 旅行售货员问题
- §4.7 超Hamilton图
- §4.8 犈图和犎图的联系
- §4.9 无限图中的Euler, Hamilton问题
- 习题4
- 第五章 匹配与因子分解
- §5.1 匹配
- §5.2 偶图的匹配与覆盖
- §5.3 Tutte定理与完美匹配
- §5.4 因子分解
- §5.5 最优匹配与匈牙利算法
- §5.6 匹配在矩阵理论中的应用
- 习题5
- 第六章 平面图
- §6.1 平面图
- §6.2 一些特殊平面图及平面图的对偶图
- §6.3 平面图的判定及涉及平面性的不变量
- §6.4 平面性算法
- 习题6
- 第七章 图的着色
- §7.1 图的边着色
- §7.2 顶点着色
- §7.3 与色数有关的几类图
- §7.4 完美图
- §7.5 着色的计数与色多项式
- §7.6 List着色
- §7.7 全着色
- §7.8 着色的应用
- 习题7
- 第八章 Ramsey定理
- §8.1 独立集和覆盖
- §8.2 Ramsey定理
- §8.3 广义Ramsey数
- §8.4 应用
- 习题8
- 第九章 有向图
- §9.1 有向图及其连通性
- §9.2 有向树
- §9.3 有向路与有向圈
- §9.4 生成树的计数
- §9.5 运输网络与最大流
- §9.6 求最大流的算法及最大流问题的推广
- §9.7 网络流与Menger定理
- 习题9
- 第十章 图、群与矩阵
- §10.1 图的特征值与谱
- §10.2 图的自同构群
- §10.3 图的对称性与强正则图
- §10.4 Cayley图
- §10.5 循环图
- §10.6 Cayley图的Hamilton性
- 习题10
- 主要参考文献
