图论刘汝佳课件

目录DFS相关算法二分图相关算法网络流相关算法最小树形图目录DFS相关算法1DFS相关算法DFS相关算法2基本应用找连通分量二分图判定无向图的连通性有向图的连通性基本应用找连通分量3时间戳和边分类时间初始化为0，最大值为2|E|。数值本身无意义，但大小关系有意义voidPREVISIT(intu){pre[u]=++dfs_clock;}voidPOSTVISIT(intu){post[u]=++dfs_clock;}无向图：只有树边和反向边时间戳和边分类时间初始化为0，最大值为2|E|。数值本身无意4无向连通图的割顶DFS森林一定只有一棵树。树根是不是割顶呢？不难发现，当且仅当它有两个或更多的儿子时，它才是割顶——无向图只有树边和反向边，不存在跨越两棵子树的边。对于其他点，情况就要复杂一些。我们有下面的定理：定理：在无向连通图G的DFS树中，非根结点u是G的割顶当且仅当u存在一个儿子w，使得w及其所有后代都没有反向边连回u的祖先（连回u不算）。无向连通图的割顶DFS森林一定只有一棵树。树根是不是割顶呢？5定理的证明u存在一个儿子w，使得w及其所有后代都没有反向边连回u的祖先（连回u不算）。定理的证明u存在一个儿子w，使得w及其所有后代都没有反向边连6为了方便起见，我们设low(u)为u及其后代所能连回的最早的祖先的pre值，则定理中的条件就可以简写成：结点u存在一个儿子w，使得low(w)>=pre(u)。若low(w)>pre(u)，即w最多只能连回自己，则只需删除(u,w)一条边就可以让图G非连通了。满足这个条件的边称为桥（bridge）为了方便起见，我们设low(u)为u及其后代所能连回的最早的7low函数本身的计算voiddfs(intu,intfa){//u的父亲结点是fa，初次调用fa=-1low[u]=pre[u]=++dfs_clock;//初始化low(u)intd=G[u].size();for(inti=0;i<d;i++){//枚举每条边(u,w)intw=G[u][i];if(!pre[w]){//没有访问过点v（所有pre值初始化为0）dfs(w,u);//w的父亲结点是ulow[u]=min(low[u],low[w]);//用后代的low函数更新}elseif(w!=fa)low[u]=min(low[u],pre[w]);//用反向边更新}}low函数本身的计算voiddfs(intu,int8双连通与边-双连通如果一个无向连通图没有割顶，称它是点-双连通的，一般简称双连通（biconnected）；如果没有桥，称它是边-双连通（edge-biconnected）的。点-双连通的等价条件：任意两点存在两条“点不重复”的路径。这个要求等价于任意两条边都在同一个简单环中，因此内部无割顶。边-双连通的等价条件：任意两点存在两条“边不重复”的路径。这个要求要低一点，只需要每条边都至少在一个简单环中，因此所有边都不是桥。双连通与边-双连通如果一个无向连通图没有割顶，称它是点-双连9点/边-双连通分量下图有两个点-双连通分量：{1,2,3}和{3,4,5}，但只有一个边-双连通分量：{1,2,3,4,5}。点/边-双连通分量下图有两个点-双连通分量：{1,2,3}和10算法边-双连分量：两步走，先求出所有的桥，然后再做一次dfs染色。因为边-双连通分量是没有公共顶点的，所以只要在第二次dfs的时候保证不经过桥即可。点-双连通分量：Tarjan算法（见后）算法边-双连分量：两步走，先求出所有的桥，然后再做一次dfs11voiddfs(intu,intfa){low[u]=pre[u]=++dfs_clock;intd=G[u].size();for(inti=0;i<d;i++){intw=G[u][i];

//求BCC用.每遇到一条边(u,w)都要加到栈中，不管w是否已编号if(ins[u][w])continue;ins[u][w]=ins[w][u]=1;S.push(mp(u,w));

if(!pre[w]){dfs(w,u);low[u]=min(low[u],low[w]);if(low[w]>=pre[u]){//u是割顶或者根，意味着一个bcc的终止++bcc_cnt;printf("BCC%d,containing(%d,%d):\n",bcc_cnt,u,w);pair<int,int>e;do{e=S.top();S.pop();printf("%d%d\n",e.first,e.second);}while(e!=mp(u,w));}}elseif(w!=fa)low[u]=min(low[u],pre[w]);}}voiddfs(intu,intfa){12有向图的强连通分量理想情况：依次从I,C,D…出发DFS，则每次DFS恰好得到一个SCC有向图的强连通分量理想情况：依次从I,C,D…出发DFS13Kosaraju算法执行两次DFS，其中第一次DFS得到了关于各个SCC拓扑顺序的有关信息，而第二次DFS按照这个拓扑顺序的逆序进行DFS，从而把每个SCC分开。第一步：对G进行普通的DFS，把各个结点按照访问结束时间从后往前的顺序放入列表list中。第二步：计算G的转置GT（即把所有有向边(u,v)变为有向边(v,u)）第三步：对GT进行DFS，其中主循环中按下标从小到大的顺序依次考虑list中的各个结点，则每次dfs将会得到一个不同的SCC。Kosaraju算法执行两次DFS，其中第一次DFS得到了关14圆桌骑士每次圆桌会议由至少3个骑士参加，骑士的数目必须为奇数，且在圆桌旁坐下后相邻骑士不能相互憎恨。统计有多少个骑士不可能参加任何一个会议。有n个骑士，m个相互憎恨的骑士对N<=1000,m<=1000000圆桌骑士每次圆桌会议由至少3个骑士参加，骑士的数目必须为奇数15以骑士作为顶点建立无向图G。如果两个骑士不相互憎恨，在他们之间连一条无向边。则题目转化为求不在任何一个奇圈上的顶点个数。如果图G不连通，应对每个连通分量分别求解。下面假设图G连通。假设结点v在某个奇圈上，则根据定义，该圈上的所有结点都属于同一个点-双连通分量。由于该双连通分量中含有奇圈，它一定不是二分图。反过来是否成立呢？即：如果结点v所属的某一个双连通分量B（因为v可能属于多个双连通分量）不是二分图，v是否一定属于一个奇圈呢？以骑士作为顶点建立无向图G。如果两个骑士不相互憎恨，在他们之16问题在于：尽管B不是二分图意味着它一定包含一个奇圈C，这个C可能并不包含v。我们得想办法让v搀和进来。如图，根据连通性，从v一定可以到达C中的某个结点u1；根据双连通性，C中还应存在另一个结点u2，使得从v出发有两条不相交路径（除起点外无公共结点），分别到u1和u2。由于在C中，从u1到u2的两条路的长度一奇一偶，总能构造出一条经过v的奇圈。主算法：对于每个连通分量的每个双连通分量B，若它不是二分图，给B中所有结点标记为“在奇圈上”。问题在于：尽管B不是二分图意味着它一定包含一个奇圈C，这个C17井下矿工有一座地下的稀有金属矿由n条隧道和一些连接点组成，其中每条隧道连接两个连接点。任意两个连接点之间最多只有一条隧道。为了降低矿工的危险，你的任务是在一些连接点处安装太平井和相应的逃生装置，使得不管哪个连接点倒塌，不在此连接点的所有矿工都能到达太平井逃生（假定除倒塌的连接点不能通行外，其他隧道和连接点完好无损）。为了节约成本，你应当在尽量少的连接点安装太平井。你还需要计算出在太平井的数目最小时的安装方案总数。井下矿工有一座地下的稀有金属矿由n条隧道和一些连接点组成，其18本题的模型是：把一个无向图上选择尽量少的点涂黑（对应太平井），使得任意删除一个点后，每个连通分量至少有一个黑点。不难发现，把割顶涂黑是不划算的，而且在同一个点-双连通分量中图两个黑点也是不划算的。进一步分析发现：如果把每个点-双连通分量收缩成一个点，则整个图会变成一棵树。最优方案是在树的每个叶结点中选一个非割顶涂黑，两个问题同时解决。一个特殊情况是整个图没有割顶。此时至少需要涂两个点，方案总数是C(V,2)，其中V是连接点个数。本题的模型是：把一个无向图上选择尽量少的点涂黑（对应太平井）19等价性证明在数学中，我们常常需要完成若干个命题的等价性证明。比如，有四个命题a,b,c,d，我们证明a

b，然后b

c，最后c

d。注意每次证明都是双向的，因此一共完成了6次推导。另一种方法是证明a

b，然后b

c，接着c

d，最后d

a，只需4次。现在你的任务是证明n个命题全部等价，且你的朋友已经为你作出了m次推导（已知每次推导的内容），你至少还需要做几次推导才能完成整个证明？n<=20000,m<=50000等价性证明在数学中，我们常常需要完成若干个命题的等价性证明。20分析用图论术语来说，本题是给出n个结点m条边的有向图，要求填加尽量少的边，使得新图强连通。先找出强连通分量，然后把每个强连通分量缩成一个点，得到一个DAG接下来，设有a个结点（别忘了，这里的每个结点对应于原图的一个强连通分量）的入度为0，b个结点的出度为0，则max{a,b}就是答案。注意特殊情况：当原图已经强连通时，答案是0而不是1。证明留给读者。分析用图论术语来说，本题是给出n个结点m条边的有向图，要求填21无向仙人掌仙人掌被定义为每个点最多在一个简单（结点不重复经过）回路上的连通无向图。你的任务是计算一个无向图的“仙人掌度”，即它有多少个生成子图（包括自身）也是仙人掌。如果原图不是仙人掌，输出0无向仙人掌仙人掌被定义为每个点最多在一个简单（结点不重复经过22我们采用分析DFS树的方法来寻求解决问题的方法。首先，对于一个节点u，如果它在DFS树上的某个孩子v满足low(v)<pre(u)，那么(u，parent(u))这条边就必然在一个环上；同样的，如果u能够通过反向边访问到它的某个祖先节点w，那么(u，parent(u))这条边就一定在另外一个环上。我们对于每个节点u记录下这两种情况发生的次数c(u)。如果c(u)>1，那么这个图必然不是仙人掌，直接输出0。我们采用分析DFS树的方法来寻求解决问题的方法。首先，对于一23对于一个仙人掌，如果计算它的仙人掌度呢？显然，对于一条不属于任何一个环的边，它一定是不可以删去的，而对于一个长度为L的环，我们则有L+1种选择（全部保留或者删去其中的任意一条边）。根据乘法原理，答案就是所有环长度加一后相乘的结果。因为所有的工作都可以在一次DFS之内完成，所有整个算法的时间复杂度为O(m)。具体实现的时候有一点需要注意：为了避免栈溢出，最好不要在递归的同时计算答案。一种较好的方法是递归时只记录每个环的长度，待全部处理完之后再进行高精度计算。对于一个仙人掌，如果计算它的仙人掌度呢？显然，对于一条不属于24二分图最大匹配二分图最大匹配25二分图最大匹配二分图：结点可以分为两部分X和Y，每部分内部无边相连匹配：无公共点的边集合未盖点：不与任何匹配边邻接的点最大匹配：包含边数最多的匹配XY二分图最大匹配二分图：结点可以分为两部分X和Y，每部分内部26交替路、增广路从未盖点开始经过非匹配边、匹配边、非匹配边……序列，最终通过一条非匹配边到达另一个未盖点非匹配边个数比匹配边个数多一如果把匹配边和非匹配边互换，匹配仍合法，但基数加一交替路、增广路从未盖点开始经过非匹配边、匹配边、非匹配边……27增广路定理匹配是最大匹配当且仅当不存在增广路这个定理适用于任意图011001011010匈牙利树思考：忽略虚线边会导致存在增广路却找不到吗？增广路定理匹配是最大匹配当且仅当不存在增广路这个定理适用于任28增广路定理的证明必要性.如果存在则增广后得到更大匹配.充分性.如果M不是最大匹配,取最大匹配M’,作M’和M的对称差G’,则G’在M’中的边应比M’中更多.G’有三种可能的连通分支孤立点.当某边(u,v)同时属于两个匹配,则u和v都是孤立点.交替回路.该回路中属于M和M’的边数相同交替道路.如果不存在增广路,则|M’|=|M|,与假设矛盾;如果存在M关于M’的增广路,又与M’是最大匹配矛盾,因此存在M’关于M的增广路增广路定理的证明必要性.如果存在则增广后得到更大匹配.29Hall定理在二分图(X,Y,E)中,X到Y存在完全匹配(X的结点全被匹配)的充要条件是对于X的任意子集A,恒有必要性.若存在A使得右边>左边,则A无法全部匹配充分性.假设G的最大匹配M不是完全匹配,一定存在结点X的结点x0关于M是非饱和点.如果x0的邻集为空,则令A={x0}引出矛盾;如果非空则其中每个结点均为饱和点(否则会有增广路).寻找与x0为端点的关于M的一切交错路,设其中Y结点的集合为Y’,X结点的集合为X’,则Y’结点与X’-{x0}的结点一一对应,因此|X’|>|Y’|,令A=X’引出矛盾.Hall定理在二分图(X,Y,E)中,X到Y存在完全匹配(30二分图最大匹配算法匈牙利树是从所有未盖点,而不是从固定未盖点长出的树Edmonds-Karp算法:把所有未盖点放到队列中,BFS寻找/增广路时间均为O(m)最多找O(n)次时间复杂度O(nm)Hopcroft算法：每次沿多条增广路同时增广每次寻找若干条结点不相交最短增广路每次的最短增广路集是极大的时间复杂度基于DFS的算法:每次选一个未盖点u进行DFS.如果找不到增广路则换一个未盖点,且以后再也不从u出发找增广路.二分图最大匹配算法匈牙利树是从所有未盖点,而不是从固定未盖31Hopcroft算法可以证明：如果每次找到的最短增广路集是极大的，则只需要增广次关键：用O(m)时间找一个极大最短增广路集步骤1：用距离标号扩展匈牙利树，找到第一个未盖点时并不停止，把此时的距离标号设为上限。这样，找到的所有未盖点距离标号都相同步骤2：每次任取一个未盖点，用DFS找到它到起点的增广路(只沿着距离标号下降的方向),标记经过的点,找所有增广路的总时间为O(m)Hopcroft算法可以证明：如果每次找到的最短增广路集是极32基于DFS的算法从贪心匹配,而不是空匹配开始每次从一个未盖点开始DFS找增广路,而不是一次性把所有未盖点放入队列进行BFS如果从一个未盖点u开始找不到增广路,则以后再也不用考虑u了.为什么?定理:假设G的匹配为M,不存在从非饱和点u出发的增广路,而存在另外一条增广路P,则G也不存在从u出发关于增广后新匹配的增广路基于DFS的算法从贪心匹配,而不是空匹配开始33定理的证明(1)定理:假设G的匹配为M,不存在从非饱和点u出发的增广路,而存在另外一条增广路P,则G也不存在从u出发关于增广后新匹配M’的增广路证明:假设增广后从u出发有增广路Q.若Q与P不相交,则Q就是M-增广路,矛盾.因此Q与P相交.下面借助P和Q构造出从u出发关于M的增广路,从而得到矛盾定理的证明(1)定理:假设G的匹配为M,不存在从非饱和点34定理的证明(2)Q与P相交.设P的两个M-非饱和点为u0和v0,而Q的两个M’-非饱和点是u,v.从u开始沿Q走,设第一个P中结点为w,则w把P分为两段,其中必有一段以M中边与w关联,得到从u出发增广路wv0u0vuPQ定理的证明(2)Q与P相交.设P的两个M-非饱和点为u0和35应用举例：最大最小匹配求一个完备匹配，使得匹配边中权值最大的边权值最小算法一：二分最大边权，删除不符合条件的边，然后进行最大匹配算法二：从权值最低的边开始，每次增加一条边，维护交错树森林。最多只可能增加一个交错轨。因为找到N条交错轨即可，而维护交错树森林的平摊复杂度为O(1)，所以总时间复杂度依然为O(N3)应用举例：最大最小匹配求一个完备匹配，使得匹配边中权值最大的36分析如果有完美匹配，则Alice输，因为Bob只需沿着匹配边走即可否则Alice赢：任意求一个最大匹配，Alice把棋子放在任一个未盖点上，则Bob只能把它移动到已盖点上（否则得到增广路）。Alice沿着匹配边移动，下一步Bob又只能把它移到另一个已盖点上…只要Bob能移动，Alice就能移动分析如果有完美匹配，则Alice输，因为Bob只需沿着匹配边37应用举例：机器调度有两台机器A和B及N个需要运行的任务。每台机器有M种不同的模式，而每个任务i都恰好在一台机器上运行。如果它在机器A上运行，则机器A需要设置为模式ai，如果它在机器B上运行，则机器B需要设置为模式bi。每台机器上的任务可以按照任意顺序执行，但是每台机器每转换一次模式需要重新启动一次。请合理为每个任务安排一台机器并合理安排顺序，使得机器重启次数尽量少应用举例：机器调度有两台机器A和B及N个需要运行的任务。每台38机器重启次数是两台机器需要使用的不同的模式个数。但是如果把每个任务看成一个X结点，把每台机器的每个模式看成一个Y结点，则此模型没有任何意义。应该把每个任务看成一条边，即A机器的每个模式看成一个X结点，B机器的每个模式看成一个Y结点，任务i为边(ai,bi)。本题即为求最少的点让每条边都至少和其中的一个点关联，这个数称为覆盖数(VertexCover)König定理:二分图覆盖数等于匹配数机器重启次数是两台机器需要使用的不同的模式个数。但是如果把每39构造最小点覆盖需要借助匈牙利树从左边所有未盖点出发扩展匈牙利树，标记树中的所有点，则左边的未标记点和右边的已标记点组成了最小点覆盖（黑色）01100101100构造最小点覆盖需要借助匈牙利树0110010110040为什么恰好选了|M|个点？左边的未盖点没选，因为有标记（作为起点）右边的未盖点没选，因为无标记（如果出现在匈牙利树中，意味着找到增广路）在树中的匹配边两边都有标记不在树中的匹配边两边都无标记因此匹配边和标记点一一对应为什么是点覆盖？有一条边没被覆盖

左边在树中，而右边不在树中，说明匈牙利树还没扩展完，矛盾为什么是最优的？只考虑最大匹配，显然至少要M个点才能覆盖左边的未标记点和右边的已标记点为什么恰好选了|M|个点？左边的未标记点和右边的已标记点41应用举例：骑士一个n*n(n<=100)的棋盘上，有一些单位小方格不能放置骑士。棋盘上有若干骑士，任一个骑士不在其他骑士的攻击范围内。请告诉我棋盘上最多能有几个骑士。骑士攻击范围如图所示（S是骑士的位置，X表示攻击范围）。应用举例：骑士一个n*n(n<=100)的棋盘上，有一些单位42二分图最大独立集如果把剩余单位小方格抽象成图的顶点，并在相互属于对方攻击范围的顶点对间连线，那么很明显，由于跳马特殊的“日”字形路线，使得只有黑色与白色小方格间才有连线，所以此题的模型是一个二分图G。而我们的目标就是找出G的最大独立集定理:

若顶点集为V,最大独立点集为U，最大匹配为M，则|U|=|V|-|M|最大独立集与最小点覆盖互补二分图最大独立集如果把剩余单位小方格抽象成图的顶点，并在相互43应用举例：新汉诺塔有N根柱子，现在有任意正整数编号的球各一个，请你把尽量多的球放入这N根柱子中，满足放入球的顺序必须是1,2,3,…，且每次只能在某根柱子的最上面放球；同一根柱子中，相邻两个球的编号和为完全平方数。请问，最多能放多少个球在这N根柱子上？例如，4根柱子可以放11个球应用举例：新汉诺塔有N根柱子，现在有任意正整数编号的球各一个44最小路径覆盖把每个球看做一个顶点，如果两个球i和j（i<j）的编号和i+j为平方数，那么把两个顶点连成一条有向边i→j。我们首先解决这样一个判定问题：给定球总数n和柱子数m，能否把所有球放到柱子上？即需要解决如下所示的一个问题。最小路径覆盖问题.

用尽量少的不相交简单路径覆盖有向无环图G的所有顶点。最小路径覆盖把每个球看做一个顶点，如果两个球i和j（i<j）45把所有顶点i拆为两个：X结点i和Y结点i’，如果图G中存在有向边i→j，则在二分图中引入边i→j’，设二分图的最大匹配数为m，则结果就是n-m。这个结果不难理解，因为匹配和路径覆盖是一一对应的。路径覆盖中的每条简单路径除了最后一个结点之外都有惟一的后继和它对应（即匹配结点），因此匹配边数就是非路径结尾的结点数。因此匹配数达到最大时，非路径结尾的结点数达到最大，故路径结尾结点数目最少，即路径数最少把所有顶点i拆为两个：X结点i和Y结点i’，如果图G中存在有46二分图最大权匹配二分图最大权匹配47完全二分图的最大权完美匹配完全二分图，每条边有一个非负整数权值目标：求出权和最大的完美匹配特点：完美匹配容易求，但权最大的不易可行顶标：结点函数l，对任意弧(x,y)满足相等子图：G的生成子图，包含所有点，但只包含满足l(x)+l(y)=w(x,y)的所有弧(x,y)完全二分图的最大权完美匹配完全二分图，每条边有一个非负整数权48相等子图定理：如果相等子图有完美匹配，则该匹配是原图的最大权匹配证明：设M*是相等子图的完美匹配，则根据定义设M是原图的任意完美匹配，则关键：寻找好的可行顶标，使相等子图有完美匹配相等子图定理：如果相等子图有完美匹配，则该匹配是原图的最大权49算法思想关键：寻找好的可行顶标，使相等子图有完美匹配思想：随便构造一个可行顶标（例如Y结点顶标为0，X结点的顶标为它出发所有弧的最大权值，然后求相等子图的最大匹配存在完美匹配，算法终止否则修改顶标使得相等子图的边变多，有更大机会存在完美匹配考虑相等子图不存在完美匹配时的情形算法思想关键：寻找好的可行顶标，使相等子图有完美匹配50Kuhn-Munkres算法如右图，相等子图的最大匹配基数为6，不是完美匹配算法在寻找增广路失败的同时得到了一棵匈牙利树虽然此匈牙利树并没有包含未盖点（因此没有找到增广路），但仍然含有重要信息Kuhn-Munkres算法如右图，相等子图的最大匹配基数为51Kuhn-Munkres算法设匈牙利树中的X结点集为S，Y结点集为T，则S到T没有边（否则匈牙利树可以继续生长）S到T的边都是非匹配边（想一想，为什么）但若把S中所有点的顶标同时减少一个相同整数a，则S到T中可能会有新边进入相等子图SSTTKuhn-Munkres算法设匈牙利树中的X结点集为S，Y结52Kuhn-Munkres算法把S中所有点的顶标同时减少一个相同整数a，则S到T中可能会有新边进入相等子图为了保证S-T的匹配边不离开相等子图，把T中所有点的顶标同时增加aSSTT-a+a为保证有新边进入，取如果S中每个顶标的实际减小值比这个值小则不会有新边进入；如果比这个值大则顶标将变得不可行Kuhn-Munkres算法把S中所有点的顶标同时减少一个相53Kuhn-Munkres算法设边(x,y)进入相同子图y是未盖点，则找到增广路y和S中的点z匹配，则把z和y分别加入S和T中每次修改顶标要么找到增广路，要么使匈牙利树增加两个结点因此一共需要O(n2)次修改顶标操作关键：快速修改顶标SSTT-a+aKuhn-Munkres算法设边(x,y)进入相同子图SST54顶标的修改方法1：枚举S和T中的每个元素，根据定义计算最小值，每次修改的时间为O(n2)，总O(n4)方法2：对于T中的每个元素y，定义松弛量则a的计算公式变为顶标的修改方法1：枚举S和T中的每个元素，根据定义计算最小值55顶标的快速修改每次增广后用O(n2)时间计算所有点的初始slack，由于每次生长匈牙利树时所有S-T弧的增量相同，因此修改每个slack值只需要常数时间，计算所有slack值需要O(n)时间每次增广后最多修改n次顶标，因此每次增广后修改顶标总时间降为O(n2)，总O(n3)结论：Kuhn-Munkres算法的总时间复杂度为O(n3)顶标的快速修改每次增广后用O(n2)时间计算所有点的初始sl56应用举例：冰激凌加派有n种派和m种冰激凌,把第i种派与第j种冰激凌搭配可以买Wij元钱.给出第k种派的数量Pk与第k种冰激凌的数量Ik,求销售额的最大值和最小值应用举例：冰激凌加派有n种派和m种冰激凌,把第i种派与第j57最大流问题最大流问题58流网络定义一个流网络(flownetwork)G=(V,E)是一个有向图,每个边(u,v)有一个非负容量(capacity)c(u,v)>=0.对于不在E中的(u,v),规定c(u,v)=0有两个特殊结点:源(source)s和汇(sink)t.假设对于任意其他点v,存在通路svt流网络定义一个流网络(flownetwork)G=(V,59流的定义流(flow)是一个边的函数f(u,v),满足:容量限制:f(u,v)<=c(u,v)对称性:f(u,v)=-f(u,v)收支平衡:对于不是s或t的其他点u,有把整个网络的流量定义为(即从s流出的流量):最大流问题:寻找流函数f,使得网络流最大流的定义流(flow)是一个边的函数f(u,v),满足:60等价条件1)f是最大流2)残量网络中无可增广路3)存在某个切割(S,T),|f|=c(S,T)12:反证.若存在,可沿它增广得到更大流23:此时不存在s-t通路.定义S为s可达结点集,T为可达t结点集,则|f|=c(S,T)(若跨越(S,T)的弧不满载,残量网络中会有更多弧存在)31:因为对于任意一个切割,f(S,T)=|f|,因此任意可行流量不会超过最小切割的容量等价条件1)f是最大流61Gomory-Hu树Gomory-Hu树62每对结点之间的s-t割有N个点M条边的无向带权图，对于所有s,t(s<t)，求出s-t的最小割的容量每对结点之间的s-t割有N个点M条边的无向带权图，对于所有s63Gomory-Hu树的构造初始时令所有点在同一集合中若所有点属于不同点集，则退出，否则任找两个点s,t，同时属于某点集P求最小s-t割(S,T)，并把P分裂为两个，一个是在S中的，另一个是在T中的。增加两点a,a’,增加边(a,a’),容量为割(S,T)容量，对所有跨越(S,T)的边(u,v),从图中删去,并增设边(u,a),(a’,v),,容量与边(u,v)容量相同。转到1Gomory-Hu树的构造初始时令所有点在同一集合中64每次调用最大流过程都使某点集分裂成两个非空集合。因此N-1次调用后算法停止,这时我们共增设了N-1个点对，每个点对中的边删去后都会使点集被分成不联通的两部分,也就是说这时点集与增设的N-1个点对中的边可以构成一棵树。这棵树就是Gomory-Hu树，原图中任两点的最小割就是其在Gomory-HuTrees中对应点的唯一路径上的最小边权。每次调用最大流过程都使某点集分裂成两个非空集合。因此N-1次650,50,20,50,266最后结果最后结果67全局最小割全局最小割68全局最小割可以枚举所有(s,t)点对,求s-t最大流,求最小的一个,但时间…先求Gomory-Hu树，时间复杂度倒是不错，但编程比较麻烦…MechthildStoer,FrankWagner,ASimpleMin-CutAlgorithm,1997时间:O(VE+V2logV)全局最小割可以枚举所有(s,t)点对,求s-t最大流,求69定理对于G的任意两个结点s和t,令G/{s,t}表示合并s和t之后的图,则G的全局最小割可以取G的s-t最小割和G/{s,t}的最小割之间的较小者递归计算，则只需要求|V|次s-t最小割可是还是要求|V|次s-t最大流啊?不必,因为可以任意选择s-t,我们当然是选择一些比较好算的s-t割了!方法:MAS(MaximumAdjacencySearch)定理对于G的任意两个结点s和t,令G/{s,t}表示合并s70MAS从任意结点a开始生长集合A,每次选择连接A最紧的结点(即与A中结点的所有边权和W(A,z)最大的z)加入.本次最后加入的点和其他点形成的割称为cut-of-the-phase,每次合并最后两个加入的点.每阶段的a可以不变也可以重选MAS从任意结点a开始生长集合A,每次选择连接A最紧的结点71正确性定理:每阶段的cut-of-the-phase是最后加入的两个点的最小s-t割证明:考虑任意s-t割C.对于不是a的其他点v,设v和它前一个加入的点在C中的不同部分,称v是active的,设Av为v之前(不含)被加入的所有点的集合,Cv是到v为止所有被加入点在C中诱导出的割,只需证明对任意active点v正确性定理:每阶段的cut-of-the-phase是最后72证明对active结点的个数归纳.第一个active点出现时,诱导出的割只含一条弧,不等式变为等式,满足;下面考虑在u是v的下一个active结点,则vu根据v的选择方式,W(Av,u)<=W(Av,v),根据归纳假设,W(Av,v)<=W(Cv)根据传递性,W(Au,u)<=W(Cv)+W(Au\Av,u)由图上可知,这两部分是W(Cu)的子集,故W(Av,u)<=W(Cu)完成归纳假设.注意到t总是active的…证明对active结点的个数归纳.第一个active点出现73时间复杂度显然每个phase时间相同,一共|V|次每个phase,每个不在A中的结点按”与A的边权和”为关键字组成优先队列|V|次ExtractMax:取出最紧的点加入A|E|次IncreaseKey:每次选择结点u加入后,所有边uv对应的v(在A外)的关键字要增加w(u,v)二叉堆:O(ElogV)时间复杂度显然每个phase时间相同,一共|V|次74最大流算法——最短增广路最大流算法——最短增广路75概述每次找边数最少的增广路进行增广定理：最多增广O(nm)次Edmonds-Karp：每次BFS找增广路，无需维护附加信息Dinic：多次BFS构造层次图，DFS找增广路。附加信息：层次（起点到u的距离值）ISAP：动态维护距离标号（重标号），DFS找增广路。距离标号是u到汇点的距离下限。选择：熟练编写Dinic和ISAP之一即可概述每次找边数最少的增广路进行增广76严格来说，SAP是一类算法的集合，Edmonds-Karp、Dinic和ISAP都属于它。网络文章中的SAP基本都是特指ISAP。Dinic一般采用多路增广，同时用手工模拟栈，而不是递归找增广路当效率要求不高时每次只找一条路，迭代即可ISAP初始距离标号可以统一设为0，也可以用BFS找，效率相差不大一定要用GAP优化建议用当前弧优化，迭代实现严格来说，SAP是一类算法的集合，Edmonds-Karp、77ISAP距离标号d(i)是顶点到非负整数的映射,它的动机是:描述i到t的最短路下界,它必须满足以下条件:d(t)=0d(i)<=d(j)+1,对于所有残量网络中的边(i,j)如果d(s)>=n,则残量网络中一定没有s-t路d(i)=d(j)+1的弧(i,j)称为允许弧,允许路是最短路,强制走允许路ISAP距离标号d(i)是顶点到非负整数的映射,它的动机是78可以证明,如果一条弧是非允许弧,则只要d(i)不变,它不可能再次变成允许弧因此如果扫描到最后一条弧还是没有找到允许弧,必须对i进行重新标号:取d(i)=min{d(j)+1|(i,j)在Gf中}并设当前弧为第一条弧,重新标号以后往回走一步而不要继续找允许弧,因为当前路径已经不是允许路了（GAP优化）假设重标号是把x改成了y，检查是否还有结点的距离标号为x，没有的话终止算法可以证明,如果一条弧是非允许弧,则只要d(i)不变,它79最大流算法——预流推进最大流算法——预流推进80预流推进算法并不检查整个网络,而是每次考虑一个结点,在残量网络中只检查它的邻居预流推进算法并不始终保持流量平衡条件,而是生成预流。预流也满足对称性和容量限制，和流不同的是：流进每个非s点的净流非负(蓄势待发,等着流出)。记e(u)为点u的盈余自上而下的水流，边是管道，点是连接口每个点有一个小型蓄水池用于储存盈余水量随着算法进行，每个点的高度逐渐增大水往低处流，直到没有水了或者弧满载(push)；如果有水却流不动,需要抬高水位,让它可以继续往低处流(relabel)预流推进算法并不检查整个网络,而是每次考虑一个结点,在残81水源高度固定为|V|,汇的高度固定为0,其他点的高度初始为0,随着时间推移慢慢增加首先尽量多的从水源把水”推”出来,即让s出发的所有弧满载.水流入某个结点u后,进入该结点的蓄水池如果u出发有到达更低点v的非饱和弧,把尽量多的水推入v(push过程)如果u出发的所有非饱和弧都连接着与u水平甚至更高的点,把u抬高直到可以推(relabel过程)最终,所有能流到t的水都已经流到t了,把所有点的蓄水池里的水都倒回s(只需把水位抬得比s还高)水源高度固定为|V|,汇的高度固定为0,其他点的高度初始82Push操作基本操作PUSH(u,v)的条件u有盈余（e[u]>0），且(u,v)在残量网络中，且h(u)=h(v)+1推进量:min{e[u],residual(u,v)}饱和推进(水太多)非饱和推进(水不够)Push的效果是修改e（盈余）和f（流量）进行非饱和推进后,盈余e[u]变为0高度函数，类似于距离标号初始h(s)=|V|,其他h(u)=0Push操作基本操作PUSH(u,v)的条件高度函数，类似于83Relabel操作基本操作RELABEL(u)的条件u有盈余的残量网络中的所有弧(u,v)满足h[u]<=h[v]即:虽然u有盈余,可是由于位置太低,无法进行PUSH操作,需要RELABEL注意:s和t是不会有盈余的,因此不需要RELABEL既然u有盈余,在残量网络中,u出发一定有弧操作：增加h[u]h[u]=1+min{h[v]|(u,v)在残量网络)}Relabel操作基本操作RELABEL(u)的条件84RELABEL-TO-FRONT算法队列：维护结点列表,从头开始扫描,每次对一个盈余结点进行discharge(即连续进行push和relabel,直到它没有盈余)，relabel时放到列表尾部当前弧优化：假设v为当前弧，V为空,则需要RELABEL(u)V非空且(u,v)是允许弧,则PUSH(u,v)V非空且(u,v)不是允许弧,无操作RELABEL之后加入GAP优化非饱和推进减少，时间复杂度为O(V3)RELABEL-TO-FRONT算法队列：维护结点列表,从85最小费用流问题最小费用流问题86最小费用流如下图,弧上除了网络外还有一个费用值总费用等于每条弧的流量与费用的乘积最小费用流如下图,弧上除了网络外还有一个费用值87残量网络残量网络N’=(G’,c’,s,t)c’的定义同不带费用的网络流问题费用定义正向弧费用为w(e)反向弧费用为-w(e)残量网络残量网络N’=(G’,c’,s,t)88消圈定理消圈定理:流量为f的可行流x为流量为f的最小费用流当且仅当x没有负费用增广圈必要性显然，用反证法证明充分性。假设存在不同的可行流x0使得它的费用比x更低，则它们的差x1=x0-x是网络中的负费用循环流。既然是循环流，x1一定可以分解为至多m个非零圈流之和，则它们中至少有一个圈是负费用的（有限个非负费用之和仍是非负的），这个圈就是题目中非负增广圈，矛盾消圈定理消圈定理:流量为f的可行流x为流量为f的最小费用流89消圈算法经典的消圈算法(Klein):利用bellman-ford找负圈,最坏情况需要迭代O(C)次每次用O(nm)时间找平均费用最小的增广圈进行增广,则对于整数权来说最多迭代O(nmlog(nC)),而对于任意实数权来说最多迭代O(nm2logn)次结论:虽然是强多项式时间复杂度,但阶太高,不实用消圈算法经典的消圈算法(Klein):利用bellman-90连续最短路算法由Jewell(1958),Iri(1960),Busacker和Gowen(1961)等人独立提出算法是迭代式的,流量为v时的当前费用流是流量为v的最小费用流最小费用增广路是残量网络中最短的s-t路.由于残量网络中的费用有正有负,所以最短路只能用bellman-ford算法计算,每次需要O(mn)时间,假设增广k次,则时间复杂度为O(kn3),对稀疏图为O(knm)连续最短路算法由Jewell(1958),Iri(196091正确性证明如下图,箭头都代表多步到达,w是负圈,故P(i->a->b->c->j)+P(j->i)<0,因此P(i->a->b->c->j)<P(i->j)sijtabcPW正确性证明如下图,箭头都代表多步到达,w是负圈,故si92假设增广前s到u的距离为d(u),增广后的费用函数为w(e),对于弧e=uv定义一个新的权值w*(e)=w(e)+d(u)–d(v),则对于任意s-t路X,有w*(X)=w(X)–d(x),即对于权函数w(e),w*(e),从s出发的单源最短路树完全一样改进算法:用w*(e)=w(e)+d(u)-d(v)作为权函数计算单源最短路d*(x),然后计算出真正的新最短路注意到w*(e)是非负的,所以可以用dijkstra实现.为什么是非负的?因为如果w*(e)=w(e)+d(u)-d(v)<0,有d(v)>d(u)+w(e)和d(u)是最短距离矛盾时间复杂度降为O(kn2),稀疏图O(kmlogn)假设增广前s到u的距离为d(u),增广后的费用函数为w(e93应用：特殊二分图最佳匹配每个X点有一个权值，最后要求所有被匹配到的X点的权和尽量大算法：将X点按照权值从大到小排序，套用二分图最大基数匹配框架，先从权值大的点开始增广，得到的就是最优解想一想，为什么应用：特殊二分图最佳匹配每个X点有一个权值，最后要求所有被匹94最小树型图最小树型图95朱-刘算法（固定根）首先消除自环，显然自环不在最小树形图中。然后判定是否存在最小树形图，以根为起点DFS一遍即可。对于除根外的每个顶点，选择一条权最小的入边。如果选出来的V-1条边不构成环，则可以证明这些边就是满足要求的答案。否则收缩每个环，调整权值后求新图的最小树形图朱-刘算法（固定根）首先消除自环，显然自环不在最小树形图中。96453-4-3-5从新结点出去的边权不变如果用了从外面进来的边，就得删除里面的边最终答案加上人工点的权和453-4-3-5从新结点出去的边权不变97应用：举办比赛给出一些有向边，边有带宽，还有一个修建费用，然后开始的时候你有cost钱问你怎么修建一个从0到达其他所有点的网络，使得所有网络中最小的带宽值最大应用：举办比赛给出一些有向边，边有带宽，还有一个修建费用，然98题目分析与讨论题目分析与讨论991.太空旅行太空里有n个星球，你的任务是用最少的步数从星球S到达星球T。每次可以从一个星球跳到另一个星球，但并不是所有n(n-1)种跳法都是可行的。所有顶点一共有k个“禁止区间”，其中每个禁止区间用(U,V1,V2)表示，即从星球U出发，不可以直接跳到V1,V1+1,V1+2,…,V2这些星球。1.太空旅行太空里有n个星球，你的任务是用最少的步数从星球S1002.有向图D和E给一个n个结点的有向图D，你可以构造这样一个图E：D的每条边对应E的一个结点（比如，若D有一条边uv，则E有个结点的名字叫uv），对于D的两条边uv和vw，E中的两个结点uv和vw之间连一条有向边。E中不包含其他边。给定图E，你的任务是判断是否存在对应的图D。2.有向图D和E给一个n个结点的有向图D，你可以构造这样一个1013.01串处理机给M个长度为N的串，包含字符0,1或星号*。每个串最多包含一个星号。比如01*表示010和011。用尽量少的指令处理所有串，其中每个指令也是一个长度为N，包含0,1或星号，且最多包含一个星号的串（指令10*处理100和101）。例如：{*01,100,011}至少需要两条指令10*和0*1。N<=10,M<=1000。3.01串处理机给M个长度为N的串，包含字符0,1或星号*。1024.带宽难题给一个无向图G，令T(u,v)为u到v的最大流流量。给定矩阵T，求满足条件的边数最少的无向图G。T(u,u)总是0，T(u,v)总是等于T(v,u)，