上财系列】运筹学课件第五章图与网络分析

1、 5 图与网络分析图与网络分析 5.1 图的基本概念图的基本概念 5.2 树树 5.2.1 树与支撑树树与支撑树 5.2.2 最小支撑树问题最小支撑树问题 5.3 最短路问题最短路问题 5.4 网络最大流问题网络最大流问题 5.1 图的基本概念图的基本概念 图图: 由点和点与点之由点和点与点之 间的连线组成。若点与间的连线组成。若点与 点之间的连线没有方向，点之间的连线没有方向， 称为边，由此构成的图称为边，由此构成的图 为无向图。记为为无向图。记为G=（V， E）。）。 端点端点 相邻相邻 关联边关联边 环环 多重边多重边 简单图简单图 多重图多重图 次：一个点关联的边数称为该点的次。次：一

2、个点关联的边数称为该点的次。 链：是一个点链：是一个点、边交错序列边交错序列, 如（如（ v1,e2,v2,e3,v4). 中间点中间点 圈：链中，若起始点和终了点是同一个点，则称为圈。圈：链中，若起始点和终了点是同一个点，则称为圈。 例如例如(v1,e2,v2, e3,v4,e4,v3,e1,v1)。 奇点奇点 偶点偶点 悬挂点悬挂点 悬挂边悬挂边 孤立点孤立点 例例 v1 v2 v3 v4 v5 v6 e2 e4 e5 e6 e7 e8 e1 e3 e9 e10v4 连通图连通图 不连通图不连通图 连通分图连通分图 支撑子图支撑子图 若点与点之间的连若点与点之间的连 线有方向，称为弧，线有

3、方向，称为弧， 由此构成的图为有向由此构成的图为有向 图。图。 D=（V，A） 基础图基础图 始点始点 终终 点点 路路 回路回路 v1 v2 v3v4 v5 v6 e2 e4 e5 e6 e7 e8 e1 e3 v7 v8 e9 e10 v1 v2 v3v4 v5 v6 e2 e4 e5 e6 e7 e8 e1 e3 例例 例例 树：一个无圈的连通图称为树。树图树：一个无圈的连通图称为树。树图G=（V,E） 的点数记为的点数记为p，边数记为，边数记为q，则，则q=p-1。 例如例如 支撑树：图支撑树：图T=（V，E/）是图）是图G=（V，E） 的支撑子图，若图的支撑子图，若图T是一个树，则称

4、是一个树，则称T是是G的一的一 个支撑树。个支撑树。 5.2 树树 5.2.1 树与支撑树树与支撑树 例例 图图G有支撑树，有支撑树， 当且仅当图当且仅当图G是连通是连通 的。求连通图的支的。求连通图的支 撑树的方法有撑树的方法有“破破 圈法圈法”和和“避圈避圈 法法”。 v1 v2 v3 v5 e2 e3 e5 e1 e6 e7 e8 破圈法破圈法 v1 v2 e1 v3 e2 e4 e4 v4 v4 v5 e6 避圈法避圈法 v1 v2 v3 v5 e2 e3 e5 e1 e6 e7 e8 e4 v4 5.2 树树 5.2.2 最小支撑树问题最小支撑树问题 给图给图G中的每一条边中的每一条

5、边vi，vj一个相应的一个相应的 数数 ij，则称，则称G为赋权图。在赋权图为赋权图。在赋权图G的所有的所有 支撑树中，必有某个支撑树，其所有边的和支撑树中，必有某个支撑树，其所有边的和 为最小，称为最小树。为最小，称为最小树。求赋权图求赋权图G的最小支的最小支 撑树的方法也有两种撑树的方法也有两种,“破圈法破圈法”和和“避圈避圈 法法”。 6 5 5 17 2 3 4 4 v1 v2 v3 v4 v5 v6 破圈法：任选一破圈法：任选一 个圈，从圈中去掉权个圈，从圈中去掉权 最大的一条边。在余最大的一条边。在余 下的图中重复这个步下的图中重复这个步 骤，直到得到一不含骤，直到得到一不含 圈的

6、图为止。圈的图为止。 v3 v2 1 v4 2 v5 3 v6 4 v1 5 6 5 5 17 2 3 4 4 v1 v2 v3 v4 v5 v6 避圈法：开始选一条权最小的边，避圈法：开始选一条权最小的边， 以后每一步中，总从未被选取的边中选以后每一步中，总从未被选取的边中选 一条权尽可能小，且与已选边不构成圈一条权尽可能小，且与已选边不构成圈 的边。的边。 5.3 最短路问题最短路问题 对于有向图对于有向图D D(V,A)(V,A)，给其每一个弧给其每一个弧( (v vi i,v,vj j) )一一 个相应的权值个相应的权值w wij ij， ，D D就成为赋权有向图。给定赋权有就成为赋权

7、有向图。给定赋权有 向图向图D D中的两个顶点中的两个顶点v vs s和和v vt t，设设P P是由是由v vs s到到v vt t的一条路，的一条路， 把把P P中所有弧的权之和称为路中所有弧的权之和称为路P P的权，记为的权，记为w(P)w(P)。如如 果路果路P P* *的权的权w(Pw(P* *) )是由是由v vs s到到v vt t的所有路的权中的最小者，的所有路的权中的最小者， 则称则称P P* *是从是从v vs s到到v vt t的最短路。最短路的最短路。最短路P P* *的权的权w(Pw(P* *) )称为称为 从从v vs s到到v vt t的距离，记为的距离，记为d(

8、vd(vs s,v,vt t) )。 v1 v2 v3 v4 v5 v6 v7 v8 v9 6 1 2 2 3 1 10 6 410 2 4 3 2 6 3 V 1V 2V 3V 4V 5V 6V 7V 8V 9 -,0(v1,) (v1,) (v1,)(v1,1) v1,1 (v1,6) (v1,6) (v1,3)(v1,)(v1,) (v4,11) (v1,) (v1,) (v1,)(v1,3) v1,3 (v1,) (v1,)(v1,) (v1,)(v3,5) v3,5 (v4,11) (v4,11) (v1,) (v1,)(v2,6) v2,6 (v1,) (v5,9) v5,9 (v

9、5,10)(v5,12) (v1,) (v5,10) v5,10 (v5,12) (v1,) (v1,)(v5,12) v5,12 (v1,) (v1,) v1, 对无向图，与此方法类似。对无向图，与此方法类似。 在所有弧的权都非负在所有弧的权都非负 的情况下，目前公认的情况下，目前公认 最好的求最短路的方最好的求最短路的方 法是法是Dijkstra标号法。标号法。 用实例介绍如下：用实例介绍如下： 例例 求上图中求上图中v1到到v8的最短路。的最短路。 v1 v2 v3 v4 v5 v6 v7 v8 v9 6 1 2 2 3 1 10 6 410 2 4 3 2 6 3 给一个有向图给一个有

10、向图D D(V,A)(V,A)，指定两个点，指定两个点， 一个点称为一个点称为发点发点，记为，记为v vs s，另一个点称为另一个点称为 收点收点，记为，记为v vt t，其余点称为中间点。其余点称为中间点。 5.4 最大流问题最大流问题 5.4.1基本概念和定理基本概念和定理 容量网络容量网络 3 5 1 1 4 2 3 5 2 vs v2 v1v3 v4 vt 对于对于D D中的每一个弧中的每一个弧( (v vi i,v,vj j) )，相应相应地地 给给一个数一个数c cij ij（ （c cij ij0 0），），称为弧称为弧( (v vi i,v,vj j) )的的 容量容量。我们把

11、这样的。我们把这样的D D称为称为网络（或容量网网络（或容量网 络）络），记为，记为D D(V,A,C)(V,A,C)。 流的概念 所谓网络上的所谓网络上的流流，是指定义在弧集，是指定义在弧集A A上的上的 函数函数f ff(vf(vi i,v,vj j)，并称并称f(vf(vi i,v,vj j) )为弧为弧 ( (v vi i,v,vj j) )上的上的流量流量，简记为，简记为f fij ij。 。 4,1 v2 v4 3,1 5,2 1,0 1,0 2,2 3,1 5,2 2,1 vs v1v3 vt 可行流的概念 st 53 42 (4,0) (3,0) (2,0) (1,0) (1,

12、0) (5,0) (3,0) (2,0) (5,0) 容量限制条件：容量限制条件：0fij cij 平衡条件平衡条件： tifv tsi sifv ff Avv ji Avv ij jiji )( ,0 )( ),(),( 对于一个网络而言，可行流总是存在的。对于一个网络而言，可行流总是存在的。 满足下列条件的流称为可行流：满足下列条件的流称为可行流： 3,1 5,2 1,0 1,0 2,2 3,1 5,2 2,1 vs v1v3 vt 4,1 v2v4 最大流问题 就是求一个流就是求一个流fij使其流量达到最大，并且满使其流量达到最大，并且满 足：足： 容量限制条件：容量限制条件：0fij

13、cij 平衡条件：平衡条件： tifv tsi sifv ff Avv ji Avv ij jiji )( ,0 )( ),(),( st 42 31 9(4) 6(1) 9(9) 2(0) 5(4) 7(5) 8(8) 10(8) 5(5) ：把网络中的发点和收点分开，并使把网络中的发点和收点分开，并使st的流中断的一组弧的集合，的流中断的一组弧的集合， 也叫做割。也叫做割。如（如（s,1），（），（s,2） ：网路的最大流等于最小截集容量：网路的最大流等于最小截集容量 一般把包含一般把包含 s 点的节点集合用点的节点集合用V表示，包含表示，包含 t 点的的节点集合用点的的节点集合用 表示表

14、示 V 是指截集中正向弧的容量之和是指截集中正向弧的容量之和 网路的最大流为网路的最大流为14 若把某一截集的弧从网络中去掉，则从若把某一截集的弧从网络中去掉，则从vs到到vt便不存在路。所以，直观便不存在路。所以，直观 上说，截集是从上说，截集是从vs到到vt的必经之路。的必经之路。 V 对于可行流对于可行流f fffij ij ， ，我们把网络中使我们把网络中使f fij ij c cij ij的 的 弧称为弧称为饱和弧饱和弧，使，使f fij ijc 0 0的弧称为的弧称为非零流弧非零流弧。 设设f f是一个可行流，是一个可行流，是从是从v vs s到到v vt t的一条链，若的一条链，

15、若 满足前向弧都是非饱和弧满足前向弧都是非饱和弧, ,后向弧都是都是非零流弧后向弧都是都是非零流弧, , 则称则称是（可行流是（可行流f f的）一条的）一条增广链增广链。 3,1 5,2 1,0 1,0 4,1 2,2 3,1 5,2 2,1 vs v2 v1v3 v4 vt 若若是联结发点是联结发点v vs s 和收点和收点v vt t的一条链，我的一条链，我 们规定们规定链的方向链的方向是从是从v vs s 到到v vt t，则链上的弧被分则链上的弧被分 成两类：成两类：前前向弧、向弧、后后向向 弧弧。 增广链 对最大流问题有下列定理：对最大流问题有下列定理： 定理定理1 1 可行流可行流

16、f f* *ffijij* * 是最大流，是最大流， 当且仅当当且仅当D D中不存在关于中不存在关于f f* *的增广链。的增广链。 定理定理2 2（最大流最小截定理）任一（最大流最小截定理）任一 网络中，最大流的流量等于最小截集的网络中，最大流的流量等于最小截集的 截量截量。 5.4 最大流问题最大流问题 5.4.2 求最大流的标号法求最大流的标号法 标号法思想是：先找一个可行流。标号法思想是：先找一个可行流。 对于一个可行流，经过标号过程得到对于一个可行流，经过标号过程得到 从发点从发点v vs s到收点到收点v vt t的增广链；经过调的增广链；经过调 整过程沿增广链增加可行流的流量，整

17、过程沿增广链增加可行流的流量， 得新的可行流。重复这一过程，直到得新的可行流。重复这一过程，直到 可行流无增广链，得到最大流。可行流无增广链，得到最大流。 标号过程标号过程: : (1) (1)给给v vs s标号标号(-,+)(-,+)，v vs s成为已标号未检查的点，成为已标号未检查的点， 其余都是未标号点。其余都是未标号点。 (2) (2)取一个已标号未检查的点取一个已标号未检查的点v vi i，对一切未标号点对一切未标号点 v vj j：若有非饱和弧若有非饱和弧( (v vi i,v,vj j) )，则则v vj j标号标号( (v vi i,l(v,l(vj j)，其其 中中l(v

18、l(vj j) )minl(vminl(vi i),c),cij ij-f -fij ij ， ，v vj j成为已标号未检查的成为已标号未检查的 点；若有非零弧点；若有非零弧( (v vj j,v,vi i) )，则则v vj j标号标号(-(-v vi i,l(v,l(vj j)，其中其中 l(vl(vj j) )minl(vminl(vi i),f),fji ji ， ，v vj j成为已标号未检查的点。成为已标号未检查的点。 v vi i成为已标号已检查的点。成为已标号已检查的点。 (3) (3)重复步骤重复步骤(2)(2)，直到，直到v vt t成为标号点或所有标号成为标号点或所有标

19、号 点都检查过。若点都检查过。若v vt t成为标号点，表明得到一条成为标号点，表明得到一条v vs s到到v vt t 的增广链，转入调整过程；若所有标号点都检查过，的增广链，转入调整过程；若所有标号点都检查过， 但但v vt t仍未仍未标号，停止标号，表明这时的可行流就是最标号，停止标号，表明这时的可行流就是最 大流，算法结束。大流，算法结束。 调整过程：在增广链上，前向弧流量增加调整过程：在增广链上，前向弧流量增加l(vl(vt t) )， 后向弧流量减少后向弧流量减少l(vl(vt t) )。 下面用实例说明具体的操作方法：例 (3,3) (5,1) (1,1) (1,1) (4,3)

20、 (2,2) (3,0) (5,3) (2,1) vs v2 v1v3 v4 vt (3,3) (5,1) (1,1) (1,1) (4,3) (2,2) (3,0) (5,3) (2,1) vs v2 v1v3 v4 vt 在图中给出的可在图中给出的可 行流的基础上，行流的基础上， 求求vs到到vt的最大流。的最大流。 (-,+) (vs,4) (-v1,1) (-v2,1) (v2,1) (v3,1) (3,3) (5,2) (1,0) (1,0) (4,3) (2,2) (3,0) (5,3) (2,2) vs v2 v1v3 v4 vt (vs,3) (-,+) 得增广链，标号结束，得

21、增广链，标号结束， 进入调整过程进入调整过程 无增广链，标号结束，得无增广链，标号结束，得 最大流。同时得最小截。最大流。同时得最小截。 例某河流中有几个岛屿，从两岸至各岛屿及岛屿之间的桥梁如图。在例某河流中有几个岛屿，从两岸至各岛屿及岛屿之间的桥梁如图。在 一次军事行动中，问至少炸断几座桥，才能完全切断两岸的交通联系？一次军事行动中，问至少炸断几座桥，才能完全切断两岸的交通联系？ A D B C D E F A F D E C B 2(0) 1(0) 3(0) 1(0) 2(0) 1(0) 2(0) 1(0) 1(0) A F D E C B 2(0) 1(0) 3(0) 1(0) 2(0) 1(0) 2(0) 1(0) 1(0) (-, ) (A,2) (B,2) (D,1) A F D E C B 2(1) 1(1) 3(0) 1(0) 2(0) 1(0) 2(1) 1(0) 1(0) (-, ) (A,2) (C,1) (D,1) (E,1) A F