运筹学基础及应用第五图与网络分析

2023/11/121运筹学

OPERATIONSRESEARCH

2023/11/122§1．图的基本概念与模型§2．树图和图的最小部分树§3．最短路问题§4．网络的最大流§5．最小费用流第六章图与网络分析2023/11/123BACD

当地的居民热衷于这样一个问题：一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。哥尼斯堡的七桥问题2023/11/124

为了寻找答案，1736年欧拉把陆地缩为一点，把桥作为连接点的边，将这个问题抽象成图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。BACD2023/11/125

在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。例有六支球队进行足球比赛，我们分别用点v1…v6

表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1

队战胜v2

队，v2

队战胜v3队，v3

队战胜v5

队，如此等等。这个胜负情况，可以用下图所示的有向图反映出来。v3v1v2v4v6v52023/11/126§6.1．图的基本概念与模型

图（graph）是由一些结点或顶点（nodes

orvertices）以及连接点的边（edges）构成。记做G={V,E}，其中V是顶点的集合，E是边的集合。

给图中的点和边赋以具体的含义和权值，我们称这样的图为网络图（赋权图）一、基本概念2023/11/127

图中的点用

v

表示，边用

e表示，对每条边可用它所联结的点表示，如图，则有：e1=[v1,v1]，e2=[v1,v2]或e2=[v2,v1]用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。通常用点表示研究对象,用点与点之间的线表示研究对象之间的特定关系。一般情况下，图中点的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。2023/11/128端点，关联边，相邻

若边e可表示为e

=[vi

,vj]，称vi

和vj是边

e

的端点，同时称边

e

为点vi

和vj的关联边，若点vi

,vj与同一条边关联，称点vi

和vj相邻；若边ei与ej有公共端点，称边ei

和ej相邻；

如果边e

的两个端点相重，称该边为环，如果两个点之间的边多于一条，称为具有多重边，对无环、无多重边的图称为简单图。环，多重边，简单图2023/11/129次，奇点，偶点，孤立点

与某个点相关联的边的数目，称为该点的次（或度、线度），记作

d(v)。次为奇数的点称为奇点，次为偶数的点称为偶点，次为零的点称为孤立点。如图：奇点为v5，v3偶点为v1,v2,

v4,

v6孤立点为

v62023/11/1210链，圈，路，回路，连通图

图中有些点和边的交替序列μ={v0,e1,v1,e2,…,ek

,vk}，若其各边e1,e2,…,ek

各不相同，且任意vi,t-1,vit(2≤t≤k)都相邻，称μ为链，如果链中所有的顶点v0,v1,…,vk也不相同，这样的链成为路，起点和终点重合的链称为圈，起点和终点重合的路称为回路，若在一个图中，每一对顶点之间至少存在一条链，称这样的图为连通图，否则称该图为不连通的。链路圈2023/11/1211完全图，偶图

一个简单图中若任意两点之间均有边相连，称这样的图为完全图，含有

n

个顶点的完全图，其边数有条。如果图的顶点能分成两个互不相交的非空集合V1和V2,使在同一集合中任意两个顶点均不相邻，称这样的图为偶图（也称二分图），如果偶图的顶点集合V1和V2

之间的每一对顶点都有一条边相连，称这样的图为完全偶图，完全偶图中V1含m

个顶点，V2含有n

个顶点，则其边数共m·n条。2023/11/1212子图，部分图

图G1={V1,E1}和G2={V2,E2}，如果有和，称G1是G2的一个子图；若有，则称G1是G2的一个部分图。注意：部分图也是子图，但子图不一定是部分图。子图：部分图2023/11/1213§2．树图和最小部分树

树图（简称树，记作T(V,E)）是无圈的连通图。（无圈，无多重边）

一.树的性质性质1.任何树中必存在次为1的点。

次为1的点称为悬挂点，与之关联的边称为悬挂边。

性质2.具有

n

个顶点的树恰有（n-1）条边。

性质3.任何具有n个点、(n-1)条边连通图是树。说明：

1.树中只要任意再加一条边，必出现圈。

2.树中任意两点之间有且只有一条通路，从树中任意删掉一条边，就不再连通。（树是最脆弱的连通图）2023/11/1214二.图的最小部分树如果G1是G2的部分图，又是树图，则称G1是G2

的部分树（或支撑树）；树图的各条边称为树枝(假定各边均有权重)；树枝总长最小的部分树，称为该图的最小部分树(也称最小支撑树)。定理1.图中任一个点i，若j

是与i相邻点中距离最近的，则边[i,j]一定包含在该图的最小部分树中。推论.把图的所有点分成V和两个集合，则两集合之间连线的最短边一定包含在最小部分树内。2023/11/1215三.避圈法和破圈法

寻找最小部分树的方法主要有避圈法和破圈法两种。

避圈法步骤：1.从图中任选一点vi，让vi

∈V，图中其余点均包含在中；2.从V

与的连线中找出最小边，这条边一定包含在最小部分树中，不妨设这条边为[vi,vj]将其加粗，标记为最小部分树中的边。3.令V∪vj→V，-vj→；4.重复2、3两步，一直到图中所有点均包含在V中。2023/11/1216

避圈法另一种做法：

1.在所有各边中找到边权最小的一条，将其作为最小部分树中的第一边；在剩余的边中，仍然找到边权最小的作为最小部分树的第二条边；2.在剩余的边中，找到边权最小的边，查看其是否与前面的边形成圈，如果没有，则在最小部分树中添加该边，如果形成了圈，则不再考虑该边；3.重复进行第二步，直到找到第n-1条边为止。（因为有n

个顶点的树中一定有n-1条边）2023/11/1217例：分别用两种避圈法构造下图的最小部分树。第一种解法：1.在点集中任选一点，不妨取S，令V={S}

2.找到和S

相邻的边中，权值最小的[S,A]。2023/11/12183.V={S,A}4.重复第2，3步，找到下一个点。2023/11/1219第二种做法求解过程：2023/11/1220破圈法求解步骤：1.从图N中任取一回路，去掉这个回路中边权最大的边，得到原图的一个子图N1。2.从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；3.重复第2步，直到图中不再含有回路为止。用破圈法求解上例：1.任意找到一回路，不妨取DETD，去掉边权最大的边[T,E];2023/11/12212.从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；依次类推。2023/11/1222破圈法的另一种解法：1.从剩余图中找到边权最大的一条边，如果将其删除后图仍然是连通的，则删除此边，否则不再考虑此边；2.重复上述步骤，直到剩余边数为

n-1为止。用此法求解上述问题：2023/11/1223注意：1.一个图的最小部分树不唯一，该题中用几种解法得到的结果都是相同的，是特殊情况；2.不同解法得到的最小部分树所包含的边虽然可能不相同，但是，每个最小部分树中所有边权的总和一定都是相同的，即都达到了最小。2023/11/1224§3．最短路问题最短路问题是指从给定的网络图中找出任意两点之间距离最短（权值和最小）的一条路。某些整数规划和动态规划问题可以归结为求最短路的问题。如选址问题、管道铺设选线问题、设备更新、投资等问题。

最短路的求法：1.从某一点至其它各点之间最短距离的狄克斯屈拉(Dijksrta

)算法;2.求网络图中任意两点之间的最短距离的矩阵算法。2023/11/1225

一.Dijkstra算法1.设

dij

表示图中两相邻点i

与j

的距离，若i

与j

不相邻，令dij

=∞，显然dii=0。

Dijkstra算法假设：基本思路：如果v1→v2→v3→v4是v1→v4

的最短路径，则v1→v2→v3

一定是v1→v3

的最短路径。v2→v3→v4

一定是v2→v4的最短路径。2.设Lsi表示从s点到i

点的最短距离。2023/11/1226Dijkstra算法步骤：1.对起始点

s，因Lss=0，将0标注在s

旁的小方框内，表示s

点已标号；2.从点s

出发，找出与s相邻的点中距离最小的一个，设为

r，将Lsr=Lss+dsr的值标注在r

旁的小方框内，表明点r

也已标号；3.从已标号的点出发，找出与这些点相邻的所有未标号点p，若有Lsp=min{Lss+dsp,Lsr+drp}，则对p点标号，并将Lsp的值标注在p点旁的小方框内；4.重复第3步，直到

t

点得到标号为止。求从起始点s

到终止点t的最短路径。2023/11/1227例.求下图中从v1到v7的最短路。解：(1)

从v1点出发，对v1点标号，将L11=0标注在旁的小方框内，令v1∈V，其余点属于；2023/11/1228L1r=min{0+d12

,0+d13

}=min{5,2}=2=L13(2)

同v1相邻的未标号点有v2、v3，2023/11/1229对

v3

标号，将L13的值标注在v3旁的小方框内；将(v1,v3)加粗，并令V∪v3→V，。2023/11/1230L1p=min{L11+d12

,L13+d34,L13+d36

}=min{0+5,2+7,2+4}=5=L12(3)

同v1,v3相邻的未标号点有v2、v4、v6，2023/11/1231对

v2

标号，将L12的值标注在v2旁的小方框内；将(v1,v2)加粗，并令V∪v2→V，2023/11/1232L1p=min{L12+d25

,L12+d24,

L13+d34

,L13+d36

}=min{5+7,5+2,2+7,2+4}=6=L16。(4)

同v1,v2

,v3相邻的未标号点有v4、v5、v6，2023/11/1233对

v6

标号，将L16的值标注在v6旁的小方框内；将(v3,v6)加粗，并令V∪v6→V，2023/11/1234L1p=min{L12+d25

,L12+d24,L13+d34

,L16+d64,L16+d65,L16+d67

}=min{5+7,5+2,2+7,6+2,6+1,6+6}=7=L14=L15(5)

同v1,v2

,v3,

v6相邻的未标号点有v4、v5、v7，2023/11/1235对

v4,v5同时标号，将L14=L15的值标注在v4,v5旁的小方框内；将(v2,v4),(v6,v5)加粗，并令V∪v4∪v5→V，2023/11/1236L1p=min{L15+d57

,L16+d67

}=min{7+3,6+6}=10=L17(6)

同v1,v2

,v3,v4,v5,

v6相邻的未标号点只有v7，2023/11/1237

对

v7

标号，将L17的值标注在v7旁的小方框内；将(v5,v7)加粗。图中粗线表明从点v1到网络中其它各点的最短路，各点旁的数字就是点v1到各点的最短距离。2023/11/1238二.求任意两点间最短距离的矩阵算法用Dijkstra

算法只能计算从图中某一点到其他点的最短距离，如果要计算各点之间的最短距离就需要对每个点分别计算，而用矩阵算法则可以同时求出所有各点间的最短距离。例.利用矩阵算法求上述网络图中各点间的最短距离。解.设

dij

表示图中两相邻点i

与j

的距离，若i

与j

不相邻，令dij

=∞，显然dii=0。建立距离矩阵：2023/11/12392023/11/1240从上述距离矩阵可以看出从i点到

j点的直接距离，但从i到j的最段距离不一定就是从i点直接到

j点。如上述问题中，从v1→v2的最短距离应该是min{d11+d12,d12+d22,d13+d32,d14+d42,d15+d52,d16+d62,d17+d72}即min{d1r+dr2}。因此可以构造一个新的矩阵D(1)，令D(1)中每一个元素为：dij(1)=min{dir+drj}，则矩阵D(1)给出了网络中任意两点之间直接到达及经由一个中间点时的最短距离。2023/11/1241再构造矩阵D(2)，

dij(2)=min{dir(1)

+drj(1)}。依次类推构造矩阵D(k)，

dij(k)=min{dir(k-1)

+drj(k-1)}

计算停止的控制：

p是图中顶点数。2023/11/1242该例中k=32023/11/1243

上述D(2)

中的元素给出了各点间的最短距离，但是并没有给出具体是经过了哪些中间点才得到的这个最短距离，如果要知道中间点具体是什么，需要在计算过程中进行记录。教材160页例52023/11/1244§4．网络的最大流一.网络最大流的有关概念1.有向图与容量网络图中每条边有规定指向的图称为有向图，有向图的边称为弧，记作(vi,vj)，表示方向从点vi指向点vj，有向图是点与弧的集合，记作D(V,A)。弧(vi,vj)的最大通过能力，称为该弧的容量，记为c(vi,vj)，或简记为cij。定义了弧容量的网络称为容量网络。2023/11/1245容量网络通常规定一个发点(源点，记为s)一个收点(汇点，记为t)，网络中其余的点称为中间点。从发点到收点之间允许通过的最大流量称为最大流。多个收(发)点的网络可以转换为只含一个收(发)点。2.流与可行流流是指加在网络各条弧上的一组负载量，对加在弧(vi,vj)上的负载量记作f(vi,vj)，或简记作

fij，若网络上所有的fij=0，这个流称为零流。2023/11/1246以v(f)表示网络中从s→t

的流量，则零流是可行流，求最大流就是求v(f)的最大值。称网络上满足下述条件(1)、(2)的流为可行流：(1)容量限制条件:对所有弧有0≤f(vi,vj)

≤c(vi,vj)(2)中间点平衡条件：∑f(vi,vj)-∑f(vj,vi)

=0(i≠s,t)2023/11/1247二.割和流量割(集）是指将容量网络中的发点和收点分割开，并使s→t

的流中断的一组弧的集合（截集）弧旁数字为cij(fij)有不同的割见教材162页上图中KK

将网络上的点分割成V和两个集合，并有s∈V,t∈，称弧的集合(V,)={(v1,v3),(v2,v4)}是一个割。注意，这里不包含(v3,v2)。2023/11/1248割的容量是组成它的集合中各弧容量之和，用c(V,)表示，

f(V,)表示通过割(V,)中所有V→方向弧的流量的总和;f(,V)表示通过割中所有→V方向弧的流量的总和，则有：2023/11/1249从s→t

的流量等于通过割的从V→的流量减→V的流量，有：用v*(f)表示网络中从s→t

的最大流，则有因此，上例中最大流不会超过14（所有割集中最小者）

。最大流v*(f)应最小割的容量(用c*(V,)表示)2023/11/1250三.最大流最小割定理增广链：如果在网络的发点和收点之间能找到一条链，在这条链上：所有指向为s→t的弧（称前向弧，记作μ+），存在f<c(非饱和)；（正向弧不饱和）所有指向为t→s的弧（称后向弧，记为μ

-），存在f>0(非零)，（反向弧非零流）这样的链称增广链。2023/11/1251当有增广链存在时，找出再令显然，经过计算后

f’

仍然为可行流，但较原来的可行流f

流量增大了θ。因此，只有当网络图中找不到增广链时，s→t流才不可能进一步增大。2023/11/1252定理2.在网络中s→t

的最大流量等于它的最小割集的容量，即证明：略（教材163页）三.求网络最大流的标号算法

Ford-Fulkerson

标号算法，其本质是判断是否存在增广链，如果存在，则找出增广链，调整流量；若不存在，则说明已达到最大流。2023/11/1253第一步：首先给发点s标号(0,ε(s))。第一个数字是使这个点得到标号的前一个点的代号，因s

是发点，因此记为0。第二个数字ε(s)表示从上一个标号到这个标号点的流量的最大允许调整值，s为发点，不限允许调整容量，故ε(s)=∞。第二步：列出与已标号点相邻的所有未标号点：考虑从标号点

i

出发的弧(i,j)（即正向弧)，如果有

fij=cij，不给点

j

标号；若fij<cij，则对j标号，记为(i,ε(j))，其中

ε(j)=min{ε(i),(cij-fij)}2023/11/1254考虑所有指向标号点i的弧(h,i)（即反向弧)

，如果有fhi=0，对h不标号，若fhi>0，则对h

点标号，记为(i,ε(h))，其中ε(h)=min{ε(i),fhi)}.

如果某未标号点k

有两个以上相邻的标号点，可按(1),(2)中所述规则分别计算出ε(k)的值，并取其中的最大的一个标记。第三步：重复第二步可能出现如下两种结果：

1.标号过程中断，t

得不到标号，说明该网络中不存在增广链，给定流量即为最大流量。记已标号点集为V，未标号点集为，(V,)为网络的最小割。t得到标号，这时可用反向追踪法在网络中找到一条从s→t

的有标号点以及相应的弧连接而成的增广链。2023/11/1255第四步：修改流量。设原图中可行流为f，令这样得到网络上的一个新的可行流

f’

。第五步：抹掉图上所有标号，重复第一到第四步。注意：在求解步骤中，第三步起到控制运算停止的作用，而不是第五步。2023/11/1256例：用标号法求下述网络图

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

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

点标号(s,2)。

(s,v1)饱和，不标号。2023/11/1259(3)弧(v1,v2)，因有f12>0

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

点标号(v2

,2)。

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

点标号(v1

,2)。2023/11/1261(5)弧(v4,v3)，因有f43>0

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

点标号(v3

,1)。

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

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

点标号(v4

,1)。2023/11/1263(7)由于收点t

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

s、v1、v2、v3标号后，标号中断，故图中的可行流即为最大流，v*(f)=14已标号点集为V={s,v1,v2,v3}，未标号点集，(V,)={(3,t),(2,4)}为网络的最小割。2023/11/1266三.应用举例例1：P166，例7ADECBF2321211111、方向含义2、E、D之间3、数字含义切断A、F之间的通路，相当于求最小割集。2023/11/1267例2：P167，例81、匹配关系1234562、匹配限制145f=1f14

f152023/11/1268134f=1f34

f14

3、等价网络图123456st1111111111112023/11/1269§5．最小费用流

在产销平衡问题中，研究的是使费用最小的物资调运方案；最大流问题中考虑了联结两个点之间的弧的容量限制，但是没考虑流量通过各条弧时发生的费用。

实际物资调运中，既要考虑弧的容量又要考虑调运费用的节省，这就是最小费用流要研究的问题。即要寻求一个最大流f，使