运筹学课件：6图与网络分析

第六章

图与网络分析

6.1图的基本概念

6.2树图和图的最小部分树

6.3最短路问题

6.4网络最大流问题

6.5网络模型的实际应用（1）图：点V和边E的集合，用以表示对某种现实事物的抽象。记作G=｛V,E｝,V=｛v1,v2,···,vn｝,E=｛e1,e2,···,em｝点：表示所研究的事物对象；边：表示事物之间的联系。端点关联边两点相邻两边相邻（2）若边e的两个端点重合，则称e为环。（3）多重边：若某两端点之间多于一条边，则称为多重边。v1v2v3v4v0e1e2e3e4e5e6e7e0

6.1图的基本概念

图是一种模型，如公路、铁路交通图，通讯网络图等。图是对现实的抽象，以点和线段的连接组合表示。（4）简单图：无环、无多重边的图称为简单图。（5）链：点和边的交替序列，其中点可重复，但边不能重复。（6）路：点和边的交替序列，但点和边均不能重复。（7）圈：始点和终点重合的链。（8）回路：始点和终点重合的路。（9）连通图：若一个图中，任意两点之间至少存在一条链，称这样的图为连通图。（10）子图，部分图：设图G1=｛V1,E1｝,G2={V2,E2},如果有V1V2，E1E2，则称G1是G2的一个子图；若V1=V2，E1E2，则称G1是G2的一个部分图。（11）次：某点的关联边的个数称为该点的次，以d(vi)表示。

次为奇数的点称为奇点，次为偶数的点称为偶点，次为0的点称为孤立点例：有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛。如表中所示，打“√”的项目是各运动员报名参加比赛的项目。问：六个项目的比赛顺序应如何安排，才能做到使每名运动员不连续地参加两项比赛？甲乙丙丁戊己项目人ABCD EF √√√√ √ √ √ √ √ √ √√ √解：项目作为研究对象，排序。设点：表示运动项目。边：若两个项目之间无同一名运动员参加。ADEFBCA—C—D—E—F—BA—F—E—D—C—BA—C—B—F—E—DA—F—B—C—D—E顺序：（1）树：无圈的连通图称为树图，简称为树。一、树图的概念6.2树图和图的最小部分树（2）树的特性：①树是边数最多的无圈连通图。在树中任加一条边，就会形成圈。②树是边数最少的连通图。在树中任减一条边，则不连通。（3）图的最小部分树：定义：若G1是G2的一个部分图，且为树图，则称G1是G2的一个部分树。G2：ABCD547365576G1：ACBD图的最小部分树：树枝总长为最短的部分树。树枝：树图中的边称为树枝。SABCDET252414317557最小部分树长Lmin=14二、最小部分树的求法例1：要在下图所示的各个位置之间建立起通信网络，试确定使总距离最佳的方案。1.避圈法：开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选边不构成圈的边。2.破圈法：任选一个圈，从圈中去掉权最大的一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。SABCDET252414317557××

××××最小部分树长Lmin=14例2v1v2v3v5e2e3e5e1e6e7e8破圈法v1v2e1v3e2e4e4v4v4v5e6避圈法v2e2e3e5e4v4v1v3v5e1e6e7e86.3最短路问题最短路问题一般是求解图中任意两点间距离最短的路径及其长度。这里所说的距离最短是指广义概念而言的，也就是说，根据图中各条边上权数的含义的不同，最短路问题还包括最优设备更新问题、最佳路线问题等。最短路问题包括两种类型：一种是求图中某点到另一点的最短路，或是某点到其余各点的最短路，即有确定起点的最短路问题。另一种是求图中任意两点间的最短路，即无确定起点的最短路问题。对于第一种类型的问题，本节将介绍Dijkstra标号算法；而第二种类型的问题，本节将介绍矩阵算法。一、Dijkstra标号算法1.Dijkstra标号算法的基本思路是：如果v1→v2→v3→v4是v1→v4的最短路，那么v1→v2→v3

一定是v1→v3的最短路之所以将某点到另一点的最短路和某点到其余各点的最短路归结为一种类型的问题，原因在于图中某点到另一点的最短路一般要途经若干个点，根据Dijkstra标号算法的基本思路，则要依次计算出某点到各途经点的最短路，进而求出确定两点间的最短路。不失一般性，当确定两点间的最短路途径了图中其他所有点时，意味着我们在计算出某点到另一点的最短路之前，已经分别计算出了某点到各途经点的最短路，也即求出了某点到图中其余各点的最短路。另外，Dijkstra标号算法既能对无向图进行求解，又能对有向图进行求解。2.Dijkstra标号算法的计算步骤(以求vs→vt的最短路为例)被标号的点分为两种类型，一种是以中括号形式进行标记，表示该点为永久标号点；另一种是以小括号形式进行标记，表示该点为临时标号点。每一点的标号又分为两部分，数字表示起点到该点的距离，字母表示通过哪点对该点进行标号。①首先给起点vs标号vs[Lss,vs]=[0,vs]。对其他点vj进行标号，若vs与vj相邻且边或弧上的权数是dsj，则vj的标号为(Lss+dsj,vs)，否则vj的标号为(+∞,vs)。②选择所有临时标号点中标号数值最小的点，将其变为永久标号点，设其为vi[Lsk+dki,vk

]。现考虑用新的永久标号点来更新所有临时标号点，不失一般性，设临时标号点为vj(Lsp+dpj,vp)。若Lsp+dpj

＜

Lsi+dij

，则vj的标号不更新；若Lsp+dpj

＞

Lsi+dij

，则vj的标号更新为(Lsi+dij

,vi)；若Lsp+dpj

＝

Lsi+dij

，则vj的标号表示为(Lsi+dij

,vi,vp)。这表示对vj标号为现有数值的途径有两种，分别是通过vi和vp

点。③若临时标号点vj有多种标号形式，则选择Lsj＝min{Lsi+dij

,Lsp+dpj

}，其中vi和vp点为永久标号点，vj仍为临时标号点。④重复上述过程，直到终点vt也取得了永久性标号。如需求vs到图中各点的最短路，须按上述方法计算至所有点都成为永久标号点为止。⑤每个永久标号点的数字标号为起点到该点的最短路长度，通过对字母标号的反向追踪可确定最短路径。例：求右图中v1到v7的最短路。v2v57●●●●●●●v1v3v4v6v7572262

4136[0,--](5,v1)(2,v1)

(+∞,v1)

(+∞,v1)

(+∞,v1)

(+∞,v1)[2,v1](5,v1)(9,v3)(6,v3)

(+∞,v1)

(+∞,v1)[5,v1](7,v2)(12,v2)(6,v3)

(+∞,v1)[6,v3](7,v6)(7,v2)(12,v6)[7,v2][7,v6](10,v5)[10,v5]v1到v7的最短路为10，路径为v7v5→v6→v3→v1→[--,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](v5,10)(v5,12)

(v1,∞)(v5,10)[v5,10](v5,12)

(v1,∞)

(v1,∞)(v5,12)[v5,12](v1,∞)

(v1,∞)[v1,∞]例4求上图中v1到v8的最短路。v1v2v3v4v5v6v7v8v9612231106410243263二、求任意两点间最短距离的矩阵算法⑴构造任意两点间直接到达的最短距离矩阵D（0）=dij（0）SABCDETS0254A2027B520153C4104D75015E34107T570D（0）=⑵构造任意两点间直接到达、或者最多经过1个中间点到达的最短距离矩阵D（1）=dij（1）其中dij（1）=min{

dir（0）+drj（0）}

，SABCDETS024498A20237512B42014310C43105411D9745015E8534106T121011570D（1）=irjdir（0）drj（0）rdSE（1）=min{dSS（0）+dSE（0）,dSA（0）+dAE（0）,dSB（0）+dBE（0）,dSC（0）+dCE（0）,dSD（0）+dDE（0）

,dSE（0）+dEE（0）,dST（0）+dTE（0）

}=8例如其中dij（2）=min{

dir（1）+drj（1）}SABCDETS02448714A20236511B4201439C43105410D8645015E7534106T1411910560D（2）=irjdir（1）drj（1）r⑶构造任意两点间最多可经过3个中间点到达的最短距离矩阵D（2）=dij（2）其中dij（3）=min{

dir（2）+drj（2）

}SABCDETS02448713A20236511B4201439C43105410D8645015E7534106T1311910560D（3）=irjdir（2）drj（2）r⑷构造任意两点间最多可经过7个中间点到达的最短距离矩阵D（3）=dij（3）说明：一般，对于D（k）=dij（k），其中dij（k）=min{dir（k-1）+drj（k-1）}，k=0，1，2，3，······

最多可经过2k-1个中间点：其数列为

{0，1，3，7，15，31，······，2k-1，······}收敛条件：当D（k+1）=D（k）时，计算结束；设网络中有p个点，即有p-2个中间点，则2k-1-1<p-22k-1k-1<log2(p-1)k∴K<log2(p-1)+1，∴计算到k=lg(p-1)/lg2+1时，收敛，计算结束。例：有7个村镇要联合建立一所小学，已知各村镇小学生的人数大致为S—30人，A—40人，B—20人，C—15人，D—35人，E—25人，T—50人。问：学校应建在那一个地点，可使学生总行程最少？SABCDETS02448713A20236511B4201439C43105410D8645015E7534106T1311910560L=30402015352550人数=[1325103088010359108651485]T解：6.4网络最大流问题一、网络最大流中有关概念⑴有向图：含有以箭头指示方向的边的网络图。⑵弧：有向图上的边称为弧。用（vi,vj）表示。⑶弧的容量：弧上通过负载的最大能力，简称容量。以cij表示。⑷流：加在网络每条弧上的一组负载量，以fij表示。⑸可行流：能够通过网络的负载量，通常应满足两个条件：①容量限制条件：对所有的弧，0fijcij

②

中间点平衡条件：对任何一个中间点，流入量=流出量⑹发点、收点、中间点：流的起源点称发点，终到点称收点，其余的点称中间点。⑺最大流；能够通过网络的最大流量。⑻割集：一组弧的集合，割断这些弧，能使流中断。简称割。8(8)v1vsv2v3v4vt7(5)9(4)9(9)2(0)6(1)5(5)10(8)(0,+∞)(vs,2)(v2,2)(v1,2)(v3,1)(v4,1)5(4)cijfij⑼割的容量：割集中各弧的容量之和。⑽最小割：所有割集中容量之和为最小的一个割集。⑾前向弧μ+：一条发点到收点链中，由发点指向收点的弧，又称正向弧。⑿后向弧μ-：一条发点到收点链中，由收点指向发点的弧，又称逆向弧。⒀增广链：由发点到收点之间的一条链，如果在前向弧上满足流量小于容量，即fij<cij，后向弧上满足流量大于0，即fij>0，则称这样的链为增广链。定理：网络的最大流量等于它的最小割集的容量。定理：当网络中不存在任何增广链时，则网络达到最大流状态。二、两个定理st6(4)5(3)4(4)8(7)设有如下增广链：∵△f=1∴该网络没有达到最大流状态。二、求最大流的标号法标号法思想是：先找一个可行流。对于一个可行流，经过标号过程得到从发点vs到收点vt的增广链；经过调整过程沿增广链增加可行流的流量，得新的可行流。重复这一过程，直到可行流无增广链，得到最大流。标号过程:(1)给vs标号(-,+∞)，vs成为已标号未检查的点，其余都是未标号点。(2)取一个已标号未检查的点vi，对一切未标号点vj：若有非饱和弧(vi,vj)，则vj标号(vi,l(vj))，其中l(vj)＝min[l(vi),cij-fij]，vj成为已标号未检查的点；若有非零弧(vj,vi)，则vj标号(-vi,l(vj))，其中l(vj)＝min[l(vi),fji]，vj成为已标号未检查的点。vi成为已标号已检查的点。(3)重复步骤(2)，直到vt成为标号点或所有标号点都检查过。若vt成为标号点，表明得到一条vs到vt的增广链，转入调整过程；若所有标号点都检查过，表明这时的可行流就是最大流，算法结束。调整过程：在增广链上，前向弧流量增加l(vt)，后向弧流量减少l(vt)。

例：用标号法求下述网络图

s→t的最大流量，并找出该网络图的最小割。解：(1)先给s

点标号(0,∞)；(2)从s点出发的弧(s,v2)，因有fs2<cs2，且ε(v2)=min{ε(s),(cs2-fs2)}=2故对v2

点标号(s,2)。(s,v1)饱和，不标号。(3)弧(v1,v2)，因有f12>0

，且ε(v1)=min{ε(v2),f12)}=2故对v1

点标号(v2

,2)。(v2,v4)饱和，不标号。(4)弧(v1,v3)，因有f13<c13，且ε(v3)=min{ε(v1),(c13-f13)}=2故对v3

点标号(v1

,2)。(5)弧(v4,v3)，因有f43>0

，且ε(v4)=min{ε(v3),f43)}=1故对v4

点标号(v3

,1)。(v3,t)饱和，不标号,v2已标号。(6)弧(v4,t)，因有f4t<c4t

，且ε(t)=min{ε(v4),(c4t-f4t)}=1故对t

点标号(v4

,1)。(7)由于收点t

得到标号，用反追踪法找出网络图上的一条增广链。(8)修改增广链上各弧的流量：非增广链上的所有弧流量不变，这样得到网络图上的一个新的可行流。重复上述标号过程，由于对点

s、v1、v2、v3标号后，标号中断，故图中的可行流即为最大流，v*(f)=14已标号点集为V={s,v1,v2,v3}，未标