《[互联网]12997171025437500011图与网络.ppt》由会员分享，可在线阅读，更多相关《[互联网]12997171025437500011图与网络.ppt（72页珍藏版）》请在三一办公上搜索。
1、Chapter 11：图与网络模型,图与网络模型,11.1 图与网络的基本概念11.2最短路问题11.3 最小生成树问题11.4 最大流问题11.5 最小费用最大流问题,11.1 图与网络的基本概念,图论：图是由点和边构成，可以反映一些对象之间的关系,图G区别于几何学中的图。这里只关心图中有多少个点、以及哪些点之间有连线。,例如：在一个人群中，对相互认识这个关系我们可以用图来表示,一般情况下，图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。,11.1 图与网络的基本概念,图论：图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与
2、点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。,图的定义：若用点表示研究的对象，用边表示这些对象之间的联系，则图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 具有公共的端点，称
3、边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 图与网络的基本概念,图中某些点和边的交替序列，若其中各边
4、互不相同，且对任意vt-1和vt均相邻，称为链。用表示：,起点与终点重合的链称作圈（回路）如果任意两个顶点之间至少存在一条链，称这样的图为连通图,11.1 图与网络的基本概念,链，圈（回路），连通图,如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的连线就很难刻画他们之间的关系了，这时我们引入一个带箭头的连线，称为弧。相互认识用两条反向的弧表示。,11.1 图与网络的基本概念,有向图的定义：图D被定义为“点”和“弧”的集合，记作：其中:V点集；A弧集,无向图 G(V,E)，对G的每一条 边(vi,vj)相应赋予数量指标wij，称wij为边(vi,vj)上的权，称图G为
5、赋权图赋权的有向图 D=(V,A)，指定一点为 发点（vs），指定另一点为 收点（vt），称其它点为中间点，并把 D 中每一条弧的 赋权数 cij 称为弧(vi,vj)的容量，这样的赋权有向图D就称为网络,赋权图，网络,11.1 图与网络的基本概念,权可以代表距离、费用、通过能力(容量)等等,11.2 最短路问题,有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。,最短路问题,对一个赋权的图（G或D）中的指定的两个点 Vs 和 Vt 找到一条从 Vs 到 Vt 的路，使得这条路上所有 弧（边）的权
6、数的总和最小，这条路被称之为从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 双标号法 的步骤：,
7、如果上述的弧(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到该点的最短路线及最短距离
8、，因此可以将每个点标号，求出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
9、.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.电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路
10、的长度（单位：公里）。,11.2 最短路问题,解：这是一个求无向图的最短路的问题。,11.2 最短路问题,(0,s),(10,1),(13,3),(14,3),(16,5),(18,5),(22,6),甲地到乙地的最短路为：,例5.设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表,11.2 最短路问题,设备维修费如下表,解：将问
11、题转化为最短路问题，如下图：用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：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。,树
12、：无圈的连通图即为树,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
13、最小生成树问题,避圈法,最小生成树问题：在一个赋权的、连通的、无向图 G 中找出一个生成树，并使得这个生成树的所有边的权数之和为最小,11.3 最小生成树问题,图的最小生成树（支撑树）,1.在给定的赋权的连通图上任找一个圈2.在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。,求解最小生成树的破圈算法,破圈法：任取一圈，去掉圈中最长边，直到无圈。,v3,边数n-1=5,11.3 最小生成树问题,图的最小生成树（支撑树）,6,Min C(T)=15,11.3 最小生
14、成树问题,图的最小生成树（支撑树）,练习：应用破圈法求最小树,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.某大学准备对
15、其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,v7 表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。,11.3 最小生成树问题,此问题实际上是求图11-14的最小生成树，这在例6中已经求得，即按照图(f)的设计，可使此网络的总的线路长度为最短，为19百米。,v5,11.4 最大流问题,最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。,一、最大流的数学模型 例8.某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由
16、于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地 v1向销地 v7运送石油，问每小时能运送多少加仑石油？,v5,11.4 最大流问题,我们可以为此例题建立线性规划数学模型：设弧(vi,vj)上流量为fij，网络上的总的流量为F，则有：,一、最大流的数学模型,11.4 最大流问题,1、在这个线性规划模型中，其约束条件中的前6个方程表示了网络中的流量必须满足守恒条件：发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。2、对每一条弧(vi,vj)的流量fij要满足流量的可行条件，
17、应小于等于弧(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)和(
18、d)的意义相同。,11.4 最大流问题,11.4 最大流问题,二、最大流问题的网络图论解法用以上方法对例8的图的容量标号作改进，得下图：,（1）找出一条从发点到收点的路，在这条路上的每一条弧 顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。（2）找出这条路上各条弧的 最小的顺流的容量pf，从而通过这条路增加网络的流量pf。（3）在这条路上，减少每一条弧的顺流容量pf，同时增加这些弧的逆流容量pf，返回步骤（1）。*为了使算法更快捷有效，我们一般在步骤（1）中尽量选择包含弧数最少的路。,11.4 最大流问题,二、最大流问题的网络图论解法基本算法步骤：,第一次迭代：选择路为 v1 v
19、4 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,
20、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,v
21、7,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 最大流问题,二、最大流问题的网络图论解法,经过第五次迭代后在图中已
22、经找不到从发点到收点的一条路路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为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
23、,vj）除了有不同的流量限制cij外，还有不同的单位流量的费用bij，cij的单位为万加仑/小时，bij的单位为百元/万加仑。如下图所示。从采地 v1 向销地 v7 运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量的最小费用。,11.5 最小费用最大流问题,一、最小费用最大流的数学模型,11.5 最小费用最大流问题,一、最小费用最大流的数学模型 一般来说，所谓最小费用流的问题就是：在给定了收点和发点并对每条弧(vi,vj)赋权以容量cij及单位费用bij的网络中，求一个给定流量 f 的最小费用，这个给定流量 f 应小于等于最大流量F，否则无解。求最小费用流的问题的线性规
24、划的模型只要把最小费用最大流模型中的约束条件中的发点流量F改为f即可。,11.5 最小费用最大流问题,二、最小费用最大流问题的网络图论解法 对网络上弧（vi,vj）的（cij,bij）的表示作如下改动,11.5 最小费用最大流问题,11.5 最小费用最大流问题,二、最小费用最大流问题的网络图论解法用以上方法对例9的图形进行改进，得下图：,11.5 最小费用最大流问题,二、最小费用最大流问题的网络图论解法最小费用最大流的基本算法：在对弧的标号作了改进的网络图上求最小费用最大流的基本算法，与求最大流的基本算法完全一样，不同的只是：*在步骤（1）中要选择一条总的单位费用最小的路，而不是包含边数最小的
25、路。,用上述方法对例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 最小费用最大流问题,二、最小费用最大流问题的网络图论解法,第
26、四次迭代：找到最短路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,
