管理系统工程第十八章图与网络.ppt

第十八章 图与网络1.哥尼斯堡七桥问题 德国古城哥尼斯堡普雷格尔河七桥问题：从任一桥头出发，依次走过每一座桥，每座桥只走一次，最后回到出发点。一笔画问题,2.中国邮递员问题 邮递员送信送报要走完全部所负责的街道，最后回到邮局，如何走路程最短？,3.铁路交通图,第一节 图的基本概念一、图的概念定义 图是由点与边组成的集合，记为G=(V，E)，其中V表示图G中点的集合，是一个非空集合，记为V（G），这些点称为顶点，E表示图G中边的集合，记为E（G）。例181 图184中的图可表示为G=（V，E），其中,定义 设G=（V，E）（1）图G中含顶点的个数，记为p（G），称 为图G的阶；图G中含边的条数，记为 q（G），称为图的边数。（2）若e=u，vE，则称u，v是边e的端 点，称e为u，v的关联边。（3）若u和v是同一条边相关联，则称u和v 是相邻的，若边ei、ej有公共的端点，称边ei和ej是相邻的。,（4）若e的两个端点重合，则称e为环。（5）若两点之间多于一条边，称之为多重边。（6）含多重边的图，称为多重图，无环也无多 重边的图，称为简单图。（7）以顶点v为端点的边的条数，称为点v的 次（或称度），记为d（v）。（8）若d（v）=1，则称v为悬挂点，与悬挂点 相关联的边称为悬挂边。（9）若d（v）=0，则称v为孤立点。（10）若d（v）=奇数，则称v为奇点，若 d（v）=偶数，则称v为偶点。,定理1 在图G中，所有顶点次的和，等于边数的两倍。即这是显然的，因为在计算各点的次时，每条边都用过两次，所以，所有顶点次的和等于边数的两倍。定理2 在任一图中，奇点的个数必为偶数。,二、图的同构定义 设是两个图，如果顶点集合V1与V2之间以及边的集合E1与E2之间都建立了一一对应关系，并且图形的两顶点之间的边对应于另一图形对应顶点的边，则称图G1与图G2是同构的。同构的图被认为是相同的。,三、子图定义 设，如果，则称G1是G2的子图。应当指出，从图G2的顶点集合V2中任选一些顶点，从图G2的边集合E2中任选一些边，不一定就能组成G2的子图G1而只有当所有被选入G1的边的端点也都被选入G1时，G1才是G2的子图。并且：（1）若,则称G1是G2的一个部分图，例如图186（b）就是图186（a）的一个部分图。（2）若，则称G1是G2的真子图。例如图186（c）就是图186（a）的一个真子图。,第二节 连通图定义 设是一个图，Q为G中一个由部分顶点和边交错组成的非空有限序列其中 则称Q为从到的一条链，如果Q中，而且与重合，则称Q为圈（或称闭链）。如果链（圈）Q中含的边均不相同，则称Q为简单链（圈）。如果链（圈）Q中含的边与顶点均不相同，则称Q为初等链（圈）。,定义 如果在图中的任何两个顶点之间都至少有一条连接这两个顶点的链，则称图G为连通图，否则，称G为非连通图。,一笔画问题欧拉链：给定一个连通图G,若存在一条链，过每边一次且仅一次，则称这条链为欧拉链。欧拉圈：若存在一个简单圈，过每边一次，则称这个圈为欧拉圈。欧拉图：有欧拉圈的图称为欧拉图。能一笔画的图一定是欧拉圈或含有欧拉链。定理：连通的多重图G是欧拉图的充要条件是G中无奇点。推论：连通的多重图G有欧拉链的充要条件是G中恰有两个奇点。,第三节 树一、树的概念及性质,定义 如果图G是一个无圈的连通图，则称G为树。关于树T，具有下列性质：1在树T中，任意两个顶点之间必有一条且仅有一条链。2在树T中去掉任意一条边，则T成为非连通图。3在树T中不相邻的两个顶点之间添上一条边，恰好构成一个圈。4树的边数恰等于树的顶点数减1。,二、图的部分树定义 如果图的部分图是树，其中，则称T为G的一个部分树（或生成树）。T中的边称为树枝。由这个定义，显然可以得到：若图G有部分树，则G必定是连通图。反之，若图G是连通图，则G必有部分树。,用丢边破圈法，可找出连通图G的部分树。所谓丢边破圈法，就是取图G中任意一个圈，丢去圈上任意一边，然后重复这一步骤，直到图中无圈为止，则剩下的图为无圈的连通图，就是G的一棵部分树。也可以用避圈法找G的部分树。所谓避圈法，就是在连通图G中任意取一边e1，找一条不与e1构成圈的边e2，然后再找一条不与e1，e2构成圈的e3，这样继续下去，直到这一过程不能进行时为止，这样得到的图，就是连通图G的一棵部分树。,三、最小部分树定义 若图G的每一条边（vi，vj)都相应地有一个数wij，则称这样的图G为赋权图，wij称为边（vi，vj)上的权。一个连通图的部分树是不唯一的，其中使各边权的总和最小的那棵部分树，称为最小部分树。,设有一个赋权的连通图，求G的一棵部分树，使取得最小值。,求最小部分树的两种方法 算法（Kruskal算法）：其基本思想是，每一步从未选的边中，选一条具有最小权的边，使与已选的边不构成圈，直到每一条边都选查过为止。算法（破圈法）：其基本思想是，从G中任选一个圈，去掉圈上权最大的边。然后在余下图中，重复上述过程，直到无圈为止。,例:某工厂内联结六个车间的道路网如图所示，已知每条道路的长，要求沿道架设联结六个车间的电话线网，使电话线的总长最小。,第四节 最短路问题1狄克斯特拉（Dijkstra）算法步骤如下：（1）对起点vs进行标号。每个标号点的标号包含两部分，前者表示它的标号是从哪一点来的；后者表示从起点vs到该点的最短距离。对起点vs，将Lss=0填进vs近旁的圆括号内，表示vs点已标号。（2）从vS点出发，找出与vS相邻的顶点中距离最小的一个vr，将Lsr=Lss+dsr的值填入vr近旁圆括号内，表示vr已经标号。,（3）从已标号的顶点出发，找出与已标号点相邻的所有未标号点。若式中vs，vr为已标点，vp为未标号点，则对vp进行标号。（4）重复第3步，直到vT点得到标号为止。,例4 求如图1815所示的网络图中v1到v6的最短距离及其路线。,例5 某厂使用一种设备，每年年初都要决定该设备是否需要更新。若购买新设备，每年需支付购置费用（第i年的购置费设为li）；若继续使用旧设备，则要支付维修与运行费用（第i年的维修与运行费为Ci）。计划期（五年）中每年的li与如Ci表181所示，工厂要制定今后五年的设备更新计划，问采取何种方案，使总费用最小。表181,2矩阵计算法例6 网络图如图1815所示，用矩阵计算法求各点之间的最短距离。,解 设dij表示相邻两点vi与vj间的距离，若vi与vj不相邻时，令dij=。,先考虑vi与vj之间有一个中间点情况，如图1815中的最短距离为为此可以构造一个新的矩阵D(1)，令 D(1)，中每个元素为则矩阵D(1)给出了网络中任意两点之间直接到达和经过一个中间点时的最短距离。,再构造矩阵D(2)，令则D(2)给出网络中任意两点直接到达，经过一至三个中间点时的最短距离。一般，矩阵给出网络中任意两点直接到达，经过一个，两个，到个中间点时比较得到的最短距离。,求中心 在一个连通图G中，设d(vi,vj)为vi至vj的最短距离，令：为点vi至点vj的最大距离,若G中的一点v*满足：则称点v*为图G的中心。,求重心在一个连通图G中，设w(vi)为点vi的权重，令表示将点vi的物资运到点vj的总运输量。若满足则称点 为图G的重心。,例：上例中，v1，v2，v3，v4，v5，v6，v7为七个村子，现决定要办一所小学，已知各村学生人数分别为：v130，v240，v325，v420，v550，v660,v760，问小学应建在那个村子，使学生上学走的路程最短。解：计算见表。小学应建在v6村。,例：下图为一大型企业区域交通网络图。设点v1v7为某公司的7个分厂，边表示经过测绘的交通路线，边旁的数字表示两点之间的距离。现该企业欲修建正规道路使各分厂互通，并欲在某一分厂建一俱乐部。问如何选择交通路线来修建正规道路既保证各分厂畅通，又使道路总长度最短？俱乐部应建在那个分厂才能使离该俱乐部最远的分厂的职工所走的路程最短？解:显然，第一个问题就是求最短树问题。第二个问题就是求中心问题。用避圈法或破圈法求出最小部分树见图。,先用公式 计算d(vi)，见下表：再用公式 计算d(v*)，由表可知，应将俱乐部建在分厂v2或v6。,例：仍以上例为例，现准备在该地区建一个中心仓库以贮存分发给各分厂的原材料。已知各分厂每月的原材料需求量见下图。问中心仓库应建在那个分厂，能使每月总的运输量最小。解：由计算重心的公式：既可算得应把中心仓库建在v6分厂，每月的最小运输量为122000。,第五节 最大流问题最大流问题，就是在一定条件下要求流过网络的流量为最大的问题。以图1818所示的运输网络为例来说明求解过程。,一、基本概念1容量在D=（V，A）上的每条弧（vi，vj），都规定对应一个正数Cij，称为弧（vi，vj）的容量，在运输网络中Cij表示弧（vi，vj）的最大通过能力。定义了容量的图D，称为容量网络。记D=（V，A，C）。,在容量网络上通常规定一个发点vS，一个收点vT，其余都是中间点。对于有多个发（收）点的网络，只要假设一个总发（收）点，并分别与各发（收）点连起来，这样多个发（收）点的网络问题就转化为单个发（收）点的网络问题了。最大流问题就是：要把发点处的一批货物运到终点去，在每一条弧上通过货物的总量不能超过这条弧的容量，问应该怎样安排运输，才能使发点到收点的总运量达到最大。,2流设D=（V，A，C），则称定义在弧集A上的函数为网络D的一个流，其中每一个f（vi，vj），简记为fij，称为弧（vi，vj）上的流量。例如图1818,满足下列条件的流f，称为可行流（1）相容条件：对每一条弧，有（2）平衡条件：对每一个中间点vij，有其中等式左端第一项表示从点vi流出货物的总量，简记为f（vi，V）；第二项表示流进vi点的货物的总量，简记为f（V，vi）。（3）对于发点vS，收点vT，有其中v（f）为非负数，称为可行流的流量。,零流是最简单的可行流。在所有可行流中使流量v（f*）最大的可行流f*，称为最大流。,把流量fij作为变量，根据可行流的定义及网络最大流问题的提法，可见最大流问题也是一个线性规划问题，其数学模型为：求一组流量fij使,3增广链定义 设网络D=（V，A，C）中有一个流f=fij，则称fij=Cij的弧（vi，vj）为饱和弧。fijCij的弧（vi，vj）为非饱和弧。fij=0的弧（vi，vj）为零流弧。fij0的弧（vi，vj）为非零流弧。定义 设是网络D中从vS到vT的一条链，这条链上的弧可以分成两类，把弧的方向与链的方向一致的弧，称为前向弧，链中的全体前向弧记为+；把弧的方向与链的方向相反的弧，称为后向弧，链中的全体后向弧记为-。,定义 设有D中一条从vS到vT的链，如果的所有前向弧是非饱和弧，的所有后向弧为非零流弧，则称为增广链。例图18-18,4截集与截量 截集是指将容量网络中的发点与收点分割开，使vS到vT的流中断的一个弧的集合。例图18-18,令 则称弧的集合（v1，v2），（v3，v4），（v3，v5）为一个截集，记为，即（v1，v2），（v3，v4），（v3，v5）称 为截量。这里,若对于一个可行流f*，网络图中有一个截集，使则f*必是最大流，而 是D的所有截集中截量最小的一个，即最小截集。定理3：可行流f是最大流的充分与必要条件是不存在关于f的增广链。定理4（最大流量最小截量定理）：任一个网络D中，从vS到vT的最大流的流量等于分离vS，vT的最小截集的容量。,二、求最大流标号法福特福尔克逊（FordFuldkerson）标号法。标号法的具体步骤如下：1标号过程标号过程就是寻找增广链的过程。先给发点vS标号，即，然后从已标号点vi出发，找出与之相邻的未标号点vj，考虑：（1）如果连接vi与vj的弧（vi，vj）是前向弧，且，则给vj标号，即。（2）如果连接vi与vj的弧（vi，vj）是后向弧，且，则给vj标号，即。,对已标号点重复（1），（2）步骤，如果vT得到标号，则找到增广链，转入调整过程；如果标号中断，说明不存在增广链，则现行的可行流即为最大流。2调整过程由标号过程得到一条增广链，则调整量为然后在增广链的一切前向弧+上增加，一切后向弧-上减少，不在增广链上的弧流量不变。这样得到一个新的可行流，对新的可行流重新转入标号过程。,例7 求图1820所示网络的最大流，弧旁的数字是容量Cij，弧旁括号内的数字是流量fij。,某河流中有几个岛屿，从两岸至各岛屿及各岛屿之间的桥梁编号如图6-20所示。在一次敌对的军事行动中，问至少应炸断几座及哪几座桥梁，才能完全切断两岸的交通联系。,例：电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？图7-6给出了甲、乙两地间的交通图，图中的点v1，v2，v7表示7个地名，其中v1表示甲地，v7表示乙地，点之间的联线（边）表示两地之间的公路，边的赋权数表示两地间公路的长度（单位为公里）。,