




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第七章图与网络理论例1哥尼斯堡七桥问题ABCDABCD哥尼斯堡七桥问题哥尼斯堡城中有一条河,河上有七座连结着两岸和河中的两个小岛,如图7.1所示。问题是一个人能否从一点出发,经过每座桥一次且仅一次,回到原出发点。图7.11第七章图与网络理论例1哥尼斯堡七桥问题ABCDABCD第一节图的基本概念所谓图,就是顶点和边的集合,点的集合记为V={v1,v2…,
vn},边的集合记为E={e1,e2…,
em},vi称为图的顶点,ej称为图的边,若边ej联结vs和vt,则记为(vs,vt),即ej=(vs,vt)。
则图可以表示为:G=(V,E),点代表被研究的事物,边代表事物之间的联系,因此,边不能离开点而独立存在,每条边都有两个端点。在画图时,顶点的位置、边和长短形状都是无关紧要的,只要两个图的顶点及边是对应相同的,则两个图相同。2第一节图的基本概念所谓图,就是顶点和边的集合有些图的边带有方向,这样的图称为有向图。而边不带方向的图称为无向图。图7.7是一个无向图。图7.8是一个有向图。v1v5v2v3v4e1e2e3e4e6e5e7图7.7图7.83有些图的边带有方向,这样的图称为有向图。而边不带方向的图称为在一个图中,若e=(u,v),则称u,v是边e的端点.并u,v称相邻.称e是点u(v及点)的关联边。若边ei,ej有一个公共的端点u,称边ei,ej相邻。若边e的两个端点是同一顶点,则称此边为环。若两顶点之间有多于一条的边,则这些边称为多重边。如图7.7中,e7是环,e1,e2是多重边。一个不含环和多重边的图称为简单图。含有多重边的图称为多重图。我们这里所说的图,如不特别指明,都是简单图。4在一个图中,若e=(u,v),则称u,v是边以点v为端点的边的条数称为点v的度,记作d(v),如图7.7中d(v1)=3,d(v3)=1。度为零的点称为弧立点,度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点,度为偶数的点称为偶点。不难证明:在一个图中,顶点度数的总和等于边数的2倍,奇顶点的个数必为偶数。
链:由两两相邻的点及其相关联的边构成的点边序列;如:v0
,e1,v1,e2,v2
,e3,v3
,…,vn-1,en
,vn;
v0,vn分别为链的起点和终点;
简单链:链中所含的边均不相同;
初等链:链中所含的点均不相同;圈:在链中,若v0=vn则称该链为圈;连通图:图中任意两点之间均至少有一条链相连
,5以点v为端点的边的条数称为点v的度,记作d(第二节树树是一类结构简单而又十分有用的图。一个不含圈的连通图称为树。设图T=(V,E),含有n个顶点,则下列命题是等价的。(1)T是树。(2)T的任意两顶点之间,有唯一的链相连。(3)T连通且有n-1条边。(4)T无圈且有n-1条边。(5)T无圈但添加一条边得唯一一圈。(6)T连通但去掉一条边则不连通。6第二节树6给定图G=(V,E),若V’
V,E’
E,并且E’中的边的端点都属于V’
,则称G’=(V’,E’)是G的一个子图。特别地,若V’
=
V,则称G’为G的支撑子图。设T是图G的一个支撑子图,若T是一树,则称T是G的一个支撑树。给定图G=(V,E),对于G的每一条边,可赋以一个实数w(e),称为边e的权,图G连同它边上的权称为赋权图。赋权图在图论的应用中经常出现。根据实际问题的需要,权可以有不同的实际含义,它可以表示距离、流量、时间、费用等。7给定图G=(V,E),若V’V给定图G=(V,E),设T=(V,E’)是G的一个支撑树,定义树T的权为即支撑树T上所有边的权的总和。图G的最小支撑树就是图G中权最小的支撑树。求图G的最小支撑树的方法是建立在求图G的支撑树基础上,只需在求图G的支撑树的算法再加适当限制。因此,求最小支撑树方法也有相应的破圈法;避圈法。
8给定图G=(V,E),设T=(V例2分别用破圈法,避圈法求图7.17的最小支撑树。图7.17v1v5v2v3v42v6v7v834346236645859例2分别用破圈法,避圈法求图7.17的最小支撑树。图7.v1v5v2v3v42v6v7v83434623664585解破圈法10v1v5v2v3v42v6v7v83434623664585v1v5v2v3v42v6v7v83434623664585避圈法:11v1v5v2v3v42v6v7v83434623664585第三节最短路问题最短路问题,一般来说就是从给定的赋权图中,寻找两点之间权最小的链(链的权即链中所有边的权之和)。许多优化问题都需要求图的最短路,如选址、管道铺设、设备更新、整数规划等问题。由于所求问题不同,需要使用不同的方法。下面我们介绍常用的算法。一、Dijkstra算法Dijkstra算法是求赋权有向图中,某两点之间最短路的算法。实际上,它可以求某一点到其它各点的最短路。它是Dijkstra于1959年提出。目前被认为是求非负权最短路的最好的算法。12第三节最短路问题12Dijkstra算法的基本思想是基于以下原理:若vs,vl,…,vj是vs到vj的最短路,vi是此路中某一点,则vs,vl,…,vi必是从vs到vi的最短路。此算法的基本步骤是采用标号法,给图G每一个顶点一个标号。标号分两种:一种是T标号,一种是P标号。T标号也称临时标号,它表示从vs到这一点的最短路长度的一个上界,P标号也称固定标号,它表示从vs到这一点的最短路的长度(这里最短路长度是指这条路上个边权的和)。算法每一步都把某点的T标号改变为P标号。当终点得到P标号,算法结束。若要求某点到其它各点的最短路,则最多经过n-1步算法结束。13Dijkstra算法的基本思想是基于以下原理:设lij表示边(vi,vj)的权,则Dijkstra算法步骤如下:(1)给始点以P标号P(0,0),给其它各点vj以T标号T(dj,v1),其中,dj=l1j,(若vj与v1不相邻,则令l1j=+∞)。(2)在所有T标号点中,若vk的T标号最小,则把vk的T标号改为P标号。若最小的T标号不止一个,则可任取一个改为P标号。(3)修改所有T标号T(dj,vt);dj=min{dj,dk+lkj},若dk+lkj<djvt=vk否则不变。(4)当终点或全部顶点都得到P标号,算法结束,否则返回(2)。14设lij表示边(vi,vj)的权,则Dijkstra算法步骤例3求图7.20中,v1到v8的最短路。图7.20v4v2v1v3v6v5v7v8983834256767109415例3求图7.20中,v1到v8的最短路。图7.20v4图7.20v4v2v1v3v6v5v7v89838342567671094解
P(0,0)T(9,v1)T(3,v1)T(8,v1)16图7.20v4v2v1v3v6v5v7v898383425图7.20v4v2v1v3v6v5v7v89838342567671094解
P(0,0)T(9,v1)T(7,v3)T(3,v1)T(8,v1)P(3,v1)17图7.20v4v2v1v3v6v5v7v898383425图7.20v4v2v1v3v6v5v7v89838342567671094解
P(0,0)T(9,v1)T(7,v3)T(8,v1)P(3,v1)P(7,v3)T(14,v6)T(16,v6)18图7.20v4v2v1v3v6v5v7v898383425图7.20v4v2v1v3v6v5v7v89838342567671094解
P(0,0)T(9,v1)T(8,v1)P(3,v1)P(7,v3)T(14,v6)P(9,v1)P(8,v1)T(17,v2)T(16,v6)19图7.20v4v2v1v3v6v5v7v898383425图7.20v4v2v1v3v6v5v7v89838342567671094解
P(0,0)P(3,v1)P(17,v2)P(7,v3)T(14,v6)P(9,v1)P(8,v1)T(17,v2)T(16,v6)P(14,v6)P(16,v6)20图7.20v4v2v1v3v6v5v7v898383425图7.20v4v2v1v3v6v5v7v89838342567671094解
P(0,0)P(3,v1)P(17,v2)P(7,v3)P(9,v1)P(8,v1)P(14,v6)P(16,v6)21图7.20v4v2v1v3v6v5v7v898383425例4求图7.22中,v1到其它各点的最短路。图7.22v4v2v1v3v6v5v7v8354263441517498Dijkstra算法同样可用于求无向图的最短路。22例4求图7.22中,v1到其它各点的最短路。图7.22v图7.22v4v2v1v3v6v5v7v8354263441517498解
P(0,0)T(3,v1)T(4,v1)T(2,v1)23图7.22v4v2v1v3v6v5v7v835426344图7.22v4v2v1v3v6v5v7v8354263441517498解
P(0,0)T(3,v1)T(4,v1)T(2,v1)P(2,v1)T(7,v4)T(3,v4)P(3,v1)T(8,v2)T(9,v2)24图7.22v4v2v1v3v6v5v7v835426344图7.22v4v2v1v3v6v5v7v8354263441517498解
P(0,0)P(2,v1)T(7,v4)T(3,v4)P(3,v1)T(8,v2)T(9,v2)P(3,v4)T(6,v3)25图7.22v4v2v1v3v6v5v7v835426344图7.22v4v2v1v3v6v5v7v8354263441517498解
P(0,0)P(2,v1)T(7,v4)P(3,v1)T(8,v2)P(3,v4)T(6,v3)P(6,v3)T(7,v6)T(15,v6)26图7.22v4v2v1v3v6v5v7v835426344图7.22v4v2v1v3v6v5v7v8354263441517498解
P(0,0)P(2,v1)T(7,v4)P(3,v1)P(3,v4)P(6,v3)T(7,v6)P(7,v6)T(15,v6)T(11,v5)P(7,v4)27图7.22v4v2v1v3v6v5v7v835426344图7.22v4v2v1v3v6v5v7v8354263441517498解
P(0,0)P(2,v1)P(3,v1)P(3,v4)P(6,v3)P(7,v6)T(11,v5)P(7,v4)P(11,v5)28图7.22v4v2v1v3v6v5v7v835426344图7.22v4v2v1v3v6v5v7v8354263441517498解
P(0,0)P(2,v1)P(3,v1)P(3,v4)P(6,v3)P(7,v6)P(7,v4)P(11,v5)29图7.22v4v2v1v3v6v5v7v835426344二、逐次逼近法前面介绍的Dijkstra算法,只适用于权为非负的赋权图中求最短路问题。逐次逼近法可用于存在负权,但无负有向回路的赋权图的最短路问题。因为,如果dj是从v1到vj的最短路的长度,而这从条最短路的最后一条边为(vk,vj),则从v1到vj的最短路中,从v1到vk这一段,必然也是从v1到vk的最短路。若其长度记为dk,lkj表示边(vk,vj)的权,那么dj,dk和lkj应满足下列方程:30二、逐次逼近法30逐次逼近法就是用迭代方法解这个方程。第一次逼近是找点v1到点vj由一条边所组成的最短路,其长记为dj(1);第二次逼近是求从v1到点vj不多于两条边组成的最短路,其长记为dj(2);以此类推,第m次逼近是求从v1到vj不多于m条边组成的最短路,其长记为dj(m)。因为图中,不含负有向回路,所以从v1到vj的最短路上最多有n-1条边。从而可知,最多做n-1次逼近就可求出从v1到vj的最短路。
31逐次逼近法就是用迭代方法解这个方程。第一次逼近逐次逼近法步骤如下:(1)首先令dj(1)=l1j(j=1,2,…,n),若v1与vj之间无边时,lij=+∞,而ljj=0;(3)若对所有的j,有dj(m)=dj(m-1),则计算结束,dj(m)(j=1,2,…,n)即为v1到其它各点的最短路的长度,否则返回(2)。32逐次逼近法步骤如下:(3)若对所有的j,有dj(m)=例4求下图中,v1到其它各点的最短路。v1139538362v6v5v3v4v233例4求下图中,v1到其它各点的最短路。v11395v1139538362v6v5v3v4v2026∞∞∞34v1139538362v6v5v3vv1139538362v6v5v3v4v2026∞∞∞035v1139538362v6v5v3vv1139538362v6v5v3v4v2026∞∞∞0236v1139538362v6v5v3vv1139538362v6v5v3v4v2026∞∞∞0225②37v1139538362v6v5v3vv1139538362v6v5v3v4v2026∞∞∞0225②10②38v1139538362v6v5v3vv1139538362v6v5v3v4v2026∞∞∞0225②10②9③39v1139538362v6v5v3vv1139538362v6v5v3v4v2026∞∞∞0225②10②9③∞40v1139538362v6v5v3vv1139538362v6v5v3v4v2026∞∞∞0225②10②9③∞025108③10⑤41v1139538362v6v5v3vv1139538362v6v5v3v4v2026∞∞∞0225②10②9③∞025108③10⑤025108③9⑤42v1139538362v6v5v3vv1139538362v6v5v3v4v2026∞∞∞0225②10②9③∞025108③10⑤025108③9⑤025108943v1139538362v6v5v3v例5求图7.24中,v1到其它各点的最短路。图7.24v1v2v3v4v5v6v7v834-14-22545-3-2-435444例5求图7.24中,v1到其它各点的最短路。图7.24v1vjilijdj(1)dj(2)dj(3)dj(4)dj(5)dj(6)v1v2v3v4v5v6v7v8v1034000000v20-1-24333333v305422222v4204511111v50-2375555v6045333v7-3-40597777v801087745jlijdj(1)dj(2)dj(3)dj(4)dj(5)d第四节最大流问题给定一个有向图G=(V,E),每条边(vi,vj)给定一个非负数cij称为边(vi,vj)容量。假设G中只有一个入度为零的点vs称为发点,只有一个出度为零的点vt称为收点,其余点称为中间点,这样的有向图称为容量网络,记为G=(V,E,C)。46第四节最大流问题46例如图7.25就是一个容量网络。如果vs表示油田,vt表示炼油厂,图7.25表示从油田到炼油厂的输油管道网。边上的数字表示该管道的最大输油能力,中间点表示输油泵站。现在要问如何安排各管道输油量,才能使从vs到vt输油量最大?这就是本节所要介绍的最大流问题。
图7.25v1v2v3v4vsvt54142537847例如图7.25就是一个容量网络。如果vs表示一、基本概念给定一个容量网络G=(V,E,C),所谓网络G上的流,是指每条边(vi,vj)上确定的一个数f(vi,vj),简记为fij,称集合f={fij}为网络G上的一个流。如果网络G表示一个输油管道网,则cij表示管道输油能力,而fij表示管道当前的实际流量,因此应有0fijcij,即管道中的流量不能超过该管道的最大通过能力(即管道的容量)。对网络G上的中间点表示一个转送泵站,因此对中间点运出的总量与运进的总量应当相等。而对于发点的净流出量和收点的净流入量必相等,并且就是该运输方案的总输送量。48一、基本概念48容量网络G=(V,E,C)中的一个流f={fij}满足下列条件,称f为可行流。(1)容量限制条件:对G中每条边(vi,vj),有0fijcij。(2)平衡条件:对于中间点vi,有(即流出量=流入量)。对于收点vt与发点vs,有(即从vs的净输出量与vt的净输入量相等)。W称为可行流f的流量。可行流总是存在的,当所有边的流量fij=0时,就得到一个可行流,它的流量W=0。最大流问题就是在容量网络中,寻找流量最大的可行流。49容量网络G=(V,E,C)中的一个流f={fij}满足下对于容量网络G给定一个可行流f={fij},当fij=cij时,称边(vi,vj)为饱和边,当fij<cij时,称边(vi,vj)为非饱和边,当fij=0时,称边(vi,vj)为零流边,当fij>0时,称边(vi,vj)为非零流边。设μ是网络G中一条联结发点vs和收点vt的链。我们规定μ的正方向从vs到vt,则链μ上的边被分为两类:一类是边的方向与链的正方向一致,称它们为前向边,μ上上前向边的全体记为μ+。另一类边与链的正方向相反,称它们为后向边,μ上后向边的全体记为μ-。50对于容量网络G给定一个可行流f={fij},当fiv1v2v3v4v5vsvt(13,7)(5,5)(9,9)(4,4)(6,6)(5,2)(5,0)(4,0)(5,5)(4,4)(9,7)(10,5)图7.26例如,在图7.26中,其边上的两个数字分别表示边的容量和流量,即(cij,fij)。(v2,v5)为饱和边,(vs,v1)为非饱和边,并且(v2,v5),(vs,v1)均为非零流边,(v3,v5)是零流边。51v1v2v3v4v5vsvt(13,7)(5,5)(9,例如图7.26中,在联结vs和vt的链μ={vs,v1,v2
,v5,vt}中,(vs,v1),(v2,v5),(v5,vt)为前向边,(v1,v2)为后向边。即μ+={(vs,v1),(v2,v5),(v5,vt)},μ-={(v1,v2)}。v1v2v3v4v5vsvt(13,7)(5,5)(9,9)(4,4)(6,6)(5,2)(5,0)(4,0)(5,5)(4,4)(9,7)(10,5)图7.2652例如图7.26中,在联结vs和vt的链μ={vs,v1,设f是网络G上的一个可行流,μ是从vs到vt的一条链,若对μ上的任意一条边(vi,vj)有若(vi,vj)μ+,则0fij<cij,即μ+中每一边是非饱和边。若(vi,vj)μ-,则0<fijcij,即μ-中每一边是非零流边。则称μ是一条增广链。53设f是网络G上的一个可行流,μ是从vs到vt的一条链,若对μ例如图7.26中,链μ={vs,v1,v2,v3,v5,vt}就是一条增广链,因为μ+={(vs,v1),(v2,v3),(v3,v5),(v5,vt)}中的边均为非饱和边,而μ-={(v1,v2)}中的边为非零流边。v1v2v3v4v5vsvt(13,7)(5,5)(9,9)(4,4)(6,6)(5,2)(5,0)(4,0)(5,5)(4,4)(9,7)(10,5)图7.2654例如图7.26中,链μ={vs,v1,v2,v3,v对于给定的网络G=(V,E,C),设S,TV,并且ST=V,ST=,vs
S,vtT,以S中点为始点,以T中点为终点的边的集合,称为G的割集,记为(S,T)。割集(S,T)中所有边的容量之和称为割集(S,T)的容量,记为C(S,T),即55对于给定的网络G=(V,E,C),设S,TV,并且S例如图7.26中,设S1={vs},T
1={v1,v2,v3,v4,v5,vt},则(S1,T1)={(vs,v1),(vs,v2)},其容量为C(S1,T1)=22。设S2={vs,v1},T
2={v2,v3,v4,v5,vt}则(S2,T2)={(vs,v2),(v1,v4)},其容量为C(S2,T2)=20。v1v2v3v4v5vsvt(13,7)(5,5)(9,9)(4,4)(6,6)(5,2)(5,0)(4,0)(5,5)(4,4)(9,7)(10,5)图7.2656例如图7.26中,设S1={vs},T1={v1,v如果从网络G中去掉割集(S,T)中的边,从vs就没有路可以到达vt。对于网络G,它有许多割集,我们可以找到容量最小割集。而网络G的最大流量一定不会超过容量最小割集的容量,称网络G中容量最小的割集为G的最小割集。如果把网络G看成各种粗细不同的管道网,而最小割集就相当于管道网中最细管道部分的总和。二、最大流最小割集定理由上面例子可知,如果找到网络G的一个可行流,其流量等于网络G的最小割集容量,则该可行流一定是最大流。下面最大流最小割集定理就是要说明这一点。57如果从网络G中去掉割集(S,T)中的边,从vs就没有定理1可行流f*是最大流当且仅当G中不存在关于f*的增广链。推论在任意一个容量网络中,最大流的流量等于最小割集的容量。三、求最大流的标号算法由上面定理1可知可行流f是否是最大流,关键看网络G中是否存在关于可行流f的增广链,定理1的证明过程为我们提供了寻找增广链的方法及改进可行流f的方法。如果在网络G中存在关于可行流f的增广链(从vs到vt),则可按定理1证明中所给的方法修改可行流f,得到一个新的可行流f‘,而f‘的流量大于f的流量。如果在G中不存在关于可行流f的增广链,则可行流f就是最大流。寻找关于可行流f的增广链可按下面介绍的标号法来实现。58定理1可行流f*是最大流当且仅当G中不存在关于f*的增求网络G的最大流的标号法分为两步,第1步是标号过程,通过标号寻找增广链;第2步是调整过程,沿增广链个性可行流f的流量。设f是网络G上的可行流(初始可行流可取零流f={fij=0})。1标号过程(1)首先给发点vs标号(0,+∞)。(2)选择一个已标号的顶点vi,对所有与vi相邻而没有标号的顶点vj按下列规则处理。(a)若(vi,vj)E,并且fij<cij,则给顶点vj以标号(i,δj),其中δj=min{δi,cij-fij}。(b)若(vj,vi)E,并且fij>0,则给顶点vj以标号(i,δj),其中δj=min{δi,cij-fji}。59求网络G的最大流的标号法分为两步,第1步是标号过程,通过标号重复过程(2),可能出现两种结果,其一是终点vt得到标号,说明存在一条增广链,则转到调整过程,其二是终点vt不能获得标号,说明不存在增广链,这时可行流f即为最大流。2调整过程首先按终点vt及其它顶点的第一个标号,用反向追踪法在网络中找出增广链。例如设终点vt的第一个标号为k,则(vk,vt)是增广链上的边,然后根据vk的第一个标号,找到下一个顶点,即若vk的第一个标号为j,则(vj,vk)(或者(vk,vj))是增广链上的边,直到用此方法找到vs为止。这时就得到一条从vs到vt的增广链μ。最后按下式修改可行流f。
60重复过程(2),可能出现两种结果,其一是终点vt得到标号,说调整结束后,去掉所有标号,返回标号过程重新进行标号过程。令61调整结束后,去掉所有标号,返回标号过程重新进行标号过程。令6例10用标号法求下图中从vs到vt的最大流。
vsvt
v4
v2
v3
v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)62例10用标号法求下图中从vs到vt的最大流。vsvtv解(I)标号过程(1)首先给发点vs标以(0,+∞).
vsvt
v4
v2
v3
v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)(0,+∞)63解(I)标号过程(1)首先给发点vs标以(0,+∞).
vsvt
v4
v2
v3
v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)(0,+∞)(2)检查与vs相邻的顶点v1,v2,因为(vs,v1)E,并且fs1=4<cs1=15,所以v1可以获得标号(vs,δ1),其中δ1=min{+∞,
15-4}=11。因为(vs,v2)E,但fs2=cs2,所以v2不能标号。(vs,11)64vsvtv4v2v3v1(15,4)(9,9)(3
vsvt
v4
v2
v3
v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)(0,+∞)(3)检查与v1相邻且没有标号的顶点v2,v3,v4,因为(v2,v1)E,并且f21>0,所以v2可以获得标号(v1,δ2),其中δ2=min{δ1,f21}=min{9,3}=3。因为(v1,v4)E,并且f14=0<c14=4,所以v4可以获得标号(v1,δ4),其中δ4=min{9,
4-0}=4。因为(v1,v3)E,但f13=c13,所以v3不能标号。(vs,11)(v1,3)(v1,4)65vsvtv4v2v3v1(15,4)(9,9)(3
vsvt
v4
v2
v3
v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)(0,+∞)(4)检查与v2相邻且没有标号的顶点v3,因为(v2,v3)E,并且f23=1<c23=5,所以v3可以获得标号(v2,δ3),其中δ3
min{δ2,
c23-f23
}=min{3,5-1}=3
。(vs,11)(v1,3)(v1,4)(v2,3)66vsvtv4v2v3v1(15,4)(9,9)(3
vsvt
v4
v2
v3
v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)(0,+∞)(vs,11)(v1,3)(v1,4)(v2,3)(5)由于与v3相邻且没有标号的顶点为vt,并且vt也与已标号的顶点v4相邻,所以vt既可以以v3为基础获得标号(v3,δt),也可以以v4为基础获得标号(v4,δt’)。但为减少迭代次数,应选择δ1与δt’两者较大的给vt标号。因为δt=min{δ3,c3t-f3t}=min{3,3}=3,δt’=min{δ4,c4t-f4t}=min{4,5}=4,所以vt的标号应取(v4,4)。(v4,4)67vsvtv4v2v3v1(15,4)(9,9)(3
vsvt
v4
v2
v3
v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)(0,+∞)(vs,11)(v1,3)(v1,4)(v2,3)(v4,4)(II)调整过程由于vt的第一个标号为v4,得到顶点v4,由v4的第一个标号为v1,得到顶点v1,由v1的第一个标号为vs,得到顶点vs,由此得到关于可行流f的增广链μ={vs,v1,v4
,vt},其中(vs,v1),(v1,v4),(v4,vt)为前向边。68vsvtv4v2v3v1(15,4)(9,9)(3
vsvt
v4
v2
v3
v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+∞)(vs,11)(v1,3)(v1,4)(v2,3)(v4,4)(II)调整过程由于δt=4,所以调整量为4,即增广链μ上的前向边流量加4。69vsvtv4v2v3v1(15,8)(9,9)(3
vsvt
v4
v2
v3
v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+∞)重新开始标号过程,
(I)标号过程(1)首先给发点vs标以(0,+∞).
70vsvtv4v2v3v1(15,8)(9,9)(3
vsvt
v4
v2
v3
v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+∞)(vs,7)(2)检查与vs相邻的顶点v1,v2,因为(vs,v1)E,并且fs1=8<cs1=15,所以v1可以获得标号(vs,δ1),其中δ1=min{+∞,
15-8}=7。因为(vs,v2)E,但fs2=cs2,所以v2不能标号。71vsvtv4v2v3v1(15,8)(9,9)(3
vsvt
v4
v2
v3
v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+∞)(vs,9)(v1,3)(3)检查与v1相邻且没有标号的顶点v2,v3,v4,因为(v2,v1)E,并且f21>0,所以v2可以获得标号(v1,δ2),其中δ2=min{δ1,f21}=min{9,3}=3。因为(v1,v3)E,但f13=c13,所以v3不能标号。因为(v1,v4)E,并且f14=c14,所以v4不能标号。72vsvtv4v2v3v1(15,8)(9,9)(3
vsvt
v4
v2
v3
v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+∞)(vs,11)(v1,3)(v2,1)(v2,3)(5)检查与v2相邻且没有标号的顶点v3,v4,因为(v2,v3)E,并且f23=1<c23=5,所以v3可以获得标号(v2,δ3),其中δ3=min{δ2,
c23-f23}=min{3,4}=3。因为(v2,v4)E,并且f24=5<c24=6,所以v4可以获得标号(v2,δ4),其中δ4
=min{δ2,
c23-f23}=min{3,
6-5}=1。73vsvtv4v2v3v1(15,8)(9,9)(3
vsvt
v4
v2
v3
v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+∞)(vs,7)(v1,3)(v2,1)(v2,3)(v3,3)(5)由于与v3相邻且没有标号的顶点为vt,并且vt也与已标号的顶点v4相邻,所以vt既可以以v3为基础获得标号(v3,δt),也可以以v4为基础获得标号(v4,δt’)。但为减少迭代次数,应选择δ1与δt’两者较大的给vt标号。因为δt=min{δ3,c3t-f3t}=min{3,3}=3,δt’=min{δ4,c4t-f4t}=min{1,1}=1,所以vt的标号应取(v3,3)。74vsvtv4v2v3v1(15,8)(9,9)(3
vsvt
v4
v2
v3
v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+∞)(vs,11)(v1,3)(v1,4)(v2,3)(v4,4)75vsvtv4v2v3v1(15,8)(9,9)(3
vsvt
v4
v2
v3
v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+∞)(vs,7)(v1,3)(v2,1)(v2,3)(v3,3)(II)调整过程由于vt的第一个标号为v3,得到顶点v3,由v3的第一个标号为v2,得到顶点v2,由v2的第一个标号为v1,得到顶点v1,由v1的第一个标号为vs,得到顶点vs,由此得到关于可行流f的增广链μ={vs,v1,v2,v3,vt},其中(vs,v1),(v2,v3),(v3,vt)为前向边,(v2,v3)为后向边。76vsvtv4v2v3v1(15,8)(9,9)(3
vsvt
v4
v2
v3
v1(15,11)(9,9)(3,0)(5,4)(6,5)(7,7)(10,9)(11,11)(4,4)(0,+∞)(vs,7)(v1,3)(v2,1)(v2,3)(v3,3)(II)调整过程由于δt=3,所以调整量为3,即增广链μ上的前向边流量加3,后向边流量减3。77vsvtv4v2v3v1(15,11)(9,9)(
vsvt
v4
v2
v3
v1(15,11)(9,9)(3,0)(5,4)(6,5)(7,7)(10,9)(11,11)(4,4)(0,+∞)重新开始标号过程,
(I)标号过程(1)首先给发点vs标以(0,+∞).
78vsvtv4v2v3v1(15,11)(9,9)(
vsvt
v4
v2
v3
v1(15,11)(9,9)(3,0)(5,4)(6,5)(7,7)(10,9)(11,11)(4,4)(0,+∞)(vs,4)(2)检查与vs相邻的顶点v1,v2,因为(vs,v1)E,并且fs1=11<cs1=15,所以v1可以获得标号(vs,δ1),其中δ1=min{+∞,
15-11}=4。因为(vs,v2)E,但fs2=cs2,所以v2不能标号。79vsvtv4v2v3v1(15,11)(9,9)(
vsvt
v4
v2
v3
v1(15,11)(9,9)(3,0)(5,4)(6,5)(7,7)(10,9)(11,11)(4,4)(0,+∞)(vs,4)(3)检查与vs,v1相邻的顶点v2,v3,v4,都不满足标号条件,所以标号过程结束,这时vt没有得到标号,由此可知不存在从vs到vt的增广链,所以图中的可行流就是最大流,其流量W=fs1+fs2=11+9=20。
80vsvtv4v2v3v1(15,11)(9,9)(
vsvt
v4
v2
v3
v1(15,11)(9,9)(3,0)(5,4)(6,5)(7,7)(10,9)(11,11)(4,4)(0,+∞)(vs,4)用标号法在求得最大流的同时,可得到一个最小割集,从图可知,标号点的集合为S={vs
,v1},此时割集为,
81vsvtv4v2v3v1(15,11)(9,9)(例11用标号法求图7.26中从vs到vt的最大流。
v3
vsvt
v5
v2
v4
v1(13,7)(9,9)(4,4)(5,2)(5,5)(5,5)(10,5)(9,7)(6,6)(5,0)(4,0)(4,4)图7.2682例11用标号法求图7.26中从vs到vt的最大流。v3
v3
vsvt
v5
v2
v4
v1(13,7)(9,9)(4,4)(5,2)(5,5)(5,5)(10,5)(9,7)(6,6)(5,0)(4,0)(4,4)图7.26解(0,+∞)(vs,6)(v1,4)(v2,4)(v3,4)(v5,4)83v3vsvtv5v2v4v1(13,7)(9,9
v3
vsvt
v5
v2
v4
v1(13,11)(9,9)(4,0)(5,2)(5,5)(5,5)(10,9)(9,7)(6,6)(5,4)(4,4)(4,4)图7.26(0,+∞)(vs,6)最大流为W=fs1+fs2=11+9=20。
最小割集为84v3vsvtv5v2v4v1(13,11)(9,第七章图与网络理论例1哥尼斯堡七桥问题ABCDABCD哥尼斯堡七桥问题哥尼斯堡城中有一条河,河上有七座连结着两岸和河中的两个小岛,如图7.1所示。问题是一个人能否从一点出发,经过每座桥一次且仅一次,回到原出发点。图7.185第七章图与网络理论例1哥尼斯堡七桥问题ABCDABCD第一节图的基本概念所谓图,就是顶点和边的集合,点的集合记为V={v1,v2…,
vn},边的集合记为E={e1,e2…,
em},vi称为图的顶点,ej称为图的边,若边ej联结vs和vt,则记为(vs,vt),即ej=(vs,vt)。
则图可以表示为:G=(V,E),点代表被研究的事物,边代表事物之间的联系,因此,边不能离开点而独立存在,每条边都有两个端点。在画图时,顶点的位置、边和长短形状都是无关紧要的,只要两个图的顶点及边是对应相同的,则两个图相同。86第一节图的基本概念所谓图,就是顶点和边的集合有些图的边带有方向,这样的图称为有向图。而边不带方向的图称为无向图。图7.7是一个无向图。图7.8是一个有向图。v1v5v2v3v4e1e2e3e4e6e5e7图7.7图7.887有些图的边带有方向,这样的图称为有向图。而边不带方向的图称为在一个图中,若e=(u,v),则称u,v是边e的端点.并u,v称相邻.称e是点u(v及点)的关联边。若边ei,ej有一个公共的端点u,称边ei,ej相邻。若边e的两个端点是同一顶点,则称此边为环。若两顶点之间有多于一条的边,则这些边称为多重边。如图7.7中,e7是环,e1,e2是多重边。一个不含环和多重边的图称为简单图。含有多重边的图称为多重图。我们这里所说的图,如不特别指明,都是简单图。88在一个图中,若e=(u,v),则称u,v是边以点v为端点的边的条数称为点v的度,记作d(v),如图7.7中d(v1)=3,d(v3)=1。度为零的点称为弧立点,度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点,度为偶数的点称为偶点。不难证明:在一个图中,顶点度数的总和等于边数的2倍,奇顶点的个数必为偶数。
链:由两两相邻的点及其相关联的边构成的点边序列;如:v0
,e1,v1,e2,v2
,e3,v3
,…,vn-1,en
,vn;
v0,vn分别为链的起点和终点;
简单链:链中所含的边均不相同;
初等链:链中所含的点均不相同;圈:在链中,若v0=vn则称该链为圈;连通图:图中任意两点之间均至少有一条链相连
,89以点v为端点的边的条数称为点v的度,记作d(第二节树树是一类结构简单而又十分有用的图。一个不含圈的连通图称为树。设图T=(V,E),含有n个顶点,则下列命题是等价的。(1)T是树。(2)T的任意两顶点之间,有唯一的链相连。(3)T连通且有n-1条边。(4)T无圈且有n-1条边。(5)T无圈但添加一条边得唯一一圈。(6)T连通但去掉一条边则不连通。90第二节树6给定图G=(V,E),若V’
V,E’
E,并且E’中的边的端点都属于V’
,则称G’=(V’,E’)是G的一个子图。特别地,若V’
=
V,则称G’为G的支撑子图。设T是图G的一个支撑子图,若T是一树,则称T是G的一个支撑树。给定图G=(V,E),对于G的每一条边,可赋以一个实数w(e),称为边e的权,图G连同它边上的权称为赋权图。赋权图在图论的应用中经常出现。根据实际问题的需要,权可以有不同的实际含义,它可以表示距离、流量、时间、费用等。91给定图G=(V,E),若V’V给定图G=(V,E),设T=(V,E’)是G的一个支撑树,定义树T的权为即支撑树T上所有边的权的总和。图G的最小支撑树就是图G中权最小的支撑树。求图G的最小支撑树的方法是建立在求图G的支撑树基础上,只需在求图G的支撑树的算法再加适当限制。因此,求最小支撑树方法也有相应的破圈法;避圈法。
92给定图G=(V,E),设T=(V例2分别用破圈法,避圈法求图7.17的最小支撑树。图7.17v1v5v2v3v42v6v7v8343462366458593例2分别用破圈法,避圈法求图7.17的最小支撑树。图7.v1v5v2v3v42v6v7v83434623664585解破圈法94v1v5v2v3v42v6v7v83434623664585v1v5v2v3v42v6v7v83434623664585避圈法:95v1v5v2v3v42v6v7v83434623664585第三节最短路问题最短路问题,一般来说就是从给定的赋权图中,寻找两点之间权最小的链(链的权即链中所有边的权之和)。许多优化问题都需要求图的最短路,如选址、管道铺设、设备更新、整数规划等问题。由于所求问题不同,需要使用不同的方法。下面我们介绍常用的算法。一、Dijkstra算法Dijkstra算法是求赋权有向图中,某两点之间最短路的算法。实际上,它可以求某一点到其它各点的最短路。它是Dijkstra于1959年提出。目前被认为是求非负权最短路的最好的算法。96第三节最短路问题12Dijkstra算法的基本思想是基于以下原理:若vs,vl,…,vj是vs到vj的最短路,vi是此路中某一点,则vs,vl,…,vi必是从vs到vi的最短路。此算法的基本步骤是采用标号法,给图G每一个顶点一个标号。标号分两种:一种是T标号,一种是P标号。T标号也称临时标号,它表示从vs到这一点的最短路长度的一个上界,P标号也称固定标号,它表示从vs到这一点的最短路的长度(这里最短路长度是指这条路上个边权的和)。算法每一步都把某点的T标号改变为P标号。当终点得到P标号,算法结束。若要求某点到其它各点的最短路,则最多经过n-1步算法结束。97Dijkstra算法的基本思想是基于以下原理:设lij表示边(vi,vj)的权,则Dijkstra算法步骤如下:(1)给始点以P标号P(0,0),给其它各点vj以T标号T(dj,v1),其中,dj=l1j,(若vj与v1不相邻,则令l1j=+∞)。(2)在所有T标号点中,若vk的T标号最小,则把vk的T标号改为P标号。若最小的T标号不止一个,则可任取一个改为P标号。(3)修改所有T标号T(dj,vt);dj=min{dj,dk+lkj},若dk+lkj<djvt=vk否则不变。(4)当终点或全部顶点都得到P标号,算法结束,否则返回(2)。98设lij表示边(vi,vj)的权,则Dijkstra算法步骤例3求图7.20中,v1到v8的最短路。图7.20v4v2v1v3v6v5v7v8983834256767109499例3求图7.20中,v1到v8的最短路。图7.20v4图7.20v4v2v1v3v6v5v7v89838342567671094解
P(0,0)T(9,v1)T(3,v1)T(8,v1)100图7.20v4v2v1v3v6v5v7v898383425图7.20v4v2v1v3v6v5v7v89838342567671094解
P(0,0)T(9,v1)T(7,v3)T(3,v1)T(8,v1)P(3,v1)101图7.20v4v2v1v3v6v5v7v898383425图7.20v4v2v1v3v6v5v7v89838342567671094解
P(0,0)T(9,v1)T(7,v3)T(8,v1)P(3,v1)P(7,v3)T(14,v6)T(16,v6)102图7.20v4v2v1v3v6v5v7v898383425图7.20v4v2v1v3v6v5v7v89838342567671094解
P(0,0)T(9,v1)T(8,v1)P(3,v1)P(7,v3)T(14,v6)P(9,v1)P(8,v1)T(17,v2)T(16,v6)103图7.20v4v2v1v3v6v5v7v898383425图7.20v4v2v1v3v6v5v7v89838342567671094解
P(0,0)P(3,v1)P(17,v2)P(7,v3)T(14,v6)P(9,v1)P(8,v1)T(17,v2)T(16,v6)P(14,v6)P(16,v6)104图7.20v4v2v1v3v6v5v7v898383425图7.20v4v2v1v3v6v5v7v89838342567671094解
P(0,0)P(3,v1)P(17,v2)P(7,v3)P(9,v1)P(8,v1)P(14,v6)P(16,v6)105图7.20v4v2v1v3v6v5v7v898383425例4求图7.22中,v1到其它各点的最短路。图7.22v4v2v1v3v6v5v7v8354263441517498Dijkstra算法同样可用于求无向图的最短路。106例4求图7.22中,v1到其它各点的最短路。图7.22v图7.22v4v2v1v3v6v5v7v8354263441517498解
P(0,0)T(3,v1)T(4,v1)T(2,v1)107图7.22v4v2v1v3v6v5v7v835426344图7.22v4v2v1v3v6v5v7v8354263441517498解
P(0,0)T(3,v1)T(4,v1)T(2,v1)P(2,v1)T(7,v4)T(3,v4)P(3,v1)T(8,v2)T(9,v2)108图7.22v4v2v1v3v6v5v7v835426344图7.22v4v2v1v3v6v5v7v8354263441517498解
P(0,0)P(2,v1)T(7,v4)T(3,v4)P(3,v1)T(8,v2)T(9,v2)P(3,v4)T(6,v3)109图7.22v4v2v1v3v6v5v7v835426344图7.22v4v2v1v3v6v5v7v8354263441517498解
P(0,0)P(2,v1)T(7,v4)P(3,v1)T(8,v2)P(3,v4)T(6,v3)P(6,v3)T(7,v6)T(15,v6)110图7.22v4v2v1v3v6v5v7v835426344图7.22v4v2v1v3v6v5v7v8354263441517498解
P(0,0)P(2,v1)T(7,v4)P(3,v1)P(3,v4)P(6,v3)T(7,v6)P(7,v6)T(15,v6)T(11,v5)P(7,v4)111图7.22v4v2v1v3v6v5v7v835426344图7.22v4v2v1v3v6v5v
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 审批监理规划方案
- 幼儿园家长课堂教案教学课件
- 旅游局防控甲型HN流感应急工作方案
- 盆腔炎中医辨证论治
- 基于专利文本分析的技术发展趋势研究-以无人船为例
- 财务年度绩效报告
- 留学历年考试题库及答案
- java前端框架面试题及答案
- 长期静脉灌注的护理查房管理
- 导尿管管理与感染控制措施
- 数据挖掘(第2版)全套教学课件
- 氯化钾口服溶液-药品临床应用解读
- 劳务派遣劳务外包服务方案(技术方案)
- 《扣件式钢管脚手架安全技术规范》JGJ130-2023
- 山西省大同市恒山水库清淤及矿山修复工程
- 王者荣耀卖号合同模板
- VDA6.3-2023版审核检查表
- 保利地产集团-投资发展-东莞城市发展研究框架613课件1
- 20道游标卡尺题目及答案
- 独家(共21套)新人教版九年级化学上册(全册)课时练习 同步练习题汇总+各章思维导图
- 北京协和医院遗体解剖检验同意书
评论
0/150
提交评论