OR3 1
第八章 图与网络分析
引论 哥尼斯堡七桥问题
A
B
DC
A
B
C D
简捷表示事物之间的本质联系，归纳事物之间的一般规律
OR3 2
引论 图的用处
A,B,C,D,E 某公司的五支球队进行循环赛 组织机构设置图
A
B C
D E
总公司 分公司 工厂或办事处
OR3 3
8.1 图的基本概念
图是由 点 和 线 构成的。
点的集合 V表示,V={vi}
不带箭头的连线叫做 边 (edge)，边的集合记为 E= { ej },一条边可以用两点
[ vi,vj ]表示,ej= [ vi,vj ].
带箭头的连线叫做 弧 (arc),弧的集合记为
A,A= { ak },一条弧也是用两点表示，
ak= [ vi,vj ],弧有方向,vi为始点,vj为终点
OR3 4
图的基本概念 (续 )
由点和边组成的图叫做 无向图,记为 G=（ V,E）
由点和弧组成的图叫做 有向图,记为 D=（ V,A）
例 1.
v1 v2
v3v4
v1
v2
v3
v4
v5
v6
v7
e1
e2
e3 e4e5
e6
e7
a1
a2
a8
a4a
3
a5
a6 a9
a7
a10
a11
无向图：点集、边集 有向图：点集、弧集
OR3 5
图的基本概念 (续 )
以点 u为端点的边的条数，叫做点 u的 次次为 1的点叫做 悬挂点 ；次为 0的点叫做孤立点 ；次为奇数则称 奇点 ；次为偶数则称 偶点。
点弧交替序列称为 链 ；闭合的链称为 圈
首尾相接的链称为 路 ；闭合的路称 回路
任意两点之间都有边相连，称为 连通图
OR3 6
8.2 树
无圈的连通图称之为 树
赋权无向图 G=（ V,E）的最小基干称为最小支撑树
赋权有向图 D=（ V,A）,从始点到终点的权值最小的路称为 最短路
OR3 7
8.3 最短路问题
例 6 某交通网络如下图，求 v1到 v8的最短路线
解：用双标号法
v1
v2
v4
v3
v5
v6
v7
v863
1
2
2
1
6
10
4
3
10
4
4
6
v1
V2(v3,5)
V3(v1,3)
V4(v1,1)
V5(v2,6)
V6(v5,10)
V7(v5,9)
V8(v5,12)6
3
1
2
2
1
6
10
4 10
4
3
6
4
V2(v1,6）
OR3 8
8.4 最大流问题
引例：如下输水网络，南水北调工程，
从 vs到 vt送水，弧旁数字前者为管道容量，
后者为现行流量，如何调整输水最多？
vs vt
v2
v1
v4
v3
(3,3)
(5,1)
(1,1)
(4,3)
(1,1)
(2,2)
(3,0)
(2,1)
(5,3)
OR3 9
最大流问题的相关概念
网络：给定了弧的容量 C（ vi,vj）的有向图 D=
（ V,A,C）叫做一个 网络 。
可行流：各点流入量 =流出量，且 vs的流出量
=vt的流入量，这样的流称之为 可行流
截集：分离始点 vs和终点 vt的弧的集合，叫做截集
截量：截集的容量叫做 截量
增广链：一条从到的链，前向弧上可增加，后向弧上可减少，则称此链为 增广链
OR3 10
求最大流的方法
方法很简单：首先找到一条增广链，沿此进行最大可能调整，再找增广链，再调整，直到没有增广链。
寻找增广链的标号法：先给 vs标号（ 0，
+∞）,而后依次审查各条弧（ vi,vj）：对前向弧，饱和否？不饱和，给 vj点标号
（ vi,l(vj));对后向弧，可否减少？可，给
vj标号（ -vi,l(vj) ）,直到给 vt标上号，就得到了增广链。
OR3 11
解水网最大流问题
.
vs
V2
(0,+∞)
V1
(3,3)
(5,1)
(1,1)
(4,3)
(1,1)
(2,2)
(3,0)
(5,3)
(2,1)
V4
V3
Vt
(vs,4)
(-v1,1)
(-v2,1)
(v3,1)
(v2,1)
OR3 12
此题最大流图
沿增广链进行调整，前向弧增加 l(vj)，后向弧减少 l(vj)
vs
V2
V1 V3
V4
Vt
(3,3)
(5,2)
(4,3)
(1,0) (1,0)
(2,2)
(3,0)
(5,3)
(2,2)
(0,+∞)
(vs,3)
OR3 13
习题,p312－ 8.4，求最大流
给出任意可行流
找到一条增广链
调整可行流 注,’ ＝ 1,#＝ 1,$＝ 2，
*=1
vs
v1 v2
v3
v4 v5
vt
（ 4,3） ’
（ 10,4） $*
（ 3,2） #
（ 1,1）
（ 3,2） ’
（ 3,2） *
（ 4,2） $
（ 5,3） #*
（ 4,3） ’ （ 2,
2
）
（ 7,6） ’
（ 8,3） #$*
(0,+∞)
(vs,3)
第八章 图与网络分析
引论 哥尼斯堡七桥问题
A
B
DC
A
B
C D
简捷表示事物之间的本质联系，归纳事物之间的一般规律
OR3 2
引论 图的用处
A,B,C,D,E 某公司的五支球队进行循环赛 组织机构设置图
A
B C
D E
总公司 分公司 工厂或办事处
OR3 3
8.1 图的基本概念
图是由 点 和 线 构成的。
点的集合 V表示,V={vi}
不带箭头的连线叫做 边 (edge)，边的集合记为 E= { ej },一条边可以用两点
[ vi,vj ]表示,ej= [ vi,vj ].
带箭头的连线叫做 弧 (arc),弧的集合记为
A,A= { ak },一条弧也是用两点表示，
ak= [ vi,vj ],弧有方向,vi为始点,vj为终点
OR3 4
图的基本概念 (续 )
由点和边组成的图叫做 无向图,记为 G=（ V,E）
由点和弧组成的图叫做 有向图,记为 D=（ V,A）
例 1.
v1 v2
v3v4
v1
v2
v3
v4
v5
v6
v7
e1
e2
e3 e4e5
e6
e7
a1
a2
a8
a4a
3
a5
a6 a9
a7
a10
a11
无向图：点集、边集 有向图：点集、弧集
OR3 5
图的基本概念 (续 )
以点 u为端点的边的条数，叫做点 u的 次次为 1的点叫做 悬挂点 ；次为 0的点叫做孤立点 ；次为奇数则称 奇点 ；次为偶数则称 偶点。
点弧交替序列称为 链 ；闭合的链称为 圈
首尾相接的链称为 路 ；闭合的路称 回路
任意两点之间都有边相连，称为 连通图
OR3 6
8.2 树
无圈的连通图称之为 树
赋权无向图 G=（ V,E）的最小基干称为最小支撑树
赋权有向图 D=（ V,A）,从始点到终点的权值最小的路称为 最短路
OR3 7
8.3 最短路问题
例 6 某交通网络如下图，求 v1到 v8的最短路线
解：用双标号法
v1
v2
v4
v3
v5
v6
v7
v863
1
2
2
1
6
10
4
3
10
4
4
6
v1
V2(v3,5)
V3(v1,3)
V4(v1,1)
V5(v2,6)
V6(v5,10)
V7(v5,9)
V8(v5,12)6
3
1
2
2
1
6
10
4 10
4
3
6
4
V2(v1,6）
OR3 8
8.4 最大流问题
引例：如下输水网络，南水北调工程，
从 vs到 vt送水，弧旁数字前者为管道容量，
后者为现行流量，如何调整输水最多？
vs vt
v2
v1
v4
v3
(3,3)
(5,1)
(1,1)
(4,3)
(1,1)
(2,2)
(3,0)
(2,1)
(5,3)
OR3 9
最大流问题的相关概念
网络：给定了弧的容量 C（ vi,vj）的有向图 D=
（ V,A,C）叫做一个 网络 。
可行流：各点流入量 =流出量，且 vs的流出量
=vt的流入量，这样的流称之为 可行流
截集：分离始点 vs和终点 vt的弧的集合，叫做截集
截量：截集的容量叫做 截量
增广链：一条从到的链，前向弧上可增加，后向弧上可减少，则称此链为 增广链
OR3 10
求最大流的方法
方法很简单：首先找到一条增广链，沿此进行最大可能调整，再找增广链，再调整，直到没有增广链。
寻找增广链的标号法：先给 vs标号（ 0，
+∞）,而后依次审查各条弧（ vi,vj）：对前向弧，饱和否？不饱和，给 vj点标号
（ vi,l(vj));对后向弧，可否减少？可，给
vj标号（ -vi,l(vj) ）,直到给 vt标上号，就得到了增广链。
OR3 11
解水网最大流问题
.
vs
V2
(0,+∞)
V1
(3,3)
(5,1)
(1,1)
(4,3)
(1,1)
(2,2)
(3,0)
(5,3)
(2,1)
V4
V3
Vt
(vs,4)
(-v1,1)
(-v2,1)
(v3,1)
(v2,1)
OR3 12
此题最大流图
沿增广链进行调整，前向弧增加 l(vj)，后向弧减少 l(vj)
vs
V2
V1 V3
V4
Vt
(3,3)
(5,2)
(4,3)
(1,0) (1,0)
(2,2)
(3,0)
(5,3)
(2,2)
(0,+∞)
(vs,3)
OR3 13
习题,p312－ 8.4，求最大流
给出任意可行流
找到一条增广链
调整可行流 注,’ ＝ 1,#＝ 1,$＝ 2，
*=1
vs
v1 v2
v3
v4 v5
vt
（ 4,3） ’
（ 10,4） $*
（ 3,2） #
（ 1,1）
（ 3,2） ’
（ 3,2） *
（ 4,2） $
（ 5,3） #*
（ 4,3） ’ （ 2,
2
）
（ 7,6） ’
（ 8,3） #$*
(0,+∞)
(vs,3)
