应用图论

第一章图的基本概念
1.1引言.
1.2图的概念
1.2.1图的定义
1.2.2顶点的度
1.2.3图的同构
1.3子图
1.4路与连通
1.4.1路与圈
1.4.2连通性
1.4.3二分图的一个特征
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.3Huffman树
习题二
第三章图的矩阵表示
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α-β搜索法
4.2分枝定界法
第五章最短路问题
5.1解最短路问题的基本方法
5.1.1从一个始点v1到一个终点vn的最短路问题
5.1.2求任意两顶点间的最短路问题
5.2具有负权有向图中的最短路
5.2.1赋权有向图中的最短路
5.2.2具有负权的有向图中的最短路
5.3K最短路问题
5.3.1双向扫视算法基础
5.3.2双向扫视算法过程
5.3.3算法原理..
习题五
第六章可行遍性
6.1Euler图
6.2中国邮递员问题
6.2.1Euler图中的最优环游
6.2.2非Euler图中的最优环游
6.3Hamilton图
6.4旅行售货员问题
6.4.1调整Hamilton圈以得到近似最优解
6.4.2分枝定界法确定精确最优解
习题六
第七章平面图
7.1平面图的概念
7.1.1平面图
7.1.2Euler公式
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.1Hall定理
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.1Mason信号流图
10.1.1信号流图
10.1.2线性方程组的Mason信号流图表示
10.1.3信号流图的运算规则
10.2Mason公式
10.3矩阵与Coate流图
习题十
参考书目...