[互联网]12997171025437500011图与网络.ppt

Chapter 11：图与网络模型,图与网络模型,11.1 图与网络的基本概念11.2最短路问题11.3 最小生成树问题11.4 最大流问题11.5 最小费用最大流问题,11.1 图与网络的基本概念,图论：图是由点和边构成，可以反映一些对象之间的关系,图G区别于几何学中的图。这里只关心图中有多少个点、以及哪些点之间有连线。,例如：在一个人群中，对相互认识这个关系我们可以用图来表示,一般情况下，图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。,11.1 图与网络的基本概念,图论：图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。,图的定义：若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为“点”和“边”的集合，记作：,其中:V点集 E边集,图G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。,无向图,定义:图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=v1,v1;e2=v1,v2;,端点，关联边，相邻,若有边e可表示为 e=vi,vj，称vi和vj是 边 e 的端点，反之称 边e 为 点vi或vj的关联边。若 点vi、vj 与同一条边关联，称 点vi和vj 相邻；若 边ei和ej 具有公共的端点，称 边ei和ej 相邻。,11.1 图与网络的基本概念,如果 边e 的两个端点相重，称该边为 环如右图中边e1为环如果两个点之间多于一条边，称为多重边，如右图中的e4和e5对无环、无多重边的图称作简单图,环，多重边，简单图,11.1 图与网络的基本概念,与某一个 点vi 相关联的 边的数目 称为 点vi的次（也叫做度），记作d(vi)右图中d(v1)4，d(v3)=5，d(v5)=1次为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。,图的次:一个图的次等于各点的次之和。,次，奇点，偶点，孤立点,11.1 图与网络的基本概念,图中某些点和边的交替序列，若其中各边互不相同，且对任意vt-1和vt均相邻，称为链。用表示：,起点与终点重合的链称作圈（回路）如果任意两个顶点之间至少存在一条链，称这样的图为连通图,11.1 图与网络的基本概念,链，圈（回路），连通图,如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的连线就很难刻画他们之间的关系了，这时我们引入一个带箭头的连线，称为弧。相互认识用两条反向的弧表示。,11.1 图与网络的基本概念,有向图的定义：图D被定义为“点”和“弧”的集合，记作：其中:V点集；A弧集,无向图 G(V,E)，对G的每一条 边(vi,vj)相应赋予数量指标wij，称wij为边(vi,vj)上的权，称图G为赋权图赋权的有向图 D=(V,A)，指定一点为 发点（vs），指定另一点为 收点（vt），称其它点为中间点，并把 D 中每一条弧的 赋权数 cij 称为弧(vi,vj)的容量，这样的赋权有向图D就称为网络,赋权图，网络,11.1 图与网络的基本概念,权可以代表距离、费用、通过能力(容量)等等,11.2 最短路问题,有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。,最短路问题,对一个赋权的图（G或D）中的指定的两个点 Vs 和 Vt 找到一条从 Vs 到 Vt 的路，使得这条路上所有 弧（边）的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。,从给定的网络图中找出一点到各点 或任意两点之间距离最短的一条路,Dijkstra 算法(双标号法）,1.给出 点Vs 以标号(0,s)2.找出已标号的点的集合 I，没标号的点的集合 J，以及弧的集合 3.如果 B是空集，则计算结束。如果Vt已标号(Lt,Kt)，则 Vs到Vt的距离为Lt，而从 Vs到Vt的最短路径，则可以从Vt 反向追踪到起点Vs（根据 Kt 的记录）而得到。如果Vt 未标号，则可以断言不存在从 Vs到Vt的路。,11.2 最短路问题,Dijkstra 双标号法 的步骤：,如果上述的弧(B)的集合不是空集，则转下一步。4.对B中的每一条弧，计算 Sij=Li+Cij。在所有的 Sij中，找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（Scd,c），返回步骤2。,11.2 最短路问题,Dijkstra 双标号法 的步骤：,例1.求下图中v1到v6的最短路,11.2 最短路问题,Dijkstra 双标号法：,（0，s）,0+3,0+2,0+5,（2，1）,2+1,（3，1）,(3,3),3+7,3+5,(8,4),v1到v6的最短距离为8；最短路为：v1 v3 v4 v6,从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj。,注：无向图最短路的求法只将上述步骤中的弧改成边即可。,11.2 最短路问题,例3.求下图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 到该点的最短距离，最短路线就是红色的链。,11.2 最短路问题,课堂练习：1.用Dijkstra算法求下图从v1到v6的最短距离及路线。,v3,v5,4,v1到v6的最短路为：,11.2 最短路问题,2.求从v1到v8的最短路径,11.2 最短路问题,v1到v8的最短路径为v1v4v7v5v8，最短距离为10,11.2 最短路问题,3.求下图中v1点到另外任意一点的最短路径,v1,v2,v3,v4,v6,v5,3,2,2,7,6,2,1,3,3,11.2 最短路问题,v1,V2,V3,V4,V6,V5,3,2,2,7,6,2,1,3,3,0,2,4,7,1,4,11.2 最短路问题,v1,V2,V3,V4,V6,V5,3,2,2,7,6,2,1,3,3,0,2,4,7,1,4,11.2 最短路问题,例4.电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。,11.2 最短路问题,解：这是一个求无向图的最短路的问题。,11.2 最短路问题,(0,s),(10,1),(13,3),(14,3),(16,5),(18,5),(22,6),甲地到乙地的最短路为：,例5.设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表,11.2 最短路问题,设备维修费如下表,解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。,11.2 最短路问题,把所有弧的权数计算如下表，把权数赋到图中，再用Dijkstra算法求最短路。,11.2 最短路问题,最终得到下图，可知，v1到v6的距离是53，最短路径有两条：v1v3v6和 v1v4v6,11.2 最短路问题,性质1：任何树中必存在次为1的点。性质2：n 个顶点的树必有n-1 条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。,树：无圈的连通图即为树,11.3 最小生成树问题,11.3 最小生成树问题,下列图中，哪些是树？,图G1=V1、E1和图G2=V2，E2，如果有，称G1是G2的一个子图若有，则称G1是G2的一个支撑子图,(a),（G图）,子图，支撑子图,11.3 最小生成树问题,如果G2是G1的支撑图（生成图），又是树图，则称G2是G1的生成树（或支撑树）。,G1,G2,11.3 最小生成树问题,图的生成树（支撑树）,破圈法,11.3 最小生成树问题,求支撑树的方法：破圈法 和 避圈法,生成树（支撑树）,求支撑树的方法：破圈法 和 避圈法,11.3 最小生成树问题,求支撑树的方法：破圈法 和 避圈法,11.3 最小生成树问题,避圈法,最小生成树问题：在一个赋权的、连通的、无向图 G 中找出一个生成树，并使得这个生成树的所有边的权数之和为最小,11.3 最小生成树问题,图的最小生成树（支撑树）,1.在给定的赋权的连通图上任找一个圈2.在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。,求解最小生成树的破圈算法,破圈法：任取一圈，去掉圈中最长边，直到无圈。,v3,边数n-1=5,11.3 最小生成树问题,图的最小生成树（支撑树）,6,Min C(T)=15,11.3 最小生成树问题,图的最小生成树（支撑树）,练习：应用破圈法求最小树,11.3 最小生成树问题,v1,v7,v4,v3,v2,v5,v6,9,3,17,4,1,23,min=1+4+9+3+17+23=57,11.3 最小生成树问题,课堂练习：,Min C(T)=12,Min C(T)=15,答案：,11.3 最小生成树问题,3,4,1,2,2,3,2,3,2,4,2,Min C(T)=12,2,1,3,6,3,8,5,3,4,5,6,7,4,5,4,3,2,1,Min C(T)=18,11.3 最小生成树问题,例6.用破圈算法求图（a）中的一个最小生成树,11.3 最小生成树问题,例7.某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,v7 表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。,11.3 最小生成树问题,此问题实际上是求图11-14的最小生成树，这在例6中已经求得，即按照图(f)的设计，可使此网络的总的线路长度为最短，为19百米。,v5,11.4 最大流问题,最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。,一、最大流的数学模型 例8.某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地 v1向销地 v7运送石油，问每小时能运送多少加仑石油？,v5,11.4 最大流问题,我们可以为此例题建立线性规划数学模型：设弧(vi,vj)上流量为fij，网络上的总的流量为F，则有：,一、最大流的数学模型,11.4 最大流问题,1、在这个线性规划模型中，其约束条件中的前6个方程表示了网络中的流量必须满足守恒条件：发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。2、对每一条弧(vi,vj)的流量fij要满足流量的可行条件，应小于等于弧(vi,vj)的容量cij，并大于等于零，即0fij cij。我们把满足守恒条件及流量可行条件的一组网络流 fij 称之为可行流，（即线性规划的可行解），可行流中一组流量最大（也即发出点总流出量最大）的称之为最大流（即线性规划的最优解）。,11.4 最大流问题,一、最大流的数学模型,二、最大流问题的网络图论解法 对网络上弧的容量的表示作改进。对一条弧（vi,vj)的容量我们用一对数cij,0标在弧（vi,vj)上，cij靠近vi点，0靠近vj点，表示从vi到vj容许通过的容量为cij，而从vj到vi 容许通过的容量为0，这样我们可以省去弧的方向了。如下图:(a)和(b)、(c)和(d)的意义相同。,11.4 最大流问题,11.4 最大流问题,二、最大流问题的网络图论解法用以上方法对例8的图的容量标号作改进，得下图：,（1）找出一条从发点到收点的路，在这条路上的每一条弧 顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。（2）找出这条路上各条弧的 最小的顺流的容量pf，从而通过这条路增加网络的流量pf。（3）在这条路上，减少每一条弧的顺流容量pf，同时增加这些弧的逆流容量pf，返回步骤（1）。*为了使算法更快捷有效，我们一般在步骤（1）中尽量选择包含弧数最少的路。,11.4 最大流问题,二、最大流问题的网络图论解法基本算法步骤：,第一次迭代：选择路为 v1 v4 v7。弧（v4,v7）的顺流容量为2，决定了pf=2，改进的网络流量图如下图：,6,3,5,2,2,2,4,1,2,6,3,v1,v2,v5,v7,v4,v3,v6,0,0,0,0,0,0,0,0,0,0,0,4,2,0,2,2,第一次迭代后的总流量,2,11.4 最大流问题,二、最大流问题的网络图论解法用此方法对例8求解：,第二次迭代：选择路为v1 v2 v5 v7。弧（v2,v5）的顺流容量为3，决定了pf=3，改进的网络流量图如下图：,6,3,5,2,2,2,4,1,3,v1,v2,v5,v7,v4,v3,v6,0,0,0,0,0,0,0,0,4,2,0,2,2,0,3,3,3,0,3,5,5,第二次迭代后的总流量,11.4 最大流问题,二、最大流问题的网络图论解法,第三次迭代：选择路为v1 v4 v6 v7。弧（v4,v6）的顺流容量为1，决定了pf=1，改进的网络流量图如下图：,2,2,2,4,1,3,v1,v2,v5,v7,v4,v3,v6,0,0,0,0,0,0,4,2,0,2,2,0,3,3,3,3,3,0,1,3,1,6,6,第三次迭代后的总流量,11.4 最大流问题,二、最大流问题的网络图论解法,第四次迭代：选择路为v1 v4 v3 v6 v7。弧（v3,v6）的顺流容量为2，决定了pf=2，改进的网络流量图如下图：,2,2,2,3,3,v1,v2,v5,v7,v4,v3,v6,1,1,0,0,0,2,0,3,2,0,3,3,3,5,0,3,1,2,0,0,2,1,3,3,8,8,第四次迭代后的总流量,1,11.4 最大流问题,二、最大流问题的网络图论解法,第五次迭代：选择路为v1 v2 v3 v5 v7。弧（v2,v3）的顺流容量为2，决定了pf=2，改进的网络流量图如下图：,2,2,v1,v2,v5,v7,v4,v3,v6,1,0,1,2,0,2,0,3,3,3,5,0,1,2,0,2,1,3,3,1,5,0,0,2,0,2,0,5,10,第五次迭代后的总流量,10,11.4 最大流问题,二、最大流问题的网络图论解法,经过第五次迭代后在图中已经找不到从发点到收点的一条路路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为10。最大流量图如下图：,11.4 最大流问题,二、最大流问题的网络图论解法,11.5 最小费用最大流问题,一个带收发点的网络，对每一条弧（vi,vj），除了给出容量cij外，还给出了这条弧的单位流量的费用bij，要求一个最大流 F，并使得总运送费用最小,(6,6),(3,4),(5,7),(2,5),(2,4),（2,3）,(4,4),(1,3),(2,8),（3,2）,v1,v2,v5,v7,v4,v3,v6,(6,3),一、最小费用最大流的数学模型 例9.由于输油管道的长短不一，所以在例6中每段管道（vi,vj）除了有不同的流量限制cij外，还有不同的单位流量的费用bij，cij的单位为万加仑/小时，bij的单位为百元/万加仑。如下图所示。从采地 v1 向销地 v7 运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量的最小费用。,11.5 最小费用最大流问题,一、最小费用最大流的数学模型,11.5 最小费用最大流问题,一、最小费用最大流的数学模型 一般来说，所谓最小费用流的问题就是：在给定了收点和发点并对每条弧(vi,vj)赋权以容量cij及单位费用bij的网络中，求一个给定流量 f 的最小费用，这个给定流量 f 应小于等于最大流量F，否则无解。求最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量F改为f即可。,11.5 最小费用最大流问题,二、最小费用最大流问题的网络图论解法 对网络上弧（vi,vj）的（cij,bij）的表示作如下改动,11.5 最小费用最大流问题,11.5 最小费用最大流问题,二、最小费用最大流问题的网络图论解法用以上方法对例9的图形进行改进，得下图：,11.5 最小费用最大流问题,二、最小费用最大流问题的网络图论解法最小费用最大流的基本算法：在对弧的标号作了改进的网络图上求最小费用最大流的基本算法，与求最大流的基本算法完全一样，不同的只是：*在步骤（1）中要选择一条总的单位费用最小的路，而不是包含边数最小的路。,用上述方法对例9求解：第一次迭代：找到最短路v1 v4 v6 v7。第一次迭代后总流量为1，决定了pf=1,总费用为10。,v5,1,1,第一次迭代后的总流量,11.5 最小费用最大流问题,二、最小费用最大流问题的网络图论解法,第二次迭代：找到最短路v1 v4 v7。第二次迭代后总流量为3，总费用32。,3,3,第二次迭代后的总流量,11.5 最小费用最大流问题,二、最小费用最大流问题的网络图论解法,第三次迭代：找到最短路v1 v4 v3 v6 v7。第三次迭代后总流量为5，总费用56。,5,5,第三次迭代后的总流量,11.5 最小费用最大流问题,二、最小费用最大流问题的网络图论解法,第四次迭代：找到最短路v1 v4 v3 v5 v7。第四次迭代后总流量为6，总费用72。,6,6,第四次迭代后的总流量,11.5 最小费用最大流问题,二、最小费用最大流问题的网络图论解法,第五次迭代：找到最短路v1 v2 v5 v7。第五次迭代后总流量为9，总费用123。,9,9,第五次迭代后的总流量,11.5 最小费用最大流问题,二、最小费用最大流问题的网络图论解法,第六次迭代：找到最短路v1 v2 v3 v5 v7。第六次迭代后总流量为10，总费用145。已经找不到从v1到v7的每条弧容量都大于零的路了，故已求得最小费用最大流。,11.5 最小费用最大流问题,二、最小费用最大流问题的网络图论解法,如果对例7求一个最小费用流的问题：每小时运送6万加仑石油从v1到v7的最小费用是多少，或者每小时运送7万加仑呢？我们可以从第四次迭代及图11-32即可得到运送6万加仑最小费用72百元，其运送方式通过比较图11-28及图11-32即得图11-36所示。至于每小时运送7万加仑，我们可以在图11-36的基础上，再按第五次迭代所选的最短路运送1万加仑即得最小费用：72+1*17=89百元，其运送方式如图11-35所示。,1,