图论ppt课件

第五章：图论 (graph theory ) 教师:宁爱兵 Email: 第五章：图论 (graph theory ) 1.简介 2.图论基本概念 3.树及其优化问题 4.最短路问题 目录 7.练习题 5.最大流问题 6.最小费用最大流问题 2 简介 图论是应用非常广泛的运筹学分支，它 已经广泛地应用于物理学控制论，信息论， 工程技术，交通运输，经济管理，电子计算 机等各项领域。对于科学研究，市场和社会 生活中的许多问题，可以同图论的理论和方 法来加以解决。例如，各种通信线路的架设 ，输油管道的铺设，铁路或者公路交通网络 的合理布局等问题，都可以应用图论的方法 ，简便、快捷地加以解决。 w 随着科学技术的进步，特别是电子计 算机技术的发展，图论的理论获得了更 进一步的发展，应用更加广泛。如果将 复杂的工程系统和管理问题用图的理论 加以描述，可以解决许多工程项目和管 理决策的最优问题。因此，图论越来越 受到工程技术人员和经营管理人员的重 视。 。 4 这里，将对图论与网络优化的基本概念 与理论作初步的介绍。需要指出的是，不同 文献中所使用的图论术语与符号都不尽相同 ，缺乏统一的标准，因此，此处尽量使用较 普遍的术语与符号。 5 哥尼斯堡七桥问题哥尼斯堡七桥问题 图 5.1 a A B C D 8 v （见图5.1 a）当地 的居民热衷于这样一个 问题，一个漫步者如何 能够走过这七座桥，并 且每座桥只能走过一次 ，最终回到原出发地。 尽管试验者很多，但是 都没有成功。为了寻找 答案，1736年欧拉将这 个问题抽象成图5.1b所 示图形的一笔画问题。 哥尼斯堡七桥问题哥尼斯堡七桥问题 图 5.1 a A B C D 9 哥尼斯堡七桥问题可简化为以下图形哥尼斯堡七桥问题可简化为以下图形 其中的四个顶点都是奇顶点其中的四个顶点都是奇顶点 A B C D 10 C A D B 图5.1 b 11 即能否从某一点开始不重复地一笔画出这个图 形，最终回到原点。欧拉在他的论文中证明了这是 不可能的，因为这个图形中每一个顶点都与奇数条 边相连接，不可能将它一笔画出，这就是古典图论 中的第一个著名问题。 Euler在其论文中否定了这个可能性，本质上 的原因是图中每个点所关联的都是奇数条线，从而 彻底解决了这个长期困惑全城民众的难题。 12 二、四色问题 四色问题的提出来自英国，1852年，毕业于伦敦 大学的格思里(Francis Guthrie)来到一家科研单位搞 地图着色工作时，发现了一种有趣的现象：“看来， 每幅地图都可以用四种颜色着色，使得有共同边界的 国家着上不同的颜色。”这个结论能不能从数学上加 以严格证明呢？他与在大学念书的弟弟决心试一试。 兄弟二人为证明这一问题使用了一大叠稿纸，可研究 工作没有任何进展。1852年10月23日，他的弟弟拿这 个问题请教他的老师、著名数学家德摩尔根 (Augustus de Morgan)，摩尔根也没有能找到解决这 个问题的途径，于是写信向自己的好友、著名数学家 哈密尔顿爵士(Sir William Hamilton)请教。但直到 1865年哈密尔顿逝世为止，这个问题也没有得到解决 。 13 1878年6月13日，英国当时著名的数学家凯利 (Arthur Cayley)正式向伦敦数学学会提出这个问题 ，之后，四色猜想开始成了世界数学界关注的问题 。许多一流的数学家纷纷加入研究，1879年，著名 的律师兼数学家肯普(Alfred Bray Kempe)提交了证 明四色猜想的论文，宣布证明了四色定理，大家都 认为四色猜想从此解决了。11年后，即1890年，数 学家赫伍德(Percy John Heawood)以自己的精确计 算指出肯普的证明是错误的，但该方法经补救后可 用来证明五色定理。后来，越来越多的数学家虽然 对此绞尽脑汁，但一无所获。于是，人们开始认识 到，这个貌似容易的题目，其实是一个可与费马 (Fermat)猜想相媲美的难题。 14 进入20世纪以后，科学家们对四色猜想的证明 基本上是按照肯普的想法在进行。美国数学家富兰 克林(Franklin)于1922年证明了25国以下的地图都可 以用四色着色，1926年，结果推进到27国，1938年 ，推进到31国，1940年，推进到35国，1970年，推 进到40国，随后又推进到了96国。后来，由于计算 机性能的迅速提高，以及人机对话的出现，大大加 快了四色猜想证明的进程。1976年6月，美国数学家 阿佩尔(Kenneth Appel)与哈肯(Wolfgang Haken)经 过整整4年的紧张工作，在伊利诺斯大学的两台不同 计算机上，花费了1200个小时，作了100亿个判断， 终于完成了四色定理的证明。 15 四色猜想的计算机证明，轰动了世界。 它不仅解决了一个历时100多年的难题，而且 有可能成为数学史上一系列新思维的起点。 不过也有一些数学家并不满足于计算机取得 的成就，他们仍在寻找着简捷明快的纯数学 证明方法。1995年，中国学者李宏棋给出了 一个数学证明，收录于中国科学技术文库 数理科学和化学卷。 16 图论基本概念 v一、名词术语 v 图论中所考察的图不同于以往几何学与 分析学中的图形，这里的图只考虑点与点之 间由线连接的关系。至于画成直线还是曲线 ，画得长些还是短些，画在这儿还是那儿， 都无关紧要。也就是说，点线位置可随意安 排，线长不代表实际长度。 17 【定义1】 非空点集V与连接点的某个线集E之二元组 称为图，记作G = (V, E)。G 中的点v称为顶点，线e 称为边。V与E所含元素个数各记作p (G)与q (G)， 简记为p与q。 由于G中每条边都是点与点之间的连线，所以采 用记号e =u, v，其中，u、v 是e 的端点。此 时称e是u与v的关联边，而u与v互为邻点。对任一 点u，其所有邻点构成邻点集，记为N (u)。若两条 边仅有一个公共端点，称此两条边相邻。特殊地， 当u重合于v，则e =u, v只有一个端点，称为 环。当u与v之间有多条边相连时，称为多重边。 今后，边vi, vj也常记作eij。 18 环与多重边环与多重边： 两个顶点相同的 边称为环，如e22 ，两个顶点之间 的边数2时,叫多 重边,如e13 ,e13就 是二重边。 图 5-4 二重边二重边 环环 19 有多重边的图称为多重图，无环且无多 重边的图称为简单图。这里，主要研究简单 图。为便于讨论，尽量避免边与边交叉或自 交的情形。 v1 v5 v4 v3 v2 简单图 （2） （4） （3） （3） （2） v1 v5 v4 v3 v2 多重图 （4） （6） （3）（3） （2） 20 v【定义2】 点v关联边的个数称为v的次（或度）， 记为d (v) 或deg (v)。当d (v) = 0，v称为孤立点；当 d (v) = 1，v称为悬挂点；当d (v)为奇（偶）数，v称 为奇（偶）点。 规定：若v有一个环，则v的次增加2。 端点的度 d(v)：点 v 作为端点的边的个数 奇点： d(v)=奇数； 偶点：d(v) = 偶数； 悬挂点：d(v)=1； 悬挂边：与悬挂点连接的边； 孤立点：d(v)=0； 空图：E = ，无边图 21 悬挂点与孤立点悬挂点与孤立点： 次为1的顶点称 为悬挂点，如v5。 次为0的顶点称为 孤立点，如v6。 图 5-4 v6 孤孤 立立 点点 悬悬 挂挂 点点 22 v3 v2 v1 v4 例如例如. .下下图是一个无向图G=（V，E）， 其中V=v1 , v2 , v3 , v4 E=v1 , v2,v2 ,v1,v2 ,v3, v3 ,v4,v1 ,v4, v2 ,v4, v3 ,v3 d(v1)=3， d(v2 )=4,d(v3 )=4 , d(v4 )=3。 23 v1 v7 v6 v5 v4 v3 v2 V=v1 , v2 , v3 , v4 , v5 ,v6 , v7 d(v1)=3 ; d(v2)=5 ; d(v3)=4 ; d(v4)=4 ; d(v5)=1 ; d(v6)=3; d(v7)=0 其中 v5 为悬挂点， v7 为孤立点。 24 二、基本性质 【定理1】 设G为简单图，则d (v)p-1。 【证】 因为除所考察的点v外，另有p-1个点，以v为端 点至多连p-1条边，故有d (v)p-1。 25 定理二 所有顶点度数之和等于所有边数的2倍。 证明：因为在计算各个点的度时，每条边被它的 两个端点个用了一次。 26 定理三定理三在任一图中，奇点的个数必为偶数。 因为 是偶数， 也是偶数，因此 也必是偶数，从而V1 中的点数是偶数。 证明：证明：设 V1，V2 分别是图G中奇点和偶点的集合 ，由定理5.1 ，有 27 【例1】 今有9人vi (i = 1, 2, , 9) 相聚。已知v6、v7各和4人 握过手，v8、v9各和6人握过手。证明：9人中必有3人互相握 过手。 【证】 以每个人作为顶点，两点连 线表示两人握过手。 现已知v9有6个邻点，其中必有一 点vj为 v6、v7、v8之一， v否则d (v9)5，故得d (vj)4。 显然，除vj外，v9的另5个 v邻点中必有一点vk与vj相邻（否则 ，将有d (vj)8-5 = 3，矛盾），从 而v9、vj、vk互为邻点（图5-3）， 这表明确有3人互相握过手。 图5-3 v9 vj vk 注意：未标出的只 有两个点。 28 在图论中，我们只关心两点间是否有联系， 至于公路的大小、等级、状况均无关紧要，亦 即不考虑线段（边）的长度，点的位置带有随 意性，它们并不按比例尺画，如五个镇之间的 连接图也可画成右图表示。 A B C D E 29 三、连通图 架设电话线网，要求每个用户彼此都能 通话；建造铁路网，要求有关城市互相通达 。诸如此类的要求反映在图中，就抽象出连 通性的概念。 30 图的连通性：图的连通性： 链：由两两相邻的点及其相关联的边构成的点边序列 。 如:v0 ,e1 ,v1 ,e2 ,v2，e3 ,v3 ,vn-1 , en ， vn ; v0 ，vn v0 ， vn 分别为链的起点和终点 。记作 （ v0 ,v1 , v2， ,v3 , , vn-1 , vn ） 简单链：链中所含的边均不相同； 初等链：链中所含的点均不相同, 也称通路； 圈：若 v0 vn 则称该链为开链，否则称为闭链 或回路或圈； 31 简单圈：如果在一个圈中所含的边均不相同 初等圈：除起点和终点外链中所含的点 均 不相同的圈； 连通图：图中任意两点之间均 至少有一条通路，否则 称为不连通图。 v1 v2 v4 v3 v5 v6 v7 v8 v9 初等链: (v1 , v2 , v3 , v6 , v7 , v5 ) 初等圈： (v1 , v2 , v3 , v5 , v4 , v1 ) 32 简单圈： (v4 , v1 , v2 , v3 , v5 , v7 , v6 ,v3 , v4 ) 简单链：(v1 , v2 , v3 , v4 ,v5 , v3 ) 以后除特别声明，均指初等链和初等圈。 v1 v2 v3v4 v5 连通图 v1 v5 v4 v3 v2 v6 33 【定理4】 设图G为一条简单链，则至多除始点 与终点外，每一个中间点必为偶点。 【证】 设vk为任一中间点，因vk既为前邻 边之终点，又为后邻边之始点，故若vk在链 中出现n次，则得d (vk) = 2 n，此为偶数， 即vk为偶点。 34 【推论】 任何具有超过两个奇点的图G必不能一笔画 成。 v【证】 由定理3知，此时至少有4个奇点，若存在包 含G中所有边的链，则此链中至少有两个中间点为奇 点，由定理4知，它必非简单链。 v 由于一笔画成等价于G为简单链，故G若有奇 点，则必为2个，且这2个奇点必为简单链之始、终 点。多于两个奇点之图不能作一笔画。 35 【例2】 Euler的哥尼斯堡七桥问题，实质上是想对图 5-2所示之G找出一个圈，使之能一笔画成。由于d (A) = d (C) = d (D) = 3，d (B) = 5，四个顶点均为奇 点，故不可能一笔画成。从而，当地民众希冀的散 步方案永远无法实现。 C A D B 36 子图定义：如果 V1 V2 , E1 E2 称 G1 是G2 的子图； 设设 G G 1 1 = V= V 1 1 , E , E 1 1 , G , G 2 2 = V= V 2 2 ,E,E 2 2 （1）部分子图：如果 V1 = V2 , E1 E2 称 G1 是G2 的部分子图； （2）真子图：如果 V1 V2 , E1 E2 称 G1 是G2 的真子图； (3)生成子图：V1 V2，E1 = vi, vjvi, vjV1 E2，则 G1称为G2中由V1生成的子图，记作G1 = G (V1)，简称为G1是 G2的生成子图 (4) 支撑子图：V1 = V2，E1 E2，且保持G2原有的连通性，则 G1称为G2的支撑子图。 37 G1 G3 是G1的真子图 G2是G1的部分子图 G4是G1的支撑子图，但 是否是G1的生成子图？ G5是否是G1的生成子图？ 38 五、图的矩阵表示 1. 关联矩阵 定义 v则pq阶矩阵 mij 称为G的关联矩阵。 39 2. 邻接矩阵 定义 则pp阶矩阵 uij 称为G的邻接矩阵。 将一个图的结构表示为矩阵形式具有唯一性，并可以 方便地为计算机提供代数形式的数据输入。一般而言，对于 边数较少的稀疏图来说，采用关联矩阵可以占用相对少的计 算机内存；对于边数较多的稠密图来说，则采用邻接矩阵更 为节省。 40 树及其优化问题树及其优化问题 w一、树及其性质 例5.3 已知有六个城市，它们之间 要架 设电话线，要求任意两个城市均可以互相通话 ，并且电话线的总长度最短。 在各种各样的图中，有一类图是十分简单 又非常具有应用价值的图，这就是树。树。 如果用六个点v1v6代表这六个城市，在任意两个 城市之间架设电话线，即在相应的两个点之间连一条 边。这样，六个城市的一个电话网就作成一个图。 图5.8 v6 v3 v4 v2 v5 v1 42 图5.8 v6 v3 v4 v2 v5 v1 表示任意两个城市之间均可以通话，这个图必须 是连通图。并且，这个图必须是无圈的。否则，从 圈上任意去掉一条边，剩下的图仍然是六个城市的 一个电话网。图5.8是一个不含圈的连通图，代表了 一个电话线网。 43 定义定义5.15.1 一个无圈的连通图叫做树树。 树一般记为T作为树定义还可以有以下几种表述： (1) T 连通且无圈或回路； (2) T 无圈且有n1条边（如果有n个结点）； (3) T 连通有n1条边； (4) T 无回路，但不相邻的两个结点之间联以一边，恰 得一个圈； (5) T 连通，但去掉T 的任意一条边，T 就不连通了； （亦即，在点集合相同的图中，树是含边数最少的 连通图。） (6) T 的任意两个结点之间恰有一条初等链 44 下面介绍树的一些重要性质：下面介绍树的一些重要性质： 定理定理5.35.3 设图G=（V，E）是一个树 p(G) 2，那么 图G中至少有两个悬挂点。 定理5.4 图G=（V，E）是一个树的充要条件是G 不含圈，并且有且仅有p1条边。 定理定理5.55.5 图G=（V，E）是一个树的充要条件是G是 连通图，并且有且仅有 p1 条边。 定理定理5.65.6 图G是一个树的充分必要条件是任意两个 顶点之间有且仅有一条链。 45 从以上定理，不难得出以下结论： 二、支撑树 定义定义5.25.2 设图K=( V , E1 )是图G=(V , E )的 （1）从一个树中任意去掉一条边，那 么剩下的图不是连通图，亦即，在点集合相 同的图中，树是含边数最少的连通图。 （2）在树中不相邻的两个点之间加上 一条边，那么恰好得到一个圈。 46 一个支撑子图(点相同并保持图的连通性)，如 果图K=(V , E1) 是一个树,那么称K 是G 的一个 支撑树。 图5.10 v6 v5 v2 v3 v4 v1 a v6 v5 v2 v3 v4 v1 b 例如 , 图5.10 b 是图5.10a 的一个支撑树 47 显然,如果图K=(V,E1)是图G=(V,E)的一个 支撑树,那么K 的边数是p(G)1，G中不属于 支撑树K 的边数是q(G) p(G)+1。 定理定理5.75.7 一个图G有支撑树的充要条件是G 是连通图。 证明：充分性: 设图G是连通的，若G不 含圈，则按照定义，G是一个树，从而G是自 身的一个支撑树。若G含圈，则任取G的 48 一个圈，从该圈中任意去掉一条边，得到图 G的一支撑子图G1。若G1不含圈，则G1是G 的一个支撑树。 若G1仍然含圈，则任取G1的一个圈，再 从圈中任意去掉一条边，得到图G的一支撑 子图G2。依此类推，可以得到图G的一个支 撑子图GK，且不含圈，从而GK是一个支撑树 。 49 定理5.7充分性的证明，提供了一个寻找连 通图支撑树的方法叫做“破圈法”。就是从图中 任取一个圈，去掉一条边。再对剩下的图重复 以上步骤，直到不含圈时为止，这样就得到一 个支撑树。 50 例4 用破圈法求出下图的一个支撑树。 v5 v4 v2 v3 v1 e6 e5 e4 e3 e2 e1 e7 e8 51 取一个圈(v1 ,v2 ,v3 ,v1 )，在一个圈中去掉边e3 。在剩下 的图中，再取一个圈（v1 ,v2 ,v4 ,v3 ,v1 ），去掉边e4 。再从圈 （v3 ,v4 ,v5 ,v3 ）中去掉边e6 。再从圈(v1 ,v2 ,v5 ,v4 ,v3 ,v1 ）中去 掉边e7，这样，剩下的图不含圈，于是得到一个支撑树，如 图所示。 v5 v4 v2 v3 v1 e6 e5 e4 e3 e2 e1 e7 e8 v2 e1 e2 e5 e8v1 v3 v4 v5 52 1 1最小生成树最小生成树 二、最小生成树及其算法二、最小生成树及其算法 一个网络图可以有多个生成树记G 的所有生成树的 集合为： T Tk | k1，2，L 设Tk （V， Ek ）是网络图N（G，w）的一棵生成树， 则边集Ek中所有边的权数之和称为树Tk 的权数，记为 则称 T * 为网络N的一棵最小生成树，简称最小树53 a b f d e c 2 2 4 2 5 63 4 5 最小 树 比如，城市间 交通线的建造等， 可以归结为这一类 问题。 再如前面例3，在已知的几个城市之间联结电 话线网，要求总长度最短和总建设费用最少，这 类问题的解决都可以归结为最小树问题。 1 1最小生成树最小生成树 54 定理4 如果把网络的点集分割成 两个不相交的非空集合和，则联结和的 最小边必包含于G 的最小树内 2 2最小树的求法最小树的求法 根据定理4，可以给出求最小树的 两种方法，这就是避圈法与破圈法，分 述如下： 55 (1)(1)避圈法：避圈法： 从网络图中任 意节点开始寻找 与该节点关联的 权数最小的边， 使之于以选边不 构成为圈，直到 选够n-1条边为止 。 例例 最小树，权为13 v14 v2 1v3 1 23 1 v8 4 v0 4 v4 5 2 4 5 v7 3 v62 v5 1 5 从网络 中任选 一点 2 2最小树的求法最小树的求法 56 v14 v2 1 v3 1 2 3 1 v8 4 v0 4 v4 5 2 4 5 v7 3v62 v5 1 5 (2)(2)破圈法：破圈法： 在网络图中寻找 一个圈。若不存在圈 ，则已经得到最短树 或网络不存在最短树 ； 去掉该圈中权数 最大的边； 反复重复 两 步，直到最小树。 2 2最小树的求法最小树的求法 57 3 3 最短路问题最短路问题 w一.引言 最短路径问题是图论中十分重要的最优 化问题之一，它作为一个经常被用到的基本 工具，可以解决生产实际中的许多问题，比 如城市中的管道铺设，线路安排，工厂布局， 设备更新等等。也可以用于解决其它的最优 化问题。 例5 如下图所示的单行线交通网，每个 弧旁边的数字表示这条单行线的长度。现 在有一个人要从v1出发，经过这个交 通网 到达v6， 要寻求总路 程最短的线 路。 v6 v5 v3 v1 v4v2 3 6 5 1 1 2 4 3 6 59 从v1到v6的路线是很多的。比如从v1出发， 经过v2 ,v4到达v6或者从v1出发，经过v2，v3，v5 到达v6等等。但不同的路线，经过的总长度是不 同的。例如，按照第一个线路，总长度是 3+6+3=12单位，按照第二个路线，总长度是 3+1+1+6=11单位。 v6 v5 v3 v1 v4v2 3 6 5 1 1 2 4 3 6 60 一、有向图一、有向图 【定义10】 从点u到v的有向线段称为弧， 记作a = (u, v)，其中，u与v分别称为弧a 的始点 与终点，图中所有弧的集合则记作A。弧(vi, vj) 也常记作aij 。 【定义11】 非空点集V及其相应的非空弧集 A之二元组称为有向图，记作D = (V, A)。 61 显然，给定一个D，若去除弧上的方向， 则对应得到唯一的无向图G。此时的G 称为D 的基础图；反之，一个无向图G，由于可用不 同的方式来标上方向，故可伴生多个有向图 。无向图中的许多概念与术语（如链与圈等 ）可沿用于有向图中，但仍有一些不同之处 。将有向图与其基础图相对照，有下列对应 关系： D弧路回路 G边边链链圈 62 在D = (V, A)中，点vi的邻点集N (vi) 可分解为 两部分，即 当D为简单图时， N (vi)、N+(vi)、N-(vi) 常简记为Ni、Ni+、Ni-。 63 给定一个赋权有向图D ( V，A ) ,对每一 条弧aijw (vi，vj)，相应地有权w (aij )= wij ，又 有两点vs、vt V,设 p 是 D 中从vs 到vt 的一条路 ，路 p 的权是 p 中所有弧的权之和,记为w(p) 最短路问题就是求从vs 到vt 的路中一条权最小的 路 p*: 二、最短路问题 64 最短路问题是最重要的网络优化问题之一，它 不仅可以直接应用于解决生产实际中的许多问题， 如管道铺设、线路安排、厂区布局、设备更新等等 ，而且经常被作为一个基本工具，用于解决其它优 化问题。许多优化问题往往可转化为求图上的最短 路，这方面的研究工作已取得了十分丰富的成果， 迄今为止，求解的算法已不下数十种。 最短路问题按其不同的要求，可分成下列三种类型： 1、求两个定点之间的最短路； 2、求一个定点到其他各点的最短路； 3、求各点对之间的最短路。 不失一般性，总假定图中无环，以及多重弧只是由 两条互为反向的弧组成的二重弧。 65 【例4】（渡河问题）这是一个古老的趣味数学问题， 在世界不同国家与民族中有着不同的表述形式。今 设一人携带狼、羊、菜，须从一条小河的此岸渡往 对岸。河边仅有一条小船，容量为2。当人不在场时 ，狼要吃羊、羊要吃菜。问：应怎样渡河，才能使 大家安全到达对岸，且小船在河上的来回次数最少 。(船上必须要有人) 【解】 记M代表人、W代表狼、S代表羊、V代表菜。 以河的此岸为考察基点，则开始状态为MWSV，结 束状态为。共有16种状态：MWSV、MWS、 MWV、MSV、WSV、MW、MS、MV、WS、 WV、SV、M、W、S、V、。其中，有6种不允 许出现，即：WSV、MW、MV、WS、SV、M。 66 于是，可能的状态仅有10种，以每个状态作为顶 点，构造相应的图（如图5-8所示），其中，边的 连接原则为：若状态甲经一次渡河可变为乙，则连 一条边。从而，渡河问题就归结为求MWSV的 最短路。 (船上必须要有人) （算法形式化方面的内容） 图5-8 MWSVMWS MWV MSVMS WVW SV 67 三、有向图最短路算法 1964年，Ford提出了可求解含负权的最短路问 题的递推标号法。 设赋权有向图D = (V, A, W)，V中含p个点，现要求始 点v1至终点vp的最短路Rp*及其路长rp*。假定D中无 负回路（其上总权为负数的回路），将原弧集A增 广为新弧集，以使V中任意两点间均有互为反向的 两条弧，同时权集W增广为新权集。于是，原图D 增广为新图。显见，若某两相邻点之间有多于一条 的同向弧，则可弃大留小，简化为一条弧，从而是 一个完全的二重赋权有向图，其中，增广的权集， 定义为 68 其中，当i = j时，若设 ，则与实际背景 不符，若0 的弧为非零流弧，fij=0 的弧叫做零流弧 . 在图6.20中，(v4 ,v3)是饱和弧，其他的弧是非饱 和弧，并且都是非零流弧。 设是网络D中连接发点s和收点vt的一条链。 定义链的方向是从s到 vt ，于是链上的弧被分为 两类：一类是弧的方向与链的方向相同，叫做前向弧 （正向弧），前向弧的集合记做+。二类是弧的方向 与链的方向相反，叫做后向弧（反向弧），后向弧的 集合记做。 102 增广链的作用:增大流量； 增广链满足的条件：正向弧是非饱和弧（非饱和弧的 作用是增大流量），逆向弧是非零流弧（非零流弧 的作用是减少流量）； 饱和弧的作用：减少流量； 零流弧的作用：增大流量； 非饱和非零流弧的作用：增大流量和减少流量。 很重要：对增广链作用的理解。 103 例如在图5.19中，在链（vs,v1,v2,v3,v4,vt)中， + = (vs,v1) ,(v1,v2) ,(v2,v3) ,(v4,vt), = (v4 ,v3). 增广链：增广链：如果链满足以下条件： 1在弧（vi ,vj）+上，有0fij 0,那么给vj 标号 (-vi , l(vj).其中l (vj)=min l(vi), fji .这时，vj 成为标号 未检查点。 3重复步骤2，直到vt被标号或标号过程无法进行下 去，则标号法结束。 若vt被标号，则存在一条可增广链，转调整过程 112 二、调整过程二、调整过程 首先按照vt 和其它的点的第一个标号，反向 追踪，找出增广链 。例如，令vt 的第一个标号 是vk，则弧（vk ,vt）在上。再看vk的第一个标号， 若是vi ，则弧(vi ,vk)都在上。依次类推，直到vs 为止。这时，所找出的弧就成为网络D 的一条增 广链。取调整量=l (vt),即vt的第二个标号，令 若vt未被标号，而标号过程无法进行下去，这时的 可行流就是最大流 113 其它不变 再去掉所有的标号，对新的可行流f =f ij,重新 进行标号过程，直到找到网络D 的最大流为止。 例5.8 求图5.20的网络最大流，弧旁的权数表示 （cij , fij）。 114 vs v1 v2 v3 v4 vt (3 , 3) (5 , 1) (4 , 3) (1 , 1) (1 , 1) (2 , 2) (3 , 0) (5 , 3) (2 , 1) 图5 20 例5 8网络图 115 解：用标号法。 1.标号过程。 （1）首先给vs标号（0，+） （2）看vs : 在弧(vs ,v2)上,fs2=cs2=3 , 不 具备标号条件。在弧(vs ,v1)上,fs1=1 0 ,故给 v2标号 （-v1 , l(v2)）,其中 l(v2)=minl(v1) , f21 = min 4 , 1 = 1. 116 vs v1 v2 v3 v4 vt (3 , 3) (5 , 1) (4 , 3) (1 , 1) (1 , 1) (2 , 2) (3 , 0) (5 , 3) (2 , 1) 图5 21 例5 8网络图 (0,+) (vs , 4) (v1 , 1)(v2 , 1) (-v2 , 1) (v3 , 1) 117 （4）看v2:在弧（v2 ,v4）上，f24 =3 0 ,故给v3标号（-v2，l(v3) , 其中 l (l(v3 )= minl(v2) , f32 = min1 , 1 =1。 （5）在v3 ,v4中任意选一个，比如v3 ,在弧（v3 , vt ） 上，f3t =1 c3t =2,故给vt标号(v3 ,l(vt),其中 l(vt)=minl(v3),(c3t-f3t)=min1,1=1.因为vt被标上号， 根据标号法，转入调整过程。 118 2 2. .调整过程调整过程 从vt开始，按照标号点的第一个标号，用反向追 踪的方法，找出一条从vs到vt的增广链，如图 622中双箭线所示。不难看出, +=(vs ,v1),(v3 ,vt), =(v2 ,v1) , (v3 ,v2),取=1， 在上调整f ，得到 f * = fs1 + =1+1=2 在+上 f3t + =1+1=2 在+上 f *= f21 =1 1=0 在-上 f32 = 1 1=0 在-上 其它的不变 119 vs v1 v2 v3 v4 vt (3 , 3) (5 , 1) (4 , 3) (1 , 1) (1 , 1) (2 , 2) (3 , 0) (5 , 3) (2 , 1) 图5 22 例5 8网络图 (5 , 2) (1 , 0) (1 , 0) (2 , 2) (cij , fij) 120 调整后的可行流f *，如图8.22所示，再对这个 可行流从新进行标号过程，寻找增广链。 首先给vs标号（0，+），看vs , 给v1 标号 （vs ,3）。看v1,在弧（v1 ,v3）上，f13=c13,弧（v2 ,v1 ） 上，f21=0,均不符合条件。因此标号过程无法进行 下去，不存在从vS到vt的增广链，算法结束。 这时，网络中的可行流f * 即是最大流，最大流的 流量v(f*)= fs1+fs2=5.同时，也找出D 的最小截集 （V1， ），其中V1是标号的集合， 是未标号 的集合。 121 vs v1 v2 v3 v4 vt (3 , 3) (5 , 2) (4 , 3) (1 , 0) (1 , 0) (2 , 2) (3 , 0) (5 , 3) (2 , 2) (cij , fij) (0 , +) (vs , 3) 图523 例5 8网络图 122 例69 求图6 24所示网络的最大流 vs v1 vt v5 v4 v3 v2 4 3 10 4 1 3 3 5 4 2 7 8 图 524 例59网络图 123 解：给定初始可行流为全零流，即 f （0） = 0 给vs 标号（0，+），检查 vs ： 给 v1 标号 (vs ,4) , 给 v3 标号(vs , 3) , 给 v3 标号(vs , 10) , vs v1 vt v5 v4 v3 v2 （4, 0 ） （10, 0 ） （3, 0 ） （3, 0 ） （3, 0 ） （4, 0 ） （1, 0 ） （2, 0 ）（5, 0 ） （4, 0 ） （7, 0 ） （8, 0 ） 124 (0 , +) (vs , 4) (vs , 3) (vs , 10) 检查 v1 ：给 v4 标号(v1 , 1) ，检查完毕； (v1 , 1) 检查 v2 ：给 v5 标号(v2 , 3) ，检查完毕； vs v1 vt v5 v4 v3 v2 （4, 0 ） （10, 0 ） （3, 0 ） （3, 0 ） （3, 0 ） （4, 0 ） （1, 0 ） （2, 0 ）（5, 0 ） （4, 0 ） （7, 0 ） （8, 0 ） (v2 , 3) 检查 v5 ：给 vt 标号(v5 , 3) ，检查完毕； (v5 , 3) 125 因为终点 vt 已标号，故找出一条从vs到vt的增 广链： vs v2 v5 vt . 取 = 3 vs v1 vt v5 v4 v3 v2 （4, 0 ） （10, 0 ） （3, 3 ） （3, 0 ） （3, 0 ） （4, 0 ） （1, 0 ） （2, 0 ）（5, 3 ） （4, 0 ） （7, 0 ） （8, 3 ） 126 (vs , 4) (v1 , 3) (vs , 10) (v1 , 1) vs v1 vt v5 v4 v3 v2 （4, 0 ） （10, 0 ） （3, 3 ） （3, 0 ） （3, 0 ） （4, 0 ） （1, 0 ） （2, 0 ）（5, 3 ） （4, 0 ） （7, 0 ） （8, 3 ） (v2 , 2) (0 , +) (v5 , 2) vs v1 vt v5 v4 v3 v2 （4, 2 ） （10, 0 ） （3, 3 ） （3, 2 ） （3, 0 ） （4, 0 ） （1, 0 ） （2, 0 ）（5, 5 ） （4, 0 ） （7, 0 ） （8, 5 ） 127 (vs , 2) (v3 , 3) (vs , 10) (v2 , 3) vs v1 vt v5 v4 v3 v2 （4, 2 ） （10, 0 ） （3, 3 ） （3, 2 ） （3, 0 ） （4, 0 ） （1, 0 ） （2, 0 ）（5, 5 ） （4, 0 ） （7, 0 ） （8, 5 ） (v3, 4) (0 , +) (v4 , 3) vs v1 vt v5 v4 v3 v2 （4, 2 ） （10, 3 ） （3, 3 ） （3, 2 ） （3, 3 ） （4, 0 ） （1, 0 ） （2, 0 ）（5, 5 ） （4, 3 ） （7, 3 ） （8, 5 ） 128 vs v1 vt v5 v4 v3 v2 （4, 2 ） （10, 3 ） （3, 3 ） （3, 2 ） （3, 3 ） （4, 0 ） （1, 0 ） （2, 0 ）（5, 5 ） （4, 3 ） （7, 3 ） （8, 5 ） vs v1 vt v5 v4 v3 v2 （4, 2 ） （10, 6 ） （3, 3 ） （3, 2 ） （3, 3 ） （4, 3 ） （1, 0 ） （2, 0 ）（5, 5 ） （4, 3 ） （7, 3 ） （8, 8 ） (0 , +) (vs , 2) (vs , 10) (v3, 4) (v5, 2) (v5, 3) 129 vs v1 vt v5 v4 v3 v2 （4, 3 ） （10, 6 ） （3, 3 ） （3, 2 ） （3, 3 ） （4, 3 ） （1, 1 ） （2, 0 ）（5, 5 ） （4, 3 ） （7, 4 ） （8, 8 ） vs v1 vt v5 v4 v3 v2 （4, 2 ） （10, 6 ） （3, 3 ） （3, 2 ） （3, 3 ） （4, 3 ） （1, 0 ） （2, 0 ）（5, 5 ） （4, 3 ） （7, 3 ） （8, 8 ） (0 , +) (vs , 2) (vs , 4) (v1 , 1) (v1 , 1) (v4 , 1) 130 vs v1 vt v5 v4 v3 v2 （4, 3 ） （10, 6 ） （3, 3 ） （3, 2 ） （3, 3 ） （4, 3 ） （1, 1 ） （2, 0 ）（5, 5 ） （4, 3 ） （7, 4 ） （8, 8 ） vs v1 vt v5 v4 v3 v2 （4, 3 ） （10, 7 ） （3, 3 ） （3, 2 ） （3, 3 ） （4, 4 ） （1, 1 ） （2, 1 ）（5, 5 ） （4, 3 ） （7, 5 ） （8, 8 ） (0 , +) (vs , 4) (vs , 1) (v3 , 1) (v5 , 1) (v4 , 1) 131 vs v1 vt v5 v4 v3 v2 （4, 3 ） （10, 7 ） （3, 3 ） （3, 2 ） （3, 3 ） （4, 4 ） （1, 1 ） （2, 1 ）（5, 5 ） （4, 3 ） （7, 5 ） （8, 8 ） vs v1 vt v5 v4 v3 v2 （4, 4 ） （10, 7 ） （3, 3 ） （3, 3 ） （3, 3 ） （4, 4 ） （1, 1 ） （2, 1 ）（5, 5 ） （4, 4 ） （7, 6 ） （8, 8 ） (0 , +) (vs , 1) (vs , 3) (v1 , 1) (v2 , 1) (v4 , 1) 132 vs v1 vt v5 v4 v3 v2 （4, 4 ） （10, 7 ） （3, 3 ） （3, 3 ） （3, 3 ） （4, 4 ） （1, 1 ） （2, 1 ）（5, 5 ） （4, 4 ） （7, 6 ） （8, 8 ） (0 , +) (vs , 3) 首先给vs标号（0，+），看vs,给v3标号（vs ,3）。 看v3,在弧（v3 ,v2）上，f32=c32,弧（v3 ,v5）上，f35= c35, 均不符合条件。因此标号过程无法进行下去，不存 在从vS到vt的增广链，算法结束。最大流量 f * = 14 。 133 5 5 最小费用最大流流问题最小费用最大流流问题 w 在实际的网络系统中，当涉及到有关流的问 w题的时候，我们往往不仅仅考虑的是流量，还经 w常要考虑费用的问题。比如一个铁路系统的运输 w网络流，即要考虑网络流的货运量最大，又要考 w虑总费用最小。最小费用最大流问题就是要解决 w这一类问题。 我们首先考察，在一个网络D中，当沿可行 流 f 的一条增广链，以调整量=1改进f ，得 到的新可行流 f 的流量，有 v(f )= v(f )+1， 设一个网络D=（V，A，C），对于每一个弧 (vi ,vj )A ,给定一个单位流量的费用 bij 0 ，网 络系统的最小费用最大流问题，是指要寻求一个 最大流 f ，并且流的总费用。 达到最小。 135 而此时总费用 b(f ) 比 b( f ) 增加了 结论：如果可行流 f 在流量为v(f )的所有 可行流中的费用最小，并且 是关于f 的所有 增广链中的费用最小的增广链，那么沿增广链 我们将 叫做这条增广链的费用。 136 调整可行流f，得到的新可行流f ，也是流量为 v(f )的所有可行流中的最小费用流。依次类推， 当f 是最大流时，就是所要求的最小费用最大流。 显然，零流f =0是流量为0的最小费用流。一 般地，寻求最小费用流，总可以从零流f =0开始 。 下面的问题是：如果已知f 是流量为v(f)的最小费 用流，那么就要去寻找关于f 的最小费用增广链。 137 对此，重新构造一个赋权有向图 M( f )，其顶 点是原网络D的顶点，而将D中的每一条弧 ( vi , vj ) 变成两个相反方向的弧（vi , vj）和(vj , vi)，并且定 义M ( f )中弧的权wij为： 权为+的弧从 M( f ) 中略去。 (其中+的含义为：这条边已 经饱和，不管付出多大代价 ， 也不能再增大流量) (其中+的含义为：此边流量 已经减少到0，不能再减少 ) 关键还是对增广链作用的理解。 138 增广链的作用:增大流量； 增广链满足的条件：正向弧是非饱和弧（非饱和弧的 作用是增大流量），逆向弧是非零流弧（非零流弧 的作用是减少流量）； 饱和弧的作用：减少流量； 零流弧的作用：增大流量； 非饱和非零流弧的作用：增大流量和减少流量。 关键还是对增广链作用的理解。 139 这样，在网络D中寻找关于f 的最小费用增广 链就等于价于在M(f )中寻求从vs 到vt 的最短路。 算法开始，取零流f (0) =0.一般地，如果在第 K-1步得到最小费用流f (K-1),则构造图 M( f (k-1) )。 在图M(f (k-1)中，寻求从vs到vt的最短路。如果不存 在最短路，则f (k-1)就是最小费用最大流。如果存在 最短路，则在原网络D中得到相对应（一一对应） 的增广链 140 在增广链上对f (k1)进行调整，取调整量 令： 得到一个新的可行流f(k)，在对f(k)重复以上的步骤， 直到D中找不到相对应的增广链时为止。 141 例5.9 求图6-24 所示网络中的最小费用最 大流，弧旁的权是（bij , cij）. (bij ,cij) (1, 8) (3,10) (2, 4) (6, 2) (1,7) (4, 10) (2, 5) v1 v2 vs v3 vt 图 5-24 142 解：解：（1）取初始可行流为零流f (0)=0,构造赋权 有向图M(f(0),求出从vs到vt的最短路(vs ,v2 ,v1 ,vt),如 图8.25a 中双箭头所示。 (1) (3) (2) (6) (1) (4) (2) M(f(0) v1 vs v2v3 vt 图 5.25 a 143 （2）在原网络D中，与这条最短路相对应的增广 链为=（vs ,v2 ,v1 ,vt ）。 （3）在上对f (0)=0进行调整，取=5，得到 新可行流f (1)，如图5.25b所示。按照以上的算法，依 次类推。 144 (8,5) (10,0) (4,0) (2,0) (7,5) (10,0) (5,5) 图 5 . 25b f(1),v( f (1)=5 v1 vs v2v3 vt M( f (1) ) 图 5.25 c v1 (2) ( -1) v3 (1) (3) (6) (1) (4) (-2) (-1)vs v2 vt = min 8 0 , 5 0 , 7 0 = 5 ,调整得 构造赋权有向图M(f(1) , 并 求出从vs到vt的最短路（vs , v1 , vt） 145 (2,0) (5,5) (8,5) (4,0) (7,7) (10,2) (10,0) 图5 . 25 d f (2),v( f (2)=7 v1 vs v2v3 vt M( f (2) ) 图 5 .25 e (1) (3) (2) (6) (-1) (4) (-2) (-1) (-4) v1 vs v3 vt v2 调整量为 = min 10 0 , 7 5 = 2，调整得 构造赋权有向图M(f(2), 并求出从vs到vt的最短路 （vs , v2 , v3 , vt） 146 (8,8) (10,3) (4,3) (2,0) (7,7) (10,2) (5,5) 图 6 . 25 f f (3),v( f (3)=10 v1 vs v2v3 vt 调整量为 = min 8 5 , 10 0 , 4 0 = 3， 调整得 (-1) (3) (2) (6)