运筹学第八章图与网络分析ppt课件

运筹学,赵明霞 山西大学经济与管理学院,1,第八章 图与网络分析,图与网络的基本概念 树 最短路问题 最大流问题 最小费用最大流问题,2,柯尼斯堡七桥问题,欧拉回路：经过每边且仅一次 厄尼斯堡七桥问题、邮路问题 哈密尔顿回路：经过每点且仅一次 货郎担问题、快递送货问题,3,第一节 图与网络的基本概念,图是由点和边构成，可以反映一些对象之间的关系。 例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图8.1就是一个表示这种关系的图。,4,描述对象之间关系， 研究特定关系之间的内在规律， 图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。,5,如果我们把上面例子中的“相互认识”关系改为“认识” 的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。,6,无向图：由点和边构成的图，记作G =（V，E）。 有向图：由点和弧构成的图，记作D =（V，A）。 无向图是有向图的基础图G(D) 有限图 无限图,7,G=(V,E) 关联边(m)：ei 端（顶）点(n)：vi, vj 点相邻(同一条边)： v1, v3 边相邻(同一个端点)：e2, e3 环：e1 多重边： e4, e5,8,简单图：无环无多重边 多重图：多重边,完全图：每一对顶点间都有边（弧）相连的简单图,9,次（d）：结点的关联边数目 d(v3)=4，偶点 d(v2)=3，奇点 d(v1)=4 d(v4)=1，悬挂点 e6, 悬挂边 d(v5)=0，孤立点,出次：d+(vi) 入次：d-(vi) d (vi) = d+(vi) + d-(vi),定理1 顶点次数总和等于边数的两倍。 定理2 次为奇数的顶点必为偶数个。,10,若 ,则G是G的子图，G是G的母图 若 ,则G是G的真子图， 若 ,则G是G的支撑（生成）图。,11,链：点边交替序列 闭链：v1 v2 v3 v4 v1 开链：v1 v2 v3 边不同，简单链：v3 v4 v5v1v6v5 边不同且结点不同，初等链：v1 v2 v3 v4 v5v6 圈：闭链，且至少有3个不同结点，v2 v3 v4 v2 初等圈：初等闭链，v1 v2 v3 v4 v1,12,路：有向图：弧的方向与链的方向一致 开路:v1v2v4v5 回路：第一个点和最后一个点相同。v1v2v4v5v1,13,连通图：若任何两个不同的点之间，至少存在一条链，则G为连通图。 赋权图：对一个图的每一条边（弧）(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。 网络：赋权连通图 无向图：开链即开路，闭链即回路 有向图：弧的方向与链的方向一致。,14,柯尼斯堡七桥问题,欧拉回路：经过每边且仅一次 厄尼斯堡七桥问题、邮路问题 充要条件：无向图中无奇点，有向图每个顶点出次等于入次,15,16,第二节 树,树是图论中的重要概念，所谓树就是一个无圈的连通图。,图8-4中，(a)就是一个树，而(b)因为图中有圈所以就不是树， (c)因为不连通所以也不是树。,16,树的基本性质 任意两点间有且仅有一条链 不相邻两点间添加一条边，有且仅有一个圈 任意去掉一条边，得不连通图. 存在悬挂点 m=n-1,17,18,生成（支撑）树,若 ,则G是G的支撑（生成）树。,18,19,1、破圈算法 步骤： （1）在给定的赋权的连通图上任找一个圈。 （2）在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。 （3）如果所余下的图已不包含圈，则计算结束，所余下的图即为最小树，否则返回第1步。,最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。,19,20,例8.1,20,2、避圈算法 步骤： （1）任找一个点S，其余各点就是 。 （2）在连接S与 的所有边中，选择权数最小的边(i, k)； （3）将最小边(i, k)的另一个端点移入S； （4）若 则停止，否则返回（2）。,21,22,例8.1,22,有向树：不考虑方向时是树 根树（外向树）：只有一个顶点入次为0，其余顶点入次为1 根：入次为0的顶点 叶：出次为0的顶点 分支点 层次：根到顶点的长度,23,m叉树：每个顶点的出次小于等于m 完全m叉树：每个顶点的出次等于m或0,24,霍夫曼树：最优二叉树,25,第三节 最短路问题,最短路问题： 对一个赋权的有向图D中的指定的两个点Vs(起点)和Vt（终点）找到一条从 Vs 到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。,26,适用于：每条弧（边）的赋权数wij 0 优点：能够求出某点至各点的最短路 基本思想： T(j) （tentative label）从始点s到j点的最短路长上界，称为试探性标号; P(j) （permanent label）从始点s到j点的最短路长，称为永久性标号.,一、狄氏标号法（Dijkstra算法）,27,例8-9,基本步骤 标号T(j)P(j),28,29,最长路问题 例8-10（7-9）设某台新设备的年效益及年均维修费、更新净费用如表。试确定今后5年内的更新策略，使总收益最大。,30,31,网络中心（r点）,例8-11 某连锁企业有6个销售点，问仓库应建在哪个地点，可使各销售点离仓库较近？,32,33,各点间的最短距离,二、Floyd算法,34,例8-12 求任意两点间的最短路,35,36,37,38,容量网络(网络)：N=(V, A, c) 或 N=(V, A)，最大流量cij = c(i,j) 网络流： 可行流：s发点，t收点 可行流流量：,第四节 最大流问题,39,割(截)集： S中各点联通，S 中各点联通 始点在S，终点在S 的集合，称为一个分离发点s和收点t的割集，（S,S） 割集容量： 最小割：最小的割集容量,40,定理8-10：网络任一可行流的流量恒不超过任一割集的容量。 定理8-11：最大流 = 最小割,41,增广（容）链： 为从发点s到收点t的一条链，且前向弧均非饱和，后向弧均非零流。 最大流：流量最大的可行流。 可行流为最大流的充要条件：不存在从s到t的增广链,42,（一）线性(整数)规划法,43,例8-13,44,（二）网络分析法 增广链调整法,45,FordFulkerson标号法 基本思想：先确定一个初始可行流，再找增容链，调整流量，直到找不到增容链为止。双标号（i, b(j)），b(j)当前最大可调容量 运算步骤： 发点s标号（0, ）； 给所有相邻点标号 正向弧且 ，则 j 标号（i, b(j)） ，则 j 不标号 逆向弧且 ，则 j 标号（-i, b(j)） 检查标号 调整量,46,例8-13,（1）计算机编程,47,（2）手算,f*=11,48,49,50,最小费用最大流问题：给了一个带收发点的网络N=(V,A,c,d)，对每一条弧（i，j），除了给出容量cij外，还给出了这条弧的单位流量的费用dij，要求一个最大流f，并使得总运送费用最小。,先求出此网络图中的最大流量f。 在最大流量f的所有解中，找出一个最小费用的解,（一）线性(整数)规划法,第五节 最小费用最大流问题,51,例8-15,第一步,第二步,52,对偶网络法：N=(V,A)，N=(V,A,w) xij = 0, 0 xij cij, xij = cij，,（二）网络分析法,53,定理8-7：对偶网络中的最短路必是原网络的最小费用增容链。 定理8-8：在流量为f的最小费用流上，按最小费用增容链调整流量后，仍为新流量上的最小费用流。 基本思想：找出对偶网络的最短路，沿此路调整流量，直到最大流量。 运算步骤,54,55,作 业,8.1 8.6 8.8 8.10 8.17,56,