《运筹学与系统分析：第5章 图与网络分析》由会员分享，可在线阅读，更多相关《运筹学与系统分析：第5章 图与网络分析（51页珍藏版）》请在金锄头文库上搜索。
1、第五章 图与网络分析主要内容：主要内容：5.1 图与网络的基本知识图与网络的基本知识5.2 树树5.3 最短路最短路问题问题5.4 最大流最大流问题问题思考：思考：哥尼斯堡七桥问题哥尼斯堡七桥问题 哥哥尼尼斯斯堡堡（现现名名加加里里宁宁格格勒勒）是是欧欧洲洲一一个个城城市市，有有一一条条河河把把该该城城分分成成两两部部分分，河河中中有有两两个个小小岛岛，十十八八世世纪纪时时，河河两两边边及及小小岛岛之之间间共共有有七七座座桥桥，当当时时人人们们提提出出这这样样的的问问题题：有有没没有有办办法法从从某某处处（如如A）出出发，经过各桥一次且仅一次，最后回到原地呢？发，经过各桥一次且仅一次，最后回到
2、原地呢？ABCD 此难题于此难题于1736年被瑞士数学家欧拉解决，他在年被瑞士数学家欧拉解决，他在“依据几何位置的解题方法依据几何位置的解题方法”论文中证明这样的论文中证明这样的走法不存在。欧拉被公认为图论的创始人。走法不存在。欧拉被公认为图论的创始人。ABCDBACD 1857年，英国数学家年，英国数学家Hamilton发明一种游戏，用一个实心发明一种游戏，用一个实心正正12面体象征地球，其面体象征地球，其20个顶点分别表示世界的个顶点分别表示世界的20个城市，个城市，要求游戏者从某一城市出发寻找一条经由每个城市一次且仅要求游戏者从某一城市出发寻找一条经由每个城市一次且仅经一次再回到原出发点
3、的路。此问题有解。经一次再回到原出发点的路。此问题有解。Euler回路：在图中找一条经过每边一次且仅一次的回路：在图中找一条经过每边一次且仅一次的路且回到原点。路且回到原点。Hamilton回路：在图中找一条经过每个点一次其仅回路：在图中找一条经过每个点一次其仅一次的路且回到原点。一次的路且回到原点。图论第一本专著：图论第一本专著：有限图与无限图的理论有限图与无限图的理论，1936，匈牙利数学家。，匈牙利数学家。图论迅速发展时期：图论迅速发展时期：20世纪中期，电子计算机的发世纪中期，电子计算机的发展以及离散数学的发展，促使图论在管理科学、信展以及离散数学的发展，促使图论在管理科学、信息论、控
4、制论等各领域广泛应用。息论、控制论等各领域广泛应用。5.1 图与网络基本知识图与网络基本知识一、图与网络的基本概念一、图与网络的基本概念企业企业A 企业企业B企业企业C企业企业D企业企业E工人工人工作工作甲甲乙乙丙丙丁丁戊戊ABCD图：反映对象之间关系的一种工具。图：反映对象之间关系的一种工具。定义定义1：一个图是由点集：一个图是由点集V=vi和边集和边集E=ek（所有边（所有边的端点都属于的端点都属于V）所构成的二元组，记为）所构成的二元组，记为G=(V,E)。vi为顶点，为顶点，ek为边，当为边，当V、E为有限集时为有限集时G为有限图。为有限图。e1v4e3v1v2e4e5v5v3e6e2
5、例：右图中例：右图中V=v1,v2,v3,v4,v5E=e1,e2,e3,e4,e5,e6e1=(v1,v1),e2=(v1,v2),无向图无向图：任意边都是无向边的图：任意边都是无向边的图有向图有向图：任意边都是有向边的图：任意边都是有向边的图环环：边的两端点相同也称环，如：边的两端点相同也称环，如e1;多重边多重边：两点间多于一条边，如：两点间多于一条边，如e4,e5定义定义2：不含环和多重边的图是：不含环和多重边的图是简单图简单图，含有多重边的，含有多重边的图称为图称为多重图多重图。下图哪些是简单图，哪些是多重图？。下图哪些是简单图，哪些是多重图？有向图中两点之间有不同方向的两条边，不是
6、多重边。有向图中两点之间有不同方向的两条边，不是多重边。(a)(b)(c)(d)a,b为简单图，为简单图，c,d为多重图。为多重图。定义定义3: 每一对顶点间都有边相连的无向简单图称为每一对顶点间都有边相连的无向简单图称为完全完全图图。每一对顶点间有且仅有一条有向边的简单图称为。每一对顶点间有且仅有一条有向边的简单图称为有有向完全图向完全图。定义定义4：图：图G的点集的点集V可以分成两个非空子集可以分成两个非空子集X,Y,使得使得E中每条边的两个端点必有一个属于中每条边的两个端点必有一个属于X，另一个属于，另一个属于Y，则，则G称为称为二部图二部图。以下哪些是二部图？以下哪些是二部图？(a)(
7、b)a,b图都是二部图。图都是二部图。定义定义5：以点：以点v为端点的边数叫做为端点的边数叫做点点v的次的次。记为。记为deg(v),简记简记d(v)。 次为奇数的点称为次为奇数的点称为奇点奇点，次为偶数的点称为，次为偶数的点称为偶偶点点。次为。次为0的点称为的点称为孤立点孤立点。e1v4e3v1v2e4e5v5v3e6e2右图中右图中d(v1)=4 (e1计算两次计算两次)d(v3)=4定理定理1：任何图中，顶点次数的总和等于边数的：任何图中，顶点次数的总和等于边数的2倍。倍。定理定理2：任何图中，次为奇数的顶点必为偶数个。：任何图中，次为奇数的顶点必为偶数个。定义定义6：有向图中以：有向图
8、中以vi为始点的边数称为为始点的边数称为vi的出次的出次，记为，记为d+(vi) ，以，以vi为终点的边数称为为终点的边数称为vi的入次的入次，记为，记为d-(vi) 。定义定义7：图：图G=(V,E)，若，若E是是E的子集，的子集，V是是V的子集，的子集，且且E中的边仅与中的边仅与V中的顶点相关联，则称中的顶点相关联，则称G=(V,E)是是G的一个的一个子图子图。若。若V=V, 则则G称为称为G的的生成子图生成子图。例，下图例，下图(b)为为(a)的子图，的子图，(c)为为(a)的生成子图。的生成子图。v1v2v3v4v5(a)v1v2v3v5(b)v1v2v3v4v5(c)权权：点或边相关
9、的某些数量指标，可代表距离、费用、：点或边相关的某些数量指标，可代表距离、费用、容量等。容量等。网络网络：点或边带有某种数量指标的图。：点或边带有某种数量指标的图。(a),(b)是常见网络例子，是常见网络例子，(a)网络图常见于最短路问题，网络图常见于最短路问题，(b)网络图常见于管道运输网络。网络图常见于管道运输网络。v3v1v4v5v2(a)v3v1v4v5v2(b)54362525436225二、连通图二、连通图定义定义8：无向图：无向图G中能够连接两点的点、边序列构成一中能够连接两点的点、边序列构成一条条链链。没有重复点或重复边的链为。没有重复点或重复边的链为初等链初等链。v3v1v4
10、v5v2e1e2e3e4e5e6e7S1=v1,e1,v3,e7,v5,e6,v3,e7,v5,e4,v4为连接为连接v1,v4的一条链；的一条链；S2=v1,e1,v3,e7,v5,e4,v4为初等链为初等链定义定义9：无向图：无向图G中一条链的始点和终点是同一点时，中一条链的始点和终点是同一点时，称为称为圈圈。没有重复点或重复边的圈为。没有重复点或重复边的圈为初等圈初等圈。S1=v1,e1,v3,e7,v5,e6,v3,e7,v5,e4,v4,e2,v1为一个圈；为一个圈；S2=v1,e1,v3,e7,v5,e4,v4,e2,v1为一个初等圈。为一个初等圈。有向图中边的方向相同时，链和圈分
11、别称为有向图中边的方向相同时，链和圈分别称为道路道路和和回路回路。定义定义10：一个图中任意两点间至少有一条链，称为：一个图中任意两点间至少有一条链，称为连通图连通图。任何非连通图都可以分为若干个连通子图任何非连通图都可以分为若干个连通子图(分图分图)。三、图的矩阵表示三、图的矩阵表示v1v2v3v4v5745629483定义定义11：网络：网络(赋权图赋权图)G=(V,E)上的上的边边(vi,vj)有权有权wij，构造矩阵，构造矩阵A=(aij)nn，其中，其中称矩阵称矩阵A为网络为网络G的的权矩阵权矩阵。右图的权矩阵为：右图的权矩阵为：三、图的矩阵表示三、图的矩阵表示v1v2v3v4v5定
12、义定义12：图：图G=(V,E)的顶点的数量的顶点的数量为为n，构造矩阵，构造矩阵A=(aij)nn，其中，其中称矩阵称矩阵A为图为图G的的邻接矩阵邻接矩阵。当。当G为为无向图时，邻接矩阵为对称矩阵。无向图时，邻接矩阵为对称矩阵。右图的邻接阵为：右图的邻接阵为：四、欧拉回路与中国邮路问题四、欧拉回路与中国邮路问题定义定义13：连通图中，若存在一条回路，经过每边一次且：连通图中，若存在一条回路，经过每边一次且仅一次，则称之为仅一次，则称之为欧拉回路欧拉回路。具有欧拉回路的图称为。具有欧拉回路的图称为欧欧拉图拉图（E图）。图）。定理定理3：无向连通图：无向连通图G是欧拉图，当且仅当是欧拉图，当且仅
13、当G中无奇点。中无奇点。定理定理4：有向连通图：有向连通图G是欧拉图，当且仅当是欧拉图，当且仅当G的每个顶点的每个顶点的出次等于入次。的出次等于入次。中国邮路问题：邮递员从邮局出发，走遍该地区所有街中国邮路问题：邮递员从邮局出发，走遍该地区所有街道再返回邮局，如何安排路线可以使所走总路程最短？道再返回邮局，如何安排路线可以使所走总路程最短？中国邮路问题可以转化为如下问题：中国邮路问题可以转化为如下问题：在连通图在连通图G=(V,E)中，求一个边集中，求一个边集E1 E，把，把G属于属于E1的边均变为二重边得到的边均变为二重边得到G*=G+E1，使其满足，使其满足G*无奇点，无奇点，且且L(E1
14、)最小。最小。 定理定理5：已知图：已知图G*=G+E1无奇点，则无奇点，则L(E1)最小的充要最小的充要条件是：条件是：（1）每条边最多重复一次；）每条边最多重复一次；（2）对图）对图G中每个初等圈来讲，重复边的长度之和不中每个初等圈来讲，重复边的长度之和不超过圈长的一半。超过圈长的一半。例：利用定理例：利用定理5求解下面网络的中国邮路问题求解下面网络的中国邮路问题解：解：(1)检查是否有奇点检查是否有奇点?共有四个奇点：共有四个奇点：v2,v4,v6,v8v1v2v3v4v5v6v9v8v7256354434944(a)v1v2v3v4v5v6v9v8v7256354434944(b)59
15、(2)将将v2与与v4,v6与与v8配对，配对，分别经分别经v1和和v9作出重复边，作出重复边，使整个网络图没有奇点，且使整个网络图没有奇点，且满足定理满足定理5中的条件中的条件(1) ;初等圈都满足条件初等圈都满足条件(2)？圈圈v1v2v5v4v1不满足条件不满足条件(2)；(3)做调整，画出做调整，画出c图，满足图，满足条件条件(2)吗？吗？v1v2v3v4v5v6v9v8v7256354434944(c)圈圈v2v3v6v9v8v5v2不满足不满足条件条件(2)。(4)做调整，将做调整，将v2与与v6，v4与与v8重新配对，画出重新配对，画出d图，满图，满足条件足条件(2)吗？吗？已经
16、满足，图中任一欧拉回已经满足，图中任一欧拉回路即为最优邮路，如红线所路即为最优邮路，如红线所示为最优邮路。示为最优邮路。v1v2v3v4v5v6v9v8v7256354434944(d)注：最优邮路不唯一注：最优邮路不唯一5.2 树树一、树的概念和性质一、树的概念和性质树在许多领域有广泛应用。树在许多领域有广泛应用。AB CD运运动动员员体育比赛四强相遇体育比赛四强相遇厂长厂长人事科人事科生产科生产科财务科财务科生生产产计计划划室室质质量量监监控控室室生生产产执执行行室室某工厂的组织结构某工厂的组织结构定义定义14：连通且不含圈的无向图称为树。树中次为：连通且不含圈的无向图称为树。树中次为1的
17、的点称为树叶，次大于点称为树叶，次大于1的点称为分枝点。的点称为分枝点。定理定理6：图：图T=(V,E)的的V有有n个顶点，个顶点，E有有m条边，则下条边，则下面对树的说法是等价的：面对树的说法是等价的：(1)T是一个树；是一个树；(2)T无圈，且无圈，且m=n-1;(3)T连通，且连通，且m=n-1;(4)T无圈，但每加一新边即得唯一一个圈；无圈，但每加一新边即得唯一一个圈；(5)T连通，但舍去一边就不连通；连通，但舍去一边就不连通；(6)T中任意两点，有唯一链相连。中任意两点，有唯一链相连。二、图的生成树二、图的生成树定义定义15：若图：若图G的生成子图是一棵树，则称该树为的生成子图是一棵
18、树，则称该树为G的的生成树生成树（支撑树），简称（支撑树），简称G的树。的树。G中属于生成树中属于生成树的边称为的边称为树枝树枝，不在生成树中的边称为，不在生成树中的边称为弦弦。例，如图例，如图b是是a的生成树，边的生成树，边e4,e5,e6为弦。为弦。e3e5e2e4e8e7e6e9e1(a)e2e3e8e7e9e1(b)定理定理7：图：图G(V,E)有生成树的充要条件是有生成树的充要条件是G是连通图是连通图在图中找生成树的方法分两种：在图中找生成树的方法分两种：(a)深探法深探法(1)任取一点任取一点v,标号标号0；(2)若某点若某点u已编号已编号i，检查端点有，检查端点有u的各边，其另一
19、端是的各边，其另一端是否已编号？否已编号？ 若有边若有边(u,w)的的w端未标号，则标端未标号，则标w为为i+1,令令w取代取代u，重复步骤，重复步骤(2); 若有若有u的所有边另一端均已编号，退到的所有边另一端均已编号，退到i-1编号的点编号的点r，以，以r代替代替u，重复步骤，重复步骤(2);如此重复直到全部点得到编号为止，得到生成树。如此重复直到全部点得到编号为止，得到生成树。例：利用深探法找出下图的生成树。例：利用深探法找出下图的生成树。原图原图对应生成树对应生成树012345678910111213012345678910111213(b)广探法广探法(1)任取一点任取一点v,标号标
20、号0；(2)检查编号检查编号i的点，包含的点，包含i点的所有边的另一端是否已编点的所有边的另一端是否已编号？对所有未编号的这些点都编相同的号号？对所有未编号的这些点都编相同的号i+1;(3)对编号对编号i+1的所有点重复步骤的所有点重复步骤(2);如此重复直到全部点得到编号为止，得到生成树。如此重复直到全部点得到编号为止，得到生成树。例：利用广探法找出下图的生成树。例：利用广探法找出下图的生成树。原图原图10122132122343对应生成树对应生成树01234212112233注：图的生成树不唯一注：图的生成树不唯一三、最小生成树问题三、最小生成树问题定义定义16：连通图：连通图G=(V,E
21、)，每条边上有非负权，每条边上有非负权L(e)。一。一棵生成树所有树枝上权的总和，称为生成树的权。具棵生成树所有树枝上权的总和，称为生成树的权。具有最小权的生成树称为最小生成树有最小权的生成树称为最小生成树(最小支撑树最小支撑树)，简称，简称最小树最小树。许多网络问题都可以归结为最小树问题。如：许多网络问题都可以归结为最小树问题。如：(1)交通系统中设计总长度最小的公路网，将若干城市交通系统中设计总长度最小的公路网，将若干城市联系起来；联系起来；(2)通信系统中用最小成本把计算机系统和设备连接到通信系统中用最小成本把计算机系统和设备连接到局域网。局域网。找出最小树的算法：找出最小树的算法：(a
22、)Kruskal算法：算法：(1)从未选的边中选取边从未选的边中选取边e，使它与已选边不构成圈，使它与已选边不构成圈，且且e是未选边中最小权边；是未选边中最小权边；(2)重复步骤重复步骤(1)，直至选够，直至选够n-1(n为图的顶点数为图的顶点数)条条边为止。边为止。例：一个乡有例：一个乡有9个村，相互间道路及路长如下图，问如个村，相互间道路及路长如下图，问如何拉线连通各个村，且使用线最短。何拉线连通各个村，且使用线最短。v2v0v3v4v5v1v8v7v64121415531342424v2v0v3v4v5v1v8v7v612113122解：先将图中各边按路长由小至大排列，然后按顺序解：先将
23、图中各边按路长由小至大排列，然后按顺序依次选择依次选择: (v0,v2), (v2,v3), (v3,v4), (v1,v8), (v0,v1), (v0,v6), (v5,v6),(v6,v7)，得到最小树，权为，得到最小树，权为13。找出最小树的算法：找出最小树的算法：(b)破圈法：破圈法：(1)从图从图G中任选一棵树中任选一棵树T1;(2)加上一条弦加上一条弦e1,使使T1+e1能生成一个圈。去掉此能生成一个圈。去掉此圈中最大权边，得到新树圈中最大权边，得到新树T2。以。以T2代替代替T1,重复重复步骤步骤2，直到所有弦检查完毕。，直到所有弦检查完毕。v2v0v3v4v5v1v8v7v6
24、4121415531342424v2v0v3v4v5v1v8v7v612113122例：将上例用破圈法求解最小树例：将上例用破圈法求解最小树解：先求出一棵生成树如下，加弦解：先求出一棵生成树如下，加弦(v1,v2) 发现其自身发现其自身是圈是圈(v1v2v0v1)中最大权边并去掉中最大权边并去掉, 逐步求解得：逐步求解得：v2v0v3v4v5v1v8v7v621453424四、根树及其应用四、根树及其应用定义定义17：一个有向图在不考虑边的方向时是一棵树，：一个有向图在不考虑边的方向时是一棵树，则这个有向图为有向树。则这个有向图为有向树。定义定义18：有向树：有向树T恰有一个结点入次为恰有一个
25、结点入次为0，其余各点入，其余各点入次均为次均为1，则称，则称T为为根树根树（又称外向树）。入次为（又称外向树）。入次为0的点的点为为根根，出次为，出次为0的点称为的点称为叶叶，其他顶点称为，其他顶点称为分枝点。分枝点。设设每边长为每边长为1，则根到某点，则根到某点vi的路长称为的路长称为vi点的层次点的层次。v1v2v3v4v5v6v7定义定义19：根树中每个顶点的出次小于或等于：根树中每个顶点的出次小于或等于m，则称，则称这棵树为这棵树为m叉树叉树。若每个顶点的出次恰好都等于。若每个顶点的出次恰好都等于m或或0，则称之为，则称之为完全完全m叉树叉树。当。当m=2时，称为时，称为二叉树二叉树
26、。令有令有s个叶子的二叉树个叶子的二叉树T各叶子的权分别为各叶子的权分别为pi，根到各，根到各叶子的距离叶子的距离(层次层次)为为 li (i=1,s)，则二叉树的总权数，则二叉树的总权数为为满足总权数最小的二叉树称为满足总权数最小的二叉树称为最优二叉树最优二叉树。求最优二叉树的算法：霍夫曼算法求最优二叉树的算法：霍夫曼算法(1)将将s个叶子按权由小至大排序，设个叶子按权由小至大排序，设p1 p2 ps;(2)将两个具有最小权的叶子合并成一个新分枝点，其权将两个具有最小权的叶子合并成一个新分枝点，其权为为p1+p2 ,将该新分枝点作为一个叶子，令将该新分枝点作为一个叶子，令s=s-1(若若s=
27、1停停止计算止计算)，转步骤，转步骤(1)。例：若叶子例：若叶子s=6,其权分别为其权分别为4,3,3,2,2,1, 求最优二叉树。求最优二叉树。解：按霍夫曼算法将最优二叉树构造如下解：按霍夫曼算法将最优二叉树构造如下:132 2 3 3 43 3 41 22535493 361 2236155493 31 22363 3 41 2253直观意义直观意义：叶子的距离按权的递减而增加，总权最小。：叶子的距离按权的递减而增加，总权最小。总权总权 pili =14 +24+23+32+32+42=385.3 最短路最短路问题问题 最短路问题一般提法：设最短路问题一般提法：设G(V,E)为连通图，图中
28、各边为连通图，图中各边(vi,vj)有权有权 lij (lij=表示两点间无边表示两点间无边)，vs和和vt是图中任意是图中任意两点，求一条道路从两点，求一条道路从vs到到vt且该道路总权最小。且该道路总权最小。一、一、Dijkstra算法算法它被公认是求无负权网络最短路问题的最好方法。它被公认是求无负权网络最短路问题的最好方法。基本原理基本原理：若：若vs,v1,vt-1,vt是从是从vs到到vt的最短路，则的最短路，则vs,v1,vt-1是从是从vs到到vt-1的最短路。该算法采用标号法。的最短路。该算法采用标号法。T标号标号：给：给vi点点T标号表示从标号表示从vs到到vi点的估计最短路
29、权的点的估计最短路权的上界，是临时标号，没有上界，是临时标号，没有P标号的点都标有标号的点都标有T标号。标号。P标号标号：给：给vi点点P标号表示从从标号表示从从vs到到vi点的最短路权，是点的最短路权，是永久标号不再改变。永久标号不再改变。 此算法每一步把某点的此算法每一步把某点的T标记改为标记改为P标记，当终点标记，当终点vt得到得到P标号时，全部计算结束。具体算法如下：标号时，全部计算结束。具体算法如下：(1)给给vs以以P标号标号,P(vs)=0,其余各点均给其余各点均给T标号标号,T(vi)= ;(2)若若vi点为刚得到点为刚得到P标号的点，寻找点标号的点，寻找点vj要求要求 (vi
30、,vj)属于属于E且且vj为为T标号。对所有找到的标号。对所有找到的vj点的点的T标号值进行更改：标号值进行更改：T(vj) = minT(vj), P(vi)+lij;(3)比较所有比较所有T标号的点，把最小标号的点，把最小T值的点值的点v*改为改为P标号，标号，即即P(v*)=minT(vi)。若全部点均为。若全部点均为P标号时算法结束，标号时算法结束，否则返回步骤否则返回步骤(2)。例：用例：用Dijkstra算法求下图算法求下图v1到到v6的最短路。的最短路。解解: (1)P(v1)=0, 其余点其余点T(vi)= +;(2)(v1,v2)和和(v1,v3)属于属于E,且且v2和和v3
31、是是T编号，对这两点改变编号，对这两点改变T值：值：T(v2)=minT(v2),P(v1)+l12=min+,0+4=4T(v3)=minT(v3),P(v1)+l13=min+,0+6=6(3)比较所有比较所有T标号标号,T(v2)最小最小,令令P(v2)=4,记录路径记录路径(v1,v2)(4) v2为刚得到的为刚得到的P点点,考察边考察边(v2,v4)和和(v2,v5)的端点的端点v4,v5 T(v4)=minT(v4),P(v2)+l24=min+,4+5=9 T(v5)=minT(v5),P(v2)+l25=min+,4+4=8(5)比较所有比较所有T标号标号,T(v3)最小最小,
32、令令P(v3)=6,记录路径记录路径(v1,v3)v1v3v5v2v4v6456447575(6)考察考察v3: T(v4)=minT(v4),P(v3)+l34=min9,6+4=9 T(v5)=minT(v5),P(v3)+l35=min8,6+7=8(7)比较所有比较所有T标号标号,T(v5)最小最小,令令P(v5)=8,记录路径记录路径(v2,v5)(8)考察考察v5: T(v6)=minT(v6),P(v5)+l56=min+,8+5=13(9)比较所有比较所有T标号标号,T(v4)最小最小,令令P(v4)=9,记录路径记录路径(v2,v4)(10)考察考察v4: T(v6)=min
33、T(v6),P(v4)+l46=min13,9+7=13(11)比较所有比较所有T标号标号,T(v6)最小最小,令令P(v6)=13,记录路径记录路径(v5,v6)计算结束，最短路为计算结束，最短路为v1 v2 v5 v6, 路长路长P(v6)=13，同时得到，同时得到v1点到其余各点的最短距离。点到其余各点的最短距离。v1v3v5v2v4v6456447575例：某公司在某地区有例：某公司在某地区有6个销售点，已知该个销售点，已知该6个点的交通个点的交通网络如图所示，边表示公路，数字表示路长，问公司的网络如图所示，边表示公路，数字表示路长，问公司的仓库应该建在哪个点，使得离仓库最远的销售点到
34、仓库仓库应该建在哪个点，使得离仓库最远的销售点到仓库的距离最近？的距离最近？25v2v5v6v3v41520v12060301815解：实际是求网络中心。先求出解：实际是求网络中心。先求出v1到其他各点的最短路到其他各点的最短路长长dj,令令D(v1)=max(d1,d2,d6),表示仓库建在表示仓库建在v1时离仓时离仓库最远的销售点的距离为库最远的销售点的距离为D(v1)。逐次求出所有。逐次求出所有D(vi) (i=1,2,6), D(vi)中最小值对应的中最小值对应的vi即是网络中心。即是网络中心。 本例中：本例中：D(v1)=63, D(v2)=50, D(v3)=33, D(v4)=6
35、3, D(v5)=48, D(v6)=63, 其中其中D(v3)最小最小, v3即是网络中心。即是网络中心。二、二、Floyd算法算法该算法可直接求出网络中任意两点的最短路。该算法可直接求出网络中任意两点的最短路。 令网络的权矩阵为令网络的权矩阵为D=(dij)nn，lij为为vi到到vj的距离，而的距离，而矩阵元素矩阵元素Floyd算法步骤：算法步骤：(1)输入权矩阵输入权矩阵D(0) =D;(2)计算计算 其中其中(3) 中元素中元素 即是即是vi到到vj的最短路。的最短路。例：用例：用Floyd法求下图法求下图G中任意两点间的最短距离。中任意两点间的最短距离。25v2v5v6v3v415
36、20v12060301815解：由图得到网络权矩阵为解：由图得到网络权矩阵为D (1) =D (0), D (4) =D (3), D (6) =D (5)，计算结束，计算结束， D (6)中矩阵元素即为任意两点的中矩阵元素即为任意两点的最短路最短路 。 表示从表示从vi点到点到vj点直接有边或点直接有边或经经v1为中间点时的最短路长为中间点时的最短路长, 和和 分别表示从分别表示从vi到到vj最多经中间点最多经中间点v1,v2与与v1,v2,v3的最短路长。的最短路长。5.4 最大流最大流问题问题一、最大流相关概念一、最大流相关概念 如图看作输油管道网，如图看作输油管道网，vs起点，起点，v
37、t终点，其它终点，其它6点点为中转站，数字表示管道的最大输油能力，问应如为中转站，数字表示管道的最大输油能力，问应如何安排各管道输油量，才能从始点到终点的总输油何安排各管道输油量，才能从始点到终点的总输油量最大？量最大？vsvtv1v2v3v4v5v653453322435定义定义20：设有向连通图：设有向连通图G=(V,E)，G的每条边的每条边(vi,vj)上有上有非负的容量非负的容量cij，仅有一个入次为，仅有一个入次为0的点的点(发点发点,或称源或称源)和一和一个出次为个出次为0的点的点(收点收点,或称汇或称汇)，其余点为中间点，则，其余点为中间点，则G称称为容量网络，记为为容量网络，记
38、为G=(V,E,C) 对对G中任一边中任一边(vi,vj)有流量有流量fij，称集合，称集合f=fij为网络为网络G上上的一个流。称满足下列条件的流的一个流。称满足下列条件的流f为可行流：为可行流：(1)容量限制条件：对容量限制条件：对G中每条边中每条边(vi,vj) ，有，有0 fij cij;(2)平衡条件：中间点平衡条件：中间点vi有有fij= fki, 即输入输出相等；即输入输出相等；对收、发点对收、发点vs,vt有有 fsi = fjt =W，W为网络总流量。为网络总流量。可行流总是存在的，可行流总是存在的，f=0是流量为是流量为0的可行流。的可行流。最大流问题最大流问题就是在容量网
39、络中寻找流量最大的可行流。就是在容量网络中寻找流量最大的可行流。当当fij = cij ，称流，称流f 对边对边(vi,vj)是饱和的。是饱和的。定义定义21：容量网络：容量网络G=(V,E,C)中，中，vs, vt分别是发、收点，分别是发、收点，若有边集若有边集E是是E的子集，它将的子集，它将G分为两个子图分为两个子图G1, G2，其顶点集合记为其顶点集合记为S, S(SS =V, SS=), 其中其中vs, vt分分属属S, S, 同时满足同时满足(1)G(V, E-E)不连通；不连通；(2)E为为E的真的真子集时，子集时，G(V,E-E)仍连通，则称仍连通，则称E为为G的的割集割集，记为
40、，记为E=(S,S)。 割集中所有始点在割集中所有始点在S，终点在，终点在S的边的容量的边的容量之和称为割集容量。割集容量最小的称为之和称为割集容量。割集容量最小的称为G的的最小割最小割。图中图中(vs,v1),(vs,v2),(v3,v6)和和(v1,v4),(v5,vt), (v6,vt)都是割集，其容量分别是都是割集，其容量分别是11和和13。vsvtv1v2v3v4v5v653453322435二、最大流二、最大流-最小割定理最小割定理容量网络中割集是由容量网络中割集是由vs到到vt的必经之路，无论拿掉哪的必经之路，无论拿掉哪个割集，个割集， vs和和vt不再相通，故任一可行流的流量不
41、超不再相通，故任一可行流的流量不超过任一割集的容量。过任一割集的容量。定理定理10：设：设f为网络为网络G(V,E,C)的任一可行流的任一可行流, 流量为流量为W, (S,S)为分离为分离vs和和vt的任一割集的任一割集, 则有则有W C(S,S)定理定理11: (最大流最大流-最小割定理最小割定理) 任一网络任一网络G中，从中，从vs到到vt的最大流流量等于分离的最大流流量等于分离vs和和vt的最小割容量。的最小割容量。定义定义22：容量网络：容量网络G中，若中，若为从为从vs到到vt的一条链，的一条链，给给定向为从定向为从vs到到vt，上的边与上的边与同向的称为同向的称为前向边前向边，与与
42、反向的称为反向的称为后向边后向边，其集合分别用，其集合分别用+和和-表示，表示，f是一个可行流，如果满足是一个可行流，如果满足则称则称为从为从vs到到vt的的(关于关于f的的)可增广链可增广链。推论推论：可行流：可行流f是最大流的充要条件是不存在从是最大流的充要条件是不存在从vs到到vt的的(关于关于f的的)可增广链。可增广链。可增广链的实际意义可增广链的实际意义：沿着这条链输送的流有潜力：沿着这条链输送的流有潜力可挖，可按一定方法把流量调高。调整后的流在各可挖，可按一定方法把流量调高。调整后的流在各点仍满足平衡条件和容量限制条件，仍为可行流。点仍满足平衡条件和容量限制条件，仍为可行流。 寻求
43、最大流的方法可从一个可行流开始，寻求它寻求最大流的方法可从一个可行流开始，寻求它的可增广链，若存在则调整到流量更大的可行流，的可增广链，若存在则调整到流量更大的可行流，直到不能找到可增广链为止，其流量即为最大流。直到不能找到可增广链为止，其流量即为最大流。三、求最大流的标号算法三、求最大流的标号算法1. 标号过程标号过程 (通过标号寻找可增广链通过标号寻找可增广链)(1)给发点给发点vs标号标号(,+)，此时，此时 s+;(2)选择一个已标号的顶点选择一个已标号的顶点vi , 处理处理vi所有未标号邻接点所有未标号邻接点vj :(a)若边若边(vj,vi) E, 且且fji0, 则令则令j=m
44、in(fji, i), 给给vj标号标号(-vi, j)(b)若若(vi,vj) E, 且且fijcij , 令令j=min(cij-fij, i), 给给vj标号标号(+vi, j)(3)重复重复(2)直到收点直到收点vt被标号或不再有顶点可标号为止被标号或不再有顶点可标号为止, 若若vt获得获得标号标号,则找到可增广链则找到可增广链, 转到调整过程转到调整过程, 若若vt未获标号且标号过程未获标号且标号过程已无法进行已无法进行, 则则f已是最大流。已是最大流。2. 调整过程调整过程 (沿可增广链调整沿可增广链调整f以增加流量以增加流量)(1)令令(2)去掉所有标号去掉所有标号, 回到步骤回
45、到步骤1, 对可行流对可行流f重新标号。重新标号。例：下图为一个网络，边上数字例：下图为一个网络，边上数字(cij,fij)为容量及初始流量，为容量及初始流量，试求网络的最大流。试求网络的最大流。vsvtv1v2v3v4v5v6(5,5)(3,2)(4,2)(5,2)(3,3)(3,0)(2,2)(2,2)(4,2)(3,3)(5,4)解解: (1) 给给vs标号标号(,+ );检查检查vs邻接点邻接点v1,v2,v3。v2满满足足fs2=24, 令令2=min4-2, + =2, 给给v2点标号点标号(+vs,2), 同理同理v3点标号点标号(+vs,1)(2)检查检查v2点邻接的未标号点点
46、邻接的未标号点v5,v6。v5满足满足f250, 令令1=min3,2=2, 给给v1标号标号(-v5,2)。(3)检查检查v4点点, f145, 令令4=min5-2,2=2, 给给v4标号标号(+v1,2)。检查检查vt, f4t4, 令令t=min4-2,2=2, 给给vt标号标号(+v4,2)。(4)vt已标号已标号, 如后图如后图(a), 存在可增广链存在可增广链vs v2 v5 v1 v4 vt, 进入调整过程。进入调整过程。 (5)以以t=2为调整量为调整量, 从从vt点开始逆着可增广链方向给每个边点开始逆着可增广链方向给每个边调整流量调整流量,其中其中: f4t=2+2=4;
47、f14=2+2=4;f15=3-2=1(后向边后向边); f25=0+2=2; fs2=2+2=4。调整结束。调整结束,如图如图(b)。 (6)去掉所有标号去掉所有标号, 回到步骤回到步骤1重新标号。当给重新标号。当给v3标标(+vs,1)后后, 其他点无法再标号其他点无法再标号,算法结束。算法结束。此时，最大流此时，最大流 W=fs1+fs2+fs3=5+4+2=11网络的一个最小割网络的一个最小割E=(vs,v1),(vs,v2),(v3,v6)的容量的容量C(E)= 5+4+2=11, 恰好等于最大流。恰好等于最大流。vsvtv1v2v3v4v5v6(5,5)(3,2)(4,2)(5,2)(3,3)(3,0)(2,2)(2,2)(4,2)(3,3)(5,4)(a)(,+ )(+vs,1)(+vs,2)(+v2,2)(-v5,2)(+v1,2)(+v4,2)vsvtv1v2v3v4v5v6(5,5)(3,2)(4,4)(5,4)(3,1)(3,2)(2,2)(2,2)(4,4)(3,3)(5,4)(b)(+vs,1)(,+ )
