第七章第七章 图与网络优化图与网络优化图是最直观的模型图是最直观的模型BACD图论图论Graph Theory哥尼斯堡七桥问题哥尼斯堡七桥问题(Knigsberg Bridge Problem)LeonhardEuler(1707-1783)在在1736年发表第一篇图论年发表第一篇图论方面的论文，奠基了图论中的一些基本定理方面的论文，奠基了图论中的一些基本定理很多问题都可以用点和线来表示，一般点表示实体，很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联线表示实体间的关联27.1图与图与网络网络的基本概念的基本概念1图与网络图图与网络图节点节点(Vertex)物理实体、事物、概念物理实体、事物、概念一般一般用用vi表示表示边边(Edge)节点间的连线，表示有节点间的连线，表示有关联关联一般一般用用eij表示表示图图(Graph)节点和边的集合节点和边的集合一般用一般用G(V,E)表示表示点集点集V=v1,v2,vn边集边集E=eij 网络图网络图 (Network)边上具有表示连接强度边上具有表示连接强度的权值，如的权值，如 wij又称又称加权图加权图(Weighted graph)v1v5v4v3v2e12e34e13e24e22e13e45图图 7.232无向图与有向图无向图与有向图所有边都没有方向的图称为无向图，如图所有边都没有方向的图称为无向图，如图7.2在无向图中在无向图中eij=eji，或或(vi,vj)=(vj,vi)当所有边都有方向时，称为有向图，用当所有边都有方向时，称为有向图，用D(V,A)表示表示在有向图中，有向边又称为在有向图中，有向边又称为弧弧，用，用aij表示，表示，i,j 的顺序的顺序是不能颠倒的，图中弧的方向用箭头标识是不能颠倒的，图中弧的方向用箭头标识图中既有边又有弧，称为混合图图中既有边又有弧，称为混合图43端点，关联边，相邻，次端点，关联边，相邻，次图中可以只有点，而没有边；而有边必有点图中可以只有点，而没有边；而有边必有点若节点若节点vi,vj之间有一条边之间有一条边eij，则称则称vi,vj是是eij 的的端点端点(end vertex)，而而eij是节点是节点vi,vj 的的关联边关联边(incident edge)同一条边的两个端点称为同一条边的两个端点称为相邻相邻(adjacent)节点节点，具有共，具有共同端点的边称为同端点的边称为相邻边相邻边一条边的两个端点相同，称为一条边的两个端点相同，称为自环自环(self-loop)；具有两具有两个共同端点的两条边称为个共同端点的两条边称为平行（多重）边平行（多重）边(parallel edges)既没有自环也没有平行边的图称为既没有自环也没有平行边的图称为简单图简单图(simple graph)在无向图中，与节点相关联边的数目，称为该节点的在无向图中，与节点相关联边的数目，称为该节点的“次次”(degree)，记为记为d；次数为奇数的点称为次数为奇数的点称为奇点奇点(odd),次数为偶数的点称为次数为偶数的点称为偶点偶点(even)；图中都是偶点图中都是偶点的图称为偶点图的图称为偶点图(even graph)53端点，关联边，相邻，次端点，关联边，相邻，次有向图中，由节点向外指的弧的数目称为有向图中，由节点向外指的弧的数目称为正次数，记为正次数，记为d+，指向该节点的弧的数指向该节点的弧的数目称为负次数，记为目称为负次数，记为d次数为次数为0的点称为的点称为孤立点孤立点(isolated vertex)，次数为次数为1的点称为的点称为悬挂点悬挂点(pendant vertex)定理定理1：图中点的次数和是边数个：图中点的次数和是边数个2倍倍定理定理2：图中奇点的个数总是偶数个：图中奇点的个数总是偶数个64链，圈，初等链，初等圈，简单链（圈）链，圈，初等链，初等圈，简单链（圈）相邻节点的序列相邻节点的序列v1 ,v2 ,vn 构成构成一条一条链链(link)p178；在无向图中，节点不重复出现的链称为在无向图中，节点不重复出现的链称为初初等链等链；首尾相连的链称为首尾相连的链称为圈圈(loop)；首尾相连首尾相连的初等链称为的初等链称为初等圈初等圈；边不重复出现的链（圈）称为边不重复出现的链（圈）称为简单链（圈）简单链（圈）75完全图，偶图完全图，偶图简单图中任意两点间都有边相连，则称为完全简单图中任意两点间都有边相连，则称为完全图。图。n个点的完全图有个点的完全图有n（n-1）/2条边条边若图的顶点能分成两个互不相交的非空集合若图的顶点能分成两个互不相交的非空集合V1、V2，其在同一个集合中任意两点间都没有边相，其在同一个集合中任意两点间都没有边相连，则称为偶图（二部图）。连，则称为偶图（二部图）。若偶图的顶点集合若偶图的顶点集合V1、V2之间的每一对不同之间的每一对不同顶点都有一条边相连，则称为完全偶图。顶点都有一条边相连，则称为完全偶图。在完全偶图中，若顶点分别为在完全偶图中，若顶点分别为n1、n2，有，有n1n2条边条边86子图，部分图；连通图，成分子图，部分图；连通图，成分设有两个图设有两个图G1(V1,E1),G2(V2,E2),若若V2 V1,E2 E1，则则G2是是G1的子图。的子图。若若V2=V1,E2 E1，则则G2是是G1的部分图（支撑子图）。的部分图（支撑子图）。无向图中，若任意两点间至少存在一条无向图中，若任意两点间至少存在一条链链，则称为，则称为连连通图通图(connected graph)，否则为否则为非连通图非连通图(discon-nected graph)；非连通图中的每个非连通图中的每个连通子（分）图连通子（分）图称为称为成分成分(component)链，圈，路径链，圈，路径(简称路简称路)，回路都是原图的子图，回路都是原图的子图支撑子图也是子图，子图不一定是支撑子图。支撑子图也是子图，子图不一定是支撑子图。平面图平面图(planar graph)，若在平面上若在平面上可以可以画出该图而没画出该图而没有任何边相交有任何边相交97基础图，基础图，路，回路，欧拉回路路，回路，欧拉回路在有向图在有向图D(V,A)中去掉箭头，称为中去掉箭头，称为D的的基础图，基础图，G（D）在有向图中，在有向图中，链链路路圈圈回路回路走过图中所有边且每条边仅走一次的闭行走称为走过图中所有边且每条边仅走一次的闭行走称为欧拉回欧拉回路路定理定理：偶点图一定存在欧拉回路：偶点图一定存在欧拉回路(一笔画定理一笔画定理)107.2树树图与最小图与最小支撑支撑树树一般研究无向图一般研究无向图树图：倒置的树，树图：倒置的树，根根(root)在上，在上，树叶树叶(leaf)在下在下多级辐射制的电信网络、管理的指标体系、家谱、分多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图类学、组织结构等都是典型的树图117.2.1树的定义及其性质树的定义及其性质任两点之间有且只有一条链的图称为任两点之间有且只有一条链的图称为树树(tree)。无圈的连通图称为无圈的连通图称为树树(tree)p180。记为记为T（V，E）树的性质树的性质：p180-181任何树必存在次数为任何树必存在次数为1的点的点具有具有n个节点的树个节点的树T的边恰好为的边恰好为 n 1条，条，反之，任何有反之，任何有n个节点，个节点，n 1条边的连通条边的连通图必是一棵树图必是一棵树最少边的连通子图，树中必不存在回路最少边的连通子图，树中必不存在回路127.2.2支撑支撑树树树树T是连通图是连通图G的的支撑树支撑树(spanning tree)，若，若T是是G的支撑的支撑图且是树图图且是树图树枝总长最小的支撑树称为最小支树枝总长最小的支撑树称为最小支撑树。撑树。13支撑树支撑树连通图连通图G 最小支撑树？最小支撑树？14 7.2.3最小支撑树最小支撑树有有n 个乡村，各村间道路的长度是已知的，如何个乡村，各村间道路的长度是已知的，如何敷设光缆线路使敷设光缆线路使n 个乡村连通且总长度最短个乡村连通且总长度最短显然，这要求在已知边长的网路图中找最小支撑显然，这要求在已知边长的网路图中找最小支撑树树最小支撑树的算法最小支撑树的算法：Kruskal算法：将图中所有边按权值从小到大排算法：将图中所有边按权值从小到大排列，依次选所剩最小的边加入边集列，依次选所剩最小的边加入边集T，只要不和只要不和前面加入的边构成回路，直到前面加入的边构成回路，直到T中有中有n 1条边，条边，则则T是最小支撑树是最小支撑树15Kruskal算法基于下述定理算法基于下述定理定理定理4.1指定图中任一点指定图中任一点vi，如果如果vj是距是距vi 最近的最近的相邻节点，则关联边相邻节点，则关联边eij 必在某个最小支撑树中。必在某个最小支撑树中。推论推论4.1将网路中的节点划分为两个不相交的集合将网路中的节点划分为两个不相交的集合V1和和V2，V2=V V1，则，则V1和和V2间权值最小的边必间权值最小的边必定在某个最小支撑树中。定在某个最小支撑树中。最小支撑树不一定唯一最小支撑树不一定唯一定理定理4.1推论推论4.1是一个构造性定理，它指示了找是一个构造性定理，它指示了找最小支撑树的有效算法最小支撑树的有效算法16方法一方法一（ Prim Prim 算法算法）：1 1、根据网路写出边权矩阵，两点间若没有边，则用、根据网路写出边权矩阵，两点间若没有边，则用 表示；表示；2 2、从、从 v v1 1 开始开始标记，在第一行打标记，在第一行打 ，划去第一列；，划去第一列；3 3、从所有打、从所有打 的行中找出尚未划掉的最小元素，对该元素画的行中找出尚未划掉的最小元素，对该元素画圈，划掉该元素所在列，与该列数对应的行打圈，划掉该元素所在列，与该列数对应的行打 ；4 4、若所有列都划掉，则已找到最小生成树、若所有列都划掉，则已找到最小生成树( (所有画圈元素所对所有画圈元素所对应的边应的边) )；否则，返回第；否则，返回第 3 3 步。步。该算法中，打该算法中，打 行对应的节点在行对应的节点在 V V1 1中，未划去的列在中，未划去的列在 V V2 2中中 1712222312222333445方法二（避圈法）方法二（避圈法）开始选一条最小权的边，以后每一步中，开始选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈，直到选出边不构成圈，直到选出n-1条边为止。条边为止。PrimPrim算法是多项式算法算法是多项式算法PrimPrim算法可以求最大生成树算法可以求最大生成树网路的边权可以有多种解释，如效率网路的边权可以有多种解释，如效率次数受限的最小生成树次数受限的最小生成树尚无有效算法尚无有效算法18方法三（破圈法）方法三（破圈法）任取一个圈，从圈中去掉一条权最大的边。在余下的图任取一个圈，从圈中去掉一条权最大的边。在余下的图中，重复这个步骤，直到出现一个不含圈的图为止。中，重复这个步骤，直到出现一个不含圈的图为止。12222333445122223334512222333412222333122233212223219斯坦纳树问题斯坦纳树问题假设我们在北京、上海、西安三城假设我们在北京、上海、西安三城市之间架设电话线，一种办法是分别市之间架设电话线，一种办法是分别联通北京联通北京-上海和北京上海和北京-西安。另一西安。另一种办法是选第四个点，假设郑州。由种办法是选第四个点，假设郑州。由此分别向三城市架线，可能你不会想此分别向三城市架线，可能你不会想到第二种办法所用的电话线只是第一到第二种办法所用的电话线只是第一种办法的种办法的86.6%，即可取得比第一种，即可取得比第一种办法节约办法节约13%的显著经济效益。这就的显著经济效益。这就是离散数学界是离散数学界30年代提出的著名的斯年代提出的著名的斯坦纳树问题，但一直未能得到证明。坦纳树问题，但一直未能得到证明。20 1967年大名鼎鼎的贝尔电话公司，遇上了一家精明的用户航空公司，这家用户要求在第四个点的位置上架上电话线。这样使得电话公司不仅要拉新线，增加服务网点，而且要减少收费。这件事的连锁反应迫使电话公司改变了坚持长达10年按照最少发生树长度收费的原则，并且不得不对最短网络问题进行研究。 21斯坦纳比 贝尔实验室数学中心主任波雷克和研究员吉尔伯特对斯坦纳比问题作了许多研究，根据自己多年研究所得提出如下猜想：对欧氏平面上的任何有限点集，其最小的Steiner树同最小发生树的长度之比(称为Steiner比，即斯坦纳比)不小于3/2。 22正三角形加点可以节省最多。 23242526由于其在运输、通信和计算机等现代经济与科技中由于其在运输、通信和计算机等现代经济与科技中的重要作用，近几十年来它的研究进展越来越快。的重要作用，近几十年来它的研究进展越来越快。1985年，格拉姆和金芳容借助于计算机进行了大量运年，格拉姆和金芳容借助于计算机进行了大量运算，证明了斯坦纳比大于算，证明了斯坦纳比大于0.824，虽距，虽距0.866不遥远，却不遥远，却始终未能达到最终目标。美国数学会主席曾感叹道：始终未能达到最终目标。美国数学会主席曾感叹道：“这问题已经公开了这问题已经公开了22年，这件事总令你不安，你不年，这件事总令你不安，你不能证明这样初级的东西。能证明这样初级的东西。”也许源于猜想提出的戏剧也许源于猜想提出的戏剧性背景，也许源于理论意义以及贝尔实验室的学术权性背景，也许源于理论意义以及贝尔实验室的学术权威，也许源于数学家对形成初等而又难解问题的爱好，威，也许源于数学家对形成初等而又难解问题的爱好，人们对这个问题的研究历久不衰。人们对这个问题的研究历久不衰。斯坦纳比的证明（1）27斯坦纳比的证明（2）1990年，年，41岁的堵丁柱因为攻克这一问题而成为世岁的堵丁柱因为攻克这一问题而成为世界数学界冒出的奇葩。他与贝尔实验室黄光明研究员界数学界冒出的奇葩。他与贝尔实验室黄光明研究员合作，找到了一个全新途径，给出了吉尔伯特合作，找到了一个全新途径，给出了吉尔伯特-波雷克波雷克猜想完整的证明。证明的核心是关于鞍点的一个定理。猜想完整的证明。证明的核心是关于鞍点的一个定理。其主要思想是，首先在欧氏平面含其主要思想是，首先在欧氏平面含n点的集合与点的集合与2n-3维维空间的点之间建立一一对应的关系，使得猜想可以化空间的点之间建立一一对应的关系，使得猜想可以化为为2n-3维空间上函数的极值问题。然后利用鞍点定理维空间上函数的极值问题。然后利用鞍点定理找出可以达到极值的临界点应满足的必要条件。之后，找出可以达到极值的临界点应满足的必要条件。之后，再将此条件转换为临界点对应的点集上的几何性质。再将此条件转换为临界点对应的点集上的几何性质。最后，利用这几何性质确定几何结构，验证该猜想。最后，利用这几何性质确定几何结构，验证该猜想。28斯坦纳比的证明（3）证明于证明于1990年年10月在会议上正式公开，月在会议上正式公开，纽约时纽约时报报立刻做了报道。接着立刻做了报道。接着科学科学杂志、杂志、科学新闻科学新闻新科学论新科学论SLAM新闻新闻等报刊上出现了许多等报刊上出现了许多报道。值得提及的报道。值得提及的SLAM新闻新闻在头版上用了个有在头版上用了个有趣的趣的“在计算机时代欧氏几何的欧氏平面上在计算机时代欧氏几何的欧氏平面上n点的集合点的集合2n-3维空间的点力与运气维空间的点力与运气”。在。在不列颠百科全不列颠百科全书书1992年鉴年鉴中，该证明进一步被列为入选的中，该证明进一步被列为入选的6项数学项数学成果的第一项。因此，堵丁柱也荣获了中国科学院自成果的第一项。因此，堵丁柱也荣获了中国科学院自然科学一等奖、国家科技进步二等奖和中国青年科学然科学一等奖、国家科技进步二等奖和中国青年科学家奖等殊荣。家奖等殊荣。297.3 最短路问题最短路问题p185p1854.5.1.2狄克斯特拉算法狄克斯特拉算法 (Dijkstra algorithm, 1959)计算两节点之间或一个节点到所有节点之间的最短路计算两节点之间或一个节点到所有节点之间的最短路令令 dij 表示表示vi到到vj的直接距离的直接距离(两点之间有边两点之间有边)，若两点之间，若两点之间没有边，则令没有边，则令dij = ；令；令dii =0，s表示始点，表示始点，t表示表示终终点点0、令、令始点始点Ts=0，并用并用框框住，框框住，所有其它节点临时标记所有其它节点临时标记Tj= ；1、从从vs出发，对其相邻节点出发，对其相邻节点vj1进行临时标记，有进行临时标记，有Tj1=ds,j1；2、在所有临时标记中找出最小者，在所有临时标记中找出最小者，并并框住作为框住作为永久标记永久标记，设其，设其为为vr，加粗该边。，加粗该边。若此时全部节点都是永久标记，算法结束若此时全部节点都是永久标记，算法结束；否则到下一步；否则到下一步；3、从新的永久标记节点、从新的永久标记节点vr出发，对其相邻的临时标记节点进行出发，对其相邻的临时标记节点进行再标记，设再标记，设vj2为其相邻节点，则为其相邻节点，则Tj2=minTj2,Tr+dr,j2，返返回第回第2步。步。30例例1 1 狄克斯特拉算法狄克斯特拉算法0 81510121511311331最短路问题的标号过程 Dijkstra算法的基本思想：若vs,v1,vk是从vs到vk的最短路，则vs,v1,vi是从vs到vi的最短路。 T(临时)标号：从vs到某一节点最短距离的上界。 P(永久)标号： 从vs到某一节点的最短距离。步骤： 给vs标上永久标号P(vs)=0，其余节点标上临时标号T(vj)= (1)若节点vi是刚得到P标号的点。把与vi有弧(边)直接相连而且有属于T标号的节点，改为下列T标号T(vj)=minT(vj),P(vi)+dij (2)把T标号中标号最小的节点vj0的临时标号T(vj0)改为P(vj0),直至算法终止;否则转(1)33例 求节点v1到节点v5的最短距离及其路线vSv1v2v3v4v5122233344解 P(vs)=0 T(vj)=,j=1,5第一步：T(v1)=minT(v1),P(vs)+ds1=min,0+4=4 (1)与节点vs直接相连的临时标号的节点为 v1, v2，将这两个节点的临时标号改为T(v2)=minT(v2),P(vs)+ds2=min,0+3=30 (2)在所有T标号中，最小的为T(v2)=3,于是令P(v2)=3vSv1v2v3v4v5122233344043第二步： (1)与节点v2直接相连的临时标号的节点为V1和v4，把这两个节点的T标号改为T(v1)=minT(v1),P(v2)+d21=min4,3+2=4T(v4)=minT(v4),P(v2)+d24=min,3+2=5 (2).在所有T变化中，T(v1)=4最小，于是令P(v1)=4535第三步： (1).与节点v1相连的临时标号的节点为v3,v4，把这两个节点的T标号改为T(v3)=minT(v3),P(v1)+d13=min,4+3=7T(v4)=minT(v4),P(v1)+d14=min5,4+1=5 (2).在T标号中，T(v4)=5最小，令P(v4)=5vSv1v2v3v4v51222333440453 7第四步： (1).与节点v4相连的T标号有v3,v5把这两个节点的T标号改为T(v3)=minT(v3),P(v4)+d43=min7,5+2=7T(v5)=minT(v5),P(v5)+d45=min,5+4=9vSv1v2v3v4v5122233344045379 (2).T(v3)最小,P(v3)=7第五步： (1).与v3相连的临时标号有v5T(v5)=minT(v5),P(v3)+d35=min9,7+3=9(2).P(v5)=9最短路线：vsv1v4 v5 vsv2v4 v5vSv1v2v3v4v512223334404537938也可以用表格的形式求解。也可以用表格的形式求解。p19039 Dijkstra最短路算法的最短路算法的特点特点和和适应范围适应范围一种隐阶段的动态规划方法，而且是正向递推一种隐阶段的动态规划方法，而且是正向递推每次迭代只有一个节点获得永久标记，若有两个或两个以上每次迭代只有一个节点获得永久标记，若有两个或两个以上节点的临时标记同时最小，可任选一个永久标记；总是从一节点的临时标记同时最小，可任选一个永久标记；总是从一个新的永久标记开始新一轮的临时标记，是一种个新的永久标记开始新一轮的临时标记，是一种深探法深探法被框住的永久标记被框住的永久标记Tj 表示表示vs到到vj 的最短路，因此的最短路，因此要求要求dij 0，第，第k 次迭代得到的永久标记，其最短路中最多有次迭代得到的永久标记，其最短路中最多有 k条边，条边，因此最多有因此最多有n 1 次迭代次迭代如果只求如果只求vs到到vt的最短路，则当的最短路，则当vt得到永久标记算法就结束得到永久标记算法就结束了；但算法复杂度是一样的了；但算法复杂度是一样的应用应用Dijkstra 算法算法 n 1 次次，可以求所有点间的最短路，可以求所有点间的最短路vs到所有点的最短路也是一棵生成树，但不是最小生成树到所有点的最短路也是一棵生成树，但不是最小生成树40Warshall-Floyd算法算法 (1962)Warshall-Floyd算法可以解决有算法可以解决有负权值负权值边边( (弧弧) )的最短路问题的最短路问题该算法是一种整体算法，一次求出所有点间的最短路该算法是一种整体算法，一次求出所有点间的最短路该算法不允许有该算法不允许有负权值回路负权值回路，但可以发现负权值回路，但可以发现负权值回路该算法基于基本的三角运算该算法基于基本的三角运算定义定义 对给定的点间初始距离矩阵对给定的点间初始距离矩阵dij，令，令dii= ， i。对一对一个固定点个固定点j，运算运算dik=mindik,dij+djk, i,k j , 称为称为三角三角运算。运算。( (注意，这里允许注意，这里允许 i=k) )定理定理 依次对依次对 j=1,2,n 执行三角运算，则执行三角运算，则 dik 最终等于最终等于 i到到 k 间最短路的长度。间最短路的长度。41Floyd-Warshall算法算法 (1962)for i=1to ndodii= ;foralleij=0;forj=1tondofori=1tondoifi jthenfork=1tondoifk jthenbegindik=mindik,dij+djk;ifdikdij+djk theneik=j end;若网路中存在负回路，则计算若网路中存在负回路，则计算中，某些中，某些dii 会小于会小于0，此时应，此时应中断算法中断算法显然，显然，Floyd算法要进行算法要进行 n(n-1)2次加法和比较次加法和比较如何回溯找出任两点之间的最如何回溯找出任两点之间的最短路？短路？在在Floyd算法中设一伴随矩阵算法中设一伴随矩阵E=eik，eik记录了记录了i到到k最最短路短路中最后一个中间节点中最后一个中间节点42小结小结最短路有广泛的应用最短路有广泛的应用(4.3.4节节市话局扩容方案市话局扩容方案)最短路的多种形式：无向图，有向图无循环圈，有向最短路的多种形式：无向图，有向图无循环圈，有向图，混合图，无负边权，有负边权，有负回路，图，混合图，无负边权，有负边权，有负回路，k-最最短路等短路等当存在负权值边时，当存在负权值边时，Floyd算法比算法比Dijkstra算法效率高，算法效率高，且程序极简单。但且程序极简单。但Dijkstra算法灵活算法灵活若图是前向的，则若图是前向的，则Dijkstra算法也可以求两点间最长路算法也可以求两点间最长路一般情况下，两点间最长路是一般情况下，两点间最长路是 NP-complete，但最短但最短路是路是P算法算法两点间两点间k-最短路：分为边不相交的和边相交的最短路：分为边不相交的和边相交的求边求边不相交的不相交的k-最短路非常容易：先求最短路，将该最最短路非常容易：先求最短路，将该最短路中的边从网路删去，再用短路中的边从网路删去，再用Dijkstra算法可求次最短算法可求次最短路，以此类推路，以此类推434.5.1.3最短路应用举例最短路应用举例市话扩容市话扩容( (实装率实装率= =0.8) )447.4网络的最大流和最小截网络的最大流和最小截7.4.1网络流的概念网络流的概念p192网络流一般在有向图上讨论网络流一般在有向图上讨论D=（V，A，C）定义网络上支路的定义网络上支路的容量容量为其最大通过能力，记为为其最大通过能力，记为cij ，支路上的实际支路上的实际流量流量记为记为fij 。当支路上当支路上fij =cij ，称为，称为饱和弧饱和弧图中规定一个发点图中规定一个发点s s，一个收点一个收点t;t;节点没有容量限制，节点没有容量限制，流在节点不会存储流在节点不会存储集合集合f=fij |（vi,vj）A 称为该网络称为该网络D的一个的一个流流fij（cij，fij）457.4网络的最大流和最小截网络的最大流和最小截7.4.1网络流的概念网络流的概念p193集合集合f=fij |（vi,vj）A 称为该网络称为该网络D的一个的一个流流f容量限制条件容量限制条件：0 fij cij 平衡条件平衡条件：满足上述条件的满足上述条件的网络网络流称为流称为可行流可行流，总存在，总存在可行流，如可行流，如0流流f=0 |（vi,vj）A ；v= v(f)称为从称为从s s到到t t的可行流的可行流f的的流量。流量。最大流问题也是一个线性规划问题最大流问题也是一个线性规划问题viA(vi)B(vi)46最大流问题也是一个线性规划问题最大流问题也是一个线性规划问题p194477.4.1增广链增广链当支路上当支路上fij =cij ，称为，称为饱和弧饱和弧当支路上当支路上fij 0 ，称为，称为非零流弧非零流弧487.4.1增广链增广链链中与链中与s到到t 方向一致的弧称为方向一致的弧称为前向弧前向弧，反，反之称为之称为后向弧后向弧前向弧前向弧的全体记为的全体记为后向弧后向弧的全体记为的全体记为497.4.1增广链增广链f为可行流，为可行流，为为s到到t的链。若满足下列条件称为的链。若满足下列条件称为增广链。增广链。中每一弧是中每一弧是非饱和弧非饱和弧中每一弧是中每一弧是非零流弧非零流弧50截集与截集容量截集与截集容量定义定义：截集截集把网路分割为两个成分的正向弧的集合，其中一把网路分割为两个成分的正向弧的集合，其中一个个成分包含成分包含s点，另一个包含点，另一个包含t点点。（割、割集）。（割、割集）一般包含一般包含s点的成分中的节点集合用点的成分中的节点集合用S表示，包含表示，包含t点的成点的成分中的节点集合用分中的节点集合用S表示表示截集容量截集容量是指截集中正向弧的是指截集中正向弧的容量容量之和之和51定义定义：最小最小截集截集是截集容量最小的截集（最小割）是截集容量最小的截集（最小割）st42314(4)2(1)5(5)3(1)3(2)5(3)9(7)7(7)6(3)14151412191616111352535455定理p195福特福特-富克森定理：网路的最大流等于最小截集容富克森定理：网路的最大流等于最小截集容量。量。567.4.2确定网路最大流的标号法确定网路最大流的标号法从任一个初始可行流出发，如从任一个初始可行流出发，如0流流基本算法：找一条从基本算法：找一条从s到到t点的点的增广链增广链(augmenting path)若在当前可行流下找不到增广链，则已得到最大流若在当前可行流下找不到增广链，则已得到最大流增广链中与增广链中与s到到t 方向一致的弧称为方向一致的弧称为前向弧前向弧，反之，反之后向弧后向弧增广过程：前向弧增广过程：前向弧f ij=fij +q q , , 后向弧后向弧f ij=fij q q 增广后仍是可行流增广后仍是可行流 ，找从找从s到到t点的点的增广链增广链57最大流最小截的标号法步骤最大流最小截的标号法步骤第一步：标号过程，找一条增广链第一步：标号过程，找一条增广链1、给源点给源点s标号标号s+,q q(s)= ，表示，表示从从s 点有无限流出潜力点有无限流出潜力2、找找出与已标号节点出与已标号节点i相邻的所有未标号节点相邻的所有未标号节点j，若若(1)(i,j)是前向弧且饱和，则节点是前向弧且饱和，则节点j不标号；不标号；(2)(i,j)是前向弧且未饱和，则节点是前向弧且未饱和，则节点j标号为标号为i+,q q(j)，表示从节点表示从节点i正向正向流出，可增广流出，可增广q q(j)=minq q(i),cij fij；(3)(j,i)是后向弧，若是后向弧，若fji=0，则节点则节点j不标号；不标号；(4)(j,i)是后向弧，若是后向弧，若fji0，则节点则节点j标号为标号为i ,q q(j)，表示从节点表示从节点j流向流向i，可增广可增广q q(j)=minq q(i),fji；3、重复步骤重复步骤2，可能出现两种情况：，可能出现两种情况：(1)节点节点t尚未标号，但无法继续标记，说明网路中已不存在增广链，尚未标号，但无法继续标记，说明网路中已不存在增广链，当前流当前流v(f)就是最大流；所有获标号的节点在就是最大流；所有获标号的节点在V中，未获标号节中，未获标号节点在点在V中，中，V 与与V间的弧即为最小截集；算法结束间的弧即为最小截集；算法结束(2)节点节点t获得标号，找到一条增广链，由节点获得标号，找到一条增广链，由节点t标号回溯可找出该增标号回溯可找出该增广链；到第二步广链；到第二步58最大流最小截的标号法步骤最大流最小截的标号法步骤第二步：增广过程第二步：增广过程1、对、对增广链中的前向弧，令增广链中的前向弧，令f =f+q q(t)，q q(t)为节点为节点t的标记的标记值值2、对对增广链中的后向弧，令增广链中的后向弧，令f =f q q(t)3、非增广链上的所有支路流量保持不变非增广链上的所有支路流量保持不变第三步：抹除图上所有标号，回到第一步第三步：抹除图上所有标号，回到第一步以上算法是按广探法描述的，但在实际图上作业时，按深以上算法是按广探法描述的，但在实际图上作业时，按深探法进行更快捷探法进行更快捷一次只找一条增广链，增广一次换一张图一次只找一条增广链，增广一次换一张图最后一次用广探法，以便找出最小截集最后一次用广探法，以便找出最小截集59最大流最小截集的标号法举例最大流最小截集的标号法举例(s+, )(s+,6)(2 ,6)(3+,1)(4+,1)(s+, )(s+,5)(2+,2)(5 ,2)(4+,2)60最大流最小截集的标号法举例最大流最小截集的标号法举例(s+, )(s+,3)(2 ,3)最小截集最小截集61最大流标号法的复杂度讨论最大流标号法的复杂度讨论找一条增广链的计算量是容易估计的，不会超过找一条增广链的计算量是容易估计的，不会超过O(n2)但是最多迭代多少次但是最多迭代多少次(即增广的次数即增广的次数)就很难估计，在最坏就很难估计，在最坏情况下，与边的容量有关；如上图：先增广情况下，与边的容量有关；如上图：先增广suvt,然后增广然后增广svut，每次只能增广每次只能增广1个单位，故要个单位，故要增广增广4000次才能结束次才能结束克服这种缺点的经验方法：克服这种缺点的经验方法：尽量先用段数少的增广链尽量先用段数少的增广链尽量不重复前面出现过的增广链尽量不重复前面出现过的增广链62多端网路问题多端网路问题虚发点虚发点s(20,0)(20,0)t(20,0)(15,0)虚收点虚收点63定义定义弧的剩余容量弧的剩余容量64656667686970717273747.5 最小费用最大流最小费用最大流双权网路双权网路：每条弧不但有容量，还有单位流量的通过费用：每条弧不但有容量，还有单位流量的通过费用两种解法：一种基于最小费用路径算法；一种基于可行弧集两种解法：一种基于最小费用路径算法；一种基于可行弧集的最大流算法的最大流算法基于最小费用路径算法基于最小费用路径算法：总是在当前找到的最小费用的路径：总是在当前找到的最小费用的路径上增广流；缺点是每次增广后要改变弧的费用，且出现负权上增广流；缺点是每次增广后要改变弧的费用，且出现负权值费用的弧值费用的弧基于可行弧集的最大流算法基于可行弧集的最大流算法：从：从0费用弧集开始应用最大流费用弧集开始应用最大流算法，然后根据计算信息提高费用的限界算法，然后根据计算信息提高费用的限界P，使可行弧集增使可行弧集增大，再应用最大流算法，直至所有弧都进入可行弧集。这种大，再应用最大流算法，直至所有弧都进入可行弧集。这种算法是一种主算法是一种主-对偶规划的解法。使用这种方法的还有运输对偶规划的解法。使用这种方法的还有运输问题、匹配问题问题、匹配问题75