图论及应用

图书标准信息

• 作者 冯林 编
• 出版社 哈尔滨工业大学出版社
• 出版时间 2012-03
• 版次 1
• ISBN 9787560332918
• 定价 32.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 240页
• 字数 311千字
• 正文语种 简体中文
• 丛书 ACM-ICPC程序设计系列

【内容简介】

《图论及应用》主要介绍ACM-ICPC比赛中涉及的图论，其中包括许多实际问题的抽象表示与求解，以及部分图论理论内容的证明。全书共分6章，第1章介绍了图论的基础知识，包括基础概念、存储方法和遍历方法；第2章介绍了有关树的问题，着重讲解生成树和一些树上特殊点集的求法；第3章介绍了最短路径问题，包括几种通用算法和特殊图上的算法；第4章介绍图论中有关连通性的问题，包括有向图的强连通、无向图的双连通及其扩展问题；第5章介绍网络流解法，包括几种常用的网络流算法和对于问题如何抽象成网络流模型的经验方法；第6章介绍二分图的相关问题，重点为二分图的匹配及其变种问题。《图论及应用》的内容基本满足ACM-ICPC比赛对于图论方面的要求，讲解清晰易懂，代码规范，例题丰富。

【目录】

第1章图
1.1图的定义和术语
1.1.1图的定义
1.1.2特殊的图
1.1.3有向图和无向图
1.1.4路径与连通
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.2图的生成树
2.2.1最小生成树
2.2.2次小生成树
2.2.3有向图的最小树形图
2.3树的其他问题
2.3.1树上两点的最近公共祖先
2.3.2树的最小支配集，最小点覆盖与最大独立集

第3章图的最短路径问题
3.1单源最短路径
3.1.1Dijkstra算法
3.1.2Bellman-Ford算法
3.1.3SPFA算法
3.1.4例题
3.2每对顶点间的最短距离
3.2.1Floyd算法
3.2.2例题
3.3最短路问题的扩展与应用
3.3.1k短路
3.3.2差分约束系统
3.3.3DAG图上的单源最短路径
3.3.4Floyd求最小环

第4章连通性问题
4.1图的强连通
4.1.1强连通的定义
4.1.2Kosaraju算法
4.1.3Tarjan算法
4.1.4Garbow算法
4.1.5例题
4.2最小点基
4.2.1最小点基的定义
4.2.2最小点基
4.2.3最小权点基
4.2.4例题
4.3图的双连通
4.3.1双连通的定义
4.3.2点双连通分量
4.3.3边双连通分量
4.3.4例题
4.4图的全局最小割问题和Stoer-Wagner算法
4.52-SAT
4.5.1SAT
4.5.22-SAT
4.5.3例题

第5章网络流
5.1网络
5.1.1容量与流
5.1.2残留网络及增广路
5.1.3最小割最大流定理
5.2最大流算法
5.2.1Ford-Fulkson方法的基本思想
5.2.2Edmond-Karp算法
5.2.3SAP算法及其优化
5.2.4Dinic算法
5.2.5例题与应用
5.3有上下界的网络流
5.3.1解决上下界网络流的一般思路
5.3.2例题与应用
5.4网络的费用流
5.4.1连续最短路算法
5.4.2例题与应用

第6章二分图及匹配算法
6.1匹配问题
6.2匹配基本定理
6.2.1Berge定理
6.2.2Hall定理
6.3二分图最大匹配
6.3.1匈牙利算法
6.3.2Hopcroft-Karp算法
6.3.3二分图多重匹配
6.3.4二分图最大匹配的网络流解法
6.4二分图最佳匹配
6.4.1KuhnMunkras算法
6.5二分图模型的应用
6.5.1二分图最小点覆盖
6.5.2有向无环图的最小路径覆盖
6.5.3二分图的最大独立点集
6.5.4最小点权覆盖
参考文献