《图与网络计划》PPT课件.ppt

《《图与网络计划》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图与网络计划》PPT课件.ppt（267页珍藏版）》请在三一办公上搜索。

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

2、的两百年间图论的发展是缓慢的，直到 1936 年匈牙利数学家 O.Knig写出了图论的第一本专著有限图与无限图的理论。,四色猜想,图论的历史上最具有传奇色彩的问题也许要数著名的“四色猜想”了历史上许许多多数学猜想之一。世界近代三大数学难题：费马最后猜想、哥德巴赫猜想和“四色”猜想。它描述对一张地图着色的问题，在一维直线上用两种颜色可以区分任意多不同线段，在二维平面内至少需要四种颜色可以区分任意多区域（当然最简单的情况是二色，如国际象棋棋盘）；在三维空间内至少需要八种颜色可以区分任意多的立体，（最简单的情况还是二色，如NaCl）,Euler回路问题,A C D B,Ramsey问题,vj,vt,

3、vk,vi,vj,vt,vk,Ramsey问题,vi,vj,vt,vk,Ramsey问题,vi,vj,vt,vk,Ramsey问题,vi,第一节：图的基本概念,1.图的概念2.关联的概念3.简单图、完全图和二分图4.连通与回路5.部分图与子图,1.图的概念,（1）图：图是点和边的集合，记作 G=（V，E）；其中V是点的集合，E是边的集合。（2）有向图：有向图是点和弧的集合，记作G=（V，U）；U是弧的集合，弧是两点的有序偶对。（3）赋权图：图中的每一条边均有一个权数wij相对应的图称为赋权图。,图的基本概念,可见图论中的图与几何图、工程图是不一样的。,例如：在一个人群中，对相互认识这个关系我们

4、可以用图来表示。,1.图的概念,图,有向图,赋权图,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的关联边。,v4和v5均与e8相关联，所以v4和v5相邻。e6和e7有一个公共的端点v3，e6和e7相邻。e1即为一个环,2.关联

5、的概念,(4)多重边：若vi,和vj两点之间有两条或两条以上的边存在,则 称vi,和vj两点之间有多重边。(5)点的度（或次）：与点vi相关联的边的数量称为点vi的度（或次）；度（或次）为偶数的点称为偶点，度（或次）为奇数的点称为奇点；度（或次）为1的点称为悬挂点；度（或次）为0的点称为孤立点。,图的度:一个图的度等于各点的度之和。,v2和v5之间存在e4和e5二条边，所以称v2和v5之间具有二重边 d(v1)=4、d(v2)=4、d(v5)=5、d(v4)=1。v5和v4为奇点,v4为悬挂点,v1、v2、v3为偶点,2.关联的概念,定理1 任何图中，顶点度数之和等于所有边数的2倍。,定理2

6、任何图中，度为奇数的顶点必为偶数个。,3.简单图、完全图和二分图,(1)简单图：无环无多重边的图称为简单图。(2)完全图：任意一对顶点均相邻的简单图称为完全图。(3)二分图：若图的点集V能被分成二个不相交的子集V1和V2，使得同一个集合中的任何两点均不相邻，则称此图为二分图。,简单图、完全图和二分图,图的基本概念,二分图（偶图）,图G=(V,E)的点集V可以分为两各非空子集X，Y，集XY=V,XY=,使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。,(a),(b),(c),(a)明显为二分图，(b)也是二分图，但不明显，改画为(c)时可以清楚看出。,4.连通与回路,(1)链：链是相关联的

7、点和边的交替序列；边不重 复的链称为简单链；边和点均不重复的链称为 初等链。(2)连通：任意一对顶点之间均有链相连的图称为 连通图。(3)回路：链的首尾重合便构成了回路；简单链的 首尾重合便构成了简单回路；初等链的首尾重 合便构成了初等回路。,4.连通与回路,e5,v1,v5,v4,v3,v2,e1,e4,e3,e2,e6,e8,v4到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-

8、v1-e3-v3-e8-v5,5.部分图与子图,(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,F 6个项目的比赛。下表中打的是各运动员报告参加的比赛项目。问6个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。,图的基本概念与模型,解：用图来建模。把比赛项目作

9、为研究对象，用点表示。如果2个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。,在图中找到一个点序列，使得依次排列的两点不相邻，即能满足要求。如：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，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。,思考题,图的基本概念与模型,思考题解答：以每门课程为一个顶点，共同被选修的课程之间用边

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

11、表示的图可以构造邻接矩阵A如下,对于赋权图G=(V,E),其中边 有权,构造矩阵B=(bij)nn 其中：,图的基本概念与模型,2.关联矩阵对于图G=(V,E),|V|=n,|E|=m,有mn阶矩阵M=(mij)mn，其中:,3.权矩阵,图的基本概念与模型,1 0 1 0 0 0 0 0 0 0 0 01 1 0 0 1 0 0 0 0 0 0 00 1 0 0 0 1 1 1 0 0 0 00 0 0 0 0 0 0 0 1 0 0 10 0 1 1 1 1 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 00 0 0 0 0 0 0 0 0 1 1 10 0 0 1 0

12、0 1 1 0 0 0 0,v1v2v3v4v5v6v7v8,e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12,例9.3 下图所表示的图可以构造邻接矩阵M如下:,M=（mij）=,图的基本概念与模型,例9.4 下图所表示的图可以构造权矩阵B如下:,第二节：树图,1.树的概念2.树的性质3.部分树4.最小部分树5.最小部分树的求解,树与图的最小树,树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。,例9.4 乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。,运动员,树与图的最小树,例9.5 某企业的组织机构图也可用树图表示。,1.树的概念,树

13、：树是不含回路的连通图。树枝：树图的各条边称为树枝,2.树的性质,树：无圈的连通图即为树,性质1：树中任意两个顶点之间，恰有且仅有一条链。性质2：树连通，但去掉任一条边，必变为不连通。性质3：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。性质4：n 个顶点的树必有n-1 条边。性质5：任何树中必存在度为1的点。树中至少存在两个悬挂点。,3.部分树,部分树：如果图G的部分图T是一棵树，则称T是G的部分树。一般图G含有多个部分树。,图G的部分树T1,图G的部分树T2,4.最小部分树,最小部分树：在赋权图G的所有部分树中，树枝权数和最小的部分树称为最小部分树（或最小支撑树）。,图G的部分树（

14、15）,图G的最小部分树（8）,2,3,1,6,9,2,2,3,1,9,2,3,1,2,树与图的最小树,树与图的最小树,树与图的最小树,树与图的最小树,树与图的最小树,5.最小部分树的求解,（1）破圈（回路）法（2）避圈（回路）法（3）顺序生枝法,破圈法:在连通图中任意选取一个回路，从该回路中去掉一条权数最大的边（如果权数最大的边不唯一，则任意选取其中一条）。在余下的图中，重复这一步骤，直至得到一个不含回路的连通图（有个顶点条边），该连通图便是最小部分树。,求树的方法：破圈法和避圈法,树与图的最小树,破圈法,树与图的最小树,部分树,树与图的最小树,避圈法,树与图的最小树,破圈法：任取一圈，去掉

15、圈中最长边，直到无圈。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,边数n-1=5,赋权图中求最小树的方法：破圈法和避圈法,树与图的最小树,得到最小树：,Min C(T)=15,（1）破圈（回路）法,A,S,B,D,C,E,T,（1）破圈（回路）法,2,2,7,5,4,1,4,3,5,7,1,5,A,S,B,D,C,E,T,（1）破圈（回路）法,2,2,7,4,1,4,3,5,7,1,5,A,S,B,D,C,E,T,（1）破圈（回路）法,2,2,7,4,1,4,3,5,7,1,5,A,S,B,D,C,E,T,（1）破圈（回路）法,2,2,7,1,4,3,5,7,1,5,A,S,B,

16、D,C,E,T,（1）破圈（回路）法,2,2,7,1,4,3,5,7,1,5,A,S,B,D,C,E,T,（1）破圈（回路）法,2,2,1,4,3,5,7,1,5,A,S,B,D,C,E,T,（1）破圈（回路）法,2,2,1,4,3,5,7,1,5,A,S,B,D,C,E,T,（1）破圈（回路）法,2,2,1,3,5,7,1,5,A,S,B,D,C,E,T,（1）破圈（回路）法,2,2,1,3,5,7,1,5,A,S,B,D,C,E,T,（1）破圈（回路）法,2,2,1,3,7,1,5,A,S,B,D,C,E,T,（1）破圈（回路）法,2,2,1,3,7,1,5,A,S,B,D,C,E,T,（

17、1）破圈（回路）法,2,2,1,3,1,5,总权数和为14,A,S,B,D,C,E,T,避圈法:从图中任选一点vi，让其他各点均属于；从沟通集合V和 的连线中找出最小边，使之包含在最小部分树内。不妨假设最小边为（vi,vj）令，其他各点均属于；重复寻找从集合V到 的最小边并使之包含在最小部分树内，直到图中的所有点都包含在集合V中为止。,树与图的最小树,避圈法:去掉G中所有边，得到n个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。,树与图的最小树,v1,v2,v3,v4,v5,v6,4,3,5,2,1,Min C(T)=15,（2）避圈

18、（回路）法,2,2,7,5,4,1,4,3,5,7,1,5,0,A,S,B,D,C,E,T,（2）避圈（回路）法,2,2,7,5,4,1,4,3,5,7,1,5,A,S,B,D,C,E,T,（2）避圈（回路）法,2,2,7,5,4,1,4,3,5,7,1,5,0,A,S,B,D,C,E,T,（2）避圈（回路）法,2,2,7,5,4,1,4,3,5,7,1,5,A,S,B,D,C,E,T,（2）避圈（回路）法,2,2,7,5,4,1,4,3,5,7,1,5,A,S,B,D,C,E,T,（2）避圈（回路）法,2,2,7,5,4,1,4,3,5,7,1,5,A,S,B,D,C,E,T,（2）避圈（回

19、路）法,2,2,7,5,4,1,4,3,5,7,1,5,A,S,B,D,C,E,T,（2）避圈（回路）法,2,2,7,5,4,1,4,3,5,7,1,5,A,S,B,D,C,E,T,（2）避圈（回路）法,2,2,7,5,4,1,4,3,5,7,1,5,A,S,B,D,C,E,T,（2）避圈（回路）法,2,2,7,5,4,1,4,3,5,7,1,5,A,S,B,D,C,E,T,（2）避圈（回路）法,2,2,7,5,4,1,4,3,5,7,1,5,A,S,B,D,C,E,T,（2）避圈（回路）法,2,2,7,5,4,1,4,3,5,7,1,5,A,S,B,D,C,E,T,树与图的最小树,练习：应用

20、破圈法求最小树,树与图的最小树,树与图的最小树,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,树与图的最小树,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,树与图的最小树,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,树与图的最小树,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,树与图的最小树,v1,v7,v4,v3,v2,v5,v6,9,16,25,3,28,17,4,1,23,树与图的最小

21、树,v1,v7,v4,v3,v2,v5,v6,9,16,25,3,28,17,4,1,23,树与图的最小树,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,树与图的最小树,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,树与图的最小树,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,树与图的最小树,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,树与图的最小树,v1,v7,v4,v3,v2,v5,v6,9,3,17,4,1,23,min=1+4+9+3+17+23=57,

22、树与图的最小树,练习：应用避圈法求最小树,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,树与图的最小树,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,树与图的最小树,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,树与图的最小树,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,树与图的最小树,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,

23、3,28,17,4,1,23,36,树与图的最小树,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,树与图的最小树,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,min=1+4+9+3+17+23=57,Kruskal顺序生枝法:首先将图中的所有边按权的大小从小到大的进行排列，在确保不出现回路的前提下，将依次排列的边逐一绘出；若在增加某条边时出现了回路，则排除该边并继续寻找下一条边。,（3）顺序生枝法,现有五口油井，相互之间的距离（千米）如下表所示，问应如何铺设输油管线使输油管

24、长度最短。为便于检修和计量，输油管只允许在井口处分路。,（3）顺序生枝法,（1）排序：按井距从小到大排列 d15=d45=0.7 d14=d23=0.9 d25=1.2 d12=1.3 d35=1.7 d24=1.8 d13=2.1 d34=2.6（2）生枝：按排序顺序生枝，如果某生枝形成 回路，略去该枝并继续直到生成P-1条边。,（3）顺序生枝法,w5,w4,w1,0.7,0.7,（3）顺序生枝法,w5,w4,w1,0.7,0.7,（3）顺序生枝法,w5,w4,w1,0.7,0.7,w3,w2,0.9,（3）顺序生枝法,w5,w4,w1,0.7,0.7,w3,w2,0.9,1.2,最短路问题

25、,如何用最短的线路将三部电话连起来？此问题可抽象为设ABC为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如ABAC）。,A,B,C,最短路问题,A,B,C,P,但若增加一个周转站（新点P），连接4点的新网络的最短路线为PAPBPC。最短新路径之长N比原来只连三点的最短路径O要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。,最短路问题,问题描述：就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路.有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际

26、中得到广泛应用。,最短路问题,例 渡河游戏一老汉带了一只狼、一只羊、干草想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃干草，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。,最短路问题,定义：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

27、=(M,W,G);v3,u3=(M,W,H);v4,u4=(M,G,H);v5,u5=(M,G),此游戏转化为在下面的二分图中求从 v1 到 u1 的最短路问题。,v1,v2,v3,v4,v5,u5,u4,u3,u2,u1,第三节：最短路问题,1.求图中某一点到其他各点最短路的Dijkstra标号算法2.求图中所有点之间最短路的Floyd矩阵算法,令,Dijkstra算法,若用Lij代表从点到点的最短路，那么求从点i到点j的最短路的Dijkstra算法的具体步骤可概括如下：从点s出发，因Lss=0，将“0”标注在旁的小方框内，表示点s已标号；从点s出发，找出与点s相邻且距离最小的点r，将Lsr

28、=Lss+Lsr的值标注在点r旁的小方框内，表明点r也已标号；,Dijkstra算法,找出所有与已标号点相邻的末标号点，若Lsp=minLss+Lsp,Lsr+Lrp，则给点p标号，即将Lsp的值标注在p旁的小方框内；重复第三步，一直到t点得到标号为止；此时各点小方框内的标注值就是s点到该点的最短路。,Dijkstra算法,2,2,7,5,4,1,4,3,5,7,1,5,S,A,B,C,D,E,F,0,第一步：从点s出发，对其标“0”，令，其他各点均属于；,2,2,7,5,4,1,4,3,5,7,1,5,S,A,B,C,D,E,F,0,故A点得到标号“2”，,令,其余各点均属于,2,第二步：与

29、s点相邻的未标号点有A、B、C三个点，又因：,，,2,2,7,5,4,1,4,3,5,7,1,5,S,A,B,C,D,E,F,0,2,第三步：与标号点s和A相邻的未标号点有B、C、E三个点，又因：,故B、C两点同时得到标号“4”，,其余各点均属于,4,4,2,2,7,5,4,1,4,3,5,7,1,5,S,A,B,C,D,E,F,0,2,4,依此类推，直到所有的点均得到标号,4,7,8,13,2.求图中所有点之间最短路的Floyd矩阵算法,dij(0)=wij(if i与 j相邻)dij(0)=0(if i=j)dij(0)=(if i与 j不相邻),dij=,D(0)=dij(0)代表从i直

30、接到达 j的距离矩阵,2.求图中所有点之间最短路的Floyd矩阵算法,D(0)=dij代表从i直接到达 j的距离矩阵从i到达 j的最短路并不局限在直接到达，两点之间可以有1、2、个中间点。先考虑i和 j两点之间可以有1个中间点的情况：dij(1)=mindik(0)+dkj(0)k=1,2,P,i,k,j,k,2.求图中所有点之间最短路的Floyd矩阵算法,再考虑i和 j两点之间可以有3个中间点的情况：dij(2)=mindik(1)+dkj(1)k=1,2,P,i,k,j,n,m,2.求图中所有点之间最短路的Floyd矩阵算法,i和 j两点之间可以有2n-1个中间点的情况：dij(n)=mi

31、ndik(n-1)+dkj(n-1)k=1,2,P 结束条件：或,即,2.求图中所有点之间最短路的Floyd矩阵算法,S,A,C,B,E,D,T,S,A,C,B,E,D,T,最短路问题,例 设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表,最短路问题,设备维修费如下表,解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购

32、进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,最短路问题,把所有弧的权数计算如下表，把权数赋到图中，再用Dijkstra算法求最短路。,最短路问题,最终得到下图，可知，v1到v6的距离是53，最短路径有两条：v1v3v6和 v1v4v6,2.求图中所有点之间最短路的Floyd矩阵算法,案例：某城有5个区组成，各区之间的道路情况如下图所示，各边的权数为距离（千米）。已知各区年消费粮食分别为6000、4000、10000、7000和9000吨，若该城准备建一座统一的粮库，问就运输的吨千米数最小粮库应建在哪个区？,10,E,D,C

33、,B,A,20,5,10,20,10,15,25,2.求图中所有点之间最短路的Floyd矩阵算法,0 10 20 15 10 0 5 20 D(0)=20 5 0 10 10 15 10 0 25 20 10 25 0,2.求图中所有点之间最短路的Floyd矩阵算法,0 10 15 15 30 10 0 5 15 15 D(1)=15 5 0 10 10 15 15 10 0 20 30 15 10 20 0,2.求图中所有点之间最短路的Floyd矩阵算法,0 10 15 15 25 10 0 5 15 15 D(2)=15 5 0 10 10 15 15 10 0 20 25 15 10 2

34、0 0,2.求图中所有点之间最短路的Floyd矩阵算法,0 10 15 15 25 10 0 5 15 15 D(2)=15 5 0 10 10 15 15 10 0 20 25 15 10 20 0,6000,4000,10000,7000,9000,2.求图中所有点之间最短路的Floyd矩阵算法,0 60,000 90,000 90,000 150,00040,000 0 20,000 60,000 60,000150,000 50,000 0 10,000 10,000105,000 105,000 70,000 0 140,000225,000 135,000 90,000 180,0

35、00 0520,000 350,000 270,000 340,000 360,000,合计,C*,最短路问题思考题,1、求下图v1到各点的最短距离及最短路线。,0,4,5,2,2,3,10,3,9,6,12,6,4,11,6,6,18,8,12,24,8,24,18,所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。,最短路问题,2.求从v1到v8的最短路径,最短路问题,v1到v8的最短路径为v1v4v7v5v8，最短距离为10,最短路问题,3.求下图中v1点到另外任意一点的最短路径,v1,v2,v3,v4,v6,v5,3,2,2,7,6,2,1,3,3,最短路问题,

36、v1,V2,V3,V4,V6,V5,3,2,2,7,6,2,1,3,3,0,2,4,7,1,4,最短路问题,v1,V2,V3,V4,V6,V5,3,2,2,7,6,2,1,3,3,0,2,4,7,1,4,最短路问题,最短路问题的应用：4、电信公司准备准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。,v1（甲地）,15,17,6,2,4,4,3,10,6,5,v2,v7(乙地),v3,v4,v5,v6,第五节：最大流问题,1.基本概念2.求网络流图最大流的标号算法,1.基本概念,正、负线度：从一点发出的弧的数目

37、称为点的正线度；进入点的弧的数目称为点的负线度。2.发点（source）：负线度为“0”的点。3.收点（sink）：正线度为“0”的点。,1.基本概念,4.网络流图：（1）只有一个发点和一个收点；（2）各弧有一个非负的“容量（capacity）”，cij；（3）各弧有一个不大于“容量”的“流量（flow）”，fij。,1.基本概念,4.容量网络：网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中通常规定一个发点(也称源点，记为s)和一个收点(也称汇点，记为t)，网络中其他点称为中间点。,s,t,4,8,4,4,1,2,2,6,7,9,1.基本概念,5

38、.流、可行流和最大流：流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的负载量记为fij。若fij=0，称为零流。可行流：满足以下条件的一组流称为可行流。,容量限制条件。容量网络上所有的弧满足：0fijcij 中间点平衡条件。,若以v(f)表示网络中从st的流量，则有：,网络的最大流,网络的最大流 网络的最大流是指网络中从发点到收点之间允许通过的最大流量。,6.饱和弧：fij=cij 的弧。7.非饱和弧：fij cij 的弧。8.零流弧：fij=0 的弧。,结论：任何网络上一定存在可行流。（零流即是可行流）,网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使v(f)值达到最大

39、。,1.基本概念,9.正向弧与反向弧：若是从发点vs到收点vt的一条链，定义链的方向为从vs到vt，则链上的弧被分为两类：（1）弧的方向与链的方向一致（在该链上所有指向为st的弧），则称正向弧（+）；（2）弧的方向与链的方向相反（在该链上所有指向为 t s的弧），则称反向弧（-）。10.增广链：设 f 是一个可行流，是从发点vs到收点vt的一条链，若满足下列条件，则称其为一条增广链：（1）+中的每一个弧均为非饱和弧；（2）-中的每一个弧均为非零流弧。,若f0，则称这样的链为增广链。例如下图中，sv2v1v3v4t。,定理3 网络N中的流 f 是最大流当且仅当N中不包含任何增广链,网络的最大流,

40、求网络最大流的标号算法：基本思想 由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。,基本方法,找出第一个可行流，（例如所有弧的流量dij=0。）用标号的方法找一条增广链,首先给发点s标号(),标号中的数字表示允许的最大调整量。选择一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查：,网络的最大流,如果弧的起点为vi，vj未标号且相邻，并且有dij0，则vj标号(-vi,j),(3)重复第(2)步，可能出现两种结局：,标号过程中断，t无法标号，说明网络中不存在增广链，目前流量为最大流。t得到标号，反向追踪在网络中找到一条从s到t得由标号点及相应的弧

41、连接而成的增广链。继续第(4)步,网络的最大流,(4)修改流量。设原图可行流为f，令,得到网络上一个新的可行流f。,(5)擦除图上所有标号，重复(1)-(4)步，直到图中找不到任何增广链，计算结束。,1.基本概念,（1）链=vs,v1,v2,v4,v3,vt是一条增广链；（2）链=vs,v2,v3,v4,vt不是增广链；（3）链=vs,v1,v2,v4,v3,vt不是增广链。,（0，）,2.求网络流图最大流的标号算法,（vs，3）,（vs，1）,（-v2，1）,（v3，1）,2.求网络流图最大流的标号算法,v4,v3,v2,vt,v1,vs,(5,4),(3,0),(4,3),(1,0),(2

42、,2),(5,2),(4,3),(2,2),(1,0),2.求网络流图最大流的标号算法,v4,v3,v2,vt,v1,vs,(5,4),(3,0),(4,3),(1,0),(2,2),(5,2),(4,3),(2,2),(1,0),（0，）,2.求网络流图最大流的标号算法,v4,v3,v2,vt,v1,vs,(5,4),(3,0),(4,3),(1,0),(2,2),(1,0),(5,2),(4,4),（vs，3）,(2,2),最大流=6,网络的最大流,例 用标号算法求下图中st的最大流量,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),

43、5(4),7(5),网络的最大流,解：(1)先给s标号(0,),s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),(0,),网络的最大流,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),(0,),(2)检查与s点相邻的未标号的点，v1与v2，因ds1cs1，故对v1标号（vs，l（v1）:,(Vs,1),(Vs,2),因ds2cs2，故对v2标号（vs，l（v2）,网络的最大流,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(

44、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),网络的最大流,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(6),(0,),(vs,1),(2)检查与v1点相邻的未标号的点，因f13c13，故对v3标号 l(v3)minl(v1),c13-d13=min1,c13-d13=min1,6=1；,(v1,1),(vs,2),网络的最大流,s,t,v

45、1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),(0，),(vs,1),(v1,1),(3)检查与v3点相邻的未标号的点，因f3tc3t，故对vt标号=min1,c3t-f3t=min1,1=1,(v3,1),找到一条增广链sv1v3t,(vs,2),网络的最大流,(4)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。,s,t,v1,v3,v2,v4,8(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),网络的最大流

46、,(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。,s,t,v1,v3,v2,v4,8(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)擦除所有标号，重复上述标号过程，寻找另外的增广链。,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6(1),2(0),9(9),5(3),7(5),(vs,2),l(v2)=min,2=2,l(v1)=min2，3=2,l(v3)=min2,5=2,(-v3,1),l(v4)=min2,1=1,l(vt)=min1

47、,2=1,(0，),(-v2,2),(v1,2),(v4,1),网络的最大流,(6)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。,s,t,v1,v3,v2,v4,8(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),网络的最大流,s,t,v1,v3,v2,v4,8(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),(

48、v1,1),(v4,1),网络的最大流,s,t,v1,v3,v2,v4,8(8),9(5),5(5),10(9),6(0),2(0),9(9),5(2),7(6),(7)擦除所有标号，重复上述标号过程，寻找另外的增广链。,l(v2)=min,1=1,l(v1)=min1,2=1,l(v3)=min1,4=1,(vs,1),(0，),(v2,1),(v1,1),无法标号，不存在增广链，此可行流已为最大流。最大流量为14。,网络的最大流,例 求下图st的最大流,网络的最大流,解:(1)在已知可行流的基础上，通过标号寻找增广链。,(),(2)=min,6=6,(6),(3)=min6,2=2,(2)

49、,(t)=min2,5=2,(2),存在增广链sv2v3 t,网络的最大流,(2)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。,(),(6),(2),(2),网络的最大流,(3)擦除原标号，重新搜寻增广链。,(),(6),(2),(2),网络的最大流,(4)重新搜寻增广链。,(),(2)=min,4=4,(4),(1),(5)=min4,1=1,(3)=min1,2=1,(1),(1),(t)=min1,3=1,存在增广链：sv2v5v3 t,网络的最大流,(5)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。,(),(4),(1),(1),(1),网络的最大流,(6)

50、擦除原标号,(),(4),(1),(1),(1),网络的最大流,(),(1),(1),(1),(5)=min,1=1,(5)=min1,1=1,(5)=min1,2=1,(7)重新搜寻增广链。,存在增广链：sv5v3 t,网络的最大流,(8)调整增广链上的流量，非增广链流量不变，得到新的可行流,(),(1),(1),(1),网络的最大流,(),(1),(1),(1),(9)擦除原标号,网络的最大流,(10)重新标号，搜索增广链,(),(1)=min,1=1,(1),(5)=min1,1=1,(1),(4)=min1,1=1,(1),(t)=min1,1=1,(1),存在增广链：sv1v5v4t