运筹基础课程 7

Lecture9

GraphandNetworkAnalysisSchoolofBusinessAdministrationHunanUniversityLecturer:E-mail:

LectureOutlineBasicConceptsofGraphTreesandMinimumSpanningTreeTheShortest-PathProblemTheMaximumFlowProblemTheMinimumCostFlowProblem哥尼斯堡七桥问题一笔画问题欧拉

(E.Euler)0.IntroductionEADCB1.BasicConceptsofGraphGraphComponentandRepresentationAgraphismadeupof

vertices,

nodes,or

points

whichareconnectedby

edges,

arcs,orlines.v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10Forexample一个图G是由点集V={vj}和V

中元素的无序对的一个集合E={ek}构成的二元组，记为G

=(V,

E)，其中V中的元素vj

叫做顶点,V

表示图G

的点集合；E

中的ek

元素叫做边，E

表示图G

的边集合。v4v6v1v2v3v5V={v1,v2,v3,v4,v5,v6}，A={(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)}UndirectedandDirectedGraph无向图:由顶点和边所构成，G=(V,E)有向图:由顶点和弧所构成，D=(V,A)SimpleGraph&CompleteGraph环(loop):若某条边的两个端点是相同。多重边(multipleedges):若两个端点之间有两条以上的边。简单图(simplegraph)：无环也无多重边的图。多重图(multigraph):

一个无环但有多重边的图。完全图(completegraph):每一对顶点间恰有一条边相连的无向简单图。有向完全图(directedcompletegraph):则是指任意两个顶点之间有且仅有一条有向边的简单图。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10以点v为端点的边的个数称为点v

的度(次)，记作deg(v)或

d(v)度为零的点称为孤立点，度为1的点称为悬挂点。悬挂点的关联边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10d(v1)=？d(v2)=？TheDegreeofaVertex43定理1

所有顶点度数之和等于所有边数的2倍。所有顶点的入次之和等于所有顶点的出次之和。有向图中,以vi为始点的边数称为点vi的出次,用d

+(vi)表示；以vi为终点的边数称为点vi的入次，用d

-(vi)表示；vi点的出次和入次之和就是该点的次。定理2

在任一图中，奇点的个数必为偶数。TheRelationshipbetweenDegreesandEdges设G1=(V1,E1),G2=(V2,E2),若

V2

V1

,

E2

E1

,则称G2

是G1的子图；若V2=V1

,

E2

E1

则称G2

是G1

的部分图或支撑子图。v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)G1e5e7v1v2v5v6v7e1e6e8(b)子图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图SubgraphandSpanningsubgraphNetwork

给定一个图G=(V,E)或有向图D=(V,A),在V中指定两个点,一个称为始点(或发点),记作vi,一个称为终点(或收点),记作vn

,其余的点称为中间点。对每一条(vi,vj)

A

或E

,对应一个数wij

,称为弧上的“权”。通常把这种赋权的图称为网络。由两两相邻的点及其相关联的边构成的点边序列称为链。

如:v1,e1,v2,e4,v4,记作(v1,v2,v4)

Linke3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e10e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e10CycleandConnectedGraph若链(v1,v2,…,vn)，有v1=vn，则称之为圈若链中所含的点均不相同则称为初等链若图中任意两点之间均至少有一条链，则称此图为连通图，否则称为不连通图。v1v2v3v4v5v62.TreesandMinimumSpanningTree树(Tree):一个连通的无圈的无向图，T=(V,E)。树中次为1的点称为树叶，次大于1的点称为分支点。v1v2v3v4v5v6

TheCharacteristicsofaTreen

个顶点的树必有n-1

条边。树中任意两个顶点之间，恰有且仅有一条链（初等链）。树连通，但去掉任一条边，必变为不连通。树无回路（圈），但不相邻的两个点之间加一条边，恰得到一个回路（圈）。v1v2v3v4v5v1v2v3v4v5设连通图T=(V,E’)是图G=(V,E)的一支撑子图，如果图T=(V,E’)是一个树,那么称T是G的一个生成树(支撑树)，或简称为图G的树。SpanningTree如果图T=(V,E’)是图G的一个生成树，那么称E’上所有边的权的和为生成树T的权，记作S(T)。如果图G的生成树T*的权S(T*)，在G的所有生成树T中的权最小，即那么称T*是G的最小生成树。MinimumSpanningTreeTheApplicationofMST某六个城市之间的道路网如图所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。v1v2v3v4v5v66515723445v1v2v3v4v5v612344AlgorithmfortheMinimumSpanningTreeProblem避圈法（Kruskal,1956)将所有边按权值从小到大排序，每次从未选的边中选一条权最小的，逐步衔接，但不接成圈破圈法（管梅谷,1975）任取一个圈，从中去掉权最大的边。在余下的图重复该步骤，直到不含圈为止例：避圈法v1v21v32v412v5v1v2v3v4v514231352例：破圈法最短路问题描述：设G=(V,E)为连通图,图中各边(vi

,vj)的权为wij

(wij=+∞表示vi

,vj之间没有边),vs

,vt为图中任意两点，求一条路P0，使它为从vs到vt的所有路P中总权最小。3.TheShortest-PathProblem则称P0为从vs到vt的最短路。实际应用：管道铺设、线路安排、厂区平面布局、设备更新等。基本思想：从始点出发，逐步地向外探寻最短路。执行过程中给每个点标号，其中固定标号P表示从始点到该点的最短通路长度，临时标号T表示从始点到该点的最短通路长度上界，方法的每一步都把某个点的T标号修改为P标号，这样一旦终点得到P标号，算法终止。狄杰斯特拉(Dijkstra)算法适用于不含负权的网络。(1)

给始点vs以P标号P(vs)=0,表示从vs到

vs的最短距离为0,其余节点均给T标号,T(vi)=+∞(i=2,3,…,n)

;(2)

设节点vi

为刚得到P标号的点,考虑点vj，其中(vi,vj)

E,且vj为T标号。对vj的T标号进行如下修改：T(vj)=min{T(vj),P(vi)+wij}(3)

比较所有具有T标号的节点,把最小者改为P标号,即：

P(vk)=min{T(vi)}当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤(2)。狄杰斯特拉(Dijkstra)算法例、用Dijkstra算法求下图从v1到v6的最短路。v1v2v3v4v6v5352242421

解（1）首先给v1以P标号，给其余所有点T标号。（2）（3）（4）v1v2v3v4v6v5352242421（5）（6）（7）（8）（9）（10）反向追踪得v1到v6的最短路为：首先设任一点vi到任一点vj都有一条弧，该如果不在原网络中,即(vi,vj)

A，则令wij=+∞)

。显然，从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi,vj)到vj，则v1到vi的这条路必然也是v1到vi的所有路中的最短路。设P1j表示从v1到vj的最短路长，P1i表示从v1到vi的最短路长，必满足下列方程：

Warshall-Floyd算法求解步骤第1步，令

即用v1到vj的直接距离做初始解。第2步，使用递推公式：求，当进行到第t步，若出现停止计算，即为v1到各点的最短路长。第3步，逆向追踪得到从v1到vj的最短路径例

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v837求图中v1到各点的最短路第1步，P11(1)=0,P12(1)=-1,P13(1)=-2,P14(1)=3,P15(1)=+∞,P16(1)=+∞,P17(1)=+∞,P18(1)=+∞;第2步，利用递推公式P11(2)=min[0+0,-1+6,-2+∞,3+8,∞+∞,∞+∞,∞+∞,∞+∞]=0P12(2)=min[0+(-1),-1+0,-2+(-3),3+∞,∞-1,∞+∞,∞+∞,∞+∞]=-5P13(2)=min[0+(-2),-1+∞,-2+0,3+∞,∞+∞,∞+∞,∞+∞,∞+∞]=-2P14(2)=min[0+3,-1+∞,-2+(-5),3+0,∞+∞,∞+∞,∞-1,∞+∞]=-7P15(2)=min[0+∞,-1+2,-2+∞,3+∞,∞+0,∞+1,∞+∞,∞-3]=1

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v837v1v2v3v4v5v6v7v8P(1)P(2)P(3)P(4)v10-1-23

∞∞∞∞0000v260∞

∞

2∞∞∞-1-5-5-5v3∞

-30-5

∞1∞∞-2-2-2-2v48∞

∞0

∞∞2∞3-7-7-7v5∞

-1

∞∞

0∞∞

∞∞

1-3-3v6∞

∞

∞∞

1017∞

-1-1-1v7∞

∞

∞-1

∞∞0

∞∞

5-5-5v8∞

∞∞∞-3∞-50∞

∞

66第3步，逆向追踪得从v1到v8的最短路是(v1,v3,v6,v8),长度为6。第2步递推计算最短路问题的应用案例设备更新问题

某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧设备，则需支付一定的维修费用。现在的问题是如何制定一个五年之内的设备更新计划，使得总的支付费用最少。若已知该种设备在各年年初的价格及其维修费用如下。第i年度12345购置费1111121213设备役龄0-11-22-33-44-5维修费用5681118例求：5年内，哪些年初购置新设备，使5年内的总费用最小。解：（1）分析：可行的购置方案（更新计划）是很多的，如：1）每年购置一台新的，则对应的费用为：

11+11+12+12+13+5+5+5+5+5=842)第一年购置新的，一直用到第五年年底，则总费用为：11+5+6+8+11+18=59

显然不同的方案对应不同的费用。第i年度12345购置费1111121213设备役龄0-11-22-33-44-5维修费用5681118（2）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。求解步骤：1）画赋权有向图：

设Vi

表示第i年初，(Vi,Vj

)表示第i

年初购买新设备用到第j年初（j-1年底），而Wij

表示相应费用，则5年的一个更新计划相当于从V1

到V6的一条路。2）求解（标号法）W12=11+5=16W13=11+5+6=22W14=11+5+6+8=30W15=11+5+6+8+11=41W16=11+5+6++8+11+18=59W23=11+5=16W24=11+5+6=22W25=11+5+6+8=30W26=11+5+6+8+11=41W45=12+5=17W46=12+5+6=23W56=13+5=18W34=12+5=17W35=12+5+6=23W36=12+5+6+8=31某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用，而且随着设备的老化会逐年增加。计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。年份12345购置费1820212324使用年数0~11~22~33~44~5维修费57121825年份12345购置费1820212324使用年数0~11~22~33~44~5维修费5712182528v1v2v3v4v5v62325262930426085324462334530设一个赋权有向图D=(V,A),在V中指定一个发点vs和一个收点vt

,其它的点叫做中间点。对于D中的每一个弧(vi

,vj)∈A,都有一个非负数cij,叫做弧的容量。通常将这样的图D叫做一个容量网络，简称网络，记做D=(V，A，C)。网络D上的流，是指定义在弧集合A上的一个函数其中f(vi

,vj)=fij

叫做弧(vi，vj)上的流量。4.TheMaximumFlowProblem*称满足下列条件的流为可行流：（1）容量条件：对于每一个弧(vi,vj)∈A有0

fij

cij

（2）平衡条件： 对于发点vs，有 对于收点vt

，有 对于中间点，有可行流中fij＝cij

的弧叫做饱和弧，fij＜cij的弧叫做非饱和弧。fij＞0的弧为非零流弧，fij＝0的弧叫做零流弧。可行流流量13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)图中为零流弧，其余为非饱和弧。例定理可行流f是最大流的充分必要条件是不存在从vs到vt

的关于f的一条可增广链。增广链13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)是一个增广链显然图中增广链不止一条例截集vsv1v2v4v3vt374556378S例13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)设，则截集为容量为2413(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)设，则截集为容量为20求最大流的标号法调整过程设1．令2．去掉所有标号，回到第一步，对可行流重新标号。求下图所示网络中的最大流，弧旁数为(1,1)v2v1v4v3vsvt(3,3)(5,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)(1,1)v2v1v4v3vsvt(3,3)(5,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)（0，+∞）（-v1,1）（+vs,4）（-v2，1）（+v2，1）(+v3，1)例(1,0)v2v1v4v3vsvt(3,3)(5,2)(1,0)(4,3)(2,2)(3,0)(5,3)(2,2)(1,0)v2v1v4v3vsvt(3,3)(5,2)(1,0)(4,3)(2,2)(3,0)(5,3)(2,2)（0，+∞）（+vs,3）最小截集13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)13(11)9(9)4(0)5(5)6(6)5(5)5(4)5(4)4(4)4(3)9(9)10(7)截集1截集2最小截量为：9+6+5=2070（70）70（50）130（100）150（130）150（150）50（20）50（50）120（30）100（100）∞（120）∞（230）∞（150）∞（200）已知网络G=（V，E，C，d），f是G上的一个可行流，为一条从vs到vt的增广链，称为链的费用。

结论：如果可行流f在流量为W(f)的所有可行流中的费用最小，并且*是关于f的所有增广链中的费用最小的增广链，那么沿增广链u*调整可行流f，得到的新可行流f*也是流量为W(f*)的所有可行流中的最小费用流。当f*

是最大流时，就是最小费用最大流。若*是从vs到vt的增广链中费用最小的增广链，则称*是最小费用增广链。5.TheMinimumCostFlowProblem寻找关于f的最小费用增广链：构造一个关于f的赋权有向图L(f)，其顶点是原网络G的顶点，而将G中的每一条弧(vi,vj

)变成两个相反方向的弧（vi，vj）和(vj

,vi)，并且定义图中弧的权lij为：1.当，令

2.当（vj，vi）为原来网络G中（vi，vj）的反向弧，令在网络G中寻找关于f的最小费用增广链等价于在L(f)中寻求从vs

到vt

的最短路。步骤：（1）取零流为初始可行流，f(0)={0}。（2）一般地，如果在第k-1步得到最小费用流f(k-1)，则构造图L(f(k-1)

)。（3）在L(f(k-1)

)中，寻求从vs到vt的最短路。若不存在最短路，则f(k-1)就是最小费用最大流；否则转(4)。（4）如果存在最短路，则在可行流f

(k－1)的图中得到与此最短路相对应的增广链，在增广链上，对f

(k－1)进行调整，调整量为：令得到新可行流f

(k)。对f

(k)重复上面步骤，返回（2）。例

求网络的最小费用最大流，弧旁权是（bij,cij）(3,2)vsv2v1vtv3(1,4)(6,7)(4,8)(1,6)(2,5)(2,3)3vsv2v1vtv3164122(1)L(f(0))(3,2)vsv2v1vtv3(1,4)(6,7)(4,8)(1,6)(2,5)(2,3)0vsv2v1vtv3300333(2)f(1)

1=3W(f(1))=3－1(3)L(f(1))－23vsv2v1vtv316412－1－21vsv2v1vtv3400343(4

)f(2)

2=1W(f(2))=4(3,2)vsv2v1vtv3(1,4)(6,7)(4,8)(1,6)(2,5)(2,3)(5)L(f(2))－3vsv2v1vtv3－1412－2－23－1661vsv2v1vtv3401453(6

)f(3)

3=1W(f(3))=5(7)L(f(3))vsv2v1vtv3－3－1