离散优化简明教程(南开大学十四五规划核心课程精品教材)

离散优化是现代应用数学的一个重要分支，属于数学与运筹、优化、统计、数据分析等多个交叉领域的范畴。离散优化问题存在于现实世界的各个角落，目前人工智能、数据科学、网络安全等新兴学科和领域的急剧发展，也促使了大量大规模离散优化问题的诞生，由此也带来了离散优化领域新的发展和挑战，离散优化领域得到越来越多的重视和关注。 本教材在编者历年讲授的讲义基础上，整理完善而成，其中包含了离散优化领域的经典问题和基本理论方法，每章相对独立，又有关联，便于教师讲授和学生学习。书中包含了大量例题和习题，有理论的证明，有程序的实现，也有书中例题和算法的延伸，适合不同专业学生有针对性的选做。

第1章 导论 1.1 离散优化的经典问题 1.2 算法简介 1.3 图论 1.4 线性规划 1.5 拓展阅读 基础练习 提升练习 实践练习 第2章 最小生成树问题 2.1 实际问题 2.2 经典算法 2.3 最小生成树与线性规划 2.4 最小树形图 2.5 Steiner树问题 2.6 拓展阅渎 基础练习 提升练习 实践练习 第3章 贪心算法与拟阵初步 3.1 贪心算法 3.2 拟阵简介 3.3 贪心算法的正确性 3.4 拓展阅读 基础练习 提升练习 实践练习 第4章 最短路问题 4.1 实际问题 4.2 经典算法 4.3 无圈有向图 4.4 非负费用 4.5 线性规划 4.6 拓展阅读 基础练习 提升练习 实践练习 第5章 网络流问题 5.1 实际问题 5.2 最大流问题 5.3 增广路的寻找方法 5.4 二部图的匹配 5.5 Menger定理 5.6 有向图中的最优闭包问题 5.7 多商品流问题 5.8 拓展阅读 基础练习 提升练习 实践练习 第6章 匹配问题 6.1 实际问题 6.2 匹配与交错路 6.3 二部图的匹配 6.4 一般图的匹配 6.5 最小权完美匹配 基础练习 提升练习 实践练习 第7章 中国邮递员问题 7.1 中国邮递员问题简介 7.2 Euler环游 7.3 无向图上的中国邮递员问题 7.4 线性规划模型 7.5 有向图上的中国邮递员问题 7.6 拓展阅读 基础练习 提升练习 实践练习 第8章 随机算法 8.1 边割问题 8.2 最大3-适定性问题 8.3 素数判定问题 基础练习 提升练习 实践练习 第9章 计算复杂性理论 9.1 多项式时间归约 9.2 P与NP类 9.3 NP-完全问题 9.4 更多的NP-完全问题 9.5 拓展阅读 基础练习 提升练习 实践练习 第10章 近似算法 10.1 顶点覆盖问题 10.2 旅行售货商问题 10.3 Steiner树问题 10.4 背包问题 10.5 拓展阅读 基础练习 提升练习 实践练习 参考文献 名词索引 人名索引