图论与网络.ppt

图与网络分析v图论运筹学,组合数学，离散数学的重要分支主要应用领域o物理学、化学、控制论、信息论、科学管理、电子计算机等图论理论和方法应用实例o在组织生产中，为完成某项生产任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。o一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。o各种通信网络的合理架设，交通网络的合理分布等问题，应用图论的方法求解都很简便。1六、图与网络分析v图论的起源与发展欧拉在1736年发表了图论方面的第一篇论文，解决了著名的哥尼斯堡七桥问题。七桥问题：o哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上有七座桥。当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。图10-1(a)欧拉将此问题归结为如图10-1(b)所示图形的一笔画问题。即能否从某一点开始，不重复地一笔画出这个图形，最后回到出发点。欧拉证明了这是不可能的，因为图10-1(b)中的每个点都只与奇数条线相关联，不可能将这个图不重复地一笔画成。图10-12 图与网络优化n第1节 图的基本概念n第2节 树n第3节 最短路问题n第4节 网络最大流问题n第5节 最小费用最大流问题n第6节 中国邮递员问题3第1节 图的基本概念v人们为反映一些对象之间关系时，常会用示意图。例1 下图是我国北京、上海等十个城市间的铁路交通图，反映了这十个城市间的铁路分布情况。这里用点代表城市，用点和点之间的连线代表这两个城市之间的铁路线。其他示意图的例子o电话线分布图、煤气管道图、航空线图等。铁路交通图铁路交通图4第1节 图的基本概念v例2 有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况用图表示出来。已知甲队和其他各队都比赛过一次，乙队和甲、丙队比赛过，丙队和甲、乙、丁队比赛过，丁队和甲、丙、戊队比赛过，戊队和甲、丁队比赛过。为了反映这个情况，可以用点 分别代表这五个队，某两个队之间比赛过，就在这两个队所相应的点之间联一条线，这条线不过其他的点，如图10-3所示。比赛情况图比赛情况图图10-35第1节 图的基本概念v例3 某单位储存八种化学药品，其中某些药品是不能存放在同一个库房里的。用点 分别代表这八种药品，若药品vi和药品vj是不能存放在同一个库房的，则在vi和vj之间联一条线。从这个图中可以看到，至少要有四个库房，因为 必须存放在不同的库房里。事实上，四个库房就足够了。例如 各存放在一个库房里(这一类寻求库房的最少个数问题，属于图论中的所谓染色问题，一般情况下是尚未解决的)。药品存放图药品存放图6第1节 图的基本概念v图：由点及点与点的连线构成，反映了实际生活中某些对象之间的某些特定关系点：代表研究的对象；连线：表示两个对象之间特定的关系。v图：是反映对象之间关系的一种抽象一般情况下，图中点的相对位置如何，点与点之间连线的长短曲直，对反映对象之间的关系并不重要。o如例2，也可以用图10-5所示的图去反映五个球队的比赛情况，与图10-3没有本质区别。比赛情况图比赛情况图图10-57第1节 图的基本概念v关系的对称性和非对称性：几个例子中涉及到的对象之间的“关系”具有“对称性”，就是说，如果甲与乙有这种关系，那么同时乙与甲也有这种关系。实际生活中，有许多关系不具有这种对称性。o如例2，如果人们关心的是五个球队比赛的胜负情况，那么从图10-3中就看不出来了。为了反映这一类关系，可以用一条带箭头的连线表示。o例如，如果球队v1胜了球队v2，可以从v1引一条带箭头的连线到v2o类似胜负这种非对称性的关系，在生产和生活中是常见的，如交通运输中的“单行线”，部门之间的领导与被领导的关系，一项工程中各工序之间的先后关系等。比赛胜负图比赛胜负图8第1节 图的基本概念v图的概念图是由一些点及一些点之间的连线(不带箭头或带箭头)组成的图形。两点之间不带箭头的连线称为边边，带箭头的连线称为弧弧。如果一个图G由点及边所构成，则称之为无向无向图图(也简称为图)，记为 ，式中V，E分别是G的点集合和边集合。一条连结点 的边记为 (或 )。如果一个图D由点及弧所构成，则称为有向有向图图，记为D=(V，A)，式中V，A分别表示D的点集合和弧集合。一条方向是从vi指向vj的弧，记为()。9第1节 图的基本概念v无向图的例子 其中无向图无向图图10-710第1节 图的基本概念v有向图的例子 其中有向图有向图图10-811第1节 图的基本概念v图的重要概念（续）图G或D中的点数记为p(G)或p(D)，边(弧)数记为q(G)(q(D)，分别简记为p，q。无向图G=(V，E)常用的一些名词和记号：若边e=u，vE，则称u，v是e的端点，也称u，v是相邻的。称e是点u(及点v)的关连边。若图G中，某个边e的两个端点相同，则称e是环(如图10-7中的e7)。若两个点之间有多于一条的边，称这些边为多重多重边边(如图10-7中的e1,e2)。12第1节 图的基本概念v图论中几个重要记号和术语图G或D中的点数记为p(G)或p(D)，边(弧)数记为q(G)或 q(D)，分别简记为p，q。无向图G=(V，E)常用的一些名词和记号：o若边e=u，vE，则称u，v是e的端点端点，也称u，v是相相邻邻的的。称e是点u(及点v)的关关连边连边。o若图G中，某个边e的两个端点相同，则称e是环(如图10-7中的e7)。o若两个点之间有多于一条的边，称这些边为多重多重边边(如图10-7中的e1,e2)。13第1节 图的基本概念v图论中几个重要记号和术语（续）一个无环，无多重边的图称为简单图简单图；一个无环，但允许有多重边的图称为多重多重图图。以点v为端点的边的个数称为v的次（度）次（度），记为dG(v)或d(v)。如图10-7中，d(v1)=4，d(v2)=3，d(v3)=3，d(v4)=4(环e7在计算d(v4)时算作两次)。称次为1的点为悬悬挂点挂点，悬挂点的关连边称为悬悬挂挂边边，次为零的点称为孤立点孤立点。14v定理定理1 图G=(V，E)中，所有点的次之和是边数的两倍，即第1节 图的基本概念证明证明：显然，在计算各点的次时，每条边被它的端点各用了一次。次为奇数的点，称为奇点奇点，否则称为偶点偶点。15第1节 图的基本概念v定理定理2 任一个图中，奇点的个数为偶数。证证明明:设V1和V2分别是G中奇点和偶点的集合，由定理1，有因 是偶数，也是偶数，故 必定也是偶数，从而V1的点数是偶数。16 则称为一条联结 的链链，记为 称点 为链的中间点中间点。v图论中几个重要记号和术语（续）给定一个图G=(V,E)和一个点、边交错序列 ,如果满足第1节 图的基本概念 (t=1，2，k-1)17v图论中几个重要记号和术语（续）链 中，若 ，则称之为一个圈圈，记为 。若链 中，点 都是不同的，则称之为初等链初等链；若圈 中，都是不同的，则称之为初等圈初等圈。若链(圈)中含的边均不相同，则称之为简简单圈单圈。以后说到链(圈)，除非特别交代，均指初等链(圈)。第1节 图的基本概念18v例子图10-9中，是一条简单链，但不是初等链，是一条初等链。图中不存在联结v1和v9的链。是一个初等圈，是简单圈，但不是初等圈。第1节 图的基本概念初等链初等链与与初等圈初等圈图10-919第1节 图的基本概念v连通图图G中，若任何两点之间至少有一条链，则称G是连通连通图图，否则称为不连通图不连通图。若G是不连通图，它的每个连通的部分称为G的一个连连通分图通分图(也简称分图分图)。图10-9是一个不连通图，它有两个连通分图。20第1节 图的基本概念v支撑子图给了一个图G=(V，E)，如果G=(V，E)，使V=V及EE，则称G是G的一个支撑子支撑子图图。设vV(G)，用Gv表示从图G中去掉点v及v的关联边后得到的一个图。若G如图10-10(a)所示，则G v3见图10-10(b)，图10-10(c)是图G的一个支撑子图。图10-10 21v和有向图有关的概念和术语设给定一个有向图，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，均有 ，称之为从 的一条路。若路的第一个点和最后一点相同，则称之为回路。类似定义初等路(回路)。第1节 图的基本概念22v有向图的例子图10-8。是一个回路；是从v1到v6的路；是一条链，但不是路。第1节 图的基本概念v对无向图，链与路对无向图，链与路(圈与回路圈与回路)两个概念是一致的。两个概念是一致的。v类似于无向图，可定义简单有类似于无向图，可定义简单有向图、多重有向图。向图、多重有向图。v图图10-8是一个简单有向图。是一个简单有向图。23 定义 设X,Y 都是非空有限集,且XY=,E xy|xX,yY,称G=(X,Y,E)为二部图.二部图可认为是有限简单无向图.如果X中的每个点都与Y中的每个点邻接,则称G=(X,Y,E)为完备二部图.若F：ER+,则称G=(X,Y,E,F)为二部赋权图.二部赋权图的权矩阵一般记作 A=(aij)|X|Y|,其中aij=F(xi yj).24 定义 设G=(X,Y,E)为二部图,且M E.若M中任意两条边在G中均不邻接,则称M是二部图G的一个匹配.定义 设M是二部图G的一个匹配,如果G的每一个点都是M中边的顶点,则称M是二部图G的完美匹配；如果G中没有另外的匹配M0,使|M0|M|,则称M是二部图G的最大匹配.在二部赋权图G=(X,Y,E,F)中,权数最大的最大匹配M称为二部赋权图G的最佳匹配.显然,每个完美匹配都是最大匹配,反之不一定成立.25工作安排问题之一 给n个工作人员x1,x2,xn安排n项工作y1,y2,yn.n个工作人员中每个人能胜任一项或几项工作,但并不是所有工作人员都能从事任何一项工作.比如x1能做y1,y2工作,x2能做y2,y3,y4工作等.这样便提出一个问题,对所有的工作人员能不能都分配一件他所能胜任的工作？我们构造一个二部图G=(X,Y,E),这里X=x1,x2,xn,Y=y1,y2,yn,并且当且仅当工作人员xi胜任工作yj时,xi与yj才相邻.于是,问题转化为求二部图的一个完美匹配.因为|X|=|Y|,所以完美匹配即为最大匹配.(匈牙利算法)26工作安排问题之二 给n个工作人员x1,x2,xn安排n项工作y1,y2,yn.如果每个工作人员工作效率不同,要求工作分配的同时考虑总效率最高.我们构造一个二部赋权图G=(X,Y,E,F),这里X=x1,x2,xn,Y=y1,y2,yn,F(xi yj)为工作人员xi胜任工作yj时的工作效率.（Kuhn和 Munkas给出算法，简称 KM算法）27 定义1 设图G=(V,E),KV如果图G的每条边都至少有一个顶点在K中,则称K是G的一个点覆盖.若G的一个点覆盖中任意去掉一个点后不再是点覆盖,则称此点覆盖是G的一个极小点覆盖.顶点数最少的点覆盖,称为G的最小点覆盖.v0,v2,v3,v5,v6等都是极小点覆盖.v0,v1,v3,v5,v0,v2,v4,v6都是最小点覆盖.例如,右图中,28图的矩阵表示 邻接矩阵 邻接矩阵表示了点与点之间的邻接关系.一个n阶图G的邻接矩阵A=(aij)nn,其中29无向图G的邻接矩阵A是一个对称矩阵.30 权矩阵 一个n阶赋权图G=(V,E,F)的权矩阵A=(aij)nn,其中 31无向图G的权矩阵A是一个对称矩阵.32 关联矩阵 一个有m条边的n阶有向图G的关联矩阵A=(aij)nm,其中 若vi是ej的始点;若vi是ej的终点;若vi与ej不关联.有向图的关联矩阵每列的元素中有且仅有一个1,有 仅有一个-1.33 一个有m条边的n阶无向图G的关联矩阵A=(aij)nm,其中 若vi与ej关联;若vi与ej不关联.无向图的关联矩阵每列的元素中有且仅有两个1.34问题 一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过河到河东.由于船小,一次只能带一物过河，并且狼与羊,羊与菜不能独处.给出渡河的所有方案.35第2节 树v2.1 树及其性质v2.2 图的支撑树v2.3 最小支撑树问题36v树：一类极其简单然而却很有用的图。v例4 已知有五个城市，要在它们之间架设电话线，要求任何两个城市都可以互相通话(允许通过其他城市)，并且电话线的根数最少。图10-112.1 树及其性质372.1 树及其性质v用五个点v1，v2，v3，v4，v5代表五个城市，如果在某两个城市之间架设电话线，则在相应的两个点之间连一条边，这样一个电话线网就可以用一个图来表示。为了使任何两个城市都可以通话，这样的图必须是连通的。其次，若图中有圈的话，从圈上任意去掉一条边，余下的图仍是连通的，这样可以省去一根电话线。因而，满足要求的电话线网所对应的图必定是不含圈的连通图。图10-11代表了满足要求的一个电话线网。382.1 树及其性质v定义定义1（树的定义）（树的定义）一个无圈的连通图称为树。v例例5 某工厂的组织机构如下所示工厂组织机构图工厂组织机构图392.1 树及其性质v如果用图表示，该工厂的组织机构图就是一个树(如图10-12所示)。树树图10-1240v定理定理3 设图G=(V，E)是一个树，p(G)2，则G中至少有两个悬挂点。证证明明:令 是G中含边数最多的一条初等链，因p(G)2，并且G是连通的，故链P中至少有一条边，从而v1与vk是不同的。现在来证明：v1是悬挂点，即d(v1)=1。用反证法，如果d(v1)2，则存在边 使m2。若点vm不在P上，那么 是G中的一条初等链，它含的边数比P多一条，这与P是含边数最多的初等链矛盾。若点vm在P上，那么 是G中的一个圈，这与树的定义矛盾。于是必有d(v1)=1，即v1是悬挂点。同理可证vk也是悬挂点，因而G至少有两个悬挂点。2.1 树及其性质412.1 树及其性质v定理定理4 图G=(V，E)是一个树的充分必要条件是G不含圈，且恰有p1条边。证证明明：必要性。设G是一个树，根据定义，G不含圈，故只要证明G恰有p 1条边。对点数p施行数学归纳法。p=1，2时，结论显然成立。假设对点数pn时，结论成立。设树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=(n1)+1=n=p(G)1。充分性。只要证明G是连通的。用反证法，设G是不连通的，G含s个连通分图G1，G2，Gs(s2)。因每个Gi(i=1，2，s)是连通的，并且不含圈，故每个Gi是树。设Gi有pi个点，则由必要性，Gi有pi 1条边，于是 这与q(G)=p(G)1的假设矛盾。42v定理定理5 图G=(V，E)是一个树的充分必要条件是G是连通图，并且q(G)=p(G)1证证明：明：必要性。设G是树，根据定义，G是连通图，由定理4，q(G)=p(G)1。充分性。只要证明G不含圈，对点数施行归纳。p(G)=1，2时，结论显然成立。设p(G)=n(n1)时结论成立。现设p(G)=n+1，首先证明G必有悬挂点。若不然，因G是连通的，且p(G)2，故对每个点vi，有d(vi)2。从而这与q(G)=p(G)1矛盾，故G必有悬挂点。设v1是G的一个悬挂点，考虑Gv1，这个图仍是连通的，q(G v1)=q(G)1=p(G)2=p(G v1)1，由归纳假设知G v1不含圈，于是G也不含圈。2.1 树及其性质432.1 树及其性质v定理定理6 图G是树的充分必要条件是任意两个顶点之间恰有一条链。证明证明 必要性。因G是连通的，故任两个点之间至少有一条链。但如果某两个点之间有两条链的话，那么图G中含有圈，这与树的定义矛盾，从而任两个点之间恰有一条链。充分性。设图G中任两个点之间恰有一条链，那么易见G是连通的。如果G中含有圈，那么这个圈上的两个顶点之间有两条链，这与假设矛盾，故G不含圈，于是G是树。442.1 树及其性质v由定理6，很容易推出如下结论：(1)从一个树中去掉任意一条边，则余下的图是不连通的。由此可知，在点集合相同的所有图中，树是含边数最少的连通图。这样，例4中所要求的电话线网就是以这五个城市为点的一个树。(2)在树中不相邻的两个点间添上一条边，则恰好得到一个圈。进一步地说，如果再从这个圈上任意去掉一条边，可以得到一个树。如图10-11中，添加 ，就得到一个圈 ，如果从这个圈中去掉一条边 ，就得到如图10-13所示的树。图10-13452.2 图的支撑树v定义定义2 设图T=(V，E)是图G=(V，E)的支撑子图，如果图T=(V，E)是一个树，则称T是G的一个支撑树。图10-14(b)是图10-14(a)所示图的一个支撑树支撑树。图10-14462.2 图的支撑树v若T=(V，E)是G=(V，E)的一个支撑树，则显然，树T中边的个数是p(G)1，G中不属于树T的边数是q(G)p(G)+1。472.2 图的支撑树v定理定理7 图G有支撑树的充分必要条件是图G是连通的。证证明：明：必要性是显然的。充分性。设图G是连通图，如果G不含圈，那么G本身是一个树，从而G是它自身的一个支撑树。现设G含圈，任取一个圈，从圈中任意地去掉一条边，得到图G的一个支撑子图G1。如果G1不含圈，那么G1是G的一个支撑树(因为易见G1是连通的)；如果G1仍含圈，那么从G1中任取一个圈，从圈中再任意去掉一条边，得到图G的一个支撑子图G2，如此重复，最终可以得到G的一个支撑子图Gk，它不含圈，于是Gk是G的一个支撑树。定理定理7充分性的证明，提供了一个寻求连通图的支撑树的充分性的证明，提供了一个寻求连通图的支撑树的方法。这就是任取一个圈，从圈中去掉一边，对余下的方法。这就是任取一个圈，从圈中去掉一边，对余下的图重复这个步骤，直到不含圈时为止，即得到一个支撑图重复这个步骤，直到不含圈时为止，即得到一个支撑树，称这种方法为树，称这种方法为“破圈法破圈法”。482.2 图的支撑树v例例6 在图10-15中，用破圈法求出图的一个支撑树。解解 取一个圈 ，从这个圈中去掉边 ；在余下的图中，再取一个圈 ，去掉边 ；在余下的图中，从圈 中去掉边；再从圈中去掉边 。这时，剩余的图中不含圈，于是得到一个支撑树，如图10-15中粗线所示。也可以用另一种方法来寻求连通图的支撑树。在图中任取一条边e1，找一条与e1不构成圈的边e2，再找一条 与不构成圈的边e3，一般，设已有 ，找一条与 中的任何一些边不构成圈的边ek+1。重复这个过程，直到不能进行为止。这时，由所有取出的边所构成的图是一个支撑树，称这种方法为“避圈法”。492.2 图的支撑树图10-16图10-15502.3 最小支撑树问题v例例7 在图10-16中，用避圈法求出一个支撑树。解解 首先任取边e1，因e2与e1不构成圈，所以可以取e2，因为e5与 不构成圈，故可以取e5(因e3与 构成一个圈 ，所以不能取e3)；因e6与 不构成圈，故可取e6；因e8与 不构成圈，故可取e8(注意，因e7与 中的e5，e6构成圈 ，故不能取e7)。这时由 所构成的图就是一个支撑树，如图10-16中粗线所示。实际上，由定理4，5可知，在“破圈法”中去掉的边数必是q(G)p(G)+1条，在“避圈法”中取出的边数必定是p(G)1条。512.3 最小支撑树问题v定定义义3 给图G=(V，E)，对G中的每一条边 ，相应地有一个数wij，则称这样的图G为赋权图，wij称为边 上的权。这里所说的“权”，是指与边有关的数量指标。根据实际问题的需要，可以赋予它不同的含义，如表示距离、时间、费用等。赋权图在图的理论及其应用方面有重要的地位。赋权图不仅指出了各点之间的邻接关系，而且同时也表示了各点之间的数量关系。所以，赋权图被广泛应用于工程技术及科学生产管理等领域的最优化问题。最小支撑树问题就是赋权图上的最优化问题之一。522.3 最小支撑树问题v设有一个连通图G=(V，E)，每一边e=，有一个非负权 w(e)=wij(wij 0)v定定义义4 如果T=(V，E)是G的一个支撑树，称E中所有边的权之和为支撑树T的权，记为w(T)。即v如果支撑树T*的权w(T*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树(简称最小树)。即 式中对G的所有支撑树T取最小。532.3 最小支撑树问题v最小支撑树问题p最小支撑树问题就是要求给定连通赋权图G的最小支撑树。p例子假设给定一些城市，已知每对城市间交通线的建造费用。要求建造一个联结这些城市的交通网，使总的建造费用最小，这个问题就是赋权图上的最小树问题。p下面介绍两个求解最小支撑树的方法。542.3 最小支撑树问题1.避圈法(kruskal)v开始选一条最小权的边，以后每一步中，总从与已选边不构成圈的那些未选边中，选一条权最小的。(每一步中，如果有两条或两条以上的边都是权最小的边，则从中任选一条)。v算法的具体步骤如下：第1步：令i=1，。第2步：选一条边 ，使ei是使 不含圈的所有边e()中权最小的边。令 ，如果这样的边不存在，则T=(V，Ei-1)是最小树。第3步：把i换成i+1，转入第2步。552.3 最小支撑树问题v在证明这个方法的正确性之前，先介绍一个例子。v例例8 某工厂内联结六个车间的道路网如图10-17(a)所示。已知每条道路的长，要求沿道路架设联结六个车间的电话线网，使电话线的总长最小。562.3 最小支撑树问题v解解 这个问题就是求如图10-17(a)所示的赋权图上的最小树，用避圈法求解。i=1,E0=，从E中选最小权边v2，v3，E1=v2，v3；i=2,从EE1中选最小权边v2，v4(v2，v4与v2，v3不构成圈)，E2=v2，v3，v2，v4；i=3，从EE2中选v4，v5(V，E2v4，v5)不含圈)，令E3=v2，v3，v2，v4，v4，v5；i=4，从EE3中选v5，v6(或选v4，v6)(V，E3v5，v6)不含圈)，令E4=v2，v3，v2，v4，v4，v5，v5，v6；i=5，从EE4中选v1，v2(V，E4v1，v2)不含圈)。注意，因v4，v6与已选边v4，v5，v5，v6构成圈，所以虽然v4，v6的权小于v1，v2的权，但这时不能选v4，v6)，令E5=v2，v3，v2，v4，v4，v5，v5，v6，v1，v2；i=6，这时，任一条未选的边都与已选的边构成圈，所以算法终止。(V，E5)就是要求的最小树，即电话线总长最小的电话线网方案(图10-17(b)，电话线总长为15单位。572.3 最小支撑树问题v证明避圈法的正确性。v令G=(V，E)是连通赋权图，根据2.2中所述可知：方法一终止时，T=(V，Ei-1)是支撑树，并且这时i=p(G)。记E(T)=e1，e2，ep-1 式中p=p(G)，T的权为 582.3 最小支撑树问题v反证法：设T不是最小支撑树，在G的所有支撑树中，令H是与T的公共边数最大的最小支撑树。因T与H不是同一个支撑树，故T中至少有一条边不在H中。令ei(1ip-1)是第一个不属于H的边，把ei放入H中，必得到一个且仅一个圈，记这个圈为C。因为T是不含圈的，故C中必有一条边不属于T，记这条边为e。在H中去掉e，增加ei，就得到G的另一个支撑树T0，可见v因为 (因H是最小支撑树)，推出 。但根据算法，ei是使(V,e1，e2，ei)不含圈的权最小的边，而(V,e1，e2，ei-1，e)也是不含圈的，故必有 ，从而 。这就是说T0也是G的一个最小支撑树，但是T0与T的公共边数比H与T的公共边数多一条，这与H的选取矛盾。592.3 最小支撑树问题2.破圈法破圈法任取一个圈，从圈中去掉一条权最大的边(如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条)。在余下的图中，重复这个步骤，直至得到一个不含圈的图为止，这时的图便是最小树。602.3 最小支撑树问题v例例9 用破圈法求图10-17(a)所示赋权图的最小支撑树。解解:任取一个圈，比如(v1，v2，v3，v1)，边v1，v3是这个圈中权最大的边，于是丢去v1，v3；再取圈(v3，v5，v2，v3)，去掉v2，v5；取圈(v3，v5，v4，v2，v3)，去掉v3，v2；取圈(v5，v6，v4，v5)，这个圈中，v5，v6及v4，v6都是权最大的边，去掉其中的一条，比如说v4，v6。这时得到一个不含圈的图(如图10-17(b)所示)，即为最小树。v破圈法的证明从略。61第10章 图与网络优化n第1节 图的基本概念n第2节 树n第3节 最短路问题n第4节 网络最大流问题n第5节 最小费用最大流问题n第6节 中国邮递员问题62第3节 最短路问题v3.1 引例v3.2 最短路算法v3.3 应用举例63v例10 已知如图10-18所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用。现在某人要从v1出发，通过这个交通网到v8去，求使图10-18总费用最小的旅行路线。3.1 引例图10-18643.1 引例v由上例可见从v1到v8的旅行路线有很多o例如可以从v1出发，依次经过v2，v5，然后到v8；也可以从v1出发，依次经过v3，v4，v6，v7，然后到v8等。不同的路线所需总费用是不同的。用图的语言来描述，从v1到v8的一条旅行路线就是图中从v1到v8的一条路；一条旅行路线的总费用就是相应的从v1到v8的路中所有弧旁数字之和。653.1 引例v一般意义的最短路问题给定一个赋权有向图，即给了一个有向图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)不一定相等。最短路问题是一类重要的优化问题，它不仅可以直接应用于解决生产实际中的许多问题，如管道铺设、线路安排、厂区布局、设备更新等，而且还经常作为一个基本工具，用于解决其他优化问题。663.2 最短路算法v在一个赋权有向图中寻求最短路的方法，实际上求从给定一个点vs到任一个点vj的最短路。v如下事如下事实实是是经经常要利用的常要利用的如果P是D中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。事实上，如果这个结论不成立，设Q是从vs到vi的最短路，令P是从vs沿Q到达vi，再从vi沿P到达vj的路，那么，P的权就比P的权小，这与P是从vs到vj的最短路矛盾。673.2 最短路算法v首先介绍所有wij0情形下的求最短路的方法。目前公认最好的方法是由Dijkstra1959年提出的。vDijkstra方法的基本思想从vs出发，逐步向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短路的权(称为P标号)，或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，这样，至多经过p1步，就可以求出从vs到各点的最短路。683.2 最短路算法v以例10为例说明该方法的基本思想。例10中，s=1。因为所有wij0，故有d(v1，v1)=0。这时，v1是具P标号的点。现考查从v1发出的三条弧，(v1，v2)，(v1，v3)，和(v1，v4)。o如果从v1出发沿(v1，v2)到达v2，需要d(v1，v1)+w12=6单位的费用；o如果从v1出发，沿(v1，v3)到达v3，则需要d(v1，v1)+w13=3单位的费用；o类似地，若沿(v1，v4)到达v4，需要d(v1，v1)+w14=1单位的费用。因为 mind(v1,v1)+12,d(v1,v1)+w13，d(v1,v1)+w14=d(v1,v1)+w14=1所以从v1出发到v4所需要的最小费用必定是1单位，即从v1到v4的最短路是(v1，v4)，d(v1，v4)=1。这样就可以使v4变成具P标号的点。693.2 最短路算法v现考查从v1及v4指向其余点的弧由上已知，从v1出发，分别沿(v1，v2)、(v1，v3)到达v2，v3，需要6单位或3单位的费用，而从v4出发沿(v4，v6)到达v6，所需要的费用是d(v1，v4)+w46=1+10=11单位，因为 mind(v1，v1)+w12，d(v1，v1)+w13，d(v1，v4)+w46=d(v1，v1)+w13=3 可以断言，从v1到v3的最短路是(v1，v3)，d(v1，v3)=3。这样又可以使点v3变成具P标号的点。v重复这个过程，可以求出从v1到任一点的最短路。703.2 最短路算法v在Dijkstra方法中P，T分别表示某个点的P标号、T标号，Si表示第i步时，具P标号点的集合。为了在求出从vs到各点的距离的同时，也求出从vs到各点的最短路，给每个点v以一个值。算法终止时，如果(v)=m，表示在从vs到v的最短路上，v的前一个点是vm；如果(v)=M，则表示D中不含从vs到v的路；(v)=0表示v=vs。713.2 最短路算法vDijkstra方法的具体步方法的具体步骤骤：给定赋权有向图D=(V，A)。开始(i=0)令S0=vs，P(vs)=0，(vs)=0，对每一个vvs，令T(v)=+，(v)=M，令k=s。如果Si=V，算法终止，这时，对每个vSi，d(vs，v)=P(v)；否则转入。考查每个使(vk，vj)A且的点vj。如果T(vj)P(vk)+wkj，则把T(vj)修改为P(vk)+wkj，把(vj)修改为k；否则转入。令。如果，则把的T标号变为P标号，令，把i换成i+1，转入；否则终止，这时对每一个vSi，d(vs，v)=P(v)，而对每一个，d(vs，v)=T(v)。723.2 最短路算法v用Dijkstra方法求例10中从v1到各个顶点的最短路这时s=1。(1)i=0，S0=v1，P(v1)=0，(v1)=0，T(vi)=+，(vi)=M(i=2，3，9)，以及k=1。转入，因(v1，v2)A，P(v1)+w12T(v2)，故把T(v2)修改为P(v1)+w12=6，(v2)修改为1；同理，把T(v3)修改为P(v1)+w13=3，(v3)修改为1；把T(v4)修改为P(v1)+w14=1，(v4)修改为1。转入，在所有的T标号中T(v4)=1最小，于是令P(v4)=1，令S1=S0v4=v1，v4，k=4。(2)i=1 转入，把T(v6)修改为P(v4)+w46=11，(v6)修改为4。转入，在所有T标号中，T(v3)=3最小，于是令P(v3)=3，令S2=v1，v4，v3，k=3。733.2 最短路算法v(3)i=2 转入，因(v3，v2)A，v2S2，T(v2)P(v3)+w32，把T(v2)修改为P(v3)+w32=5，(v2)修改为3。转入，在所有T标号中，T(v2)=5最小，于是令P(v2)=5，S3=v1，v4，v3，v2，k=2。v(4)i=3 转入，把T(v5)修改为P(v2)+w25=6，(v5)修改为2。转入，在所有T标号中，T(v5)=6最小，于是令P(v5)=6，S4=v1，v4，v3，v2，v5，k=5。v(5)i=4 转入，把T(v6)，T(v7)，T(v8)分别修改为10，9，12，把(v6)，(v7)，(v8)修改为5。转入，在所有T标号中，T(v7)=9最小，于是令 P(v7)=9，S5=v1，v4，v3，v2，v5，v7，k=7743.2 最短路算法v(6)i=5 转入，(v7，v8)A，但因T(v8)P(v7)+73，故T(v8)不变。转入，在所有T标号中，T(v6)=10最小，令 P(v6)=10，S6=v1，v4，v3，v2，v5，v7，v6，k=6。v(7)i=6 转入，从v6出发没有弧指向不属于S6的点，故直接转入。转入，在所有T标号中，T(v8)=12最小，令 P(v8)=12，S7=v1，v4，v3，v2，v5，v7，v6，v8，k=8。v(8)i=7 转入，这时仅有的T标号点为v9，T(v9)=+，算法终止。753.2 最短路算法v算法终止时的有关结果如下：P(v1)=0，P(v4)=1，P(v3)=3，P(v2)=5，P(v5)=6，P(v7)=9，P(v6)=10，P(v8)=12，T(v9)=+(v1)=0，(v4)=1，(v3)=1，(v2)=3，(v5)=2，(v7)=5，(v6)=5，(v8)=5，(v9)=Mv表明：对i=1，2，8，d(v1，vi)=P(vi)，而从v1到v9不存在路，根据值可以求出从v1到vi的最短路(i=1，2，8)。例如，为求v1到v8的最短路，考查(v8)，因(v8)=5，故最短路包含弧(v5，v8)；再考查(v5)，因(v5)=2，故最短路包含弧(v2，v5)；类推，(v2)=3，(v3)=1，于是最短路包含弧(v3，v2)，及(v1，v3)，这样从v1到v8的最短路是(v1，v3，v2，v5，v8)。763.2 最短路算法v有向图的最短路算法上面介绍了如何在一个赋权有向图中，求从一个顶点vs到各个顶点的最短路。对于赋权(无向)图G=(V，E)，因为沿边vi，vj既可以从vi到达vj，也可以沿vj到达vi，所以边vi，vj可以看作是两条弧(vi，vj)及(vj，vi)，它们具有相同的权wvi，vj。这样，在一个赋权图中，如果所有的w ij0，只要把Dijkstra方法中的“考查每个使(vk，vj)A且的点vj”改为“考查每个使vk，vjE且的点vj”，同样地可以求出从vs到各点的最短路(对于无向图，即为最短链)。773.2 最短路算法v例例11 用Dijkstra方法求图10-19所示的赋权图中，从v1到v8的最短路。图10-19783.2 最短路算法v解解 计算的最后结果为P(v1)=0，P(v4)=1，P(v3)=3，P(v2)=5，P(v5)=6，P(v9)=8，P(v7)=9，P(v6)=10，P(v8)=11。(v1)=0，(v4)=1，(v5)=1，(v2)=3，(v5)=2，(v9)=5，(v7)=5，(v6)=5，(v8)=9。这样从v1到v8的最短链为(v1，v3，v2，v5，v9，v8)，总权为11。793.2 最短路算法v证明Dijkstra方法的正确性。只要证明对于每一个点vSi，P(v)是从vs到v的最短路的权，即d(vs,v)=P(v)即可。对i施行归纳，i=0时，结论显然正确。设对i=n时，结论成立，即对每一个vSn，d(vs,v)=P(v)。现在考查i=n+1，因 ，所以只要证明 。根据算法，是这时的具最小T标号的点，即这里为了清晰起见，用Tn(v)表示当i=n执行步骤时点v的T标号。803.2 最短路算法v假设H是D中任一条从vs到的路，因为vsSn，而 ，那么从vs出发，沿H必存在一条弧，它的始点属于Sn，而终点不属于Sn。假设(vr，v1)是第一条这样的弧，v由归纳假设，P(vr)是从vs到vr的最短路的权，于是813.2 最短路算法v根据方法中T标号的修改规则，因vrSn，故 。v而 ，故 (因为所有的wij0，故 )。v这就证明了 是从vs到 的最短路的权，由方法，这样就证明了823.2 最短路算法vDijkstra算法只适用于所有wij0的情形，当赋权有向图中存在负权时，则算法失效。例如在如图10-20所示的赋权有向图中，如果用Dijkstra方法，可得出从v1到v2的最短路的权是1，但这显然是不对的，因为从v1到v2的最短路是(v1，v3，v2)，权是-1。图10-