文档介绍：图论与网络流理论
(Graph Theory work Flow Theory)
讲授:高随祥
中科院研究生院专业基础课
学时/学分:60/3
本课程适合基础数学、应用数学、计算数学、运筹学与控制论、概率论与数
理统计各专业的硕士学位研究生作为专业基础课,也可供物理学、化学、天文学、
地学、生物科学、计算机科学与技术、计算机软件、管理科学与工程以及通信、
信号等学科专业的硕士研究生选修。主要讲授图论与网络流理论的基本概念、方
法和定理,介绍该领域重要的问题以及典型的算法,展示图论与网络流模型及方
法的广泛应用。为学习者将来从事有关方面的理论研究打下基础,也为进行应用
性研究提供一种有力的工具。
1
内容提要
第一章图的基本概念
图的基本概念;二部图及其性质;图的同构;关联矩阵与邻接矩阵。
路、圈与连通图;最短路问题。
树及其基本性质;生成树;最小生成树。
第二章图的连通性
割点、割边和块;边连通与点连通;连通度;Whitney 定理;可靠通信网络的设计。
第三章匹配问题
匹配与最大匹配;完美匹配;二部图的最大匹配;指派问题与最大权匹配。
第四章欧拉图与哈密尔顿图
欧拉图;中国邮递员问题;哈密尔顿图;旅行商问题。
第五章支配集、独立集、覆盖集与团
支配集、点独立集、点覆盖集、边覆盖集与团的概念及其求法。
第六章图的着色问题
点着色;边着色;平面图;四色猜想;色多项式;色数的应用。
第七章网络流理论
有向图;网络与网络流的基本概念;最大流最小割定理;求最大流的标号算法;最小费
用流问题;最小费用最大流;网络流理论的应用。
主要参考书
[1] . Bondy and . Murty, Graph theory with applications, 1976, 有中译本(吴望名等译)。
[2] , Modern graph theory (现代图论),科学出版社,2001。
[3] 蒋长浩,图论与网络流,中国林业出版社,2001。
[4] 田丰,马仲蕃,图与网络流理论,科学出版社,1987。
[5] 徐俊明,图论及其应用,中国科技大学出版社,1998。
[6] 王树禾,图论及其算法,中国科技大学出版社,1994。
[7] 殷剑宏,吴开亚,图论及其算法,中国科技大学出版社,2003。
考核方式:平时成绩+期末闭卷笔试

2
第一章图的基本概念
§ 图的基本概念
1. 图(graph):一集元素及它们之间的某种关系。具体地说,图是一个二元组(V , E) ,其中
集合 V 称为顶点集,集合 E 是V ×V 的一个子集(无序对,元素可重复),称为边集。
例 G = (V , E) ,其中
V = {v1, v2 , v3 , v4 , v5}, E = {(v1, v2 ),(v2 , v3 ),(v3 , v4 ),(v3 , v5 ),(v1, v5 ),(v1, v5 ),(v5 , v5 )}。
这便定义出一个图。

2. 图的图示
通常,图的顶点可用平面上的一个点来表示,边可用平面上的线段来表示(直的或曲的)。
这样画出的平面图形称为图的图示。
例如,例中图的一个图示为

v1
e1
e6
v2
e5
e2 e4 e7
v5
v
3 e3 v4

注:(1)由于表示顶点的平面点的位置的任意性,同一个图可以画出形状迥异的很多图示。
比如下图是例中图的另一个图示:
v1
e6

e5
v4 e
1 v5
e4 e
e3 7
v3 e2 v2

(2)图的图示直观易懂,因此以后一般说到一个图,我们总是画出它的一个图示来表示。
3. 一些概念和术语
(1) 点与边的关联(incident)
(2) 点与点的相邻(adjacent)
(3) 边与边的相邻
(4) 边的端点(end vertices)
(5) 环边(loop)
(6) 重边(multiedge)
(7) 简单图(simple graph)
3
(8) plete graph)
(9) 图的顶点数(图的阶)ν、边数ε
(10) 顶点 v 的度(degree):d(v) = 顶点 v 所关联的边的数目(环边计两次)。
(11) 图 G 的最大度: ∆(G) = max{dG (v) | v ∈V (G)}
图 G 的最小度:δ(G) = min{dG (v) | v ∈V (G)}
(12)正则图(re