图与网络分析(1-5)

《图与网络分析(1-5)》由会员分享，可在线阅读，更多相关《图与网络分析(1-5)（136页珍藏版）》请在金锄头文库上搜索。

1、图与网络分析 Graph Lsr+drp，则对p点 标号，并将Lsp的值标注在p点旁的小方框内；w 重复第3步，一直到t点得到标号为止。58Dijkstra算法举例w 例3 求下图中从v1到v7的最短路 图 6-10 59解题-1w （1）从点v1出发，对v1标号，将L11=0标 注在v1旁的小方框内。令 ，其余点 属于 。V60(2)同v1相邻的未标 号点有v2、v3。 L1r=mind12,d13 =min5,2=2=L13,即对点v3标号 ，将L13的值标注 在v3旁的小方框 内。将v1,v3加 粗，并令 解题-2，61w (3)同标号点v1、 v3相邻的点有v2 、v4、v6，故有w

2、对v2点标号，将 L12的值标注在v2 点旁的小方框内 ，将v1,v2加粗 ，并令， 解题-3，(c) 62解题-4w (4)同标号点v1、 v2、v3相邻的点 有v5、v4、v6， 有w 故对点v6标号， 将L16的值标注 在v6点旁的小方 框内，将v3, v6 加粗，并令， 63解题-5w (5)同标号点v1、v2 、v3、v6相邻的点 有v4、v5、v7，有w 故对点v4和v5同时 标号，将L14=L15=7 的值分别标注在v4 和v5点旁的小方框 内，将v2,v4及 v6,v5加粗，并令 ， ，64解题-6 w 同各标号点相邻的 未标号点只有v7，因 有w 故在点v7旁小方框内 标注L

3、17=10，加粗 v6,v7 。图(f)中的粗 线表明从点v1到网络 中其它各点的最短 路，各点旁方框中 的数字是从v1点到各 点的最短距离。 1065矩阵算法 w Dijkstra算法提供了从网络图中某一点到 其它点的最短距离。 w 但实际问题中往往要求网络任意两点之 间的最短距离，如果仍采用Dijkstra算法 对各点分别计算，就显得很麻烦。 w 求网络各点间最短距离矩阵计算法 。66矩阵算法举例w 在图6-10中用矩阵计算法求各点之间的 最短距离 图 6-1067解题-1w 定义dij为图中两 相邻点的距离， 令=68解题-2 w 上面矩阵表明从i点到j点的直接最短距离。 但从i到j的最

4、短路不一定是ij，可能是 ilj，ilkj，或ilkj。 w 先考虑i与j之间有一个中间点的情况，如图6 -10中v1v2的最短距离应为 mind11+d12,d12+d22,d13+d32,d14+d42,d15+d52,d16+d62,d17+d72，也即mind1r+dr2。69解题-3w 为此可以构造一 个新的矩阵D(1)， 令D(1)中每个元素w 则矩阵D(1)给出了 网络中任意两点 之间直接到达和 包括经一个中间 点时的最短距离 70解题-4再构造矩阵D(2)。令则D(2)给出网络中任意 两点之间直接到达， 及包括经过一至三个 中间点时的最短距离 。71解题-5再构造矩阵D(3)。

5、令则D(3)给出网络中任意 两点之间直接到达，及 包括经过一至四个中间 点时的最短距离。计算可得：D(2)= D(3)D(3)各个元素值即为各点 间最短距离 72w 一般地有 w 矩阵D(k)给出网络中任意两点之间直接到 达，经过一个、两个到（2k-1）个中 间点到达时比较得到的最短距离。 w 设网络图有p个点，则一般计算到不超过 D(k)，k的值按式 计算 w 即w 如果计算中出现D(m+1)=D(m)时，计算即可 结束，矩阵中D(m)的各个元素值即为各点 间最短距离。 w 本例中， w 所以最多计算到D(3)，73例5w 假定图6-10中v1、v2、v3、v4、v5、v6、v7 为七个村子

6、，决定要联合办一所小学。 w 已知各村的小学生人数分别为v1 -30， v2 -40， v3 -25， v4 -20， v5 -50， v6 -60， v7 -60，w 则小学应建在哪一个村子，使小学生上 学走的总路程为最短？74解题w 将上例中计算得到的D（3）的第一行乘v1村的 小学生人数，则乘积数字为假定小学建于各 个村时， v1村小学生上学单程所走路程。 w 将D（3）第二行数字乘v2村小学生人数，得小 学建于各个村子时， v2村小学生上学所走路 程。 w 依此类推可计算得到下表。75v1v2v3v4v5v6v7 015060210210180300 20002808020016032

7、0 501750150125100200 1404012006040120 350250250150050150 360240240120600240 6004804803601802400 17001335143010708357701330决策方案：小学应建在v6村 小学建于vi村时，7个 村子的学生累计的一 次单程上学路程。76应用举例设备更新问题w 某企业使用一台设备，在每年年初，企 业领导部门需要决定 w 是购置新的还是继续使用旧的； w 若购置新设备需支付一定的购置费用， 若继续使用旧的，须支付一定的维修费 用。 w 问题是：如何制定一个五年之内的设备 更新计划，使得总的支出费用最

8、少。77设备在各年年初的购置费用（千元/台）年份12345费用1111121213使用不同年限的设备需要的维护费 用（千元/年）使用年限0-11-22-33-44-5维护费 用568111878用点vi表示“第i年年初 购进一台设备”； 用弧（vi，vj）表示在 第i年年初购进的设备 一直使用到第j年年初 。 则问题成为最短路径 问题。v1v6v5v4v3v2设备 在各年年初的购置费用年份12345费用1111121213使用不同年限的设备 需要的维护费 用使用年限0-11- 22-33-44-5维护费 用568111816161717182230415922304123312379第四节 网

9、络的最大流80各种流量问题 w公路系统中的车流：最大车流量问 题； w控制系统中的信息流：最大信息流 量问题（如电话传呼）； w供水系统中的水流：最大水流量问 题； w金融系统中的现金流； w财务系统中的资金流等等。81主要内容w有关概念 w割和流量 w最大流最小割定理 w求网络最大流的标号算法 w应用举例824.1 网络最大流的有关基本概念w有向图与容量网络 w流与可行流 83有向图与弧w有向图：网络图中两点之间的连线 有规定方向 w弧：有向图上有规定指向的连线。 w弧的代号：(vi，vj)表明方向是从vi 点指向vj点。 w有向图是点与弧的集合，记作D(V ，A) 8485弧的容量w弧的容

10、量：网络的组成弧所具有的 通过能力，也称为硬件能力 w弧的容量记为：c(vi,vj)或简写为cij。 w如c13 =9， c23 =286流、弧流量w流/弧流量：是指实际通过网络各条弧 上的流量/负载量，或软件能力。 w对加在弧（vi,vj）上的负载量记作 f(vi,vj)，或简写为fij， w如f13=4， f23 =0（ c13 =9， c23 =2 ）。 w若网络上所有的fij=0，这个流称为零 流。 87容量网络w 对网络流的研究是在容量网络上进行的。 w容量网络是指对网络上的每条弧(vi ，vj)都给出一个最大的通过能力 w或标有弧容量cij的网络。88容量网络的发点、收点与 中间点

11、w在容量网络中通常规定一个发点(也 称源点，记为s)和一个收点(也称汇点 ，记为t)，w网络中既非发点又非收点的点称为中 间点89网络流w网络流：容量网络中，实际流过各 弧的流量集F=fij90可行流 及其满足条件（1）w在容量网络上满足容量限制条件和 中间点平衡条件的一组流为可行流 w容量限制条件：对所有弧有 w 91可行流 及其满足条件（2） w中间点平衡条件： w每个节点的流入总量=流出总量w 如：s：Q=fs1+fs2; v1:fs1=f13+f12; v3:f13+f43=f32+f3t; v4:f24=f43+f4tw 零流是可行流； w 任何网络上一定w 存在可行流 92w 若以

12、v(f)表示网络中从st的流量， 则有w网络最大流：使得从网络发点到收点 的总容量达到最大的可行流。网络流量93网络的最大流w网络的最大流是指网络中从发点到 收点之间允许通过的最大流量。 w对有多个发点和多个收点的网络， 可以另外虚设一个总发点和一个总 收点，并将其分别与各发点、收点 连起来(见图6-15)，就可以转换为 只含一个发点和一个收点的网络 图 6-1594求网络的最大流w求网络的最大流，是指满足容量限 制条件和中间点平衡的条件下，使 v(f)值达到最大。w 显然这是一个线性规划问题。但由于网络的特殊性， 我们可以寻求比单纯形法要简单得多的方法来求解。 增广链、最小割 95前向弧、后

13、向弧 w给出网络cij,fij w前向弧/正向弧：网络中所有指向 为st的弧，记作+； w后向弧/反向弧：网络中所有指向 为ts的弧，记作-。 96增广链 w一条从网络的发点到网络的收点的 链，在这条链上所有指向为st的 弧（前向弧存在f0。w或一条从网络的发点到网络的收点 的链，且所有前向弧都为非饱和弧 ，所有后向弧都为非零弧。973(3)5(1)1(1)4(3)1(1)2(2)3(0)5(3)2(1)找出网络图中的增广链（前向 弧为非饱和弧，后向弧为非零 弧）98w增广链存在时，定义w显然f 仍是一个可行流，但较之原 来的可行流 f，这时网络中从st的 流量增大了一个值（0）。 w因此只有

14、当网络图中找不到增广链 时，st 的流才不可能进一步增大 。 99增广链的作用w 前向非饱和弧允许增大流量，后向非零 弧允许减小流量以维持节点平衡（流入= 流出），在增广链上存在增大输送能力 的潜力，即沿增广链可以增大流量。 w 增广链作用：判断网络可行流是否为网 络最大流。1004.2 割和流量101割 w割是指将容量网络中的发点和收点 分割开，并使st的流中断的一组弧 的集合。 w如下图中，KK将网络上的点分割成 V和 两个集合，并有 ， ，称 弧的集合 是一个 割。在组成上述割的弧集合 中不包括（v3,v2），因 为即使这条弧不割断， 从st的流仍然中断 102割的意义 w 一个容量网络

15、，由于各弧容量cij配置得不 恰当，会出现下列后果： w 有的地方能通过较大流量，而有的地方能 通过的流量却很小。 w 根据木桶原理，小流量的地方限制了网络 最大流的上限，成为网络的瓶颈（俗称“ 卡脖子”的地方）。 w 因此，研究从发点到收点的流径中，那些 弧的容量起了限制最大流的作用，具有实 际的意义。 w “割”是研究网络流”瓶颈”的有效工具。103割的容量w割的容量：是组成它的集合中的各 弧的容量之和，用c(V, )表示。 104网络图的全部 割 V割容量 s s, v1 s, v2 s, v1, v2 s, v1, v3 s, v2, v4 s, v1, v2, v3 s, v1, v

16、2, v4 s, v1, v2, v3, v4v1, v2, v3, v4, t v2, v3, v4, t v1, v3, v4, t v3, v4, t v2, v4, t v1, v3, t v4, t v3, t t(s, 1) (s, 2) (s, 2) (1, 2) (1, 3) (s, 1) (2, 4) (1, 3) (2, 4) (s, 2) (1, 3) (3, 2) (3, t) (s, 1) (4, 3) (4, t) (2, 4) (3, t) (1, 3) (4, 3) (4, t) (3, t) (4, t)15 21 17 18 19 24 14 25 15 1051061