《图与网络模型》PPT课件.ppt

图与网络模型,图与网络的基本概念,图与网络用来反映一些对象之间的关系 图论中，图与网络结构由下面两个元素构成 节点 边 例如：在一个人群中，对相互认识这个关系我们可以用图来表示，下图就是一个表示这种关系的图。,(v1) 赵,(v2)钱,(v3)孙,(v4)李,(v5) 周,(v6)吴,(v7)陈,e2,e1,e3,e4,e5,图与网络的基本概念,一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的 无向图：边是无向的 有向图：边是有向的 如：将上述例子中“相互认识”关系改为“认识” 如：family tree 一个图结构可记作G =（V，E） V为节点集合，E为边的集合,图与网络的基本概念,路：一个节点与边相互交错的序列（vi1, ei1, vi2, ei2, , vik-1, eik-1, vik ），其中， 对于无向图，eit的两个端点是vit-1和vit 对于有向图，eit的起点是vit-1，终点是vit 路的起点为vi1 ，路的终点为vik 圈：起点和终点是同一个节点的路 连通图：对于无向图而言，如果图中的任意两个节点都有一条路将之连接，则这个图称为连通图。,图与网络的基本概念,赋权图：对一个G的每一条边(vi, vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi, vj)上的权。 网络：在赋权的有向图G中指定一点，称为发点（vs），指定另一点称为收点（vt），其它点称为中间点，并把G中的每一条边的赋权数称为边的容量，G就称为网络。,最短路问题,对一个赋权的有向图G中的指定的两个点vs和vt找到一条从vs到vt的路，使得这条路上所有弧的权数的总和最小 这条路被称之为从vs到vt的最短路。这条路上所有弧的权数的总和被称为从vs到vt的距离。,Dijkstra算法,适用范围：适用于每条边上的赋权数为非负值的情况 Dijkstra算法也称为双标号法 双标号：图中的每一个节点vj都赋予两个标号（lj, kj），其中lj表示从起点vs到vj的最短路长度， kj表示在vs到vj的最短路上vj前一个节点的下标。,Dijkstra算法的基本步骤,给出点v1以标号(0, s) 找出已标号的点的集合I，没标号的点的集合J以及边的集合 查看vt是否已标号 如果vt已标号（lt, kt），则vs到vt的距离为lt，而从vs到vt的最短路径，则可以从kt反向追踪到起点vs 而得到。 如果vt未标号，则 如果上述边的集合是空集，则计算结束，可以断言不存在从 vs到vt的有向路。 如果上述的弧的集合不是空集，则转下一步 对上述边的集合中的每一条边，计算 sij=li+wij。在所有的sij中，找到其值为最小的边。不妨设此边为（vc, vd），则给此边的终点以双标号（scd , c）,返回步骤2。,最短路问题的例子,求下图中v1到v6的最短路,(0, s),3,5,2,(2, 1),3,(3, 1),(3, 3),10,8,(8, 4),采用Dijkstra算法，可解得最短路径为v1 v3 v4 v6,最短路问题的应用,电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。,最短路问题的应用,无向图可以表示成为有向图 无向图的最短路问题同样可以使用Dijkstra算法求解,15,10,(0, s),(10, 1),13,14,(13, 3),30,19,(14, 3),16,18,(16, 5),22,(18, 5),23,(22, 6),最短路问题的应用,设备更新问题：某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。设备每年年初的价格表和设备维修费如下。,最短路问题的应用,解：可以转化为最短路问题。 构造一个有向图，即图中的边皆为有向的。 用vi表示“第i年年初购进一台新设备”，边（vi, vj）表示第i年年初购进的设备一直使用到第j年年初。,最短路问题的应用,所有边上的权数表,最短路问题的应用,最终得到下图，可知，v1到v6的距离是53，最短路径有两条：v1 v3 v6和 v1 v4 v6,最小生成树问题,树：图论中的重要概念，即无圈的连通图。,(a)是一个树， (b) 和(c)不是树。 因为(b)图中有圈， (c)图不连通。,最小生成树问题,生成子图：给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得的图G，称之为G的生成子图 生成树：如果图G的一个生成子图还是一个树，则称这个生成子图为生成树,最小生成树问题,对于一个赋权的联通的无向图，下面的问题被称为最小生成树问题： 在这个赋权联通无向图中找到一个生成树，使得该生成树的所有边的权数之和最小 对于一个有n个节点，m条边的赋权联通无向图而言 其生成树中有n个节点，n-1条边 需要删去m-n+1条边,破圈算法,基本思想： 树结构不能存在圈，故将原图结构中的所有圈打破 打破圈的方式即消去圈中的一条边 一个圈可以在多处打破，故选择消去权数较大的边 步骤： 在给定的赋权的连通图上任找一个圈。 在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。 如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。,最小生成树问题,例：求出下图的最小生成树,v1,3,3,1,7,2,8,5,4,10,3,4,v7,v6,v5,v4,v2,v3,最小生成树的总权数为19,最小生成树问题的应用,某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,v7 表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。,最大流问题,最大流问题：给一个带收发点的网络，其每条边的赋权称之为容量，在不超过每条边的容量的前提下，求出从发点到收点的最大流量。 应用： 公路系统中的车辆流 控制系统中的信息流 供水系统中的水流 金融系统中的现金流,最大流问题的数学模型,某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi, vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地 v1向销地 v7运送石油，问每小时能运送多少加仑石油？,v5,最大流问题的数学模型,可以建立线性规划数学模型如下： 设边(vi, vj)上流量为fij，网络上的总的流量为F，则有：,最大流问题的图论解法,将有向图改成无向图，即任意两个节点之间只有一条边连接。,最大流问题的图论解法,找出一条从发点到收点的路，在这条路上的每一条边顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。 找出这条路上各条边的最小的顺流的容量pf，通过这条路增加网络的流量pf 。 在这条路上，减少每一条边的顺流容量pf，同时增加这些边的逆流容量pf ，返回步骤1。,最大流问题的图论解法,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,最大流问题的图论解法,得到最大流量为10，最大流量图如下：,最小费用最大流问题,最小费用最大流问题：给了一个带收发点的网络，对每一条边（vi, vj），除了给出容量cij外，还给出了这条弧的单位流量的费用bij，要求一个最大流F，并使得总运送费用最小。 主要目标：最大流 次要目标：最小费用 如反过来，即最小费用为主要目标，则只需不运送即可。,最小费用最大流问题,例：由于输油管道的长短不一，所以在上个例子中每段管道（ vi, vj ）除了有不同的流量限制cij外，还有不同的单位流量的费用bij，cij的单位为万加仑/小时，bij的单位为百元/万加仑。从采地 v1向销地 v7运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用。,(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),最小费用最大流问题的求解,可以用线性规划来求解此题 第一步，先求出此网络中的最大流量F：,最小费用最大流问题的求解,第二步，在最大流量F的所有解中，找出一个最小费用的解：,最小费用最大流问题的求解,所以，对于上述例子，可以得到如下的线性规划模型：,最小费用最大流问题的网络图论解法,对网络中的每条边的表示进行修改：,最小费用最大流问题的网络图论解法,对上例中的图形进行改进,最小费用最大流问题的网络图论解法,基本算法： 在对边的标号作了改进的网络图上求最小费用最大流的基本算法与求最大流的基本算法完全一样 不同的只是在步骤1中要选择一条总的单位费用最小的路。 如果把每条边的单位费用作为这条边的长度，则在步骤1中需要找到一条从发点到收点的最短路,最小费用最大流问题的网络图论解法,第一次迭代：找到最短路v1 v4 v6 v7。第一次迭代后总流量为1，总费用10。,最小费用最大流问题的网络图论解法,第二次迭代：找到最短路v1 v4 v7。第二次迭代后总流量为3，总费用32。,最小费用最大流问题的网络图论解法,第三次迭代：找到最短路v1 v4 v3 v6 v7。第三次迭代后总流量为5，总费用56。,最小费用最大流问题的网络图论解法,第四次迭代：找到最短路v1 v4 v3 v5 v7。第四次迭代后总流量为6，总费用72。,最小费用最大流问题的网络图论解法,第五次迭代：找到最短路v1 v2 v5 v7 。第五次迭代后总流量为9，总费用123。,最小费用最大流问题的网络图论解法,第六次迭代：找到最短路v1 v2 v3 v5 v7。第六次迭代后总流量为10，总费用145。 此时已经找不到从v1到v7的每条边容量都大于零的路了，故已求得最小费用最大流了,最小费用最大流问题的网络图论解法,最小费用流问题,将上一个例子的问题改为：每小时运送6万加仑的石油从采地v1到销地v7最小费用是多少？应怎样运送？这就变成了一个最小费用流的问题。 一般来说，所谓最小费用