第8讲图与网络优化

运筹学（operationsresearch,OR）

第八讲图与网络优化商学院电子商务系5/7/20241第八讲图与网络优化一.图与树二.最短路问题三.最大流问题5/7/20242一、图与树第八讲图与网络优化

人们为反映一些对象之间关系时，常会用示意图。图的相关概念铁路交通图比赛情况图药品存放图5/7/20243一、图与树第八讲图与网络优化

图是由一些点及一些点之间的连线(不带箭头或带箭头)组成的图形。图的相关概念两点之间不带箭头的连线称为边，带箭头的连线称为弧。如果一个图G由点及边所构成，则称之为无向图(也简称为图)，记为G=（V，E），式中V，E分别是G的点集合和边集合。一条连结点Vi，Vj的边记为[Vi，Vj](或[Vj，Vi])

。如果一个图D由点及弧所构成，则称为有向图，记为D=(V，A)，式中V，A分别表示D的点集合和弧集合。一条方向是从vi指向vj的弧，记为(vi,vj).5/7/20244一、图与树第八讲图与网络优化点的集合：无向图例子边的集合：5/7/20245一、图与树第八讲图与网络优化有向图例子5/7/20246一、图与树第八讲图与网络优化图的相关概念图G或D中的点数记为p(G)或p(D)，边(弧)数记为q(G)(q(D))，分别简记为p，q。若边e=［u，v］∈E，则称u，v是e的端点，也称u，v是相邻的。称e是点u(及点v)的关连边。若图G中，某个边e的两个端点相同，则称e是环(如前图中的e7)。若两个点之间有多于一条的边，称这些边为多重边(如前图中的e1,e2)。5/7/20247一、图与树第八讲图与网络优化图的相关概念一个无环，无多重边的图称为简单图；一个无环，但允许有多重边的图称为多重图。以点v为端点的边的个数称为v的次，记为dG(v)或d(v)。次为奇数的点，称之为奇点；次为偶数的点，称之为偶点。称次为1的点为悬挂点，悬挂点的关连边称为悬挂边，次为零的点称为孤立点。5/7/20248一、图与树第八讲图与网络优化图的相关概念证明：显然，在计算各点的次时，每条边被它的端点各用了一次。定理1图G=(V，E)中，所有点的次之和是边数的两倍，即：5/7/20249一、图与树第八讲图与网络优化图的相关概念定理2任一个图中，奇点的个数为偶数。证明:设V1和V2分别是G中奇点和偶点的集合，由定理1，有：因是偶数，也是偶数，故必定也是偶数，从而V1的点数是偶数。5/7/202410一、图与树第八讲图与网络优化图的相关概念给定一个图G=(V,E)和一个点、边交错序列,如果满足：

(t=1，2，…，k-1)则称为一条联结的链，记为

称点为链的中间点。5/7/202411一、图与树第八讲图与网络优化图的相关概念链中，若，则称之为一个圈，记为。若链中，点都是不同的，则称之为初等链；若圈中，都是不同的，则称之为初等圈。若链(圈)中含的边均不相同，则称之为简单圈。以后说到链(圈)，除非特别交代，均指初等链(圈)。5/7/202412一、图与树第八讲图与网络优化例子是一条简单链，但不是初等链，是一条初等链。是一个初等圈，是简单圈，但不是初等圈。5/7/202413一、图与树第八讲图与网络优化连通图图G中，若任何两点之间至少有一条链，则称G是连通图，否则称为不连通图。若G是不连通图，它的每个连通的部分称为G的一个连通分图(也简称分图)。思考：右图是连通图吗？5/7/202414一、图与树第八讲图与网络优化支撑子图给了一个图G=(V，E)，如果G′=(V′，E′)，使V=V′及E′∈E，则称G′是G的一个支撑子图。设v∈V(G)，用G−v表示从图G中去掉点v及v的关联边后得到的一个图。5/7/202415一、图与树第八讲图与网络优化和有向图有关的概念和术语设给定一个有向图，D=(V，A)，从D中去掉所有弧上的箭头，就得到一个无向图，称之为D的基础图，记之为G(D)。给定D中的一条弧a=(u，v)，称u为a的始点，v为a的终点，称弧a是从u指向v的。设是D中的一个点弧交错序列，如果这个序列在基础图G(D)中所对应的点边序列是一条链，则称这个点弧交错序列是D的一条链。类似定义圈和初等链(圈)。如果是D中的一条链，并且对t=1，2，…，k-1，均有，称之为从的一条路。若路的第一个点和最后一点相同，则称之为回路。类似定义初等路(回路)。5/7/202416一、图与树第八讲图与网络优化例子是一个回路；是从v1到v6的路；是一条链，但不是路。注：对无向图，链与路(圈与回路)两个概念是一致的。5/7/202417一、图与树第八讲图与网络优化树树：一类极其简单然而却很有用的图。树的定义：一个无圈的连通图称为树。5/7/202418一、图与树第八讲图与网络优化树的性质定理3设图G=(V，E)是一个树，p(G)≥2，则G中至少有两个悬挂点。证明:令是G中含边数最多的一条初等链，因p(G)≥2，并且G是连通的，故链P中至少有一条边，从而v1与vk是不同的。现在来证明：v1是悬挂点，即d(v1)=1。

用反证法，如果d(v1)≥2，则存在边且m≠2。若点vm不在P上，那么是G中的一条初等链，它含的边数比P多一条，这与P是含边数最多的初等链矛盾。若点vm在P上，那么是G中的一个圈，这与树的定义矛盾。于是必有d(v1)=1，即v1是悬挂点。同理可证vk也是悬挂点，因而G至少有两个悬挂点。5/7/202419一、图与树第八讲图与网络优化树的性质定理4图G=(V，E)是一个树的充分必要条件是G不含圈，且恰有p−1条边。证明：必要性。设G是一个树，根据定义，G不含圈，故只要证明G恰有p−1条边。对点数p施行数学归纳法。p=1，2时，结论显然成立。假设对点数p≤n时，结论成立。设树G含n+1个点。由定理3，G含悬挂点，设v1是G的一个悬挂点，考虑图G−v1，易见p(G−v1)=n，q(G−v1)=q(G)−1。因G−v1是n个点的树，由归纳假设，q(G−v1)=n−1，于是q(G)=q(G−v1)+1=(n−1)+1=n=p(G)−1。5/7/202420一、图与树第八讲图与网络优化树的性质定理4图G=(V，E)是一个树的充分必要条件是G不含圈，且恰有p−1条边。证明：充分性。只要证明G是连通的。用反证法，设G是不连通的，G含s个连通分图G1，G2，…，Gs(s≥2)。因每个Gi(i=1，2，…，s)是连通的，并且不含圈，故每个Gi是树。设Gi有pi个点，则由必要性，Gi有pi−1条边，于是这与q(G)=p(G)−1的假设矛盾。5/7/202421一、图与树第八讲图与网络优化树的性质定理5图G是树的充分必要条件是任意两个顶点之间恰有一条链。

证明必要性。因G是连通的，故任两个点之间至少有一条链。但如果某两个点之间有两条链的话，那么图G中含有圈，这与树的定义矛盾，从而任两个点之间恰有一条链。充分性：设图G中任两个点之间恰有一条链，那么易见G是连通的。如果G中含有圈，那么这个圈上的两个顶点之间有两条链，这与假设矛盾，故G不含圈，于是G是树。5/7/202422一、图与树第八讲图与网络优化树的性质由定理5，很容易推出如下结论：

(1)从一个树中去掉任意一条边，则余下的图是不连通的。由此可知，在点集合相同的所有图中，树是含边数最少的连通图。

(2)在树中不相邻的两个点间添上一条边，则恰好得到一个圈。进一步地说，如果再从这个圈上任意去掉一条边，可以得到一个树。5/7/202423一、图与树第八讲图与网络优化树的性质定义

设图T=(V，E′)是图G=(V，E)的支撑子图，如果图T=(V，E′)是一个树，则称T是G的一个支撑树。若T=(V，E′)是G=(V，E)的一个支撑树，则显然，树T中边的个数是p(G)−1，G中不属于树T的边数是q(G)−p(G)+1。5/7/202424一、图与树第八讲图与网络优化树的性质定理6图G有支撑树的充分必要条件是图G是连通的。证明：必要性是显然的。充分性。设图G是连通图，如果G不含圈，那么G本身是一个树，从而G是它自身的一个支撑树。现设G含圈，任取一个圈，从圈中任意地去掉一条边，得到图G的一个支撑子图G1。如果G1不含圈，那么G1是G的一个支撑树(因为易见G1是连通的)；如果G1仍含圈，那么从G1中任取一个圈，从圈中再任意去掉一条边，得到图G的一个支撑子图G2，如此重复，最终可以得到G的一个支撑子图Gk，它不含圈，于是Gk是G的一个支撑树。思考：该定理的充分性证明有什么作用？5/7/202425一、图与树第八讲图与网络优化最小支撑树问题这里所说的“权”，是指与边有关的数量指标。根据实际问题的需要，可以赋予它不同的含义，如表示距离、时间、费用等。赋权图被广泛应用于工程技术及科学生产管理等领域的最优化问题。最小支撑树问题就是赋权图上的最优化问题之一。定义

给图G=(V，E)，对G中的每一条边，相应地有一个数wij，则称这样的图G为赋权图，wij称为边上的权。5/7/202426一、图与树第八讲图与网络优化最小支撑树问题设有一个连通图G=(V，E)，每一边e=，有一个非负权：w(e)=wij(wij≥0)定义

如果T=(V，E′)是G的一个支撑树，称E′中所有边的权之和为支撑树T的权，记为w(T)。即：如果支撑树T*

的权w(T*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树(简称最小树)。即5/7/202427一、图与树第八讲图与网络优化最小支撑树问题

1.避圈法：从图中任取一点令，图中其余的点都在中；从与的连线中找出最小边，这条边一定在最小支撑树内，不停重复，一直到图中所有点均包含在V中为止。

2.破圈法：任取一个圈，从圈中去掉一条权最大的边(如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条)。在余下的图中，重复这个步骤，直至得到一个不含圈的图为止，这时的图便是最小树。下面介绍两个求解最小支撑树的方法。5/7/202428例：如图S,A,B,C,D,E,T代表村镇,村镇之间的连线上赋予了权值(可代表距离,费用,流量等)现沿图中连线架设电线,使各村镇全部通电,问如何架设使电线总长最短.(该图称为赋权图或无向网络).第八讲图与网络优化5/7/202429最小支撑树总长=2+2+1+3+1+5=14第八讲图与网络优化5/7/202430电线总长=2+2+1+3+1+5=145/7/202431二、最短路问题第八讲图与网络优化引例

已知如下图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用。现在某人要从v1出发，通过这个交通网到v8去，求总费用最小的旅行路线。5/7/202432二、最短路问题第八讲图与网络优化引例结论1：由上例可见，从v1到v8的旅行路线有很多；结论2：不同的路线所需总费用是不同的；结论3：用图的语言来描述，从v1到v8的一条旅行路线就是图中从v1到v8的一条路；一条旅行路线的总费用就是相应的从v1到v8的路中所有弧旁数字之和。5/7/202433二、最短路问题第八讲图与网络优化一般意义的最短路问题

给定一个赋权有向图，即给了一个有向图D=(V，A)，对每一个弧a=(vi，vj)，相应地赋予了权数；又给定D中的两个顶点vs，vt。设P是D中从vs到vt的一条路，定义路P的权是P中所有弧的权之和，记为w(P)。最短路问题就是要在所有从vs到vt的路中，求一条权最小的路，即求一条从vs到vt的路P0，使：上式中对D中所有从vs到vt的路P取最小，称P0是从vs到vt的最短路。路P0的权称为从vs到vt的距离，记为d(vs，vt)。显然，d(vs，vt)与d(vt，vs)不一定相等。5/7/202434二、最短路问题第八讲图与网络优化最短路算法

Dijkstra算法的基本思想：从vs出发，逐步向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短路的权(称为P标号)，或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，这样，至多经过p−1步，就可以求出从vs到各点的最短路。5/7/202435二、最短路问题第八讲图与网络优化Dijkstra算法

P，T分别表示某个点的P标号、T标号，

为了在求出从vs到各点的距离的同时，也求出从vs到各点的最短路，给每个点v以一个λ值。算法终止时，如果λ(v)=vm，表示在从vs到v的最短路上，v的前一个点是vm；λ(v)=0表示v=vs。5/7/202436二、最短路问题第八讲图与网络优化例题

用Dijkstra方法求前例中从v1到各个顶点的最短路？标P(v1)=0。其余点标T(vi)=+∞，i＝2，3，…，9；T(v2)＝min｛+∞，0＋6｝＝6，λ(v2)=v1；T(v3)＝min｛+∞，0＋3｝＝3，λ(v3)=v1；T(v4)＝min｛+∞，0＋1｝＝1，λ(v4)=v1；将具有最小T标号的v4点的标号改为P标号：P(v4)＝1；T(v6)＝min｛+∞，1＋10｝＝11，λ(v6)=v4；将具有最小T标号的v3点的标号改为P标号：P(v3)＝3；T(v2)＝min｛6，3＋2｝＝5，λ(v2)=v3；将具有最小T标号的v2点的标号改为P标号：P(v2)＝5；5/7/202437例题

用Dijkstra方法求前例中从v1到各个顶点的最短路？T(v5)＝min｛+∞，5＋1｝＝6，λ(v5)=v2；将具有最小T标号的v5点的标号改为P标号：P(v5)＝6；T(v6)＝min｛11，6＋4｝＝10，λ(v6)=v5；T(v7)＝min｛+∞，6＋3｝＝9，λ(v7)=v5；T(v8)＝min｛+∞，6＋6｝＝12，λ(v8)=v5；将具有最小T标号的v7点的标号改为P标号：P(v7)＝9；T(v8)＝min｛12，9＋4｝＝12，λ(v8)=v5；将具有最小T标号v6点的标号改为P标号：P(v6)＝11；将具有最小T标号v8点的标号改为P标号：P(v8)＝12；5/7/202438二、最短路问题第八讲图与网络优化Dijkstra算法缺陷

Dijkstra算法只适用于所有wij≥0的情形，当赋权有向图中存在负权时，则算法失效。例如在下图所示的赋权有向图中，如果用Dijkstra方法，可得出从v1到v2的最短路的权是1，但这显然是不对的，因为从v1到v2的最短路是(v1，v3，v2)，权是-1。5/7/202439二、最短路问题第八讲图与网络优化练习题V1V2V3V4V5V6V798528737143105/7/202440二、最短路问题第八讲图与网络优化

Dijkstra算法另一种写法初始值第一次

第二次第三次第四次T（）{0}

∞

∞∞∞∞∞∞∞P（）+wijT（）P（）+wijT（）P（）+wijT（）P（）+wijT（）0+60+30+10+∞0+∞0+∞0+∞0+∞{1}36∞∞∞∞∞1+101+∞1+∞1+∞1+∞1+∞1+∞6{3}∞11∞∞∞3+23+∞3+∞3+∞3+∞3+∞{5}∞11∞∞∞5+15+∞5+∞5+∞5+∞{6}11∞∞∞5/7/202441二、最短路问题第八讲图与网络优化

Dijkstra算法另一种写法初始值第五次

第六次第七次第八次T（）11∞∞∞P（）+wijT（）P（）+wijT（）P（）+wijT（）P（）+wijT（）{6}6+46+36+66+∞10{9}∞129+49+∞9+∞{10}10+∞10+∞{12}∞5/7/202442二、最短路问题第八讲图与网络优化迭代算法迭代算法是当赋权有向图中存在具负权弧时，求最短路的方法。

为方便起见，不妨设从任一点vi到任一个点vj都有一条弧(如果在D中，，则添加弧(vi，vj)。令wij=+∞)。

显然，从vs到vj的最短路总是从vs出发，沿着一条路到某个点vi，再沿(vi，vj)到vj的(这里vi可以是vs本身)，明显可知，从vs到vi的这条路必定是从vs到vi的最短路，所以d(vs，vj)必满足如下方程：5/7/202443二、最短路问题第八讲图与网络优化迭代算法

为了求得这个方程的解d(vs，v1)，d(vs，v2)，…，d(vs，vp)，可用如下递推公式：开始时，令：,(j=1，2，…，p)对t=2,…3,

，j=1，2，…，p若进行到某一步，例如第k步时，对所有j=1，2，…，p，有：则，即为vs到各点的最短路的权。5/7/202444二、最短路问题第八讲图与网络优化迭代算法例题求右图所示赋权有向图中从v1到各点的最短路。5/7/202445二、最短路问题第八讲图与网络优化迭代算法例题到从V1V2V3V4V5V6V7V8t=1t=2t=3t=4V10-1-23V2602V3-30-51V4802V5-10V61017V7-10V8-3-500-1-230-5-2-71-150-5-2-7-3-1-50-5-2-7-3-1-5665/7/202446第八讲图与网络优化三、最大流问题流(Flow)就是将目标由一个地点运送到另一个地点.如:公路中的交通流,控制系统中的信息流,供水系统中的水流,金融系统中的现金流,邮政系统中的信件流,等等.它们的共同问题是,希望经过输送系统,将目标从一个地点运送到另一个地点的运输量最大,或者将一定数量的目标在该系统中从一个地点输送到另一个地点的费用最小.这就是网络中的最大流问题和最小费用最大流问题.5/7/202447容量网络是指对网络上的每一条弧,都给出一个最大的通过能力,称为该弧的容量,记为或简记为,这样的网络称为容量网络.

在容量网络中规定一个发点(源点)s和一个收点(汇点)t,其余的点称为中间点.

网络的最大流是指:网络中从发点到收点之间允许通过的最大流量.第八讲图与网络优化

1、最大流问题相关概念5/7/202448第八讲图与网络优化我们只研究一个发点和一个收点的情况.对于多个发点和多个收点的情况可将若干个发点合并为一个新的发点对于收点也如此处理.5/7/202449流（flow）是指加在网络上的一组负载.对加在弧上的流,记为或简记为,当时称为零流.可行流（feasibleflow）：在容量网络上满足下列三个条件的一组流称为可行流：容量限制条件:对所有的弧有(2)中间点平衡条件:(3)若以v(f)表示网络中从s到t的净输出量,则有流和可行流:5/7/202450第八讲图与网络优化任何容量网络上一定存在可行流,因为零流就是可行流.所谓求网络最大流,就是指在满足容量限制条件和中间点平衡条件下,使v(f)值达到最大.5/7/202451增广链:如果在网络的发点和收点之间能找出一条链,在这条链上所有的指向为s→t的弧(称为前向弧,记为),存在f<c;所有指向为t→s的弧(称为后向弧,记为),存在f>0,这样的链称为增广链.为加在弧上的负载,是弧上的容量.第八讲图与网络优化5/7/202452当有增广链时,找出再令显然仍是一个可行流,与原来的可行流比较发现,网络中从s→t的流量增大了一个值(>0).因此,只有当网络中找不到增广链时,s→t的流才不可能进一步增大.第八讲图与网络优化5/7/202453在下图中,弧旁的数据格式为：截集：将容量网络中的发点和收点分割开,使s到t的流中断的一个弧集合.截集和截量5/7/202454截集的截量:截集的弧集合中各弧的容量之和,用表示,显然,截集截量

15

21

17

18

19

24

14

25

255/7/202455最大流量最小截集定理：任一网络D中，从到的最大流的流量等于分离和的最小截集的容量。第八讲图与网络优化5/7/202456求网络最大流的标号法该算法是由Ford和Fulker