课件第九章图与网络计划

第一节：引论第二节：图的基本概念第三节：树图第四节：最短路问题第五节：最大流问题第六节：中国邮路问题第七节：网络计划第九章图与网络计划图论引论1.Euler回路问题2.Ramsey问题近代图论的历史可追溯到18世纪的七桥问题—穿过Königsberg城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡7桥”难题。Euler1736年证明了不可能存在这样的路线。图的基本概念与模型Königsberg桥对应的图Euler回路问题Pregel

“哥尼斯堡7桥”难题最终在1736年由数学家Euler的一篇论文给予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论的发展是缓慢的，直到1936年匈牙利数学家O.König写出了图论的第一本专著《有限图与无限图的理论》。四色猜想图论的历史上最具有传奇色彩的问题也许要数著名的“四色猜想”了——历史上许许多多数学猜想之一。世界近代三大数学难题：费马最后猜想、哥德巴赫猜想和“四色”猜想。它描述对一张地图着色的问题，在一维直线上用两种颜色可以区分任意多不同线段，在二维平面内至少需要四种颜色可以区分任意多区域（当然最简单的情况是二色，如国际象棋棋盘）；在三维空间内至少需要八种颜色可以区分任意多的立体，（最简单的情况还是二色，如NaCl）Euler回路问题

ACDBRamsey问题

vjvtvk

vi

vjvtvk

Ramsey问题vi

vjvtvk

Ramsey问题vi

vjvtvkRamsey问题vi第一节：图的基本概念1.图的概念2.关联的概念3.简单图、完全图和二分图4.连通与回路5.部分图与子图1.图的概念（1）图：图是点和边的集合，记作

G=（V，E）；其中V是点的集合，E是边的集合。（2）有向图：有向图是点和弧的集合，记作G=（V，U）；U是弧的集合，弧是两点的有序偶对。（3）赋权图：图中的每一条边均有一个权数wij相对应的图称为赋权图。

图的基本概念(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来表示。1.图的概念298653图有向图赋权图2.关联的概念端点和关联边：若有边e可表示为e=(vi,vj),则称vi和vj为边e的两个端点；边e为vi和vj的关联边。(2)相邻：若点vi和vj与同一条边相关联，则称vi和vj相邻；若边ei和ej具有一个公共的端点，则称ei和ej相邻。(3)环：若边ei的两个端点相互重合，则称ei为环。

如图9-5中，v2和v5是边e4的两个端点，e4为v2和v5的关联边；v2和v5是边e4的两个端点，边e8是v4和v5的关联边。图9-5v1e2e4v2e6e5v3e7v4v5e3e1e8v4和v5均与e8相关联，所以v4和v5相邻。e6和e7有一个公共的端点v3

，e6和e7相邻。e1即为一个环

图9-5v1e2e4v2e6e5v3e7v4v5e3e1e82.关联的概念(4)多重边：若vi,和vj两点之间有两条或两条以上的边存在,则称vi,和vj两点之间有多重边。(5)点的度（或次）：与点vi相关联的边的数量称为点vi的度（或次）；度（或次）为偶数的点称为偶点，度（或次）为奇数的点称为奇点；度（或次）为1的点称为悬挂点；度（或次）为0的点称为孤立点。

图的度:

一个图的度等于各点的度之和。v3e7e4e8e5e6e1e2e3v1v2v4v5v2和v5之间存在e4和e5二条边，所以称v2和v5之间具有二重边d(v1)=4、d(v2)=4、d(v5)=5、d(v4)=1。v5和v4为奇点,v4为悬挂点,v1、v2、v3为偶点图9-5v1e2e4v2e6e5v3e7v4v5e3e1e82.关联的概念图9-5v1e2e4v2e6e5v3e7v4v5e3e1e8定理1任何图中，顶点度数之和等于所有边数的2倍。定理2任何图中，度为奇数的顶点必为偶数个。3.简单图、完全图和二分图(1)简单图：无环无多重边的图称为简单图。(2)完全图：任意一对顶点均相邻的简单图称为完全图。(3)二分图：若图的点集V能被分成二个不相交的子集V1和V2，使得同一个集合中的任何两点均不相邻，则称此图为二分图。

简单图、完全图和二分图简单图二分图完全图图的基本概念二分图（偶图）图G=(V,E)的点集V可以分为两各非空子集X，Y，集X∪Y=V,X∩Y=Ø,使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二分图，(b)也是二分图，但不明显，改画为(c)时可以清楚看出。4.连通与回路(1)链：链是相关联的点和边的交替序列；边不重复的链称为简单链；边和点均不重复的链称为初等链。(2)连通：任意一对顶点之间均有链相连的图称为连通图。(3)回路：链的首尾重合便构成了回路；简单链的首尾重合便构成了简单回路；初等链的首尾重合便构成了初等回路。

4.连通与回路e5v1v5v4v3v2e1e4e3e2e6e8v4到v5的一条链：v4–e6-v2-e2-v1-e3-v3-e5-v2-e2-v1-e1-v1-e3-v3-e8-v5v4到v5的一条简单链：v4–e6-v2-e2-v1-e3-v3-e5-v2–e4-v3-e8-v5v4到v5的一条初等链：v4–e6-v2-e2-v1-e3-v3-e8-v55.部分图与子图(1)部分图：图G1=（V1，E1）

和图G2=（V2，E2），若存在V1=V2、E1

E2，则称G1为G2的部分图。(2)子图：图G1=（V1，E1）和图G2=（V2，E2），若存在V1

V2、E1

E2，则称G1为G2的子图。

5.部分图与子图图子图部分图图的基本概念与模型图的模型应用例9.1有甲,乙,丙,丁,戊,己6名运动员报名参加A,B,C,D,E,F6个项目的比赛。下表中打√的是各运动员报告参加的比赛项目。问6个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。ABCDEF甲√√√乙√√√丙√√丁√√戊√√√己√√√图的基本概念与模型解：用图来建模。把比赛项目作为研究对象，用点表示。如果2个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。ABCDEF在图中找到一个点序列，使得依次排列的两点不相邻，即能满足要求。如：1)A,C,B,F,E,D2)D,E,F,B,C,A图的基本概念与模型

一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。思考题图的基本概念与模型思考题解答：

以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿道路，如C—E—A—F—D—B，就是一个符合要求的考试课程表。图的基本概念与模型AFEDCB图的基本概念与模型AFEDCB图的基本概念与模型图的矩阵描述：如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等。1.邻接矩阵 对于图G=（V，E），|V|=n，|E|=m，有n

n阶方矩阵A=(aij)n

n，其中图的基本概念与模型v5v1v2v3v4v64332256437例9.2下图所表示的图可以构造邻接矩阵A如下对于赋权图G=(V,E),其中边有权,构造矩阵B=(bij)n

n

其中：图的基本概念与模型2.关联矩阵对于图G=(V,E),|V|=n,|E|=m,有m

n阶矩阵M=(mij)m

n，其中:3.权矩阵图的基本概念与模型101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000v1v2v3v4v5v6v7v8e1e2e3e4e5e6e7e8e9e10e11e12v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4例9.3下图所表示的图可以构造邻接矩阵M如下:M=（mij）=图的基本概念与模型v5v1v2v3v4v64332256437例9.4下图所表示的图可以构造权矩阵B如下:第二节：树图1.树的概念2.树的性质3.部分树4.最小部分树5.最小部分树的求解树与图的最小树树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。例9.4乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。ABCDEFGH运动员树与图的最小树例9.5某企业的组织机构图也可用树图表示。厂长人事科财务科总工程师生产副厂长经营副厂长开发科技术科生产科设备科供应科销售科检验科动力科1.树的概念树：树是不含回路的连通图。树枝：树图的各条边称为树枝2.树的性质树：无圈的连通图即为树性质1：树中任意两个顶点之间，恰有且仅有一条链。性质2：树连通，但去掉任一条边，必变为不连通。性质3：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。性质4：n个顶点的树必有n-1条边。性质5：任何树中必存在度为1的点。树中至少存在两个悬挂点。v1v2v3v4v5v63.部分树部分树：如果图G的部分图T是一棵树，则称T是G的部分树。一般图G含有多个部分树。图G图G的部分树T1图G的部分树T24.最小部分树最小部分树：在赋权图G的所有部分树中，树枝权数和最小的部分树称为最小部分树（或最小支撑树）。

图G图G的部分树（15）图G的最小部分树（8）23169223192312树与图的最小树abcfedhgbfed树与图的最小树abcfedhgbfdg树与图的最小树bcedabcfedhg树与图的最小树abchabcfedhg树与图的最小树afdgabcfedhg5.最小部分树的求解（1）破圈（回路）法（2）避圈（回路）法（3）顺序生枝法破圈法:在连通图中任意选取一个回路，从该回路中去掉一条权数最大的边（如果权数最大的边不唯一，则任意选取其中一条）。在余下的图中，重复这一步骤，直至得到一个不含回路的连通图（有个顶点条边），该连通图便是最小部分树。求树的方法：破圈法和避圈法树与图的最小树破圈法树与图的最小树部分树树与图的最小树避圈法v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5树与图的最小树破圈法：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数＝n-1=5赋权图中求最小树的方法：破圈法和避圈法树与图的最小树v1v2v3v4v5v643521得到最小树：MinC(T)=15（1）破圈（回路）法227541435715

ASBDCET（1）破圈（回路）法227541435715

ASBDCET（1）破圈（回路）法22741435715

ASBDCET（1）破圈（回路）法22741435715

ASBDCET（1）破圈（回路）法2271435715

ASBDCET（1）破圈（回路）法2271435715

ASBDCET（1）破圈（回路）法221435715

ASBDCET（1）破圈（回路）法221435715

ASBDCET（1）破圈（回路）法22135715

ASBDCET（1）破圈（回路）法22135715

ASBDCET（1）破圈（回路）法2213715

ASBDCET（1）破圈（回路）法2213715

ASBDCET（1）破圈（回路）法221315总权数和为14ASBDCET避圈法:从图中任选一点vi，让其他各点均属于；从沟通集合V和的连线中找出最小边，使之包含在最小部分树内。不妨假设最小边为（vi,vj）令，其他各点均属于；重复寻找从集合V到的最小边并使之包含在最小部分树内，直到图中的所有点都包含在集合V中为止。

树与图的最小树避圈法:

去掉G中所有边，得到n个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。5v1v2v3v4v5v6843752618树与图的最小树v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=15（2）避圈（回路）法2275414357150

ASBDCET（2）避圈（回路）法227541435715

ASBDCET（2）避圈（回路）法2275414357150

ASBDCET（2）避圈（回路）法227541435715

ASBDCET（2）避圈（回路）法227541435715

ASBDCET（2）避圈（回路）法227541435715

ASBDCET（2）避圈（回路）法227541435715

ASBDCET（2）避圈（回路）法227541435715

ASBDCET（2）避圈（回路）法227541435715

ASBDCET（2）避圈（回路）法227541435715

ASBDCET（2）避圈（回路）法227541435715

ASBDCET（2）避圈（回路）法227541435715

ASBDCET树与图的最小树v1v7v4v3v2v5v620159162532817412336练习：应用破圈法求最小树树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v6201591625328174123树与图的最小树v1v7v4v3v2v5v6201591625328174123树与图的最小树v1v7v4v3v2v5v61591625328174123树与图的最小树v1v7v4v3v2v5v61591625328174123树与图的最小树v1v7v4v3v2v5v691625328174123树与图的最小树v1v7v4v3v2v5v691625328174123树与图的最小树v1v7v4v3v2v5v6925328174123树与图的最小树v1v7v4v3v2v5v6925328174123树与图的最小树v1v7v4v3v2v5v69328174123树与图的最小树v1v7v4v3v2v5v69328174123树与图的最小树v1v7v4v3v2v5v693174123min=1+4+9+3+17+23=57树与图的最小树练习：应用避圈法求最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336树与图的最小树v1v7v4v3v2v5v620159162532817412336min=1+4+9+3+17+23=57Kruskal顺序生枝法:首先将图中的所有边按权的大小从小到大的进行排列，在确保不出现回路的前提下，将依次排列的边逐一绘出；若在增加某条边时出现了回路，则排除该边并继续寻找下一条边。

（3）顺序生枝法现有五口油井，相互之间的距离（千米）如下表所示，问应如何铺设输油管线使输油管长度最短。为便于检修和计量，输油管只允许在井口处分路。到从w2w3w4w5w11.32.10.90.7w20.91.81.2w32.61.7w40.7

（3）顺序生枝法（1）排序：按井距从小到大排列

d15=

d45=0.7d14=

d23=0.9d25=

1.2d12=

1.3

d35=1.7d24=

1.8

d13=2.1d34=

2.6（2）生枝：按排序顺序生枝，如果某生枝形成回路，略去该枝并继续直到生成P-1条边。

（3）顺序生枝法w5w4w10.70.7

（3）顺序生枝法w5w4w10.70.7

（3）顺序生枝法w5w4w10.70.7w3w20.9

（3）顺序生枝法w5w4w10.70.7w3w20.91.2最短路问题如何用最短的线路将三部电话连起来？此问题可抽象为设△ABC为等边三角形，，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如AB∪AC）。ABC最短路问题ABCP但若增加一个周转站（新点P），连接4点的新网络的最短路线为PA＋PB＋PC。最短新路径之长N比原来只连三点的最短路径O要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。最短路问题问题描述： 就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路.

有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。最短路问题例渡河游戏 一老汉带了一只狼、一只羊、干草想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃干草，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。最短路问题定义：1）人—M（Man），狼—W（Wolf），羊—G（Goat），草—H（Hay）2）点——vi

表示河岸的状态3）边——ek

表示由状态vi

经一次渡河到状态vj

4）权——边ek

上的权定为1我们可以得到下面的加权有向图最短路问题状态说明：v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=(M,W,H);v4,u4=(M,G,H);v5,u5=(M,G)此游戏转化为在下面的二分图中求从v1

到u1

的最短路问题。v1v2v3v4v5u5u4u3u2u1第三节：最短路问题1.求图中某一点到其他各点最短路的Dijkstra标号算法2.求图中所有点之间最短路的Floyd矩阵算法令Dijkstra算法vi与vj不相邻vi与vj相邻vi与vj相等若用Lij代表从点到点的最短路，那么求从点i到点j的最短路的Dijkstra算法的具体步骤可概括如下：从点s出发，因Lss=0

，将“0”标注在旁的小方框内，表示点s已标号；从点s出发，找出与点s相邻且距离最小的点r，将Lsr=Lss+Lsr的值标注在点r旁的小方框内，表明点r也已标号；Dijkstra算法找出所有与已标号点相邻的末标号点，若Lsp=min{Lss+Lsp,Lsr+Lrp}

，则给点p标号，即将Lsp的值标注在p旁的小方框内；重复第三步，一直到t点得到标号为止；此时各点小方框内的标注值就是s点到该点的最短路。Dijkstra算法227541435715SABCDEF0

第一步：从点s出发，对其标“0”，

令，其他各点均属于；227541435715SABCDEF0

故A点得到标号“2”，令其余各点均属于2第二步：与s点相邻的未标号点有A、B、C三个点，又因：

，227541435715SABCDEF0

2第三步：与标号点s和A相邻的未标号点有B、C、E三个点，又因：故B、C两点同时得到标号“4”，其余各点均属于44227541435715SABCDEF0

24依此类推，直到所有的点均得到标号

478132.求图中所有点之间最短路的Floyd矩阵算法dij(0)=wij

(ifi与j相邻)dij(0)=0(ifi=j)

dij(0)=

(ifi与j不相邻)

dij=D(0)={dij(0)}代表从i直接到达j的距离矩阵2.求图中所有点之间最短路的Floyd矩阵算法D(0)={dij}代表从i直接到达j的距离矩阵从i到达j的最短路并不局限在直接到达，两点之间可以有1、2、……个中间点。先考虑i和j两点之间可以有1个中间点的情况：

dij(1)

=min[dik(0)

+dkj(0)]k=1,2,……,Pikjk’

2.求图中所有点之间最短路的Floyd矩阵算法再考虑i和j两点之间可以有3个中间点的情况：

dij(2)

=min[dik(1)

+dkj(1)]k=1,2,……,Pikjnm

2.求图中所有点之间最短路的Floyd矩阵算法i和j两点之间可以有2n-1个中间点的情况：

dij(n)

=min[dik(n-1)

+dkj(n-1)]k=1,2,……,P结束条件：或

即2.求图中所有点之间最短路的Floyd矩阵算法

SACBEDT227541435715SACBDETSACB

EDT

SACBEDT227541435715SACBDETSACB

EDT227541435715SACBDET227541435715SACBDET最短路问题例设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表年份12345年初价格1111121213最短路问题设备维修费如下表使用年数0-11-22-33-44-5每年维修费用5681118解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。v1v2v3v4v5v6最短路问题把所有弧的权数计算如下表，把权数赋到图中，再用Dijkstra算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723最短路问题最终得到下图，可知，v1到v6的距离是53，最短路径有两条：v1→v3→v6和

v1→v4→v6

V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723

V2（16,1）16(30,1)(53,3)(53,4)2.求图中所有点之间最短路的Floyd矩阵算法案例：某城有5个区组成，各区之间的道路情况如下图所示，各边的权数为距离（千米）。已知各区年消费粮食分别为6000、4000、10000、7000和9000吨，若该城准备建一座统一的粮库，问就运输的吨千米数最小粮库应建在哪个区？10EDCBA2051020101525

2.求图中所有点之间最短路的Floyd矩阵算法

0102015

100520D(0)=205010101510025

2010250

2.求图中所有点之间最短路的Floyd矩阵算法

01015153010051515D(1)=15501010151510020

301510200

2.求图中所有点之间最短路的Floyd矩阵算法

01015152510051515D(2)=15501010151510020

251510200

2.求图中所有点之间最短路的Floyd矩阵算法

01015152510051515D(2)=15501010151510020

251510200

6000

4000

10000

7000

9000

2.求图中所有点之间最短路的Floyd矩阵算法

060,00090,00090,000150,00040,000020,00060,00060,000150,00050,000010,00010,000105,000105,00070,0000140,000225,000135,00090,000180,0000520,000350,000270,000340,000360,000

合计C*最短路问题思考题1、求下图v1到各点的最短距离及最短路线。①②③④⑤⑥⑦⑧4526178393261216180452231039612641166188122482418所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。最短路问题2.求从v1到v8的最短路径237184566134105275934682最短路问题237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到v8的最短路径为v1→v4→v7→v5→v8，最短距离为10最短路问题3.求下图中v1点到另外任意一点的最短路径v1v2v3v4v6v5322762133最短路问题v1V2V3V4V6V5322762133024714最短路问题v1V2V3V4V6V5322762133024714最短路问题最短路问题的应用：4、电信公司准备准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。

v1（甲地）1517624431065v2v7(乙地)v3v4v5v6第五节：最大流问题1.基本概念2.求网络流图最大流的标号算法1.基本概念正、负线度：从一点发出的弧的数目称为点的正线度；进入点的弧的数目称为点的负线度。2.发点（source）：负线度为“0”的点。3.收点（sink）：正线度为“0”的点。

1.基本概念4.网络流图：（1）只有一个发点和一个收点；（2）各弧有一个非负的“容量（capacity）”，cij；（3）各弧有一个不大于“容量”的“流量（flow）”，fij。1.基本概念4.容量网络：网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中通常规定一个发点(也称源点，记为s)和一个收点(也称汇点，记为t)，网络中其他点称为中间点。s①②③④t48441226791.基本概念

5.流、可行流和最大流：

流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的负载量记为fij。若fij=0，称为零流。

可行流：满足以下条件的一组流称为可行流。

容量限制条件。容量网络上所有的弧满足：0≤fij≤cij

中间点平衡条件。

若以v(f)表示网络中从s→t的流量，则有：网络的最大流网络的最大流网络的最大流是指网络中从发点到收点之间允许通过的最大流量。6.饱和弧：fij=cij

的弧。7.非饱和弧：fij<cij

的弧。8.零流弧：fij=0的弧。结论：任何网络上一定存在可行流。（零流即是可行流）网络最大流问题： 指满足容量限制条件和中间点平衡的条件下，使v(f)值达到最大。1.基本概念

9.正向弧与反向弧：若是从发点vs到收点vt的一条链，定义链的方向为从vs到vt，则链上的弧被分为两类：（1）弧的方向与链的方向一致（在该链上所有指向为s→t的弧），则称正向弧（

+）；（2）弧的方向与链的方向相反（在该链上所有指向为

t→s的弧），则称反向弧（

-）。

10.增广链：设f是一个可行流，是从发点vs到收点vt的一条链，若满足下列条件，则称其为一条增广链：（1）

+中的每一个弧均为非饱和弧；（2）

-中的每一个弧均为非零流弧。

若f>0，则称这样的链为增广链。例如下图中，s→v2→v1→v3→v4→t。定理3

网络N中的流f

是最大流当且仅当N中不包含任何增广链stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)网络的最大流求网络最大流的标号算法：[基本思想]

由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。[基本方法]找出第一个可行流，（例如所有弧的流量dij

=0。）用标号的方法找一条增广链首先给发点s标号(∞),标号中的数字表示允许的最大调整量。选择一个点vi

已标号并且另一端未标号的弧沿着某条链向收点检查：网络的最大流如果弧的起点为vi，vj未标号且相邻，并且有dij<Cij，则给vj标号为(vi,δj)

如果弧的方向指向vi，并且有djj>0，则vj标号(-vi,δj)(3)重复第(2)步，可能出现两种结局：标号过程中断，t无法标号，说明网络中不存在增广链，目前流量为最大流。

t得到标号，反向追踪在网络中找到一条从s到t得由标号点及相应的弧连接而成的增广链。继续第(4)步网络的最大流(4)修改流量。设原图可行流为f，令得到网络上一个新的可行流f’。(5)擦除图上所有标号，重复(1)-(4)步，直到图中找不到任何增广链，计算结束。1.基本概念v4v3v2vtv1vs(5,3)(3,0)(4,3)(1,1)(2,2)(1,1)(5,1)(3,3)(2,1)（1）链

={vs,v1,v2,v4,v3,vt}是一条增广链；（2）链

={vs,v2,v3,v4,vt}不是增广链；（3）链

={vs,v1,v2,v4,v3,vt}不是增广链。（0，）2.求网络流图最大流的标号算法v4v3v2vtv1vs(5,4)(3,0)(4,4)(1,1)(2,2)(1,0)(5,2)(4,3)(2,1)（vs，3）（vs，1）（-v2，1）（v3，1）

2.求网络流图最大流的标号算法v4v3v2vtv1vs(5,4)(3,0)(4,3)(1,0)(2,2)(5,2)(4,3)(2,2)(1,0)

2.求网络流图最大流的标号算法v4v3v2vtv1vs(5,4)(3,0)(4,3)(1,0)(2,2)(5,2)(4,3)(2,2)(1,0)

（0，）2.求网络流图最大流的标号算法v4v3v2vtv1vs(5,4)(3,0)(4,3)(1,0)(2,2)(1,0)(5,2)(4,4)（vs，3）(2,2)最大流=6网络的最大流例

用标号算法求下图中s→t的最大流量●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)网络的最大流解：(1)先给s标号(0,∞)●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(0,∞)网络的最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(0,∞)(2)检查与s点相邻的未标号的点，v1与v2，因ds1<cs1，故对v1标号（vs

，l（v1

））:(Vs,1)(Vs,2)因ds2<cs2，故对v2标号（vs

，l（v2

））

网络的最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(6)(0,∞)(vs,1)(2)检查与v2点相邻的未标号的点，v3与v4，因（v2,v3)为负向零流弧，（v2,v4)为正向饱和弧，所以v3与v4没有得到标号。(vs,2)网络的最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(6)(0,∞)(vs,1)(2)检查与v1点相邻的未标号的点，因f13<c13，故对v3标号

l(v3)min{l(v1)

,c13-d13}=

=min{1,c13-d13}=min{1,6}=1；(v1,1)(vs,2)网络的最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(0，∞)(vs,1)(v1,1)(3)检查与v3点相邻的未标号的点，因f3t<c3t，故对vt标号=min{1,c3t-f3t}=min{1,1}=1(v3,1)找到一条增广链s→v1→v3→t(vs,2)网络的最大流(4)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)(0，∞)(vs,1)(v1,1)(v3,1)(vs,2)网络的最大流(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。●stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)(0，∞)(vs,1)(v1,1)(v3,1)网络的最大流(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。●stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)(vs,2)l(v2)=min{∞,2}=2l(v1)=min{2，3}=2l(v3)=min{2,5}=2(-v3,1)l(v4)=min{2,1}=1l(vt)=min{1,2}=1(0，∞)(-v2,2)(v1,2)(v4,1)网络的最大流(6)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。●stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)(vs,2)(v3,1)(0，∞)(v2,2)(v1,2)(v4,1)网络的最大流●stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)(7)擦除所有标号，重复上述标号过程，寻找另外的增广链。(vs,1)(v3,1)(0，∞)(-v2,1)(v1,1)(v4,1)网络的最大流●stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)(7)擦除所有标号，重复上述标号过程，寻找另外的增广链。l(v2)=min{∞,1}=1l(v1)=min{1,2}=1l(v3)=min{1,4}=1(vs,1)(0，∞)(v2,1)(v1,1)无法标号，不存在增广链，此可行流已为最大流。最大流量为14。网络的最大流例

求下图s→t的最大流stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●网络的最大流stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●解:(1)在已知可行流的基础上，通过标号寻找增广链。(∞)ε(2)=min{∞,6}=6(6)ε(3)=min{6,2}=2(2)ε(t)=min{2,5}=2(2)存在增广链s→v2→v3→t网络的最大流(2)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●(∞)(6)(2)(2)网络的最大流(3)擦除原标号，重新搜寻增广链。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)(6)(2)(2)网络的最大流(4)重新搜寻增广链。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)ε(2)=min{∞,4}=4(4)(1)ε(5)=min{4,1}=1ε(3)=min{1,2}=1(1)(1)ε(t)=min{1,3}=1存在增广链：s→v2→v5→v3→t网络的最大流(5)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)(4)(1)(1)(1)网络的最大流(6)擦除原标号stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)●(∞)(4)(1)(1)(1)网络的最大流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)●(∞)(1)(1)(1)ε(5)=min{∞,1}=1ε(5)=min{1,1}=1ε(5)=min{1,2}=1(7)重新搜寻增广链。存在增广链：s→v5→v3→t网络的最大流(8)调整增广链上的流量，非增广链流量不变，得到新的可行流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)●(∞)(1)(1)(1)网络的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)●(∞)(1)(1)(1)(9)擦除原标号网络的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)●(10)重新标号，搜索增广链(∞)ε(1)=min{∞,1}=1(1)ε(5)=min{1,1}=1(1)ε(4)=min{1,1}=1(1)ε(t)=min{1,1}=1(1)存在增广链：s→v1→v5→v4→t网络的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)●(∞)(1)(1)(1)(1)(11)调整增广链上的流量，非增广链流量不变，得到新的可行流网络的最大流stv1v2v3v4v54(4)3(3)10(7)3(3)1(1)4(4)3(3)5(5)4(4)2(2)7(7)8(7)●(∞)(1)(1)(1)(1)(11)擦除标号，在新的可行流上重新标号。网络的最大流stv1v2v3v4v54(4)3(3)10(7)3(3)1(1)4(4)3(3)5(5)4(4)2(2)7(7)8(7)●(∞)(11)擦除标号，在新的可行流上重新标号。(3)ε(1)=min{∞,3}=1无法标号，不存在增广链，此可行流已为最大流。最大流量为14。第六节：中国邮路问题v8v7v6v5v4v3v2v1v10v910949718522210

v8v7v6v5v4v3v2v1v10v910949718522210

v8v7v6v5v4v3v2v1v10v9109497185222最佳邮路总长69+2310第七节：网络计划1.引论2.网络计划的工作步骤3.网络图4.网络时间计算5.网络优化1.引论（1）1956年——美国杜邦公司制定业务部门系统规划，CPM（CriticalPathMethod）（2）1958年——美国海军武器部“北极星”导弹计划，PERT（ProgramEvaluationandReviewTechnique）（3）1960s——我国应用CPM和PERT----统筹法2.基本概念作业或工序作业或工序是指工程中在工艺技术和组织管理上相对独立的一部分工作或活动。

作业时间为完成某一作业所需要消耗的时间称为该作业的作业时间。作业时间的确定通常采用两种方法，即一点法和三点法。2.基本概念一点法对作业时间的估计采用单值的方法，即给出一个估计点；如8天、100天、120天等。这种方法一般在具备劳动定额数据或类似作业的统计信息时使用。三点法对作业时间的估计采用三值的方法，即给出乐观（a）、最可能（m）和悲观（b）三个估计点；如a=5天，m=8天，b=12天。2.基本概念不妨假设服从正态分布，如图9-26所示。一般情况下，可按加权平均的方式计算作业时间，即：对应的方差为：mba时间图9-262.基本概念作业之间顺序关系作业之间的先后顺序关系是通过紧前作业或紧后作业来加以描述的。如果作业B只有在作业A完成后才能开始，那么就称作业A是作业B的紧前作业；而作业B称为作业A的紧后作业。2.基本概念完成作业或工序的划分、作业时间的确定、明确作业关系三个基本步骤，即可构造出由作业、作业时间和紧前作业或紧后作业所组成的作业关系明细表，如表9-5所示。表9-5作业ABCDEFGHI紧前作业ABCB、DEB、F作业时间12308152091130183.网络计划的工作步骤(1)将整个项目划分为基本的工作单元——工序；(2)确定工序的逻辑顺序（紧前工序和紧后工序）；(3)绘制网络图；(4)进行网络时间计算；(5)网络优化及决策；(6)网络执行及动态调整。4.网络图网络图的构成：（1）结点——标志着工序的开始或结束；（2）箭线——代表着工序。网络图的基本要求：（1）只能有一个开始结点和一个结束结点；（2）箭头结点的标号大于箭尾结点的标号；（3）任一对结点间只能存在一项工序。iji>jijABijkAB

已知工序关系绘制网络图B1

C47683521830119201583012IHGFEDA图9-27已知工序关系绘制网络图工序代号紧前工序工序时间a___60ba45ca10da20ea40fc18gd30hd,e15mg25nb,f,m,h35

绘制网络图60ab45c10d20e40f18g30h15m2535n12345678

已知工序关系绘制网络图工序代号紧前工序工序时间a___60b___45c___10da20ea,b40fa,b18gc30hd15me25ng,f35

绘制网络图60ab45c10d20e30f18g40hm2535n12345678155.网络时间计算工序时间估计（1）一点时间估计：t

（2）三点时间估计：t=(a+4m+b)/6结点时间计算（1）结点的最早开始时间——TE（j）（2）结点的最迟结束时间——TL（i）

结点的最早开始时间—TE（j）（1）令项目的开始结点的最早开始时间TE（1）=0；（2）由左向右、加法、取最大值。ji3i2i1TE(i1)=10TE(i2)=6TE(i3)=15t(i1,j)=18t(i2,j)=12t(i3,j)=16

10+18=28TE(j)=max6+12=18=3115+16=31

图9-30BC1830119201583012IHGFEDA

1345867285312543030003069505030628080结点的最早开始时间—TE（j）计算

60ab45c10d20e30f18g40hm2535n123456781506010608010078125

结点的最迟结束时间—TL（i）（1）令项目结束结点的最迟结束时间TL（p）等于其最早开始时间TE（p）；（2）由右向左、减法、取最小值。ij3j