本书主要介绍图论的基本概念、理论和算法。涵盖图的概念与运算、树及其算法、最大流及其算法、遍历性及其算法、独立集及其算法、最大匹配及其算法、平面性及其算法、应用案例拓展等内容。每章配置了一定量的分层次、多题型的练习题。本书前两章为图与网络的基本概念及运算。自第三章始，每章节从实际问题出发，引出一个图论主题，建立相关概念和理论，清晰描述算法思想和执行步骤，严谨推演算法正确性、再用算例验证。最后一章介绍了综合运用图论知识解决具体应用问题的几个案例。本书为学习者较全面地呈现了图论研究的基本问题以及研究视角。

更多科学出版社服务，请扫码获取。

1994年—1998年，国防科学技术大学，应用数学专业，本科 1998年—2001年，国防科学技术大学，应用数学专业，硕士 2002年—2008年，国防科学技术大学，应用数学专业，博士 2001年—2008年，国防科学技术大学，理学院数学系，讲师 2008年—至今，国防科技大学，理学院数学系，副教授 1. 谢政，戴丽，《组合图论》，国防科技大学出版社，2003年，合著 2. 谢政，戴丽，李建平，《博弈论》，高等教育出版社，2018年，合著 3. 谢政，陈挚，戴丽，《线性代数学习指导》（第三版），清华大学出版社，2022年，合著 4. 谢政，陈挚，戴丽，《工程应用数学基础》，科学出版社，2015年，合著湖南省运筹学会理事

第 1 章 图的基本概念 1.1 图论发展历史与特点 1.1.1 图论 1.1.2 图论的起源与发展（不同阶段的经典图论问题案例） 1.1.3 图论特点 1.2 图的定义 1.2.1 定义 1.2.2 度 1.2.3 同构 1.3 子图和连通分支 1.3.1 子图 1.3.2 导出子图 1.3.3 连通分支 1.3.4 距离和中心 习题一 第 2 章 重要图类与图运算 2.1 重要图类 2.1.1 完全图 2.1.2 正则图 2.1.3 二部图 2.1.4 常见图类 2.2 有向图 2.2.1 定义 2.2.2 基础图 2.2.3 出度和入度 2.2.4 有向途径 2.2.5 强连通分支 2.3 网络 2.3.1 无向网络和有向网络 2.3.2 Dijkstra算法 2.4 矩阵表示 2.4.1 邻接矩阵 2.4.2 Laplace矩阵 2.4.3 关联矩阵 2.4.4 可达矩阵 2.5 运算 2.5.1 删去、添加和补图 2.5.2 交和并 2.5.3 收缩和剖分 2.5.4 笛卡尔积 2.5.5 克罗内克积 习题二 第 3 章 树及其算法 3.1 树和森林 3.1.1 树的基本概念 3.1.2 破圈法和避圈法 3.1.3 六个等价命题 3.1.4 割边 3.1.5 边割 3.1.6 割点 3.2 支撑树的计数 3.2.1 递推公式 3.2.2 矩阵-树定理 3.3 最小支撑树 3.3.1 定义 3.3.2 Prim算法 3.3.3 Kruskal算法 3.4 二元树与前缀码 3.4.1 二元树 3.4.2 有序二元树的个数 3.4.3 前缀码 3.4.4 Huffman树 3.5 与树有关的猜想 3.5.1 优美树猜想 3.5.2 强九龙树猜想 3.5.3 Erd？s-Sós猜想 习题三 第 4 章 最大流及其算法 4.1 网络模型 4.1.1 容量网络 4.1.2 流 4.1.3 流值 4.1.4 最大流 4.2 最大流算法 4.2.1 增广链 4.2.2 最大流Ford-Fulkerson算法 4.2.3 最大流最小截定理 4.2.4 最短增广链算法 4.3 最小费用最大流 4.3.1 问题描述 4.3.2 F增广圈 4.3.3 Klein算法 习题四 第 5 章 遍历性及其算法 5.1 Euler图和有向Euler图 5.1.1 定义 5.1.2 Fleury算法 5.1.3 编码盘设计 5.2 中国邮递员问题 5.2.1 问题描述 5.2.2 奇偶点图上作业法 5.3 Hamilton图 5.3.1 定义 5.3.2 闭包 5.3.3 格雷码与立方体的Hamilton圈 5.4 有向Hamilton图 5.4.1 强连通的充要条件 5.4.2 回路 5.4.3 有向Hamilton图的充分条件 5.5 连通度和边连通度 5.5.1 连通度和边连通度 5.5.2 2连通图 5.5.3 3连通图 5.6 坚韧度 5.6.1 坚韧度 5.6.2 边坚韧度 5.7 相关猜想 5.7.1 关于Hamilton图的Graffiti.PC猜想 5.7.2 Chvàtal猜想 习题五 第 6 章 独立集及其算法 6.1 独立集和覆盖 6.1.1 独立数和覆盖数 6.1.2 性质 6.1.3 极大独立集的计算 6.1.4 独立集与连通度的联系 6.2 Ramsey数 6.2.1 Ramsey数 6.2.2 Ramsey数的上界 6.2.3 Ramsey数的下界 6.2.4 广义Ramsey数 6.2.5 类似Ramsey数的问题 6.2.6 Turán定理 6.3 顶点着色 6.3.1 色数 6.3.2 色数上界 6.3.3 色数的下界 6.3.4 色多项式 6.4 支配集 6.4.1 定义 6.4.2 性质 6.4.3 极小支配集的计算 6.5 相关猜想 习题六 第 7 章 匹配及其算法 7.1 边独立集和边覆盖 7.1.1 边独立数和边覆盖数 7.1.2 完美匹配 7.1.3 Tutte定理 7.2 边着色 7.2.1 边色数 7.2.2 Vizing定理 7.2.3 第一类图和第二类图 7.3 二部图的最大匹配 7.3.1 M饱和顶点 7.3.2 增广链 7.3.3 Hall定理 7.3.4 匈牙利算法 7.4 最优匹配 7.4.1 最优匹配的概念 7.4.2 可行顶标 7.4.3 Kuhn-Munkres算法 7.5 相关猜想 习题七 第 8 章 平面性及其算法 8.1 平面图 8.1.1 平面图和平图 8.1.2 对偶图 8.2 平面图必要条件和Euler公式 8.2.1 平面图的必要条件 8.2.2 Euler公式 8.3 极大平面图和极大外平面图 8.3.1 极大平面图 8.3.2 极大外平面图 8.4 Kuratowski定理 8.4.1 剖分图和H分枝 8.4.2 Kuratowski定理 8.5 四色问题 8.5.1 四色问题的三种数学描述 8.5.2 五色定理 8.6 平面性检测算法 8.6.1 DMP算法 8.6.2 DMP算法的证明 习题八 第9章 应用案例拓展 9.1 拉普拉斯矩阵在网络中的应用 9.1.1 随机游走与电网络 9.1.2 图聚类与图分割 9.1.3 相关猜想 9.2 智能集群控制中的图论问题 9.2.1 Kalman可控性 9.2.2 支配集在最小领航集中的应用 9.2.3 相关猜想 9.3 图能量的概念与应用 9.3.1 图能量的定义 9.3.2 图能量在化学与网络中的应用 9.3.3 相关猜想 习题九 参考文献 名词索引