（2） 链、路：如果图中顶点ai到aj之间有两条以上的弧连接， 则称为一条链，在有向图中由一个顶点到另一个顶点之间有同向
的弧连接，则ai到aj构成一条路。 如果一个顶点ai有到达ai的一条链，则这条链叫圈；在有
向图中弧的方向相同的圈叫回路。
（3） 连通图：一个图中，任意两顶点ai和aj之间至少有一条链 存在，则该图为连通图，否则为不连通的图。
3、最小部分树问题
如果图 T(V是,E1图) G的一个生成树，那么称E1上所有边的权 的和为生成树T 的权，记作S(T)。如果图G的生成树T* 的
权S(T*)，在G 的所有生成树T 中的权最小，即 S(T*)m，iSn那(T么) 称T*是G 的最小生成树。
T
某六个城市之间的道路网如图所示，要求沿着已知长度 的道路联结六个城市的电话线网，使电话线的总长度最短。
时，树T为最小部分树。
式中：lij为 a(i j)的长度；为树中由ai到aj的唯一一条链。
通俗地说，上述定理的涵义为：树的任意一条外边lij比所对应的链
中最长的边还长；也可以说，最小部分树是由图中去掉圈中最长的
边构成的。
与此相反，还可得到最大树定理：
当且仅当树T的每条外边lij满足
lij≤min
lii1,li1i2 , ,likj
C运ompa筹ny Lo学go
（3） 树形图：树形图是满足以下条件的有 向树：
① 图中一顶点a0不是任何弧的终点，该点称 为树的根；
② 每一顶点ai(ai≠a0)是唯一一条弧的终点。
（4）部分树：在一连通图中，包括所有顶 点的一棵树叫部分树。对于给定的图，属 于部分树的弧称为树的内边，不属于部分 树的弧，称为树的外边。
时，树T为最大树。
由此定理，我们可以解决一类在既定的图中寻找一棵最小部分
树的问题。
C运ompa筹ny Lo学go
2、得到部分树的方法： ①破圈法
lii1,li1i2 , ,likj
C运ompa筹ny Lo学go
C运ompa筹ny Lo学go
②避圈法 v3
v1 vv2 3
v1 v2
v3
v3
v3
第五章 网络最优化方法
Company
LOGO
第五章 网络最优化方法
❖ 网络及图的基本概念 ❖ 最短路问题 ❖ 网络最大流 ❖ 最小费用最大流
C运ompa筹ny Lo学go
第一节 网络与图的基本概念 一、图与网络的基本概念
A
A
CC
D
D
B B
C运ompa筹ny Lo学go
（1） 顶点、弧（边）
用点表示组成系统的单元叫图的顶点，用线表示的两
单元之间的特定的关系叫弧或边。
一般以ai表示图的顶点，以a(i,j)表示由ai出发到aj的 一条弧，ai称为弧的起点，aj称为弧的终点，a(i,j)称为弧的 长。
如果ai到aj或aj到ai(i≠j)之间存在一条弧，则称两个顶
点是相邻的。
a3 2
a6
4
a9
5
3
3
a2
6
4
a5
a8
5
4
4
9
4
a1
a4
a7
C运ompa筹ny Lo学go
3 6 72
a6 4
3
3
a3
5
2
a5
a4
a1a5
4
a 6 3
a1
4 6 4 3
0
2
7
2 0 5 3
7
5
0
2
2 0 3
3 3 0
a2 a3 a4 a5 a6
C运ompa筹ny Lo学go
二、树的基本概念 （1） 树：连通且不含圈的图叫树。
a2
a5
a3 2
a6 4
一条链
5圈3
a2
6
4
a5
5 a1
回路
4
9
4
a4
a9
一条路
3 a8
4
a7 C运ompa筹ny Lo学go
（4）以点a为端点的边的个数称为点a 的次（度），记
作 d (。a)
次为零的点称为孤立点，次为1的点称为悬挂点。 次为奇数的点称为奇点，次为偶数的点称为偶点。
a3 2
a6 4
5
3
a2
v5
v5 v1 v6
v1
v1
v2
v2
v4 v5
v3
v5
v6
v1
v6
v4
v2
C运ompa筹ny Lo学go
用破圈法求出下图的v一2 个部分树。
e1
e4 e7
v2
v1 e2
e3 v4 e8 e5
v5
e6
v2
e1
e4 e7
v3
e4
v1 e2
e3
v4 e8
e5 e6
v3
v5
v1
v4 e8
v5
e2
e6
v3
C运ompa筹ny Lo学go
v3 5 v5
6
4
v1
17 3
v6
5
2
4
v2
v4
v3
v1
1
5
2
v2
v5 3
v4
v6 4
C运ompa筹ny Lo学go
避圈法
v2
1
v1 7
3
9
2
v4
6
1
v3
6
破圈法
v5
C运ompa筹ny Lo学go
四、一笔画问题
A
C
D
B
哥尼斯堡七桥
A C
B
D C运ompa筹ny Lo学go
C运ompa筹ny Lo学go
欧拉定理 （1）全部顶点均为偶点的图，构成一笔圈问题； （2）仅有两个奇点的图，构成一笔画问题，且必
定是从一个奇到出发到另外一个奇点。
A
C
D
B C运ompa筹ny Lo学go
a3
a1
a7
a6
Company Logo
v1
v2
（2）树的性质：
v6
v3
①树必连通，但无回路（圈）。
②n 个顶点的树必有n-1 条边。
v5
v4
③树中任意两个顶点之间，恰有且仅有一条链（
初等链）。
④树连通，但去掉任一条边， 必变为不连通。
⑤树无回路（圈），但不相邻的两个点之间加一
条边，恰得到一个回路（圈）。
6
4
a5
5 a1
4
9
4
a9
a10
3 a8
4
a7
a11
C运ompa筹ny Lo学go
有向图中，以 ai 为始点的边数称为点ai的出次,以 ai 为终点 的边数称为点ai 的入次，ai 点的出次和入次之和就是该点的次
所A 有顶点的入次之和等于所有顶点的出次之和。
v2
v4
v1
v6
C
D
v3
v5
B
定理1 所有顶点次数之和等于所有边数的2倍。
Company Logo
三、 最小部分树问题
已知有六个城市，它们之间要架
设电话线，要求任意两个城市均可 v1
v2
以互相通话，并且电话线的总长度
最短。
v6
v3
v5
v4
C运ompa筹ny Lo学go
1、最小部分树定理
在图中，当且仅当树T的每条外边lij满足
lij≥max
lii1 ,li1i2 , ,likj
定理2 在任一图中，奇次点的个数必为偶数。
C运ompa筹ny Lo学go
（5）图的矩阵表示 对于网络（赋权图）G，其中边 (ai , a有j )权 ，w i j 构造矩阵 A(ai，j)n其n 中权矩阵为：
aij
wi j
(ai ,aj)E (ai ,aj)E
称矩阵A为网络G的权矩阵。
a1 4
a2