图论与算法

本书由实际问题展开， 在介绍用图建立数学模型并 阐述相关数学原理的基础上 ，进一步介绍用计算机解决 相关问题的方法，包括经典 算法的设计和基于数学原理 的算法分析，使理论与算法 融会贯通，并通过大量的思 考题引导读者自己完成推导 过程。 本书共10章：第1章介绍 图的基本概念；第2—4章介 绍图的连通性和遍历方法， 包括基于圈的特殊遍历方法 ；第5章介绍匹配；第6章和 第7章分别介绍赋权图和有 向图，包括流网络；第8章 介绍独立、覆盖和支配：第 9章介绍边和顶点的染色； 第10章介绍平面，包括面的 染色。每节后均附有练习题 ，包括理论题和编程练习题 。 本书可作为高等学校计 算机及相关专业本科生和研 究生的教材。

第1章 图的基本概念 1.1 图的定义 1.2 图的表示 1.3 图的关系 1.4 图的运算 第2章 连通和遍历 2.1 连通和DFS 2.1.1 理论 2.1.2 算法 2.2 割点和割边 2.2.1 理论 2.2.2 算法 2.3 距离和BFS 2.3.1 理论 2.3.2 算法 第3章 圈和遍历 3.1 圈和树 3.1.1 理论 3.1.2 算法 3.2 二分图 3.2.1 理论 3.2.2 算法 3.3 欧拉图 3.3.1 理论 3.3.2 算法 3.4 哈密尔顿图 3.4.1 理论 3.4.2 算法 第4章 连通度 4.1 块 4.1.1 理论 4.1.2 算法 4.2 割集和连通度 4.2.1 理论 4.2.2 算法 第5章 匹配 5.1 匹配和最大匹配 5.1.1 理论 5.1.2 算法 5.2 完美匹配 第6章 赋权图 6.1 赋权图和距离 6.1.1 理论 6.1.2 算法 6.2 最小生成树 6.2.1 理论 6.2.2 算法 6.3 赋权欧拉图 6.3.1 理论 6.3.2 算法 6.4 赋权哈密尔顿图 6.4.1 理论 6.4.2 算法 第7章 有向图 7.1 有向图的定义 7.2 有向图的表示 7.3 有向图的连通 7.3.1 理论 7.3.2 算法 7.4 有向图的距离 7.4.1 理论 7.4.2 算法 7.5 流网络和最大流 7.5.1 理论 7.5.2 算法 第8章 独立、覆盖和支配 8.1 边的独立、覆盖和支配 8.1.1 理论 8.1.2 算法 8.2 顶点的独立、覆盖和支配 8.2.1 理论 8.2.2 算法 第9章 染色 9.1 边的染色 9.1.1 理论 9.1.2 算法 9.2 顶点的染色 9.2.1 理论 9.2.2 算法 第10章 平面 10.1 可平面图 10.1.1 理论 10.1.2 算法 10.2 面的染色 A 部分思考题提示 B 部分思考题完整证明 术语小结 参考文献