1第十一章图与网络模型§1图与网络的基本概念§2最短路问题§3最小生成树问题§4最大流问题§5最小费用最大流问题©&®byH.Q.Feng,CUFE2§1图与网络的基本概念（一）图的定义：图论中图是由点和边构成，可以反映一些对象之间的关系。例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图11-1就是一个表示这种关系的图。(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5图11-1一、图的概念©&®byH.Q.Feng,CUFE3§1图与网络的基本概念当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图11-2来表示，可见图论中的图与几何图、工程图是不一样的。(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5图11-2©&®byH.Q.Feng,CUFE4§1图与网络的基本概念a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈图11-3若将前面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，引入一个带箭头的联线，称为弧。图是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。©&®byH.Q.Feng,CUFE5§1图与网络的基本概念（二）无向图：由点和边构成的图，记作G=（V，E）。（三）有向图：由点和弧构成的图，记作D=（V，A）。（四）连通图：对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。（五）回路：若路的第一个点和最后一个点相同，则该路为回路。（六）赋权图：对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。（七）网络：在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。©&®byH.Q.Feng,CUFE6§2最短路问题一、最短路问题对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从Vs到Vt的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。二、求解最短路的Dijkstra算法(双标号法）的步骤1.给出点V1以标号(0,s)2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合{(Vi,Vj)︱Vi∈I,Vj∈J}©&®byH.Q.Feng,CUFE7§2最短路问题一、最短路问题3.如果上...
