运筹学课件ch10图与网络分析.ppt

《运筹学课件ch10图与网络分析.ppt》由会员分享，可在线阅读，更多相关《运筹学课件ch10图与网络分析.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第十十章章图与网络分析图与网络分析Graph&Network Analysis章节大纲章节大纲章节大纲章节大纲1.图的基本概念图的基本概念2.树与最小支撑树的应用树与最小支撑树的应用3.最短路问题最短路问题4.网络最大流问题网络最大流问题5.最小费用最大流问题最小费用最大流问题1847年年 物理学家克希荷夫发表了关于树的第一篇论文物理学家克希荷夫发表了关于树的第一篇论文1857年年 英国数学家凯莱利用树的概念研究有机化合物的分子结构英国数学家凯莱利用树的概念研究有机化合物的分子结构 1878年雪尔佛斯脱首次使用年雪尔佛斯脱首次使用“图图”这个名词这个名词 1936年匈牙利数学家哥尼格发表了第

2、一本图论专著年匈牙利数学家哥尼格发表了第一本图论专著有限图与无限图的理论有限图与无限图的理论20世纪世纪50年代年代 图论形成了两个本质上不同的发展方向图论形成了两个本质上不同的发展方向图论系统的理论研究图论系统的理论研究1736年年 数学家欧拉发表了关于图的第一篇论文数学家欧拉发表了关于图的第一篇论文图论的代数方向图论的代数方向图论的最优化方向图论的最优化方向1736年年 瑞士数学家瑞士数学家 欧拉（欧拉（E.Euler)提出提出“七桥问题七桥问题”通过每座桥刚好一次又回到原地通过每座桥刚好一次又回到原地。是否可以是否可以一笔画？一笔画？1859年年 英国数学家英国数学家 哈密尔顿哈密尔顿(

3、Hamiltonian)用一个规则的实心十二面体，它的用一个规则的实心十二面体，它的20个顶点标出世界个顶点标出世界著名的著名的20个城市，要求游戏者找一条沿着各边个城市，要求游戏者找一条沿着各边通过每通过每个顶点刚好一次个顶点刚好一次的闭回路，即的闭回路，即“环球旅行环球旅行”。由于运筹学、计算机科学和编码理论中的很多由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的注意和问题都可以化为哈密顿问题，从而引起广泛的注意和研究。研究。发明发明“环球旅行环球旅行”游戏游戏用图论的语言来说，游戏的目的是在十二面体的图中用图论的语言来说，游戏的目的是在十二面体的图中找出一

4、个生成圈。这个问题后来就被称为哈密顿问题。找出一个生成圈。这个问题后来就被称为哈密顿问题。1850年年 英国人格思里提出了英国人格思里提出了“四色猜想四色猜想”1976年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上，年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上，用了用了1200个小时，作了个小时，作了100亿个判断，终于完成了四色定理的证明。亿个判断，终于完成了四色定理的证明。任何一个平面图，都可以任何一个平面图，都可以用四种颜色用四种颜色来染色，使得来染色，使得任何两个相邻的区域有不同的颜色任何两个相邻的区域有不同的颜色。世界近代三大数学难题之一

5、世界近代三大数学难题之一 格思里格思里和其弟弟格里斯和其弟弟格里斯德德摩尔根摩尔根的好友、著名数学家哈密尔顿爵士的好友、著名数学家哈密尔顿爵士几百年来，许多数学家致力于这项研究：几百年来，许多数学家致力于这项研究：格思里格思里弟弟的老师、著名数学家德弟弟的老师、著名数学家德摩尔根摩尔根英国最著名数学家凯利英国最著名数学家凯利18781880年两年间，著名的律师兼数学家肯普和泰勒两人分别提交了证明四年两年间，著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。11年

6、后，即年后，即1890年，数学家赫伍德以自己的精确计算指出肯普的证明是错误的。年，数学家赫伍德以自己的精确计算指出肯普的证明是错误的。不久，泰勒的证明也被人们否定了。不久，泰勒的证明也被人们否定了。例例 2 有有A、B、C、D、E 五个球队举行比赛，已知五个球队举行比赛，已知A 队与其它各队都比赛过一队与其它各队都比赛过一 次；次；B 队和队和A、C 队比赛过；队比赛过；C 队和队和A、B、D 队赛过；队赛过；D 队和队和A、C、E 队比赛过；队比赛过；E 队和队和A、D 队比赛过。队比赛过。那么：这种比赛关系就可以用图来表示那么：这种比赛关系就可以用图来表示ABCDE点：表示球队点：表示球队

7、点与点之间的连线：表示两球队间比赛过点与点之间的连线：表示两球队间比赛过例例3 五个球队之间的比赛结果是：五个球队之间的比赛结果是：A队胜了队胜了B、D、E队；队；B队胜了队胜了C队；队；C队队 胜了胜了A、D队；队；D队没有胜过；队没有胜过；E队胜了队胜了D队；队；用点与点之间带箭头的线描述用点与点之间带箭头的线描述“胜负关系胜负关系”关系关系A队三胜一负队三胜一负B队一胜一负队一胜一负C队两胜一负队两胜一负D队三战三负队三战三负E队一胜一负队一胜一负从图从图中中可以看出各球队之间比赛情况：可以看出各球队之间比赛情况：ABCDE那么，这种胜负关系该如何用图来描述呢？那么，这种胜负关系该如何用

8、图来描述呢？1 10 0.1.1 图图的的的的基本概念基本概念基本概念基本概念v定义一个一个图图G是指一个二元组是指一个二元组(V(G),E(G)，即图是，即图是由点及点之间的联线所组成。由点及点之间的联线所组成。其中其中:1）图中的点称为图的顶点）图中的点称为图的顶点(vertex)，记为：记为：v2）图中的连线称为图的边）图中的连线称为图的边(edge)，记为：记为：e vi,vj，vi、vj是边是边 e 的端点。的端点。3）图中带箭头的连线称为图的弧）图中带箭头的连线称为图的弧(arc)，记为：记为：a(vi,vj)，vi、vj是弧是弧 a 的的 端点。端点。要研究某些对象间的二元关系时

9、，就可以借助于图进行研究要研究某些对象间的二元关系时，就可以借助于图进行研究v分类无向图：点集无向图：点集V和边集和边集E构成的图称为无向图构成的图称为无向图(undirected graph)，记为：，记为：G(V，E)若这种二元关系是对称的，则可以用无向图进行研究若这种二元关系是对称的，则可以用无向图进行研究有向图：点集有向图：点集V和弧集和弧集A构成的图称为有向图构成的图称为有向图(directed graph)，记为：，记为：D(V，A)若这种二元关系是非对称的，则可以用有向图进行研究若这种二元关系是非对称的，则可以用有向图进行研究有限图有限图:若一个图的顶点集和边集都是有限集，则若一

10、个图的顶点集和边集都是有限集，则称为称为有限图有限图.只有一个顶点的图称为只有一个顶点的图称为平凡图平凡图，其他的所有图都称为，其他的所有图都称为非平凡图非平凡图.1 图反映对象之间关系的一种工具，与几何图形不同。图反映对象之间关系的一种工具，与几何图形不同。2 图中任何两条边只可能在顶点交叉，在别的地方是立体交叉，不是图的顶点。图中任何两条边只可能在顶点交叉，在别的地方是立体交叉，不是图的顶点。3 图的连线不用按比例画，线段不代表真正的长度，点和线的位置有任意性。图的连线不用按比例画，线段不代表真正的长度，点和线的位置有任意性。4 图的表示不唯一。如：以下两个图都可以描述图的表示不唯一。如：

11、以下两个图都可以描述“七桥问题七桥问题”。图的特点：图的特点：3 奇点：次为奇数的点。奇点：次为奇数的点。4 偶点：次为偶数的点。偶点：次为偶数的点。5 孤立点：次为零的点。孤立点：次为零的点。6 悬挂点：次为悬挂点：次为1的点。的点。1 端点：若端点：若e=u，v E，则称则称u，v 是是 e 的端点。的端点。2 点的次：以点点的次：以点 v 为端点的边的个数称为点为端点的边的个数称为点 v 的次，记为：的次，记为：d(v)。在无向图在无向图G中，与顶点中，与顶点v关联的边的数目关联的边的数目(环算两次环算两次),称为顶点称为顶点v的的度度或或次数次数，记为，记为d(v)或或 dG(v).在

12、有向图中，从顶点在有向图中，从顶点v引出的边的数目称为顶点引出的边的数目称为顶点v的的出度出度，记为，记为d+(v)，从顶点，从顶点v引引入的边的数目称为入的边的数目称为v的的入度入度，记为，记为d-(v).称称d(v)=d+(v)+d-(v)为顶点为顶点v的的度度或或次次数数点点(vertex)的概念的概念例例1 G=(V,E)Vv1,v2,v3,v4,v5,v6,v7 Ee1,e2,e3,e4,e5,e6,e7,e8 奇点：奇点：v2，v3偶点：偶点：v1，v4v1v2v3v4e1e2e3e4e5e6e7e8v5v6v7悬挂点：悬挂点：v5，v6孤立点：孤立点：v7如：如：e1、e2 是多

13、重边。是多重边。e8 是悬挂边。是悬挂边。v1v2v3v4e1e2e3e4e5e6e7e8v5v6v7e7 是环是环图图 G 或或 D 中点的个数记为中点的个数记为 p(G)或或 p(D)，简记为简记为 p图图 G 或或 D 中边的个数记为中边的个数记为 q(G)或或 q(D)，简记为简记为 q点的个数点的个数p7边的个数边的个数q8定理定理推论推论 任何图中奇点的个数为偶数任何图中奇点的个数为偶数3 初等链（圈）：若链（圈）中各点均不同，则称为初等链（圈）初等链（圈）：若链（圈）中各点均不同，则称为初等链（圈）。如：如：v1,e1,v2,e3,v3 4 简单链（圈）简单链（圈）：若链（圈）中

14、各边均不同，则称为间单链（圈）：若链（圈）中各边均不同，则称为间单链（圈）。1 链：一个点、边的交替的连续序列链：一个点、边的交替的连续序列vi1,ei1,vi2,ei2,vik,eik称为链，记为称为链，记为。2 圈圈(cycle)：若链若链的的 vi1vik，即起点终点，则称为圈。即起点终点，则称为圈。链链(chain)的概念的概念v1v2v3v4e1e2e3e4e5e6e7e8v5v6v7 v1,e1,v3,e4,v4：链链初等链初等链简单链简单链不是链不是链 v1,e1,v2,e3,v3,e6,v1 圈圈初等圈初等圈间单圈间单圈圈一定是链，链不一定是圈圈一定是链，链不一定是圈路路路路P

15、ATHPATHv路路(path)：顶点和边均互不相同的一条途径。：顶点和边均互不相同的一条途径。v若在有向图中的一个链若在有向图中的一个链中每条弧的方向一致，中每条弧的方向一致，则称则称为路。（无向图中的路与链概念一致。）为路。（无向图中的路与链概念一致。）v回路回路(circuit)：若路的第一个点与最后一个点：若路的第一个点与最后一个点相同，则称为回路。相同，则称为回路。v连通性:点i和j点是连通的：G中存在一条（i，j）路G是连通的：G中任意两点都是连通的 路一定是链，但链不一定是路 例例 在右边的无向图中：在右边的无向图中：途径或链：途径或链：迹或简单链：迹或简单链：路或路径：路或路径

16、：圈或回路：圈或回路：v1v2v3v4e1e2e3e4e5e6 v1,e1,v2,e3,v3 链链不是路不是路 v1,e2,v2,e3,v3 链链且是路且是路 v1,e2,v2,e1,v1 链链是回路是回路 注意区别：环、圈、回路的概念注意区别：环、圈、回路的概念在右边的有向图中：在右边的有向图中：连通图连通图(connected graph)：若图中任何两点间至少有一条链，则称为连通图若图中任何两点间至少有一条链，则称为连通图。否则，。否则，为不连通图。为不连通图。简单图简单图(simple graph)：一个无环、无多重边的图称为间单图。一个无环、无多重边的图称为间单图。多重图多重图(mu

17、ltiple graph)：一个无环，但有多重边的图称为多重图。一个无环，但有多重边的图称为多重图。连通分图：非连通图的每个连通部分称为该图的连通分图。连通分图：非连通图的每个连通部分称为该图的连通分图。基础图：去掉有向图中所有弧上的箭头，得到的图称为原有向图的基础图。基础图：去掉有向图中所有弧上的箭头，得到的图称为原有向图的基础图。图图G(V,E)为不连通图为不连通图但但G(V,E)是是G的连通分图的连通分图其中：其中：Vv1,v2,v3,v4 Ee1,e2,e3,e4,e5,e6,e7图图G(V,E)是多重图是多重图v1v2v3v4e1e2e3e4e5e6e7e8v5v6v7连通图连通图1

18、0.2 10.2 树（树（treetree）一、树的定义一、树的定义树：一个无圈的连通图称为树。树：一个无圈的连通图称为树。例：例：红楼梦红楼梦中贾府人物之间的血统关系树中贾府人物之间的血统关系树贾演贾演贾源贾源贾代化贾代化贾代善贾代善贾放贾放贾敷贾敷贾珍贾珍贾蓉贾蓉贾赦贾赦贾政贾政贾琏贾琏贾宝玉贾宝玉贾环贾环贾珠贾珠贾兰贾兰（宁国府）（宁国府）（荣国府）（荣国府）二、树的性质二、树的性质1 设图设图G(V,E)是一个树，点数是一个树，点数P(G)2，则则 G 中至少有中至少有两个悬挂点。两个悬挂点。2 图图G(V，E)是一个树是一个树G不含圈，且恰有不含圈，且恰有p-1条边条边（p是点数）。

19、是点数）。3 图图G(V，E)一个树一个树 G 是连通图，且是连通图，且q(G)p(G)1（q是边数）。是边数）。4 图图G(V，E)是树是树 任意两个顶点之间恰有一条链。任意两个顶点之间恰有一条链。图的支撑树图的支撑树(spanning tree)(spanning tree)1 支撑子图：设图支撑子图：设图G(V，E)，图，图G(V，E)的的VV，E E，则称则称G是是G的一个的一个 支撑子图。支撑子图。2 支支 撑撑 树：设图树：设图T(V，E)是图是图G(V，E)的支撑子图，如果的支撑子图，如果T(V，E)是一个树，是一个树，则称则称 T 是是 G 的一个支撑树。的一个支撑树。如何寻找

20、如何寻找“支撑树支撑树”呢呢？图图G(V，E)的点集与图的点集与图G(V，E)的点集相同，的点集相同，VV，但图但图G(V，E)的边集仅是图的边集仅是图G(V，E)的子集的子集E E。特点边少、点不少。1 最小树定义如果如果T(V，E)是是 G 的一个支撑树，称的一个支撑树，称 T 中所有边的权之和为支撑树中所有边的权之和为支撑树T的权，的权，记为记为W（T），），即：即：若支撑树若支撑树T*的权的权W（T*）是）是G的所有支撑树的权中最小者，的所有支撑树的权中最小者，则称则称T*是是G 的最小的最小支撑树（最小树），支撑树（最小树），即：即：W（T*）min W(T)最小树最小树(minim

21、um spanning tree)(minimum spanning tree)问题问题例例8：1）破圈法：在图破圈法：在图G中任取一个圈，从圈中去掉权数最大的边，对余下中任取一个圈，从圈中去掉权数最大的边，对余下的图重复这个的图重复这个 步骤，步骤，直到直到G中不含圈为止，即可得到中不含圈为止，即可得到 G 的一个最小树。的一个最小树。2 2 求最小树的算法（求最小树的算法（求最小树的算法（求最小树的算法（minimum spanning tree algorithmminimum spanning tree algorithm）v2v14v3v4v53532142且且p5 q4 1）在圈）

22、在圈 v1v2v3v1中去掉中去掉v1,v32）在圈）在圈 v2v4v3v2中去掉中去掉v2,v33）在圈）在圈 v2v4v5v2中去掉中去掉v2,v54）在圈）在圈 v3v4v5v3中去掉中去掉v3,v5图中已经不含圈图中已经不含圈 已经求出了最小树已经求出了最小树 W(T*)42129 避圈法是一种选边的过程，其步骤如下：避圈法是一种选边的过程，其步骤如下：1.从网络D中任选一点vi，找出与vi相关联的 权最小的边vi，vj，得第二个顶点vj；2.把顶点集V分为互补的两部分V1,1，其中用避圈法解用避圈法解用避圈法解用避圈法解v5v1v3v6v4v2v7255233575711最小部分树如

23、图上红线所示；最小权和为14。思考：破圈法与必避圈法各自的思路是怎样做的呢？见圈就破，去掉其中权最大的。加边取其中最小的。例例8 要在要在5个城市架设电话线，使城镇之间能够通话两镇直接连接，每两个城镇之个城市架设电话线，使城镇之间能够通话两镇直接连接，每两个城镇之 间的架设电话线的造价如下图所示，各边上的数字为造价（间的架设电话线的造价如下图所示，各边上的数字为造价（单位：万元单位：万元）。）。问：应如何架线，可使总造价最小？问：应如何架线，可使总造价最小？v1v3v2v5v4v6v7252463112424解：解：v1v3v2v5v4v6v72524631124241 破圈法：破圈法：2 避

24、圈法：避圈法：v1v3v2v5v4v6v7252463112424总造价：总造价：W(T*)22112210（万元）万元）本节重点及难点本节重点及难点重点重点难点难点1 图的概念及性质图的概念及性质4 树的概念及性质树的概念及性质5 部分树及最小树部分树及最小树 2 点的概念及性质点的概念及性质3 链的概念及性质链的概念及性质1 图的概念及性质图的概念及性质4 部分树及最小树部分树及最小树 2 点的概念及性质点的概念及性质3 链的概念及性质链的概念及性质10.3最短路问题最短路问题 最短路问题是图论应用的基本问题，很多实际最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运

25、输网络最小费问题，如线路的布设、运输安排、运输网络最小费用流等问题用流等问题,都可通过建立最短路问题模型来求解都可通过建立最短路问题模型来求解.1)1)求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路.2)求赋权图中任意两点间的最短路求赋权图中任意两点间的最短路.例例 如如下下图图所所示示的的单单行行线线交交通通网网，每每个个弧弧旁旁边边的的数数字字表表示示这这条条单单行行线线的的长长度度。现现在在有有一一个个人人要要从从v1出出发发，经经过过这个交这个交 通网到达通网到达v6 6，要寻求总路要寻求

26、总路 程最短的线程最短的线 路。路。v6v5v3v1v4v2365112436最短路径问题最短路径问题最短路径问题最短路径问题 2)在赋权图在赋权图G中，从顶点中，从顶点u到顶点到顶点v的具有最小权的具有最小权定义定义 1)若若H是赋权图是赋权图G的一个子图，则称的一个子图，则称H的各的各边的权和边的权和 为为H的的权权.类似地，若类似地，若称为路称为路P的的权权若若P(u,v)是赋权图是赋权图G中从中从u到到v的路的路,称称 的路的路P*(u,v)，称为，称为u到到v的的最短路最短路 3)把赋权图把赋权图G中一条路的权称为它的中一条路的权称为它的长长，把，把(u,v)路的最小权称为路的最小权

27、称为u和和v之间的之间的距离距离，并记作，并记作 d(u,v).给给定定一一个个赋赋权权有有向向图图D(V，A),对对每每一一条条弧弧aijw(vi，vj)，相相应应地地有有权权w(aij)=wij，又又有有两两点点vs、vt V,设设 p 是是 D 中中从从vs 到到vt 的的一一条条路路，路路 p 的的权权是是 p 中中所所有有弧弧的的权权之之和和,记记为为w(p)最最短短路路问问题题就就是求从是求从vs 到到vt 的的路中一条权最小的路路中一条权最小的路 p*:最短路径问题最短路径问题最短路径问题最短路径问题 10.3 10.3 最短路径问题最短路径问题最短路径问题最短路径问题 下下面面

28、仅仅介介绍绍在在一一个个赋赋权权有有向向图图中中寻寻求求最最短短路路的的方方法法双双双双标标标标号号号号法法法法（Dijkstra算算法法），它它是是在在19591959年年提提出出来来的的。目目前前公公认认，在在所所有有的的权权wij 00时时，这这个个算算法法是是寻寻求求最最短短路路问问题题最最好好的的算算法法。并并且且，这这个个算算法法实实际际上上也也给给出出了了寻寻求求从从一一个个始始定定点点vs到任意一个点到任意一个点vj的最短路。的最短路。二、最短路问题的算法二、最短路问题的算法二、最短路问题的算法二、最短路问题的算法 方法：标号法（方法：标号法（DijkstraDijkstra，

29、19591959）给每点给每点vjvj标号标号 djdj，vivi。其中其中djdj为为v v1 1至至vjvj的最短距，的最短距，vivi为最短路上为最短路上VjVj的前一点。的前一点。标号法步骤：标号法步骤：例例 求求v1到到v6的最的最短路。短路。44，V2V2 5 5，V1V1 55，V3V3 33，V1V1 77，V5V599，V2V288，V3V3 1010，V4V4 11 11，V5V5（1 1）首先将）首先将v1赋给赋给VS。给。给V1以以P标号标号，d(d(v1)0 0，vs=V1=V1（2）考察考察V1的关联边，选最小权的边的端点加以标号的关联边，选最小权的边的端点加以标号

30、 0,V10,V1v6v5v3v1v4v236511243610.3 10.3 最短路径问题最短路径问题最短路径问题最短路径问题 用标号法解例用标号法解例3v5v1v3v6v4v2v72552335757110，v12，v13，v1其中2=min0+2,0+5,0+3其中3=min0+3，0+5，2+2，2+74，v27，v38，v513，v6最短距为13；4，v4最短路有2条为v1-v2-v3-v5-v6-v7 和v1-v4-v3-v5-v6-v7。最短路问题的应用例子 某汽车公司正在制订5年内购买汽车的计划。下面给出一辆新汽车的价格以及一辆汽车的使用维修费用(万元)：年号 1 2 3 4

31、5 价格22.12.32.42.6 汽车使用年龄0112233445维修费用0.71.11.522.5试用网络分析中求最短路的方法确定公司可采用的最优策略。方法：以年号作顶点绘图，连线表示连续使用期间，以 费用作路长。1345622.73.85.37.39.82.87.43.95.43.13.34.23.04.15.62.7,13.8,17.9,39.4,35.3,1P284 10.4（a）10.7 作作 业业 10.410.4 最大流问题最大流问题 v 流量问题在实际中是一种常见的问题。如公路系统中有车辆流量问题，供电系统中有电流量问题等等。最大流问题是在单位时间内安排一个运送方案，将发点的

32、物质沿着弧的方向运送到收点，使总运输量最大。网络赋权图，记D=（V，E，C），其中C=c1，cn，ci为边ei上的权（设ci ）。网络分析主要内容最小部分树、最短路、最大流。1.问题 已知网络D=（V，A，C），其中V为顶点集，A为弧集，C=cij为容量集，cij 为弧（vi，vj）上的容量。现D上要通过一个流f=fij，其中fij 为弧（vi，vj）上的流量。问应如何安排流量fij可使D上通过的总流量v最大？例如：v4v2vsv1vtv32131453252.数学模型数学模型（容量约束）（平衡条件）问题：最大流问题的决策变量、目标函数、约束条件各是什么？3.基本概念与定理基本概念与定理如：在

33、前面例举的网络流问题中，若已给定一个可行流（如括号中后一个数字所示），请指出相应的弧的类型。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）（2）可增值链（增广链）可增值链（增广链）v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）（3）截集与截量截集与截量截量：截集上的容量和，记为 。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）例4 对于下图，若V1=vs，v1，请指出相应的截集与截量。例4 对

34、于下图，若V1=vs，v1，请指出相应的截集与截量。解：v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）（4）流量与截量的关系流量与截量的关系截集上的流量和相应于截集的反向弧上流量和最大流最小割定理：v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）4.解法解法（5）最大流的判别条件最大流的判别条件步骤：例例5 用标号法求下面网络的最大流。用标号法求下面网络的最大流。解：第一次标号及所得可增值链如图，调量 =1，调后进行第二次标号如图。第二次标号未进行到底，得最大流

35、如图，最大流量v=5，同时得最小截v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）2020最大流问题的应用例子（1）汽车由A城通往B城的可能的路线如下图所示。环境保护部门拟建立足够数量的汽车尾气检查站，以便使每辆汽车至少必须经过一个检查站。建立检查站的费用根据各路段的条件而有所不同(如图上数字所示)。若求这个问题的最小费用解，可使用 模型。a.最短路模型；b.最大流模型；c.最小支撑树模型AacbdefgB824452643367378某汽车公司有两家汽车配件制造厂某汽车公司有两家汽车配件制造厂A和和B，负责向两个服务配送中心，

36、负责向两个服务配送中心C和和D供应汽车配件。运送的道路网络及各路段的允许通过容量如下供应汽车配件。运送的道路网络及各路段的允许通过容量如下图所示。假设配件厂的供应量无限制。求向图所示。假设配件厂的供应量无限制。求向C、D的供应量最大的运的供应量最大的运送方案和相应的最大供应量。送方案和相应的最大供应量。AB1234567CD60205070403050406030402010408070st求解：最大流模型求解：最大流模型10020060160最大流问题的应用例子（2）AB1234567CD60205070403050406030402010408070st100200601601。确定从。确

37、定从s到到t的可行流（观测法）的可行流（观测法）6016070801020403030606030407030302040801402。确定从。确定从s到到t的最小割（截集）的最小割（截集）标号集标号集s,A,B，2，4未标号集未标号集1,3,5,6,7,c,D,t割集割集:(a,1)(2,6)(b,3)(4,7)割量：割量：60+60+70+30=220此时已找到最大流，即此可行流就是最佳的运送方案。此时已找到最大流，即此可行流就是最佳的运送方案。C、D的供应量分别为的供应量分别为60和和160P285 11.12作作 业业 某个城市的街道图如下图，图上数字为道路的最大通行能某个城市的街道图如下图，图上数字为道路的最大通行能力。求从力。求从S到到T的最大流，如果要提高的最大流，如果要提高S到到T的车流量，应的车流量，应首先改扩哪几条道路？首先改扩哪几条道路？STABC101510152020515