第九章 图与网络分析.doc

1、1第九章 图与网络优化9.1 重点、难点提要一、图与网络的基本概念1无向图设 是一个有 个顶点的非空集合： ； 是一个有 条Vn,21nvVEm无向边的集合： ，则称 和 这两个集合构成了一个无向图，,21meE记为 。),(G中任一条边 若连接顶点 和 ，则记该边为 （或 ） ，并称uv,vue,与 为无向边 的两个端点，且边 与顶点 及 相关联，顶点 和顶点 相邻。uvee v对于图 ，顶点集 和无向边集 也可以分别表示为 和 。V)(GV)(E一般用 和 表示图中顶点个数和边的条数。|E无向图中有平行边、简单图、完备图、子图、生成子图、导出子图、链、初等链、回路、连通图、割边、赋权连通图

2、和网络等基本概念。其中赋权连通图是网络优化考虑的一个重要对象。根据实际问题的需要，每条边的权重可以是时间、距离、成本等相应的数值。2有向图设 是一个有 个顶点的非空集合： ； 是一个有 条弧Vn,21nvVEm的集合： ，则称 和 这两个集合构成了一个有向图，记为,21meEE。),(D有向图中有弧、入度、出度、平行边、孤立点、简单图、完备图、基本图、子图、导出子图、导出生成子图、同构图、链、初等链、路、路径、回路、赋权有向图和网络等基本概念。和赋权连通图一样，赋权有向图也是网络优化研究的一个重要对象。3图的矩阵表示(1) 无向图的关联矩阵和邻接矩阵设 为一个无向图，其中 ， ，),(EVGn

3、vV,21meE,21图 的关联矩阵为 ，其中mnijaA上jiijev01关联矩阵描述的是无向图顶点与边的关联状态。2图 的邻接矩阵为 ，其中GnijbB间 没 有 边 相 连与 间 有 边 相 连与 jiijv01邻接矩阵描述的是无向图顶点间的邻接状态。无向图的关联矩阵和邻接矩阵有如下特点：（i）无向图的关联矩阵 的第 行各元素之和为与顶点 关联的边的数量，Ai iv而 的任何一列元素之和总是 2；A（ii）无向图的邻接矩阵 为一个对称矩阵。B(2) 有向图的关联矩阵和邻接矩阵设 为一个有向图，其中 ，),(EVDnvV,21，同样可以构造 的一个关联矩阵 和邻接矩阵me,21 Dmija

4、A，其中nijbB，上上jijiij eva10为以顶点 为起点，以顶点 为终点的弧的数量,ijbi jv有向图的关联矩阵和邻接矩阵有如下特点：（i）有向图的关联矩阵 的第 行非零元素的个数为与顶点 关联的弧的Ai iv数量，而 的任何一列元素之和总是 0；A（ii）有向图的邻接矩阵 不一定对称；B（iii ）有向图的邻接矩阵 的第 行各元素之和为以顶点 为起点的弧的数i iv量，第 列各元素之和为以顶点 为终点的弧的数量。j iv二、常见的网络优化问题1、最小支撑树问题树是图论中最简单但却十分重要的图。我们通常需要在一个网络中用最短的线路连通若干个固定顶点，例如铺设各种管道、规划交通网络、架

5、设通讯线路等，这就是最小支撑树问题。最小支撑树在自然科学和管理科学中的许多领域有着广泛的应用。(1)树和有向树树是一种特殊的无向图，也称为无向树，要求图中无回路并且连通，树一3般用 表示。T结论 1：如果 是一棵树，且 ，则下列命题等价。),(EVmEnV|,|（1） 连通且无回路；（2） 无回路且只有 条边，即 ；1n1（3） 连通且只有 条边；T（4） 无回路，但在不相邻的任意两个顶点之间加上一条边，恰好得到一个回路；（5） 连通，但去掉 的任何一条边， 将不再连通；TT（6） 的任意两个顶点之间有且仅有一条初等链。(2)支撑树支撑树若 是无向图 的生成子图，并且 同时又是树，则称 是GT

6、的支撑树，也称为生成树。G结论 2 图 有支撑树的充分必要条件是 为连通图。),(EVG(3)最小支撑树给定一个网络 ，设 是 的支撑树，称 中所有边),(wG),(1EVTT的权数之和为树 的权，记为 ，即T(1)Ee如果 的支撑树 满足G,(*V或)(min)1TwE1* )(min)(EeEew则称 为 的最小支撑树，简称最小树。*T对于一个连通的网络，如何寻找或构造一个最小支撑树，通常称为最小支撑树问题。2、最短路问题最短路问题是网络优化中十分常见的，可以解决许多诸如管道铺设、线路安排、运费最小、运输时间最短等实际问题。对于一个赋权有向图 ， ， 。若),(EVD,21nv ijjiw

7、v),(为一条顶点 至 的有向路径，则称 为路径 的长度。由于顶QuvQew)(点 至 的有向路径不一定是唯一的，因此一定存在一条有向路径 ，使得v *Q4|)(min)(* 上vuQw我们称 为顶点 至 的最短路径， 为顶点 至 的最短路径的长度，并*Quv*记为 。),(vd求一个赋权有向图中最短路径的问题称为最短路问题。根据不同的目的，求最短路通常使用 Dijkstra 算法、逐次逼近算法、Floyd 算法等方法。3、最大流问题网络中的流量应用广泛，如交通系统中的车流、供水、供电系统中的水流、电流、经济中的现金流、供应链系统中的物流、控制系统中的信息流等问题都与网络中的流量有关。通常人们

8、需要知道在一个既定网络中能通过的最大流量，这就构成了最大流问题。(1) 基本概念容量网络设 为一个赋权有向连通图，每条弧的非负权重),(EVD为该弧的最大流容量。如果 中仅有一个入度为 0 的顶点 和一个出度为 0ijc Sv的顶点 ，则称 为一个容量网络或运输网络。其中称 为源，称 为汇，Tv T称其余顶点为中间点。容量网络一般记为 ，其中 为弧的最大流),(CEVD容量集合。由于在一个容量网络中，每条弧都有容量限制，因此在整个网络中的流必然受到一定限制，如果假设 表示弧 上的流量，则 必须受到如下约ijf),(jivijf束：（1）容量限制条件：对 中的任意一条弧 , ；Dijijijcf

9、0（2）平衡条件：对 中的任意一个中间点 ,要求 ,即中间ivkijif点的总流入量和总流出量相等,净流量(流出量与流入量之差)为零；对源和汇,要求 ,即从源发出的流量必须与汇接受到的流量相kTjSff等。可行流满足以上两个条件的流量 的集合称为一个可行流，记为ijf。显然可行流一定存在。最大流问题就是在一个容量网络中寻找流量ijf5最大的可行流。饱和弧如果容量网络 中某弧 上的流量 等于其容量限制 ，D),(jivijfijc即 ，则称 为 的饱和弧。ijijcf),(jiv前向弧、后向弧假设 为容量网络 中从 到 的链，并且规定QSvT和 为链的方向，链上与链的方向一致的弧称为前向弧，与链

10、的方向相反的SvT弧称为后向弧。前向弧集合用 表示，后向弧集合用 表示。 Q可增广链假设 是容量网络 的一个可行流，如果满足fDvcfjiijij ),(0则称 为从 到 的（关于 的）可增广链。QSvT割集容量网络 , 和 为源和汇，若存在弧集 ，),(CEVDSvT E将网络 分为两个子图 和 ，其顶点集合分别为 和 ， ，12 SV， 和 为别属于 和 ，则称弧集SSvT ,|),(,( vuSE为 的一个割集。D割集容量 为容量网络 的一割集，称 中所有),(),(CEVDE弧的容量之和 )(),(EecSC为 的割集容量。E最小割集容量网络 一般有多个割集，其中割集容量最小的割集称为

11、D的最小割集，其割集容量称为 的最小割集容量。D(2) 最大流最小割定理定理 9-1 设 为网络 的任一可行流，流量为 ， 为分f),(CEVW),(S离 到 的一个割集，则有 。SvT SW定理 9-2 （最大流最小割集定理）任意一个容量网络 中，),(CEVD6从源 到汇 的最大流的流量等于分离 、 的最小割集容量。SvT SvT推论 可行流 是最大流的充要条件是不存在从 到 关于 的可增广链。f SvTf4、最小费用最大流问题研究网络中的流时，需要注意流的可行性、高效性和经济性。实际网络中的流必须是可行流，其流量不能超过最大流的流量。网络以最小费用通过某一可行流的问题就是最小费用流问题，

12、当网络中的流量达到最大时，就是最小费用最大流问题。赋权容量网络指在容量网络 中， 的每条弧 上除了),(CEVD),(jiv给出最大流容量 外，还给出了单位流量的成本 。赋权容量网络记为ijc ijd0(。),(dCEVD最小费用流问题指求赋权容量网络 的一个可行流 ，使得流Dijf量 ，且总费用 达到最小。*)(wfWEvijjifdf),(最小费用最大流问题指 为最大流时的最小费用流问题。f当 是一个赋权容量网络， 是 上的一个可行流， 是从源),(dCEVDfDQ到汇 的一条关于 的可增广链，还有下列重要概念：SvTf链的费用称 为 的费用，记为 ，其中 为 的Qijijfdf )(d前

13、向弧集合， 为 的后向弧集合。最小费用可增广链若 是从源 到汇 所有可增广链中费用最小的链，*SvT则称 为最小费用可增广链。*Q定理 9-3 若 是流量为 下的最小费用流， 是关于 的从源 到汇f)(fWQfSv的一条最小费用可增广链，则 经过 调整流量 后得到的新可行流 一定Tv f是流量为 下的最小费用流。)(f79.2 主要解题方法和典型例题分析题型 I 求连通图的最小支撑树1、Kruskal 法Kruskal 算法的基本思想是先将网络中的边全部去除，然后逐步挑选备选边中权最小的边构成最小支撑树，并且确保与已经选好的边不产生回路。Kruskal 算法也称为加边算法或避圈法。Kruska

14、l 算法步骤如下：第 1 步：将图 的 条边按权的递增顺序排列：Gm)()(21 miii ewew第 2 步：令 ， ，循环变量赋值 ；njvlj ,)(1E1k第 3 步：设 ，若 ，转第 6 步，否则令 ；ueki )(vl kieE第 4 步：对满足 的 ，令 ；,max)(vlj j )(,in)(vluvlj第 5 步：若 中的边的条数 ，算法终止，否则继续第 6 步；1E1|nE第 6 步：若 ，终止，图 为非连通图，无支撑树，否则，|G令 ，转第 3 步。k例 9-1 用 Kruskal 算法构造图 9-1 的最小支撑树。1v4325v6v7v81513 131 12 10 1

15、48 14181317图 9-1解：根据 Kruskal 算法，不断选择权最小的边，同时新增边必须与已选边不构成回路，所选边顺序： ， ， ， ， ， ，,72v,43,87v,21,3v。具体步骤见图 9-2(a)(g)。,65v88 141v45v6v7v1513 131 12 10 141813178 1v4325v6v781513 131 12 10 148 14181317(a) (b)1v43256v7v81513 131 12 10 148 14181317 1v43256v781513 131 12 10 148 14181317(c) (d)1v4326v7v1513 131

16、 12 10 148 14181317 58 1v4321513 131 12 10 148 14181317 58(e) (f)1v4326v7v1513 131 12 10 148 14181317 5v8(g)图 9-22、Prim 算法Prim 算法类似于 Kruskal 算法，不同的是每次加上的边必须与前面已经加上的边连通。对于赋权连通图 ，求 的最小生成树的 Prim 算法步骤如下：),(wEVGG9第 1 步：在 中任取一顶点 ， ， ， ，循环变量Vv1V12VE赋值 ；0k第 2 步：对于所有连接 和 的边 ，其中 ， ，如12,jiijve1i2vj果不存在连接 和 的边

17、，算法终止，无支撑树，否则继续第 3 步；12,jiijve第 3 步：取满足 的边 ，其中 ， ，令)(min,21ijVvwuj,vu1V2v， ， ， ；1vV2,1Ek第 4 步：如果 ，或者 ，得最小支撑树 ，算法nk ),(1wET终止，否则转第 2 步。例 9-2 用 Prim 算法构造图 9-1 的最小支撑树。解：根据 Prim 算法，不断选择权最小的边，新增边必须与已选边连通且不构成回路，所选边顺序：， ， ， ， ， ， 。具体步骤见图,72v,8,21v,3,4v,5,6v9-3(a)(g)。8 141v456v7v1513 131 12 10 141813178 1v4

18、56v781513 131 12 10 14181738 1413(a) (b)1v43256v7v81513 131 12 10 148 14181317 1v43256v781513 131 12 10 148 14181317(c) (d)101v4325v6v7v81513 131 12 10 148 14181317 1v4325v6v781513 131 12 10 148 14181317(e) (f)1v4326v7v1513 131 12 10 148 14181317 5v8(g)图 9-33、破圈法破圈法和 Kruskal 算法的方向相反，逐步将网络中权最大的边去除，直至网络形成支撑树。破圈法也称为破回路法。具体算法请读者仿照 Kruskal 算法或 Prim 算法建立。例 9-3 用破圈法构造图 9-1 的最小支撑树。解：根据破圈法，不断将权最大的边剔除，每步剔除边时必须保证图的连通性，每步剔除的边分别为： ， ， ， ， 。具,41v,76,85v,65,81v体步骤见图 9-4(a)(e)。1v43256v7v81513 131 12 10 148 1413171v43256v781513 131 12 10 148 1413(a) (b)