本书系统地阐述图论与网络流理论的基本概念､方法和定理,介绍该领域重要的问题以及典型的算法,展示图论与网络流模型及方法的广泛应用｡全书立足基础､兼顾理论与应用,选材精炼,贴近研究和应用前沿,注重思想和方法｡主要内容包括图的基本概念､最短路及最小生成树､连通性､匹配､Euler 图､Hamilton 图､支配集､独立集､覆盖集､图的染色､平面图､有向图､网络流等方面的理论与算法｡每章配有大量习题和前沿性的专题参考文献｡
本书可作为数学､运筹学､系统科学各专业硕士研究生或本科高年级学生的教材或参考书,也可供物理学､化学､生命科学､计算机科学与技术､电子科学与技术､信息科学与网络工程､资源与环境､物流与交通运输､管理科学与工程､过程工程､自动控制等学科专业的本科生､研究生使用,还可供相关领域的科研工作者､广大图论爱好者参考｡
- 前辅文
- 第一章 图的基本概念
- 1.1 图的基本概念
- 1.2 最短路问题
- 1.3 树及其性质
- 1.4 生成树与最小生成树
- 1.5 图的中心与中位点
- 1.6 图的矩阵表示
- 习题一
- 参考文献
- 第二章 图的连通性
- 2.1 割点和割边
- 2.2 连通度和边连通度
- 2.3 2-- 连通图的性质
- 2.4 Menger 定理
- 2.5 可靠通信网络的设计
- 习题二
- 参考文献
- 第三章 匹配理论
- 3.1 匹配与最大匹配
- 3.2 完美匹配
- 3.3 二部图的匹配
- 3.4 二部图中最大匹配与最大权匹配的算法
- 习题三
- 参考文献
- 第四章 Euler 图与Hamilton 图
- 4.1 Euler 图
- 4.2 中国邮递员问题 (Chinese Postman Problem)
- 4.3 Hamilton 图
- 4.4 旅行商问题(Traveling Salesman Problem, TSP)
- 习题四
- 参考文献
- 第五章 支配集､独立集､覆盖集和Ramsey 数
- 5.1 支配集､点独立集､点覆盖集
- 5.2 边独立集与边覆盖集
- 5.3 支配集､点独立集､点覆盖集的求法
- 5.4 Ramsey 数
- 习题五
- 参考文献
- 第六章 染色理论
- 6.1 边染色
- 6.2 点染色
- 6.3 色多项式
- 6.4 完美图
- 6.5 图的边染色算法和点染色算法
- 习题六
- 参考文献
- 第七章 平面图
- 7.1 平面图的概念
- 7.2 Euler 公式及其应用
- 7.3 可平面图的判断
- 7.4 平面图的对偶图
- 7.5 外可平面图
- 7.6 不可平面图的几个研究方向简介
- 7.7 平面图的面染色和四色猜想
- 习题七
- 参考文献
- 第八章 有向图
- 8.1 有向图的基本概念
- 8.2 有向路与有向圈
- 8.3 有向图的连通性及无向图的强连通定向
- 8.4 Euler 有向图和Hamilton 有向图
- 8.5 竞赛图
- 8.6 根树及其应用
- 习题八
- 参考文献
- 第九章 网络流理论与算法
- 9.1 网络与网络流的基本概念
- 9.2 最大流问题及其标号算法
- 9.3 求最大流的Dinic 算法
- 9.4 求最大流的推拉流算法
- 9.5 最大流问题的一些扩展
- 9.6 最小费用流问题
- 习题九
- 参考文献
- 名词索引
