运筹学基础及应用第五图与网络分析.pptx

2024/8/11 周日1运筹学运筹学OPERATIONS RESEARCH2024/8/11 周日2 1图的基本概念与模型图的基本概念与模型 2树图和图的最小部分树树图和图的最小部分树 3最短路问题最短路问题 4网络的最大流网络的最大流 5最小费用流最小费用流第六章第六章 图与网络分析图与网络分析2024/8/11 周日3BACD 当地的居民热衷于这当地的居民热衷于这样一个问题：样一个问题：一个漫步者如何能够走过一个漫步者如何能够走过这七座桥，并且每座桥只这七座桥，并且每座桥只能走过一次，最终回到原能走过一次，最终回到原出发地。出发地。尽管试验者很多，尽管试验者很多，但是都没有成功。但是都没有成功。哥尼斯堡的七桥问题哥尼斯堡的七桥问题2024/8/11 周日4 为为了了寻寻找找答答案案，17361736年年欧欧拉拉把把陆陆地地缩缩为为一一点点，把把桥桥作作为为连连接接点点的的边边，将将这这个个问问题题抽抽象象成成图图形形的的一一笔笔画画问问题题。即即能能否否从从某某一一点点开开始始不不重重复复地地一一笔笔画画出出这这个个图图形形，最最终终回回到到原原点点。欧欧拉拉在在他他的的论论文文中中证证明明了了这这是是不不可可能能的的，因因为为这这个个图图形形中中每每一一个个顶顶点点都都与与奇奇数数条条边边相相连连接接，不不可可能能将将它它一一笔笔画画出出，这这就就是是古古典典图图论论中的第一个著名问题。中的第一个著名问题。BACD2024/8/11 周日5 在在实实际际的的生生产产和和生生活活中中，人人们们为为了了反反映映事事物物之之间间的的关关系系，常常在纸上用点和线来画出各式各样的示意图。常常在纸上用点和线来画出各式各样的示意图。例例 有有六六支支球球队队进进行行足足球球比比赛赛，我我们们分分别别用用点点v v1 1v v6 6 表表示示这这六六支支球球队队，它它们们之之间间的的比比赛赛情情况况，也也可可以以用用图图反反映映出出来来，已已知知v v1 1 队队战战胜胜v v2 2 队队，v v2 2 队队战战胜胜v v3 3队队，v v3 3 队队战战胜胜v v5 5 队队，如如此此等等等等。这这个个胜胜负负情情况况，可可以以用用下下图图所所示示的有向图反映出来。的有向图反映出来。v v3 3v v1 1v v2 2v v4 4v v6 6v v5 52024/8/11 周日66.16.1图的基本概念与模型图的基本概念与模型 图图（graphgraph）是由一些是由一些结点或顶点结点或顶点（nodesnodes or or verticesvertices ）以及连接点的以及连接点的边边（edgesedges）构成。记做构成。记做G G=V V,E E ，其中其中 V V 是顶点的集合，是顶点的集合，E E 是边的集合。是边的集合。给图中的点和边赋以具体的含义和权值，我们称这样的给图中的点和边赋以具体的含义和权值，我们称这样的图为图为网络图网络图（赋权图）（赋权图）一、一、基本概念基本概念2024/8/11 周日7 图中的点用图中的点用 v v 表示，边用表示，边用 e e 表示，对每条边可用它所表示，对每条边可用它所联结的点表示，如图，则有：联结的点表示，如图，则有：e1=v1,v1，e2=v1,v2或或e2=v2,v1用点和点之间的线所构成的图，反映实际生产和生用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。通常用活中的某些特定对象之间的特定关系。通常用点点表表示研究对象示研究对象,用用点与点之间的线点与点之间的线表示研究对象之间表示研究对象之间的特定关系。一般情况下，图中点的相对位置如何，的特定关系。一般情况下，图中点的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，的关系，显的并不重要，因此，图论中的图与几何图论中的图与几何图，工程图等本质上是不同的。图，工程图等本质上是不同的。2024/8/11 周日8端点，关联边，相邻端点，关联边，相邻 若边若边 e e 可表示为可表示为e e =v vi i ,v vj j，称称 v vi i 和和 v vj j 是边是边 e e 的的端点端点，同时称边，同时称边 e e 为点为点 v vi i 和和 v vj j 的的关联边关联边，若点，若点 v vi i ,v vj j 与同一条边关联，称点与同一条边关联，称点 v vi i 和和 v vj j 相邻相邻；若边；若边 e ei i 与与 e ej j 有有公共端点，称边公共端点，称边 e ei i 和和 e ej j 相邻相邻；如果边如果边 e e 的两个端点相重，称的两个端点相重，称该边为该边为环环，如果两个点之间的边多，如果两个点之间的边多于一条，称为具有于一条，称为具有多重边多重边，对无环、，对无环、无多重边的图称为无多重边的图称为简单图简单图。环，多重边，简单图环，多重边，简单图2024/8/11 周日9次，奇点，偶点，孤立点次，奇点，偶点，孤立点 与某个点相关联的边的数目，称为该点的与某个点相关联的边的数目，称为该点的次次（或（或度、度、线度线度），记作），记作 d d(v v)。次为奇数的点称为次为奇数的点称为奇点奇点，次为偶数的，次为偶数的点称为点称为偶点偶点，次为零的点称为，次为零的点称为孤立点孤立点。如图：如图：奇点为奇点为 v v5 5，v v3 3偶点为偶点为 v v1 1,v v2 2,v v4 4,v v6 6孤立点为孤立点为 v62024/8/11 周日10链，圈，路，回路，连通图链，圈，路，回路，连通图 图中有些点和边的交替序列图中有些点和边的交替序列 =v v0 0,e e1 1,v v1 1,e e2 2,e ek k ,v vk k，若其各边若其各边 e e1 1,e e2 2,e ek k 各不相同，且各不相同，且任意任意 v vi,ti,t-1-1,v vit it(2(2 t t k k)都相邻，称都相邻，称 为为链链，如，如果链中所有的顶点果链中所有的顶点 v v0 0,v v1 1,v vk k也不相同，这样的链也不相同，这样的链成为成为路路，起点和终点重合的链称为，起点和终点重合的链称为圈圈，起点和终点重合的，起点和终点重合的路称为路称为回路回路，若在一个图中，若在一个图中，每一对顶点之间至少存在一条链，称每一对顶点之间至少存在一条链，称这样的图为这样的图为连通图连通图，否则称该图为，否则称该图为不连通的。不连通的。链链路路圈圈2024/8/11 周日11完全图，偶图完全图，偶图 一个简单图中若任意两点之间均有边相连，称这样的图为一个简单图中若任意两点之间均有边相连，称这样的图为完全图，含有完全图，含有 n n 个顶点的个顶点的完全图完全图，其边数有，其边数有 条。条。如果图的顶点能分成两个互不相交的非空集合如果图的顶点能分成两个互不相交的非空集合 V V1 1 和和V V2 2,使在同一集合中任意两个顶点均不相邻，称这样的图为使在同一集合中任意两个顶点均不相邻，称这样的图为偶图偶图（也称（也称二分图二分图），如果偶图的顶点集合），如果偶图的顶点集合V V1 1 和和V V2 2 之间的每一对之间的每一对顶点都有一条边相连，称这样的图为顶点都有一条边相连，称这样的图为完全偶图完全偶图，完全偶图中，完全偶图中V V1 1 含含m m 个顶点，个顶点，V V2 2 含有含有 n n 个顶点，则其边数共个顶点，则其边数共 m m n n 条。条。2024/8/11 周日12子图，部分图子图，部分图 图图 G G1 1=V V1 1,E E1 1 和和 G G2 2=V V2 2,E E2 2，如果有如果有 和和 ，称，称 G G1 1 是是 G G2 2 的一个的一个子图子图；若有若有 ，则称，则称 G G1 1 是是 G G2 2 的一个的一个部分图部分图。注意：注意：部分图也是子图，但子图不一定是部分图。部分图也是子图，但子图不一定是部分图。子图：子图：部分图部分图2024/8/11 周日1322树图和最小部分树树图和最小部分树 树图树图（简称（简称树树，记作，记作 T(V,E)T(V,E)）是无圈的连通图。（无是无圈的连通图。（无圈，无多重边）圈，无多重边）一一.树的性质树的性质性质性质1.1.任何树中必存在次为任何树中必存在次为1 1 的点。的点。次为次为1 1的点称为的点称为悬挂点悬挂点，与之关联的边称为，与之关联的边称为悬挂边悬挂边。性质性质2.2.具有具有 n n 个顶点的树恰有（个顶点的树恰有（n n-1-1）条边。条边。性质性质3.3.任何具有任何具有n n 个点、个点、(n n-1)-1)条边连通图是树。条边连通图是树。说明：说明：1.1.树中只要任意再加一条边，必出现圈。树中只要任意再加一条边，必出现圈。2.2.树中任意两点之间有且只有一条通路，从树中任意删树中任意两点之间有且只有一条通路，从树中任意删掉一条边，就不再连通。（树是最脆弱的连通图）掉一条边，就不再连通。（树是最脆弱的连通图）2024/8/11 周日14二二.图的最小部分树图的最小部分树如果如果 G G1 1 是是 G G2 2 的部分图，又是树图，则称的部分图，又是树图，则称 G G1 1 是是 G G2 2 的的部分部分树树（或（或支撑树支撑树）；）；树图的各条边称为树枝树图的各条边称为树枝(假定各边均有权重假定各边均有权重)；树枝总长最小的部分树，称为该图的树枝总长最小的部分树，称为该图的最小部分树最小部分树(也称也称最小最小支撑树支撑树)。定理定理1.1.图中任一个点图中任一个点 i i ，若若 j j 是与是与 i i 相邻点中距离最近相邻点中距离最近的，则边的，则边 i i,j j 一定包含在该图的最小部分树中。一定包含在该图的最小部分树中。推论推论.把图的所有点分成把图的所有点分成 V V 和和 两个集合，则两集合之两个集合，则两集合之间连线的最短边一定包含在最小部分树内。间连线的最短边一定包含在最小部分树内。2024/8/11 周日15三三.避圈法和破圈法避圈法和破圈法 寻找最小部分树的方法主要有寻找最小部分树的方法主要有避圈法避圈法和和破圈法破圈法两种两种。避圈法步骤：避圈法步骤：1.1.从图中任选一点从图中任选一点 v vi i ，让让 v vi i V V ，图中其余点均包含在图中其余点均包含在 中；中；2.2.从从 V V 与与 的连线中找出最小边，这条边一定包含的连线中找出最小边，这条边一定包含在最小部分树中，不妨设这条边为在最小部分树中，不妨设这条边为 v vi i ,v,vj j 将其加粗，标将其加粗，标记为最小部分树中的边。记为最小部分树中的边。3.3.令令 V Vv vj jV V，-v vj j ；4.4.重复重复2 2、3 3两步，一直到图中所有点均包含在两步，一直到图中所有点均包含在 V V 中。中。2024/8/11 周日16 避圈法另一种做法避圈法另一种做法：1.1.在所有各边中找到边权最小的一条，将其作为最小部分树中在所有各边中找到边权最小的一条，将其作为最小部分树中的第一边；在剩余的边中，仍然找到边权最小的作为最小部的第一边；在剩余的边中，仍然找到边权最小的作为最小部分树的第二条边；分树的第二条边；2.2.在剩余的边中，找到边权最小的边，查看其是否与前面的边形在剩余的边中，找到边权最小的边，查看其是否与前面的边形成圈，如果没有，则在最小部分树中添加该边，如果形成了圈，成圈，如果没有，则在最小部分树中添加该边，如果形成了圈，则不再考虑该边；则不再考虑该边；3.3.重复进行第二步，直到找到第重复进行第二步，直到找到第 n n-1-1 条边为止。（因为有条边为止。（因为有 n n 个顶点的树中一定有个顶点的树中一定有 n n-1-1 条边）条边）2024/8/11 周日17例例：分别用两种避圈法构造下图的最小部分树。：分别用两种避圈法构造下图的最小部分树。第一种解法：第一种解法：1.1.在点集中任选一点，不妨取在点集中任选一点，不妨取 S S，令令 V V=S S 2.2.找到和找到和 S S 相邻的边中，权值最小的相邻的边中，权值最小的 S S,A A 。2024/8/11 周日183.V=S,A4.4.重复第重复第2 2，3 3步，找到下一个点。步，找到下一个点。2024/8/11 周日19 第二种做法求解过程：第二种做法求解过程：2024/8/11 周日20破圈法求解步骤：破圈法求解步骤：1.1.从图从图 N N 中任取一回路，去掉这个回路中边权最大中任取一回路，去掉这个回路中边权最大的边，得到原图的一个子图的边，得到原图的一个子图 N N1 1。2.2.从剩余的子图中任找一回路，同样去掉回路中边权最从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；大的一条边，得一新的子图；3.3.重复第重复第 2 2 步，直到图中不再含有回路为止。步，直到图中不再含有回路为止。用破圈法求解上例：用破圈法求解上例：1.1.任意找到一回路，不妨取任意找到一回路，不妨取 DETDDETD，去掉边权最大的边去掉边权最大的边 T T,E E;2024/8/11 周日212.2.从剩余的子图中任找一回路，同样去掉回路中边权从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；依次类推。最大的一条边，得一新的子图；依次类推。2024/8/11 周日22破圈法的另一种解法：破圈法的另一种解法：1.1.从剩余图中找到边权最大的一条边，如果将其删除后图仍从剩余图中找到边权最大的一条边，如果将其删除后图仍然是连通的，则删除此边，否则不再考虑此边；然是连通的，则删除此边，否则不再考虑此边；2.2.重复上述步骤，直到剩余边数为重复上述步骤，直到剩余边数为 n n-1-1 为止。为止。用此法求解上述问题：用此法求解上述问题：2024/8/11 周日23注意：注意：1.1.一个图的最小部分树不唯一，该题中用几种解法得到的一个图的最小部分树不唯一，该题中用几种解法得到的结果都是相同的，是特殊情况；结果都是相同的，是特殊情况；2.2.不同解法得到的最小部分树所包含的边虽然可能不相不同解法得到的最小部分树所包含的边虽然可能不相同，但是，每个最小部分树中所有边权的总和一定都是相同，但是，每个最小部分树中所有边权的总和一定都是相同的，即都达到了最小。同的，即都达到了最小。2024/8/11 周日2433最短路问题最短路问题最短路问题最短路问题是指从给定的网络图中找出任意两点之间距离是指从给定的网络图中找出任意两点之间距离最短（权值和最小）的一条路。最短（权值和最小）的一条路。某些整数规划和动态规划问题可以归结为求最短路的问题。某些整数规划和动态规划问题可以归结为求最短路的问题。如选址问题、管道铺设选线问题、设备更新、投资等问题。如选址问题、管道铺设选线问题、设备更新、投资等问题。最短路的求法：最短路的求法：1.1.从某一点至其它各点之间最短距离的狄克斯屈拉从某一点至其它各点之间最短距离的狄克斯屈拉(DijksrtaDijksrta )算法算法;2.2.求网络图中任意两点之间的最短距离的矩阵算法。求网络图中任意两点之间的最短距离的矩阵算法。2024/8/11 周日25 一一.Dijkstra 算法算法1.1.设设 d dijij 表示图中两相邻点表示图中两相邻点 i i 与与 j j 的距离，若的距离，若 i i 与与 j j 不相邻，令不相邻，令 d dijij =，显然，显然 d diiii=0=0。Dijkstra Dijkstra 算法假设：算法假设：基本思路：基本思路：如果如果 v v1 1 v v2 2 v v3 3 v v4 4 是是 v v1 1 v v4 4 的最短路径，的最短路径，则则 v v1 1 v v2 2 v v3 3 一定是一定是 v v1 1 v v3 3 的最短路径。的最短路径。v v2 2 v v3 3 v v4 4 一定是一定是 v v2 2 v v4 4 的最短路径。的最短路径。2.2.设设 L Lsi si 表示从表示从 s s 点到点到 i i 点的最短距离。点的最短距离。2024/8/11 周日26Dijkstra Dijkstra 算法步骤：算法步骤：1.1.对起始点对起始点 s s，因，因 L Lssss=0 =0，将，将 0 0 标注在标注在 s s 旁的小旁的小方框内，表示方框内，表示 s s 点已标号；点已标号；2.2.从点从点 s s 出发，找出与出发，找出与 s s 相邻的点中距离最小的一个，相邻的点中距离最小的一个，设为设为 r r ，将将 L Lsrsr=L Lssss+d dsr sr 的值标注在的值标注在 r r 旁的小方框内，旁的小方框内，表明点表明点 r r 也已标号；也已标号；3.3.从已标号的点出发，找出与这些点相邻的所有未标号从已标号的点出发，找出与这些点相邻的所有未标号点点 p p，若有若有 L Lspsp=min min L Lssss+d dsp sp,L Lsrsr+d drp rp ，则对，则对 p p 点点标号，并将标号，并将 L Lsp sp 的值标注在的值标注在 p p 点旁的小方框内；点旁的小方框内；4.4.重复第重复第 3 3 步，直到步，直到 t t 点得到标号为止。点得到标号为止。求从起始点求从起始点 s s 到终止点到终止点 t t 的最短路径。的最短路径。2024/8/11 周日27例例.求下图中从求下图中从 v v1 1 到到 v v7 7 的最短路。的最短路。解解：(1)(1)从从 v v1 1 点出发，对点出发，对 v v1 1 点标号，将点标号，将 L L1111=0=0 标标注在注在 旁的小方框内，令旁的小方框内，令 v v1 1V V，其余点属于其余点属于 ；2024/8/11 周日28L1r=min 0+d12,0+d13 =min5,2=2=L13(2)(2)同同 v v1 1 相邻的未标号点有相邻的未标号点有v v2 2 、v v3 3 ，2024/8/11 周日29对对 v v3 3 标号，将标号，将 L L13 13 的值标注在的值标注在v v3 3 旁的小方框内；旁的小方框内；将将(v v1 1,v v3 3)加粗，并令加粗，并令 V Vv v3 3 V V，。2024/8/11 周日30L1p=min L11+d12,L13+d34,L13+d36 =min0+5,2+7,2+4=5=L12(3)(3)同同 v v1 1,v v3 3 相邻的未标号点有相邻的未标号点有v v2 2 、v v4 4、v v6 6 ，2024/8/11 周日31对对 v v2 2 标号，将标号，将 L L12 12 的值标注在的值标注在 v v2 2 旁的小方框内；旁的小方框内；将将(v v1 1,v v2 2)加粗，并令加粗，并令 V Vv v2 2 V V，2024/8/11 周日32L1p=min L12+d25,L12+d24,L13+d34,L13+d36 =min5+7,5+2,2+7,2+4 =6 =L16。(4)(4)同同 v v1 1,v v2 2 ,v v3 3 相邻的未标号点有相邻的未标号点有v v4 4、v v5 5、v v6 6 ，2024/8/11 周日33对对 v v6 6 标号，将标号，将 L L16 16 的值标注在的值标注在 v v6 6 旁的小方框内；将旁的小方框内；将(v v3 3,v v6 6)加粗，并令加粗，并令 V Vv v6 6 V V，2024/8/11 周日34L1p=min L12+d25,L12+d24,L13+d34,L16+d64,L16+d65,L16+d67 =min5+7,5+2,2+7,6+2,6+1,6+6 =7 =L14 =L15(5)(5)同同 v v1 1,v v2 2 ,v v3 3,v v6 6 相邻的未标号点有相邻的未标号点有v v4 4、v v5 5、v v7 7 ，2024/8/11 周日35对对 v v4 4,v,v5 5 同时标号，将同时标号，将 L L14 14=L L15 15 的值标注在的值标注在 v v4 4,v v5 5 旁的小方框内；将旁的小方框内；将(v v2 2,v v4 4),(),(v v6 6,v v5 5)加粗，加粗，并令并令V Vv v4 4v v5 5V V，2024/8/11 周日36L1p=min L15+d57,L16+d67 =min7+3,6+6=10=L17(6)(6)同同 v v1 1,v v2 2 ,v v3 3,v v4 4,v v5 5,v v6 6 相邻的未标号点只有相邻的未标号点只有 v v7 7 ，2024/8/11 周日37 对对 v v7 7 标号，将标号，将 L L17 17 的值标注在的值标注在 v v7 7 旁的小方框内；将旁的小方框内；将(v v5 5,v v7 7)加粗。图中粗线表明从点加粗。图中粗线表明从点 v v1 1 到网络中其它各点的最到网络中其它各点的最短路，各点旁的数字就是点短路，各点旁的数字就是点 v v1 1 到各点的最短距离。到各点的最短距离。2024/8/11 周日38二二.求任意两点间最短距离的矩阵算法求任意两点间最短距离的矩阵算法用用 DijkstraDijkstra 算法只能计算从图中某一点到其他点的最短距算法只能计算从图中某一点到其他点的最短距离，如果要计算各点之间的最短距离就需要对每个点分别计离，如果要计算各点之间的最短距离就需要对每个点分别计算，而用矩阵算法则可以同时求出所有各点间的最短距离。算，而用矩阵算法则可以同时求出所有各点间的最短距离。例例.利用矩阵算法求上述网络图中各点间的最短距离。利用矩阵算法求上述网络图中各点间的最短距离。解解.设设 d dijij 表示图中两相邻点表示图中两相邻点 i i 与与 j j 的距离，若的距离，若 i i 与与 j j 不相邻，令不相邻，令 d dijij =，显然，显然 d diiii=0=0。建立距离矩阵：。建立距离矩阵：2024/8/11 周日392024/8/11 周日40从上述距离矩阵可以看出从从上述距离矩阵可以看出从 i i 点到点到 j j 点的直接距离，但点的直接距离，但从从 i i 到到 j j 的最段距离不一定就是从的最段距离不一定就是从 i i 点直接到点直接到 j j 点。点。如上述问题中，从如上述问题中，从 v v1 1 v v2 2 的最短距离应该是的最短距离应该是minmind d1111+d d12 12,d d1212+d d22 22,d d1313+d d32 32,d d1414+d d42 42,d d1515+d d52 52,d d1616+d d62 62,d d1717+d d72 72 即即 minmind d1 1r r+d dr r2 2。因此可以构造一个新的矩阵因此可以构造一个新的矩阵 D D(1)(1)，令令 D D(1)(1)中每一个元素中每一个元素为：为：d dijij(1)(1)=minmind dirir+d drjrj ，则矩阵则矩阵 D D(1)(1)给出了网络中任给出了网络中任意两点之间直接到达及经由一个中间点时的最短距离。意两点之间直接到达及经由一个中间点时的最短距离。2024/8/11 周日41再构造矩阵再构造矩阵 D D(2)(2)，d dijij(2)(2)=minmind dir ir(1)(1)+d drj rj(1)(1)。依次类推构造矩阵依次类推构造矩阵 D D(k k)，d dijij(k k)=minmind dir ir(k k-1)-1)+d drj rj(k k-1)计算停止的控制：计算停止的控制：p p是图中顶点数。是图中顶点数。2024/8/11 周日42该例中该例中 k k=3=32024/8/11 周日43 上述上述 D D(2)(2)中的元素给出了各点间的最短距离，但是中的元素给出了各点间的最短距离，但是并没有给出具体是经过了哪些中间点才得到的这个最短距并没有给出具体是经过了哪些中间点才得到的这个最短距离，如果要知道中间点具体是什么，需要在计算过程中进离，如果要知道中间点具体是什么，需要在计算过程中进行记录。行记录。教材教材160页例页例52024/8/11 周日4444网络的最大流网络的最大流一一.网络最大流的有关概念网络最大流的有关概念 1.1.有向图与容量网络有向图与容量网络图中每条边有规定指向的图称为图中每条边有规定指向的图称为有向图有向图，有向图的边称为，有向图的边称为弧弧，记作，记作(v vi i,v vj j)，表示方向从点表示方向从点 v vi i 指向点指向点 v vj j，有向图，有向图是点与弧的集合，记作是点与弧的集合，记作 D D(V V,A A)。弧弧(v vi i,v vj j)的最大通过能力，称为该的最大通过能力，称为该弧的容量弧的容量，记为，记为c c(v vi i,v vj j)，或简记为，或简记为 c cij ij。定义了弧容量的网络称为定义了弧容量的网络称为容量网络容量网络。2024/8/11 周日45容量网络通常规定一个容量网络通常规定一个发点发点(源点，记为源点，记为s s)一个一个收点收点(汇汇点，记为点，记为t t)，网络中其余的点称为网络中其余的点称为中间点中间点。从发点到收点之间允许通过的最大流量称为从发点到收点之间允许通过的最大流量称为最大流最大流。多个收多个收(发发)点的网络可以转换为只含一个收点的网络可以转换为只含一个收(发发)点。点。2.流与可行流流与可行流流流是指加在网络各条弧上的一组负载量，对加在弧是指加在网络各条弧上的一组负载量，对加在弧(v vi i,v vj j)上的负载量记作上的负载量记作 f f(v vi i,v vj j)，或简记作或简记作 f fijij ，若网络上若网络上所有的所有的 f fijij=0=0，这个流称为，这个流称为零流零流。2024/8/11 周日46以以 v v(f f)表示网络中从表示网络中从 s st t 的的流量流量，则，则零流是可行流，求最大流就是求零流是可行流，求最大流就是求v v(f f)的最大值。的最大值。称网络上满足下述条件称网络上满足下述条件(1)(1)、(2)(2)的流为的流为可行流可行流：(1)(1)容量限制条件容量限制条件:对所有弧有对所有弧有00f f(v vi i,v vj j)c c(v vi i,v vj j)(2)(2)中间点平衡条件：中间点平衡条件：f f(v vi i,v vj j)-f f(v vj j,v vi i)=0 (=0 (i is s,t t)2024/8/11 周日47二二.割和流量割和流量割割(集）集）是指将容量网络中的发点和收点分割开，并使是指将容量网络中的发点和收点分割开，并使s st t 的流中断的一组弧的集合的流中断的一组弧的集合（截集）（截集）弧旁数字为弧旁数字为 c cij ij(f fij ij)有不同的割见教材有不同的割见教材162162页页上上图图中中 KKKK 将将网网络络上上的的点点分分割割成成 V V 和和 两两个个集集合合，并并有有 s sV V,t t ，称弧的集合称弧的集合 (V V,)=(,)=(v v1 1,v v3 3),(),(v v2 2,v v4 4)是一个割。注意，这里不包含是一个割。注意，这里不包含(v v3 3,v v2 2)。2024/8/11 周日48割的容量割的容量是组成它的集合中各弧容量之和，用是组成它的集合中各弧容量之和，用c c(V,V,)表示，表示，f f(V,V,)表示通过割表示通过割(V V,),)中所有中所有 V V 方向方向弧的流量的总和弧的流量的总和;f f(,V,V)表示通过割表示通过割 中所有中所有 V V方向弧的流量的方向弧的流量的总和，则有：总和，则有：2024/8/11 周日49从从 s st t 的流量的流量等于通过割的从等于通过割的从V V 的流量减的流量减 V V的流的流量，有：量，有：用用 v v*(f f)表示网络中从表示网络中从 s st t 的最大流，则有的最大流，则有因此，上例中最大流不会超过因此，上例中最大流不会超过1414（所有割集中最小者）（所有割集中最小者）。最大流最大流 v v*(f f)应应 最小割的容量最小割的容量(用用 c c*(V V,),)表示表示)2024/8/11 周日50三三.最大流最小割定理最大流最小割定理增广链：增广链：如果在网络的发点和收点之间能找到一条链，在这条链上：如果在网络的发点和收点之间能找到一条链，在这条链上：所有指向为所有指向为 s st t 的弧（称的弧（称前向弧前向弧，记作，记作+），），存在存在f c f f 0(0(非零非零)，（反向弧非零流反向弧非零流）这样的链称这样的链称增广链增广链。2024/8/11 周日51当有增广链存在时，找出当有增广链存在时，找出 再令再令显然，经过计算后显然，经过计算后 f f 仍然为可行流，但较原来的可行流仍然为可行流，但较原来的可行流 f f 流量增大了流量增大了 。因此，只有当网络图中找不到增广链时，因此，只有当网络图中找不到增广链时，s st t 流才不可能进一步增大。流才不可能进一步增大。2024/8/11 周日52定理定理2.2.在网络中在网络中 s st t 的最大流量等于它的最小割集的容的最大流量等于它的最小割集的容量，即量，即证明：证明：略（教材略（教材163163页）页）三三.求网络最大流的标号算法求网络最大流的标号算法 FordFord-FulkersonFulkerson 标号算法标号算法，其本质是判断是否存在增广链，其本质是判断是否存在增广链，如果存在，则找出增广链，调整流量；若不存在，则说明已如果存在，则找出增广链，调整流量；若不存在，则说明已达到最大流。达到最大流。2024/8/11 周日53第一步：首先给发点第一步：首先给发点 s s 标号标号(0,(0,(s s)。第一个数字是使这个点得到标号的前一个点的代号，因第一个数字是使这个点得到标号的前一个点的代号，因 s s 是发点，因此记为是发点，因此记为0 0。第二个数字第二个数字 (s s)表示从上一个标号到这个标号点的流量的表示从上一个标号到这个标号点的流量的最大允许调整值，最大允许调整值，s s 为发点，不限允许调整容量，故为发点，不限允许调整容量，故 (s s)=)=。第二步：列出与已标号点相邻的所有未标号点：第二步：列出与已标号点相邻的所有未标号点：1.1.考虑从标号点考虑从标号点 i i 出发的弧出发的弧(i,j i,j)（即正向弧（即正向弧)，如果，如果有有 f fijij=c cijij，不给点不给点 j j 标号；若标号；若f fijij 00，则对则对 h h 点标号，点标号，记为记为(i,i,(h h)，其中其中(h h)=min)=min(i i),),f fhihi).).3.3.如果某未标号点如果某未标号点 k k 有两个以上相邻的标号点，可按有两个以上相邻的标号点，可按 (1),(2)(1),(2)中所述规则分别计算出中所述规则分别计算出 (k k)的值，并取其的值，并取其中的最大的一个标记。中的最大的一个标记。第三步：重复第二步可能出现如下两种结果：第三步：重复第二步可能出现如下两种结果：1.1.标号过程中断，标号过程中断，t t 得不到标号，说明该网络中不存在增广得不到标号，说明该网络中不存在增广 链，给定流量即为最大流量。记已标号点集为链，给定流量即为最大流量。记已标号点集为V V，未标号点未标号点 集为集为 ，(V V,),)为网络的最小割。为网络的最小割。2.2.t t 得到标号，这时可用反向追踪法在网络中找到一条从得到标号，这时可用反向追踪法在网络中找到一条从 s st t 的有标号点以及相应的弧连接而成的增广链。的有标号点以及相应的弧连接而成的增广链。2024/8/11 周日55第四步：修改流量。第四步：修改流量。设原图中可行流为设原图中可行流为 f f ，令令这样得到网络上的一个新的可行流这样得到网络上的一个新的可行流 f f 。第五步：抹掉图上所有标号，重复第一到第四步。第五步：抹掉图上所有标号，重复第一到第四步。注意：注意：在求解步骤中，第三步起到控制运算停止的作用，在求解步骤中，第三步起到控制运算停止的作用，而不是第五步。而不是第五步。2024/8/11 周日56例例：用标号法求下述网络图用标号法求下述网络图 s t 的最大流量，并的最大流量，并找出该网络图的最小割。找出该网络图的最小割。2024/8/11 周日57解解：(1)先给先给 s 点标号点标号(0,)；2024/8/11 周日58(2)从从 s 点出发的弧点出发的弧(s,v2)，因有因有 fs20，且且(v1)=min(v2),f12)=2故对故对 v1 点标号点标号(v2,2)。(v2,v4)饱和，不标号。饱和，不标号。2024/8/11 周日60(4)弧弧(v1,v3)，因有因有 f130，且且(v4)=min(v3),f43)=1故对故对 v4 点标号点标号(v3,1)。(v3,t)饱和，不标号饱和，不标号,v2 已标号。已标号。2024/8/11 周日62(6)弧弧(v4,t)，因有因有 f4tc4t，且且(t)=min(v4),(c4t-f4t)=1故对故对 t 点标号点标号(v4,1)。2024/8/11 周日63(7)由于收点由于收点 t 得到标号，用反追踪法找出网络图得到标号，用反追踪法找出网络图上的一条增广链。上的一条增广链。2024/8/11 周日64(8)修改增广链上各弧的流量：修改增广链上各弧的流量：非增广链上的所有弧流量不变，这样得到网络图上的一个新非增广链上的所有弧流量不变，这样得到网络图上的一个新的可行流。的可行流。2024/8/11 周日65重复上述标号过程，由于对点重复上述标号过程，由于对点 s s 、v v1 1、v v2 2、v v3 3 标号后，标号后，标号中断，故图中的可行流即为最大流，标号中断，故图中的可行流即为最大流，v v*(f f)=14)=14已标号点集为已标号点集为V V=s s,v v1 1,v v2 2,v v3 3 ，未标号点集未标号点集 ，(V V,)=(3,)=(3,t t),(2,4),(2,4)为网络的最小割。为网络的最小割。2024/8/11 周日66三三.应用举例应用举例例例1：P166，例，例7ADECBF2321211111、方向含义、方向含义2、E、D之间之间3、数字含义、数字含义切断切断A、F之间的通路，相当于求最小割集。之间的通路，相当于求最小割集。2024/8/11 周日67例例2：P167，例，例81、匹配关系、匹配关系1234562、匹配限制、匹配限制145f=1 f14 f152024/8/11 周日68134f=1 f34 f14 3、等价网络图、等价网络图123456st1111111111112024/8/11 周日6955最小费用流最小费用流 在产销平衡问题中，研究的是使费用最小的物资调运方案；在产销平衡问题中，研究的是使费用最小的物资调运方案；最大流问题中考虑了联结两个点之间的弧的容量限制，但最大流问题中考虑了联结两个点之间的弧的容量限制，但是没考虑流量通过各条弧时发生的费用。是没考虑流量通过各条弧时发生的费用。实际物资调运中，既要考虑弧的容量又要考虑调运费用的实际物资调运中，既要考虑弧的容量又要考虑调运费用的节省，这就是节省，这就是最小费用流最小费用流要研究的问题。要研究的问题。即要寻求一个最大流即要寻求一个最大流 f，使得总的运输费用，使得总的运输费用 b(f)最小。最小。2024/8/11 周日70寻求最大流寻求最大流 f 的方法：的方法：从某可行流出发寻找增广链，然后沿从某可行流出发寻