运 筹 学
(Operational Research)
第六章 图与网络分析
本章主要内容
图论基础知识
最短路问题
最小生成树问题
最大流问题
网络计划
一、哥尼斯堡七桥问题
欧洲的普瑞格尔河流过哥尼斯堡市中心，河中有岛两座，筑有七座古桥，经常有人上岛散步，久而久之，人们就提出了如下的智力问题：能否过每座桥恰一次，再返回出发点。这就是七桥问题（如右图）
现在将四块陆地看作四个点，若两块陆地之间有一座桥，则用一条线连起来，得到右图。这样就转化为一笔画问题（即是否是Euler图问题）即能否从某一点开始一笔画出这个图形，最后回到原点，而不重复。
二、四色问题
1852年，伦敦一位学生Guthrie提出一个猜想：任意给定一张无色地图，把每国版图染上一种颜色，且使邻国异色，用四种颜色足矣。如右图
将七个国家A,B,C,D,E,F,G收缩为7个点，若两个国家相邻则用一条线连起来，就得到下图。这实际是图论中的顶点着色问题。即用四种颜色就可使得任意相邻的两个顶点的颜色均不相同。
A
B
C
D
E
F
G
三、Ramsey问题
1928年，英国数学家、哲学家、经济学家拉姆赛（Ramsey)提出了这样一个问题：任给n个人，其中必有p人彼此相识或者q人彼此不相识，问n至少是几？
把上述最小的n记作r(p,q),到现在为止，只求出了9个数，比如
r(3,3)=6, r(3,4)=9， r（3，5）=14
任意6个人，其中必有3个人相识，或3个人不相识。这就是Ramsey问题中的一个结果。将每个人看作一个点，任意两人之间均用一条红线（表示二人相识）或蓝线（表示二人不相识）连起来（如下图）。B,C,F三人相识。
A
B
C
D
E
F
§1 图论基础知识
图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物之间具有这种关系。
一、图的基本概念
图(Graph)是由一些点和连接一对点的若干条线段组成。点称为图的顶点（Vertex），线段称为图的边(Edge)。若记V={v1,v2,…vn},E={e1,e2,…em},则G=(V,E).
连接顶点u,v的边e可记为e=[u，v]，并称u和v为边e的两个端点，边e与顶点u和v相关联，顶点u和v相邻。与同一个顶点相关联的两条边也称为相邻的。
u
e
v
e2
环（Loop) 两个顶点重合的边。(如e1)
多重边(multiple edge)两个顶点之间有多与一条边。(如e4 和e5)
简单图 (simple graph) 无环和多重边的图。
度（ 次 degree） 以点v为端点的边的个数。记为d（v）。
（注意：算次时环算两条边）如 d(v1)=4 ,d(v2)=2
奇点(Odd vertex) 度为奇数的点。(如v3,v5)
偶点(Even vertex) 度为偶数的点。(如v1,v2)
孤立点 次为0的点。（如v6)
悬挂点 次为1的点。(如v5)
v2
v1
v3
v4
v5
v6
e1
e2
e3
e4
e5
e6
e7
链（chain）图中点、边的交错序列(v1e1v2e2…vt-1et-1vt),如果满足ek=[vk,vk+1]（k=1，2，…，t-1），则称为一条连接v1到vt的链。
初等链(primary chain) 点都不同 链。
圈(cycle) 起点与终点重合的链（即v1=vt）。
初等圈 (primary cycle)除了起点和终点外，其它点均不同的圈。
简单圈(simple cycle) 边不相同的圈。
连通图 (connected graph)任意两点均存在链的图。
支撑子图(Spanning Subgraph)：称G/=(V,E’)为G=(V,E) (其中E’是E的子集)的支撑子图。
v3
v2
e2
v1
v4
v5
e1
e3
e5
e6
e7
二、两个简单定理
Theorem Ⅰ 图G=(V,E)中，所有点的度之和是边数的两倍。
证明：因为计算度时，每条边被它的端点各用了一次，所以所有点的度之和是边数的两倍。
Theorem Ⅱ 任一个图中，奇点的个数为偶数。
证明：∵∑奇点的度（奇数)+ ∑偶点的度( 偶数）
=2×边数=偶数
∴∑奇点的次=偶数
∴奇点有偶数个
三、有向图
定义： 一个有向图(Directed Graph 或 Digraph) G是由点及含有箭头的边（称为弧）所构成，记为D=(V，A). 其中V 称为图G的顶点集(Vertex Set)或节点集(Node Set)，V中的每一个元素称为该图的一个顶点(Vertex)或节点(Node)； A称为图的弧集(Arc Set)，A中的每一个元素(即称为该图的一条从vi到vj的弧 (Arc).一条方向是从vi指向vj的弧记为(vi,vj).
设G=(V,A), 称 为G的子图(Subgraph)
图的支撑子图 (Spanning Subgraph，又称生成子图)是包含G 的所有顶点的子图。
如果对有向图G中的每条弧赋予一个或多个实数，得到的有向图称为赋权有向图或有向网络, 简称为网络(Network).
有向图的链或途径(Walk)是该图的一些顶点v1,v2, …,vr和弧a1,a2,...,ar所组成的子图，这些顶点与弧可以交错排列成点弧序列v1a1v1a2...ar-1vr 其中 ak=(vk,vk+1)或 ak=(vk+1,vk) (k=1,2,...,r-1)
v1
v2
v3
v4
v5
如果链中的所有弧都指向同一方向，即
则称其为从v1到vr的一条路(Directed Walk).；若路的第一点与最后一点相同，则称之为回路。
§2 最短路问题
最短路问题就是从给定的赋权图中找出任意两点之间距离最短（权最小）的一条路。用Lst表示从s到t的最短路，dst表示边[s，t]的权。
一、Dijkstra算法(dst≥0)
基本思路：最短路中的一部分还是最短路。
算法（从s到t顺序算法）
§2 最短路问题
1、从s点出发，将Lss=0表注在s旁的小方框内，表示s点已标号；
2、从s点出发，找出与s相邻的点中距离最小的一个，设为r。将Lsr=LSS+dsr的值表注在r旁的小方框内，表明点r也已标号；
3、从已标号的点出发，找出与这些点相邻的所有未标号的点。若有LSP=min[Lss+dSP，Lsr+drp]（其中s，r为已标号的点，p为未标号的点），则对p点标号，并将LSP的值标注在p点旁的小方框内；
4、重复第3步，一直到t点得到标号为止。
§3 最小生成树问题
例1 含6个顶点的树（共有6种）：
1、弧的条数 = 节点数 - 1
2、任何两个顶点之间存在唯一的一条路
定义：无圈的连通图称为树。
一、图的概念
二、树的性质
1、任何树中必存在次为1的顶点。
2、树的边数等于数的顶点数减1。
3、任何具有n个顶点n-1条边的连通图是树。
4、树的任何两点之间有且只有一条路。
5、在树中任意去掉一条边后，便得到一个不连通的图。
6、树中任加一条边后就出现一个圈。
三、最小生成树
赋权图 各边都赋有一个实数（称为权）的图。
生成树 G的生成子图且为树。
最小生成树 G中权最小的生成树。
定理：图中任一点u，若v是与u相邻点中权最小的，则边[u，v]必含在该图的最小生成树中。
推论：把图的所有点分成V和VC两个集合，则两集合之间连线的最短边（权最小的边）必在最小生成树内。
四、最小生成树的求法
法一：避圈法（Kruskal算法）
1、从图中任选一点vi，让vi∈V，图中其余点均属于VC；
2、从V与VC的连线中找出最小边，不妨设为[vi，vj]，则此边必在最小树内，并将此边加粗；
3、令V∪vj → V，VC\vj → VC；
4、重复2、3两步，一直到图中所有点均包含在V中为止。
法二：破圈法
从图中任取一回路，去掉这个回路中权数最大的一条边，得一子图，再从子图中任取一回路，去掉这个回路中权数最大的一条边，如此继续下去，直到剩下的子图中不再含有回路为止。该子图就是最小生成树。
例2：用Kruskal算法计算最小树：
1
1
3
2
5
4
6
3
8
5
2
4
7
1
3
5
2
1
2
3
4
5
§4 网络最大流问题
一、基本概念与基本定理
(1) 网络与流
定义1 （有向图）由点与带箭头的连线（称为弧）组成的图（D）。一条方向是从vi指向vj的弧记为（vi，vj）。
定义2 给一个有向图D=（V，A），通常指定一个点为发点（源点，记为vs），另一个点为收点（汇点，记为vt）,其余点为中间点.对于每一条弧（vi，vj）∈A，对应有一个c（vi，vj）≥0(或简记为cij)(表示每条弧通过的最大容量),称为弧的容量.通常将这样的图称为网络.记作D=(V,A,C).
定义3 所谓网络上的流,是指定义在弧集合上的一个函数f={f（vi，vj）},并称f（vi，vj）为弧（vi，vj）上的流量(简记为fij).
定义4 满足下述条件的流称为可行流:
1) 容量限制条件:对每一对弧（vi，vj）∈A,有0≤fij≤cij
2) 平衡条件:
对于中间点:流出量=流入量,即对每一个i(i≠s,t)有
∑fij-∑fji=0
对于发点vs,记
∑fSj-∑fjS=v(f)
对于收点vt,记
∑ftj-∑fjt=v(f)
其中v(f)表示发点的净输出量(或收点的净输入量)称为这个可行流的流量.
(2)可行流与最大流
可行流是存在的,如零流(所有弧的流量均为零).
最大流问题就是求一个流{fij}使其流量v(f)达到最大,并且满足:
0≤fij≤cij （vi，vj）∈A (1)
(2)
(3)增广链
给定一个可行流f=(fij),在网络中使fij=cij的弧称为饱和弧,使fij<cij的弧称为非饱和弧, 使fij=0的弧称为零流弧, 使fij>0的弧称为非零流弧.
若μ是网络中连接发点与收点的链,则称在这条链上所有指向为s→t的弧为向前弧,(其全体记作μ+),其余弧为向后弧(其全体记作μ-)
定义5 设f为可行流, μ是从vs到vt的链,若μ满足下列条件,称之为(关于可行流f的)一条增广链.
在弧（vi，vj）∈μ+上, 0≤fij<cij ,即在μ+中每一条弧是非饱和弧.
在弧（vi，vj）∈μ-上, 0<fij≤cij ,即在μ-中每一条弧是非零流弧.
定义6 将网络中的收点s和发点t分割开,并使s→t的流中断的一组弧的集合称为截集(或割),用(V, Vc)表示(其中vs∈V,vt∈Vc).
截集中所有弧的容量之和称为截量(割的流量),记为c(V,Vc),即
(4)截集与截量
不难证明:任何一个可行流的流量v(f)都不超过任一截集的容量.即 v(f)≤c(V,Vc),其中(V,Vc)是网络的任一截集.
显然:若对于一个可行流f*,网络中有一个截集(V*,Vc*)使得v(f*)=c(V*,Vc*)，则f*必为最大流，而c(V*,Vc*)必是D的所有截集中，容量最小的一个，即最小截集。
定理1 可行流f*必是最大流，当且仅当不存在关于f*的增广链。
定理2 （最大流量最小截量定理）任一网络D中，从vs到vt的最大流的流量等于分离vs，vt的最小截集的容量。
二、寻求最大流的标号法（Ford，Fulkerson）
算法步骤为：
1．首先给发点vs 标号（0，l(s)）.括号中第一个数字是使这个点得到标号的前一个点的代号,因s是出发点,故记为0;第二个数字l(s)是表示从上一个标号点到这一个标号点的流量的最大允许调整值.
2.列出与已标号点相邻的所有未标号点:
1）考虑从标号点vi出发的弧(vi,vj),若有fij=cij,则不给点vj标号,若有fij<vij,则对点vj标号,记为(i, l(vj)).括号内的i表示点vj的标号是由点vi延伸过来的, l(vj)=min{ l(vi),(cij-fij)};
2）考虑所有指向标号点vi的弧(vh,vi),若有fhi=0,则对vh不标号,若有fhi>0,则对vh标号,记为(i, l(vh)),其中 l (vh)=min{ l(vi),fhi};
3）如果某未标号的点有两个以上相邻的标号点,为减少迭代次数,可按(1)和(2)中所述规则分别计算出l(vk)的值,并取其中最大的一个标号.
二、寻求最大流的标号法（Ford，Fulkerson）
3.重复步骤2,可能出现两种结果:
1）标号过程中断,vt得不到标号,说明该网络中不存在增广链,给定的流量即为最大流;
2） vt得到标号,这时可用反向追踪法在网络中找出一 条从vs到vt的由标号点及相应的弧连接而成的增广链.转入下一步.
4.修改流量.设图中原有流量为f,令
这样又得到一个新的网络流f/=(fij/),
5.抹掉所有的标号,重复上述步骤直到图中找不到任何增广链为止.
最大流流值为4
Ford-Fulkerson标号算法,例： （uij，xij）
5 t
2
S 1
5 t
2
3
4
1,1
1,1
1,1
1,0
1,1
2,2
3,0
3,2
S 1
5 t
2
3
4
1,1
1,1
1,1
1,0
1,0
2,1
3,1
3,0
S 1
3
4
1,1
1,1
1,1
1,0
1,0
2,2
3,1
3,1
§5 网络计划
一 网络图基本概念
网络图是由一些结点（点、事件、事项）、弧（作业、工序）及权所构成的有向图。即有向赋权图。
1、作业：指任何消耗时间和资源的行动。用a,b,…表示。
2、事件：标志作业的开始和结束，本身不消耗时间或资源。用圆圈表示。
3、权：完成某个作业所用的时间或资源等数据。用T(i,j)或tij通常标在弧上。
4、紧前工序和紧后工序。
如果工序a完成之后工序b就可开工，则称a是b的紧前工序，b是a的紧后工序。如下图所示
i
k
j
a
b
2、 相邻的两结点之间只能有一条弧，表示一项作业。对具有相同开始和结束事件的两项以上作业，要引进虚事件和虚作业。如右图零。
3、 各项作业之间的关系及它们在PERT网络图上的表达方式如下：
图零
图一
a
b
c
a
b
c
图二
a
b
c
图三
d
二、 建立PERT网络图的准则和注意事项
a
d
c
b
图四
（1）作业a结束后可以开始b和c；见图一
（2）作业c在a和b都结束后才能开始；见图二
（3） a、b两项作业均结束后可以开始c和d；见图三
（4）作业c在 a结束后即可进行，但作业d必须同时在a和b结束后才能开始。见图四
1、 绘制网络图时一般从左到右，从上到下。事件的编号箭头处必须大于箭尾处。
5、始点和终点。为表示工程的开始和结束，在网络图中只能有一个始点和终点。
6、 网络图的布局。
（1）尽量避免弧的交叉；
（2）尽量将关键路线布置在中心位置；
（3） 弧线尽量用水平线或具有一段水平的折线。
4、PERT网络图上不允许出现缺口和回路。
c
1
2
3
4
a
b
d
对
1
3
2
4
5
错
b
a
c
d
1
2
4
a
c
错
b
例1 求下列问题的网络图
3
b
e
4
h
i
2
a
d
3
d,e
h
2
a
c
5
d,e
g
2
\
b
2
c
f
5
\
a
时间
紧前作业
作业代号
时间
紧前作业
作业代号
1
3
4
6
7
a
5
d
2
i
4
h
3
2
b
2
e
3
g
5
c
2
5
f
2
二、网络图的时间参数
(一)事项时间参数
1、事项最早时间TE（j），表示事项j最早可在整个工程开工TE（j）后（即在第TE（j）+1天）执行。显然TE（j）即为网络图中从事项1（始点）到事项j的一条最长路的权。
计算公式如下
TE（1）=0
TE（j）=max{ TE（i）+T（i，j）|i<j,(i,j)∈}（j=2，…，n）
终点相应的事项n的最早时间TE（n）称为工程的总工期记为TE。
2、事项最迟时间TL（j），是表示不误总工期的前提下,作为开工事项j最迟应在整个工程开工TL（j）天后(即第TL（j）+1天)执行.即 箭头事项各工序的最迟必须结束时间；箭尾事项各工序的最迟必须开始时间。
显然, TL（j）即为总工期TE与事项j到事项n(终点)的最长路的权之差。
计算公式如下
TL（n）= TE（n） （n为终点事项）
TL（i）=min{ TL（j）-T（i，j）| j>i} （i=n-1，…，1）
例2 求下列网络图中各事项的时间参数
1
3
4
6
7
a
5
d
2
i
4
h
3
2
b
2
e
3
g
5
c
2
5
f
2
0
2
5
7
7
10
14
14
10
12
7
5
4
0
TE( i )
TL( i )
（二）工序时间参数
1.工序的最早开工时间TES(i，j)：紧前工序的最早结束时间，等于工序箭尾事项的最早时间，即 TES（i，j）=TE(i)
2.工序的最早完工时间TEF(i，j)：等于工序最早开始时间加上该工序的作业时间，即 TEF（i，j）=TES（i，j）+T(i,j)
3.工序的最迟完工时间TLF(i，j): 在不影响工程最早结束时间的条件下,工序最迟必须结束的时间,等于工序的箭头事项的最迟时间,即 TLF(i,j)=TL(j)
4.工序的最迟开工时间TLS(i，j): 在不影响工程最早结束时间的条件下,工序最迟必须开始的时间,等于工序最迟结束时间减去工序的作业时间,即 TLS(i,j)=TLF(i,j)-T(i,j)
5、工序(i,j)的总时差R(i,j)：表示在不误工程总工期的前提下,工序(i,j)的开工时间有多少机动时间. R(i,j)=TL(j)-TE(i)-T(i,j)
6、工序(i,j)的自由时差r(i,j):表示在不误下道工序的最早开工时间的前提下,工序(i,j)的开工时间有多少机动时间.
r(i,j)=TE(j)-TE(i)-T(i,j)
I (6,7)
h (4,6)
g (4,7)
f (5,7)
e (2,4)
d (3,4)
c (3,5)
b (1,2)
a (1,3)
TLF(i,j)=TL(j) T(i,j) TLS =TLF - T
TES(i,j)=TE(i) T(i,j) TEF =TES+T
时间
作业
5
2
2
2
3
2
5
3
4
5
2
7
5
5
9
12
10
14
0
0
5
5
2
7
7
7
10
5
4
12
7
7
14
14
10
14
5
2
2
2
3
2
5
3
4
0
2
10
5
4
12
14
7
10
1
3
4
6
7
a
5
d
2
i
4
h
3
2
b
2
e
3
g
5
c
2
5
f
2
0
2
5
7
7
10
14
10
12
7
5
4
0
14
例3、接例2
三、路线和关键路线
关键事项k: TL(k)=TE(k)的事项.
关键工序(i,j): R(i,j)=0的工序.
路线： 从始点到终点由各项作业连贯组成的一条路。
关键路线：各条路线中作业总时间延续时间最长的一条路线。
定理：(1)事项k是关键事项的充分必要条件为事项k在一条关键路线上.
(2)工序(i,j)是关键工序的充分必要条件为弧(i,j)在一条关键路线上.
关键路线的求法
(1) 利用上述定理;
(2) 求从始点到终点的最长路(方法类似于最短路).
例4 求下列网络图的关键路线
1
3
4
6
7
a
5
d
2
i
4
h
3
2
b
2
e
3
g
5
c
2
5
f
2
0
2
5
7
7
10
14
10
12
7
5
4
0
关键路线为：
1
a
3
d
4
h
6
i
7
例5 已知建一个超市库房构架的作业明细表如下，要求：
（1）绘制下列网络图；
（2）计算时间参数(TE(j),TL(j),TES,TEF,TLS,TLF)；
（3）找出关键路线。
K,M
4
清理工地交工验收
N
F
4
立房顶框架
G
L
24
引导混凝土保养
M
D,E
4
立墙架
F
C
8
引导混凝土施工
L
C
24
混凝土地面保养
E
H,I,J
16
油漆
K
B
16
预制墙及房顶的框架
D
G
12
装天花板
J
A,B
6
地面施工
C
F
4
装门
I
——
8
备料
B
F
10
装窗及边墙
H
——
10
清理现场，准备施工
A
紧前
工序
工序
时间
工序
名称
工序
代号
紧前
工序
工序
时间
工序
名称
工序
代号
0
0
1
A
10
10
10
2
C
6
II
II
II
L
8
II
II
II
B 8
8
10
3
D
16
II
II
II
E 24
F
4
II
II
II
G
4
II
II
II
H
10
I
4
II
II
II
II
II
II
J
12
K
16
M
24
II
II
II
N
4
II
II
II
