本书介绍了图与网络的核心内容与经典算法。其中，核心内容有连通性、Euler问题与Hamilton圈问题、平面图与着色问题、Ramsey数与随机图等，经典算法有最小支撑树和最短路算法、网络流算法与匹配算法。本书在内容上注重理论与实例相结合，也注重将一些现代学科的应用融入相应的章节，如信息学、生物医药、人工智能、编码设计、芯片设计等。在不失专业性的前提下，本书具有通识性、交叉性、科普性和前沿性的特点。
本书包含两类数字资源，其中一类是数学家以及著名问题的小故事，另一类是书中有难度的定理证明。这些资源以二维码的形式呈现，读者扫码就可观看，方便自学。
本书是本科生学习图与网络的一本入门教材，也可以作为研究生及科研人员的工具书。
- 前辅文
- 绪论
- 第1章 图与网络的概念与性质
- §1.1 图与网络的基本概念
- §1.2 子图与距离
- §1.3 连通
- §1.4 二部图
- §1.5 图与网络的矩阵表示
- §1.6 算法简介
- 知识拓展
- 习题1
- 第2章 树、最小支撑树与最短路
- §2.1 树的概念与性质
- §2.2 最小支撑树
- §2.3 最短(有向)路
- 知识拓展
- 习题2
- 第3章 连通性与网络流
- §3.1 连通度和边连通度
- §3.2 2-连通图的性质
- §3.3 网络的最大流
- §3.4 Menger定理
- 知识拓展
- 习题3
- 第4章 匹配与因子
- §4.1 匹配的概念与性质
- §4.2 二部图的匹配
- §4.3 二部图的最大匹配算法
- §4.4 图的完美匹配
- §4.5 图的因子
- 知识拓展
- 习题4
- 第5章 Euler图与Hamilton图
- §5.1 Euler图
- §5.2 中国邮递员问题
- §5.3 Hamilton图
- §5.4 旅行商(TSP)问题
- 知识拓展
- 习题5
- 第6章 平面图
- §6.1 多面体的平面化
- §6.2 平面图的概念
- §6.3 Euler公式及其应用
- §6.4 可平面图的判定
- §6.5 平面图的对偶图
- 知识拓展
- 习题6
- 第7章 染色理论
- §7.1 顶点染色
- §7.2 平面图的顶点染色
- §7.3 边染色
- §7.4 圆染色及交通信号周期的优化问题
- 知识拓展
- 习题7
- 第8章 Ramsey数与极值图论
- §8.1 独立集、点覆盖与支配集
- §8.2 Ramsey数
- §8.3 极值图论
- 知识拓展
- 习题8
- 第9章 随机图与概率方法
- §9.1 随机图简介
- §9.2 随机图的概念与性质
- §9.3 概率方法与应用
- §9.4 几乎所有图的性质
- 知识拓展
- 习题9
- 第10章 网络科学与图神经网络简介
- §10.1 网络科学简介
- §10.2 图神经网络简介
- 知识拓展
- 习题10
- 常用符号
- 参考文献
- 名词索引
