应用图论

本书基本内容经编著者十多年的教学实践，在理论的系统性和实用性两方面都得到充实。主要内容包括：图的基本概念，树，割集，图的矩阵表示，搜索技术与分枝定界，最短路问题，可行遍性，平面图，色数问题，匹配与覆盖，网络流和流图理论等。比较系统地介绍了图论研究的许多主要方面，并侧重于理论的实际应用。论述简单明了，深浅适中，便于教也便于学。.
本书可作为非图论专业的各科研究生或高年级本科生的教学用书或参考书，亦可供高校教师、科研人员和工程技术人员参考。...

本书基本内容经编著者十多年的教学实践，在理论的系统性和实用性两方面都得到充实。主要内容包括：图的基本概念，树，割集，图的矩阵表示，搜索技术与分枝定界，最短路问题，可行遍性，平面图，色数问题，匹配与覆盖，网络流和流图理论等。比较系统地介绍了图论研究的许多主要方面，并侧重于理论的实际应用。论述简单明了，深浅适中，便于教也便于学。

第一章 图的基本概念
1．1引言
1．2图的概念
1．2．1图的定义
1．2．2顶点的度
1．2．3图的同构
1．3子图
1．4路与连通
1．4．1 J路与圈
1．4．2连通性
1．43二分图的一个特征
1．5有向图
1．5．1基本概念
1．5．2存在有向路和有向圈的条件
1．5．3不存在有向圈的条件
习题一
第二章 树与割集
2．1树及其性质
2．1．1树的定义
2．2．2树的特征
2．2生成树
2．2．1生成树
2．2．2生成树的构造
2．2．3基本圈
2．2．4生成树的数目
2．3割集
2．3．1割集
2．3．2割集的性质
2．3．3割集的环和
2．3．4基本割集
2．3．3割点
2．4图的连通度
2．4．1(点)连通度
2．4．2边连通度
2．5最优生成树
2．6单向树
2．6．1单向树
2．6．2有序树
2．6．3 Huffman树
习题二
第三章 图的矩阵表示
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．1搜索技术
4．1．1深探法DFS
4．1．2广探法BFS
4．1．3 a—B搜索法
4．2分枝定界法
第五章 最短路问题
5．1解最短路问题的基本方法
5．1．1从一个始点y1到一个终点y2的最短路问题
5．1．2求任意两顶点间的最短路问题
5．2具有负权有向图中的最短路
5．2．1赋权有向图中的最短路
5．2．2具有负权的有向图中的最短路
5．3 K最短路问题
5．3．1双向扫视算法基础
5．3．2双向扫视算法过程
5．3．3算法原理
习题五
第六章 可行遍性
6．1Euler图
6．2中国邮递员问题
6．2．1 Euler图中的最优环游
6．2．2非Euler图中的最优环游
6．3 Hanlilton图
6．4旅行售货员问题
6．4．1调整Hamilton圈以得到近似最优解
6．4．2分枝定界法确定精确最优解
习题六
第七章 平面图
7．1平面图的概念
7．1．1平面图
7．1．2 Euler公式
7．1．3极大平面图
7．2图的平面性检测
7．2．1Kuratowski图
7．2．2平面性检测
7．3对偶图
7．4五色定理与四色猜想
习题七
第八章 着色、匹配与覆盖
8．1色数问题
8．1．1色数及其性质
8．1．2色数的一种求法
8．1．3色数多项式
8．2匹配、覆盖及独立集
8．2．1匹配
8．2．2覆盖与独立集
8．3二分图的匹配和覆盖
8．3．1 Hall定理
8．3．2匹配与覆盖的关系
8．3．3匈牙利算法
8．4人员分派问题
8．4．1人员分派问题
8．4．2最优分派问题
习题八
第九章 网络流问题与选址问题
9.1基本概念和定理
9.1.1网络的流
9.1.2割
9.1.3最大流最小割定理
9.2．解最大流问题的标号法
9．3多端最大流问题
9．4选址问题
9．4．1单服务设施问题
9．4．2一般选址问题
习题九
第十章 流图与代数方程组
10．1 Mason信号流图
10．1．1信号流图
lO．1．2线性方程组的Mas叽信号流图表示
10．1．3信号流图的运算规则
10．2 Mason公式
10．3矩阵与Coate流图
习题十
参考书目

图不仅是处理和表达问题的一种手段，而且在各学科领域中已成为对具有系统功能的模型进行分析与设计等不可缺少的理论。工程技术中很多有实用价值的问题与图论相联系，实际中卓有成效的应用以及计算机应用软件的开发，又促进了图论的迅猛发展。图论已成为近数十年发展比较活跃的一门学科。. 本书作者在为信息工程大学测绘学院硕士研究生讲授《应用图论》的十多年中，几经修改和充实讲义，最后整理成此书。其取材主要考虑非数学专业学生的基本要求，避开一些繁复的定理证明和古老难题，必要的定理和算法的推证，大多也只限于构造性的推理过程与算法思想的理解，着眼于有应用价值的基本问题，使读者能够在了..