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

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

第一章 图的基本概念

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流图

习题十

参考书目