资源描述：
《图与网络模型课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第十一章 图与网络模型1 图与网络的基本概念2 最短路问题3 最小生成树问题4 最大流问题5 最小费用最大流问题图与网络分析（GraphTheoryandNetworkAnalysis），是近几十年来运筹学领域中发展迅速、而且十分灵活的一个分支。由于它对实际问题的描述，具有直观性，故广泛应用与物理学、化学、信息论、控制论、计算机科学、社会科学、以及现代经济管理科学等许多科学领域。图与网络分析的内容十分丰富。本章只介绍图与网络的基本概念以及图论在路径问题、网络流问题等领域中应用。有重点讨论基本概念及基本计算步骤、方法。1图论中图是由点和边构成，可以反映一些对象之间的关系。例如：在一个人群中
2、，对相互认识这个关系我们可以用图来表示，图11-1就是一个表示这种关系的图。(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5图11-1基本概念2当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5图11-2如对赵等七人的相互认识关系我们也可以用图11-2来表示，可见图论中的图与几何图、工程图是不一样的。基本概念3§11.1 图与网络的基本概念a1a2
3、a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈图11-3如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图11-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。4§11.1 图与网络的基本概念无向图：由点和边构成的图，记作G=（V，E）。有向图：由点和弧构成的图，记作D=（V，A）。链：无向图G的点边交错序列连通图：对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。路：有
4、向图的点弧交错序列。回路：若路的第一个点和最后一个点相同，则该路为回路。赋权图：对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。网络：在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。5§11.2 最短路问题最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从Vs到Vt的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。v23527531512v1v6
5、v5v3v4例题：求下列网络V1到V6的最短路。64.对上述弧的集合中的每一条弧，计算sij=li+cij。在所有的sij中，找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（scd,c）,返回步骤2。一、求解最短路的Dijkstra算法(双标号法）2.找出已标号的点的集合I3.如果上述弧的集合是空集，则计算结束。如果vt已标号（Lt,kt），则vs到vt的距离为Lt，而从vs到vt的最短路径，则可以从kt反向追踪到起点Vs而得到。如果Vt未标号，则可以断言不存在从Vs到Vt的有向路。如果上述的弧的集合不是空集，则转下一步。步骤：1.给出点V1的标号(0,s)没标号
6、的点的集合J，以及弧的集合最短路问题7v23527531512v1v6v5v3v4用双标号法求出v1到v6的最短路1(0,s)点集合I={V1);J=(V2,V3,V4,V5,V6}边集合（Vi,Vj)={(V1,v2),(V1,V4),(V1,V3)}计算sij=li+cijS12=l1+c12=0+3=3,s13=l1+c12=0+2=2,s14=l1+c12=0+5=5,(2,1)8v23527531512v1v6v5v3v4用双标号法求出v1到v6的最短路2(0,s)(2,1)点集合I={V1,V3,);J=(V2,V4,V5,V6}边集合（Vi,Vj)={((V1,V2),(V
7、1,V4)V2,v4),(V5,V2)}计算sij=li+cijS12=l1+c12=0+3=3,s14=l1+c14=0+5=5,s34=l3+c34=2+1=3s35=Φ(3,3)9v23527531512v1v6v5v3v4用双标号法求出v1到v6的最短路3(0,s)(2,1)(3,3)点集合I={V1,V3,V4,);J=(V2,V5,V6}边集合Vi,Vj)={(v1,v2),(v5,v3),(v4,v2)(v4,v6)(
