第91章：图论补充内容

第91章：图论补充内容第一页，共197页。图的连通性网络流网络编码图着色超图第二页，共197页。图的连通性之前介绍过割点、割边、连通图的概念；这里再补充一些概念和理论。在连通图中，连通的程度也是有高有低；定义一种参数来度量连通图连通程度的高低。第三页，共197页。割点定义：设，如果，则称v为G的一个割点。w(G)表示图G的连通分支数。uv去掉v后，连通分支增加了第四页，共197页。点割集（顶点割集）定义：对图G，若V(G)的子集V’使得，则称V’为图G的一个点割集；含有k个顶点的点割集称为k-点割集；若V’是图G的一个点割集，而V’减少任意一个点都不再是G的点割集，则称V’是G的一个极小点割集；G中含点数最少的点割集称为G的最小点割集。说明割点是1－顶点割集；完全图没有点割集。uv{u,v}是2-点割集第五页，共197页。连通度定义：连通度为是G的顶点割集}完全图的连通度定义为，空图的连通度定义为0；使得的顶点割集V’就是G的最小点割集；若，则称G为k连通的；若G不连通，则；若G是平凡图，则；所有非平凡连通图都是1-连通的。第六页，共197页。割边定义：设，如果，则称e为G的一条割边。边e是G的割边当且仅当e不在G的任何回路中；一个连通图是树当且仅当它的每条边都是割边。uv第七页，共197页。边割集定义：对图G，若E(G)的子集E’使得，则称E’为图G的一个边割集。含有k条边的边割集称为k-边割集。对非平凡图G，若E’是一个边割集，则不连通；一条割边构成一个1－边割集；设，，，记号[S,S’]

表示一端在S中另一端在S’中的所有边的集合。对图G的每个边割集，必存在非空的，使得是G的一个边割集，其中。若E’是图G的一个边割集，而E’减少任意一条边都不再是G的边割集，则称E’是G的一个极小边割集；G中含边数最少的边割集称为G的最小边割集。第八页，共197页。边连通度：定义：完全图的边连通度定义为；空图的边连通度定义为0；对平凡图或不连通图G，；若图G是含有割边的连通图，则；若，则称G为k－边连通的；所有非平凡连通图都是1－边连通的；使得的边割集E’就是G的最小边割集。定理：

图G的结点中最小的度

点连通度

边连通度第九页，共197页。可靠通信网络的设计问题描述：要设计一个有线通讯网，使得敌人炸坏几通讯站后，其余的通讯站仍然可彼此通话；显然，有两个要求是必要的：一是不怕被敌人炸坏站的数目要多，一是整个造价要小。可靠网络设计问题：给定赋权图G和正整数m，求G的具有最小权的m连通生成子图；当m=1时，就是求最小生成树问题；当m>1时，问题尚未解决；当G=Kn且每边权皆为1时，问题成为：求Kn中边数最少的m-连通生成子图。这一问题于1962年由Harary解决。第十页，共197页。网络流简介网络流理论是图论中的一种理论与方法，研究网络上的一类最优化问题；1955年，T.E.哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R.福特和D.R.富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论；目前网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题；网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。第十一页，共197页。引例：运输方案连接产品产地V1和销地V6的交通网，每一条边（Vi，Vj）表示从Vi到Vj的运输线，产品经这条边由Vi输送到Vj，边上的数字表示这条运输线的最大通行能力（简称容量）；产品经过交通网从V1输送到V6，现要求制定一个输送方案，使得从V1运到V6的产品数量最多。1234544842产地6销地1273第十二页，共197页。下面考虑可行的输送方案，用边上方框内的数字表示该运输线的实际运输量（单位：吨）：运输方案：2吨产品沿有向路P1（V1，V2，V4，V6）运到销地；1吨产品沿有向路P2（V1，V2，V5，V6）运到销地；2吨产品沿有向路P3（V1，V3，V5，V6）运到销地。1234544842产地6销地1273222122112注意：需要满足实际的物理限制！第十三页，共197页。1234544842产地6销地12732221221121234544842产地6销地12733221223合并各个边上的运输量，得到运输方案总共有5吨产品从V1运到V6第十四页，共197页。1234544842产地6销地12733221223可行的运输方案必须满足以下三个条件：实际运输量不能是负的；每条边的实际运输量不能大于该边的容量；除了起点V1和终点V6，对其它结点（中间点）来说，不能囤积物资，即运到它那儿的物资是多少，从它那儿运走的物资也应该是多少。

思考：有没有可能改进运输方案？即根据这个运输网，是否可增大运输量？第十五页，共197页。可以找到一条有向路：P4（V1,V2,V3,V4,V6）能再增加1吨运输量1234544842产地6销地12734221123311234544842产地6销地12733221223第十六页，共197页。P5（V1，V3，V4，V6）也可再增加1吨运输量1234544842产地6销地1273432122431思考：还能再增加运输量吗？1234544842产地6销地1273422112331第十七页，共197页。观察有向路P6（V1，V3，V2，V4，V6）正方向的边（V1，V3）、（V2，V4）、（V4，V6）都可增加运输量；反方向的边（V3，V2）的运输量为1；1234544842产地6销地1273432122431第十八页，共197页。如果将反向边（V3，V2）的运量调到正向边（V2，V4）上去完成，这样有向路P6（V1，V3，V2，V4，V6）的运量可增加1。1234544842产地6销地1273432122431反向边上流量含义：节点2需要发出1吨货物，而节点3需要接收1吨货物；可以让该路径上的节点3前一条边增加流量，保持节点3的总进入流量不变；同时让该路径上节点2之后的边上也增加流量，保持节点2的出发流量不变。第十九页，共197页。这里要注意，节点4到节点6一定还应该有剩余的运输能力。再找不到可“改进”的有向路了，该交通网的最大运输量为8吨。1234544842产地6销地12734431225301234544842产地6销地1273432122431第二十页，共197页。通过上述实例分析，包含了流量因素的问题，是一类特殊的图；引例给出的交通网，其实具体的物理模型是多种多样的：网络的有向边可以表示为城市之间的公路、电信网之间的通讯线路、天然气站之间的输气管道等；边的容量则可以表示为允许通过的物资数量、汽车数量、速率或最大信号流量等。这一类特殊的图，称为网络流图；网络流图中需要解决的基本问题最大流问题最大流最小割问题最小费用最大流问题第二十一页，共197页。流网络G=(V,E)是一个有向图，其中每条边(u,v)∈E均有一个非负容量c(u,v)>=0；如果(u,v)不属于E，则假定c(u,v)=0；流网络中有两个特别的顶点：源点s和汇点t；12345432625411343st一个流网络的实例（红色数字表示边的最大容量，蓝色数字表示边上的实际流量）第二十二页，共197页。定义：带权的有向图G=(V,E)，满足以下条件，则称为网络流图(flownetwork)：（1）仅有一个入度为0的顶点s，称s为源点(source)或出发点；（2）仅有一个出度为0的顶点t，称t为汇点(sink)或结束点；（3）每条边(u,v)的权值都为非负数，称为该边的容量，记作c(u,v)；满足上述的条件的图称为网络流图，也可以记作记为G=(V,E,c)第二十三页，共197页。例：一个网络流图：stabcd44332224132源点容量汇点中间点中间点第二十四页，共197页。对一个流网络G=(V,E,c)，每条边(u,v)上给定一个实数f(u,v)，满足：0≤f(u,v)

≤c(u,v)，则f(u,v)称为边(u,v)上的流量。其中满足f(u,v)=c(u,v)的边称为饱和边。如果有一组流量满足条件：源点s：流出量=整个网络的流量汇点t：流入量=

整个网络的流量中间点：总流入量=总流出量

那么整个网络中的流量称为一个可行流。

这个是真实的实体网络中的情况，如果针对通信网络来说，不一定满足这样的条件：比如对于汇点来说，流入量可能大于整个网络的流量（当然多的那些是重复的，但是它们还是占用了网络资源）第二十五页，共197页。例：一个网络流图上的可行流：stabcd(4,3)(4,3)(3,2)(3,0)(2,1)(2,2)(2,2)(4,4)(1,1)(3,2)(2,2)容量容许流fat第二十六页，共197页。整个流网络G的流量为：|f|=∑f(s,v)(v∈V)或|f|=∑f(u,t)(u∈V)

『三个重要性质』容量约束：对所有的u,v∈V，要求f(u,v)<=c(u,v)；平衡约束（反对称性）：对所有的u,v∈V，要求f(u,v)=-f(v,u)；流守恒性：对所有u∈V-{s,t}，要求∑f(u,v)=0(v∈V)。流量平衡方程即从源出发的所有流的总和或到达汇的所有流的总和第二十七页，共197页。根据各点流量守恒的关系，可得下列各式：fsa+fsb+fsc=w(1)fat+fbt+fdt=w(2)fsa+fba＝fat+fab

(3)fsb+fcb+fab＝fba+fbt+fbd

(4)fsc＝fcb+fcd

(5)fbd+fcd＝fdt

(6)0≤fsa≤4，0≤fsb≤3，0≤fsc≤4，0≤fab≤2，0≤fba≤3，0≤fat≤3，0≤fbt≤2，0≤fbd≤2，0≤fcb≤1，0≤fcd≤2，0≤fdt≤2，w≥0stabcd44332224132第二十八页，共197页。2.最大流对于一个流网络G=(V,E,c)，在其可行流中，流量最大的一个流就是最大流；注意：最大流可能不止一个。一个可行流一个可行流（也是最大流）12345432625411343st12345432645431343st第二十九页，共197页。残留网络对于给定的一个流网络G及其上的一个流flow，网络G关于流flow的残留网络G*与G有相同的顶点集V，而网络G中的每一条边对应于G*中的1条边或2条边。设(v,w)是G的一条边：当flow(v,w)>0时，(w,v)是G*中的一条边，该边的容量为cap*(w,v)=flow(v,w)；当flow(v,w)<cap(v,w)时，(v,w)是G*中的一条边，该边的容量为cap*(v,w)=cap(v,w)-flow(v,w)。注意：两个条件可能同时都成立，因此就对应两条边。注意：反向边注意：正向边第三十页，共197页。

流网络G 残留网络G*12345432615401343st12345431633112st当flow(v,w)>0时，(w,v)是G*中的一条边，该边的容量为cap*(w,v)=flow(v,w)；当flow(v,w)<cap(v,w)时，(v,w)是G*中的一条边，该边的容量为cap*(v,w)=cap(v,w)-flow(v,w)。第三十一页，共197页。按照残留网络的定义，当原网络G中的边(v,w)是一条零流边时，残留网络G*中有唯一的一条边(v,w)与之对应，且该边的容量为cap(v,w)；当原网络G中的边(v,w)是一条饱和边时，残留网络G*中有唯一的一条边(w,v)与之对应，且该边的容量为cap(v,w)；当原网络G中的边(v,w)是一条弱流边时，残留网络G*中有两条边(v,w)和(w,v)与之对应，这两条边的容量分别为cap(v,w)-flow(v,w)和flow(v,w)。都是可以使用的，一种是可以直接被利用的，一种是可以调到其它边上的。相同点：都可以（需要）减少。第三十二页，共197页。增广路径有向路P6（V1，V3，V2，V4，V6）正向边（V1，V3）、（V2，V4）、（V4，V6）；反向边（V3，V2）的运输量为1；增广路径在残留网络Gf中从s到t的一条简单路径称为增广路径；若边(u,v)的方向与该路径的方向一致，称(u,v)为正向边（正向弧），正向边的全体记为P+；若边(u,v)的方向与该路径的方向相反，称为逆向边（反向弧），逆向边的全体记为P-。

思考：增广路径的实际意义？第三十三页，共197页。如果将反向边（V3，V2）的运量调到正向边（V2，V4）上去完成，这样有向路P6（V1，V3，V2，V4，V6）的运量可增加1。增广路径上所有的边满足：对所有正向边有：f(u,v)<c(u,v)即P+中的每一条边都是非饱和边；对所有逆向边有：f(u,v)>0即P-中的每一条边都是非零流边。

逆向边流量大于0，意味着逆向边上有流量；正向边流量小于容量，意味着逆向边的流量可以调过来。第三十四页，共197页。增广路径将增广路径中最大容量为p的残留网络定义为：cf(p)=min{cf(u,v)|(u,v)在增广路径上}简单路径：13245中，(1,3)、(2,4)、(4,5)是正向边，(3,2)是逆向边。12345432654st第三十五页，共197页。增广路径两条路径：1235、1245两条增广路径：135、1324512345432625242222st第三十六页，共197页。割（CUT）流网络中顶点的一个划分；它把流网络G(V,E)中的所有顶点划分成两个顶点集合S和T（T=V-S），其中源点s∈S，汇点t∈T，记为CUT(S,T)；如果一条边（弧）的两个顶点分别属于顶点集S和T（即一个顶点在S中，另一个顶点在T中），那么这条边称为割CUT(S,T)的一条割边；从S指向T的割边是正向割边；从T指向S的割边是逆向割边。割CUT(S,T)中所有正向割边的容量之和为割CUT(S,T)的容量；注意：不同割的容量不同。割是一个割边的集合第三十七页，共197页。s12345432625443113t顶点集合S={1，2，3}和T={4，5}构成一个割；割的容量为：3+4=7。12345432625443113st源点：s=1；汇点：t=5框外是容量，框内是流量第三十八页，共197页。12345432625443113st顶点集合S={1，3}和T={2，4，5}构成一个割；正向割边：12；35逆向割边：23割的容量：4+4=8割的正向流量：4+2=6逆向割的流量：1容量只考虑正向边，流量要考虑两个方向。第三十九页，共197页。12345432625443113st顶点集合S={1，3，5}和T={2，4}能否构成一个割？第四十页，共197页。12345432625443113st顶点集合S={1，3，4}和T={2，5}能否构成一个割？同构变形12345432625443113st4第四十一页，共197页。最大流问题『最大流定理』可行流f为最大流，当且仅当不存在关于f的增广路径。证明：若f是最大流，但图中存在关于f的增广路径，则可以沿该增广路径增广，得到的是一个更大的流，与f是最大流矛盾。所以，最大流不存在增广路径。『增广路定理』当且仅当由当前的流f压得的残留网络中不存在增广路径时，流f的流量|f|达到最大。第四十二页，共197页。最大流问题『Ford-Fulkerson方法』根据增广路定理，可以设计出最基本的求最大流的方法——Ford-Fulkerson方法；开始将流网络G=(V,E)中的流f置为零流，即对于(u,v)∈E时，f(u,v)=0；然后构建残留网络，寻找增广路径增广，再修改残留网络，重复此过程，直到无法找到增广路径。具体步骤如下：（1）如果存在增广路径，就找出一条增广路径；（2）然后沿该条增广路径进行更新流量（增加流量）。其实就是不停往流网络中加流量，直到加不进去为止第四十三页，共197页。最大流问题12345432654开始流量为：sum=012345432654一条增广路径:1235d=min{4,2,4}=2增加流量：2sum=2stst第四十四页，共197页。最大流问题一条增广路径:1245d=min{4-2,3,5}=2增加流量：2sum=2+2=412345432625242st12345432625242st222第四十五页，共197页。最大流问题12345432625242-1=1st22212345432625242st222111一条增广路径:13245d=min{6,2,3-2,5-2}=1增加流量：1sum=4+1=523减少1，加到2423减的1由13补充1第四十六页，共197页。最大流问题12345432625242-1=1st222111一条增广路径:135d=min{6-1,4-2}=2增加流量：2sum=5+2=712345432625242-1=1st22211122还能再增加吗？为什么？第四十七页，共197页。最大流问题基于DFS的Ford-Fulkerson方法找一条增广路径：1、先设d为为正无穷（d为可增加流）

若（u,v）是正向边：d=min(d,c(u,v)-f(u,v))若（u,v）是逆向边：d=min(d,f(u,v))2、对与该增广路径上的边

若（u,v）是正向边，f(u,v)=f(u,v)+d；若（u,v）是逆向边，f(u,v)=f(u,v)-d；增广后，总流量增加了d。第四十八页，共197页。最大流问题基于BFS的Edmonds-Karp（EK）算法找一条增广路径：EK算法是基于Ford-Fulkerson方法，唯一的区别是用BFS（宽度优先搜索）来实现对增广路径p的计算；对于EK算法，每次用一遍BFS寻找从源点s到汇点t的最短路作为增广路径，然后增广流量f并修改残量网络，直到不存在新的增广路径；EK算法的理论时间复杂度为：O(nm2)，由于BFS要搜索全部小于最短距离的分支路径之后才能找到终点，因此频繁的BFS效率是比较低的；类似用BFS实现的还有Dinic算法。第四十九页，共197页。基于SAP算法（最短增广路算法）找一条增广路径：定义距离标号为到汇点距离的下界；在初始距离标号的基础上，不断沿可行弧找增广路增广，一般采用DFS深度优先。可行弧定义为：{(i,j)|h[i]=h[j]+1}遍历当前节点完成后，为了使下次再来的时候有路可走，重标号当前节点为：min{h[j]|(i,j)}+1

（注意要满足距离标号的性质：不超过真实距离）重标号后当前节点处理完毕。当源点被重标号后，检查其距离标号，当大于顶点数时，图中已不存在可增广路，此时算法结束；否则再次从源点遍历；理论时间复杂度为：O(n2m)。第五十页，共197页。最小割问题『流与割的关系』网络流量：5割的流量：割正逆161250350450s12345432625443113t1234可以看到什么规律？第五十一页，共197页。最小割问题『定理一』如果f是网络中的一个流，CUT(S,T)是任意一个割，那么f的值等于正向割边的流量与负向割边的流量之差。『推论一』如果f是流网络中的一个流，CUT(S,T)是流网络中一个割，那么f的值不超过割CUT(S,T)的容量。『推论二』流网络中的最大流不超过任何割的容量。第五十二页，共197页。最小割问题『定理二』在任何网络中，如果f是一个流，CUT(S,T)是一个割，且f的值等于割CUT(S,T)的容量，那么f是一个最大流，CUT(S,T)是一个最小割（容量最小的割）。『定理三：最大流最小割定理（Ford-Fulkerson定理）』在任何的网络中，最大流的值等于最小割的容量。第五十三页，共197页。例：plan问题某软件公司有n个可选的软件项目，其中第i个项目，需要项目资金ai元，开发成功后可以获取收益为bi元；但是这些项目之间不是相互独立的：开发第i个项目之前必须开发完成一些其他项目；这些项目称为项目i的前驱项目；目标：在给出所有项目的前驱项目及每个项目的ai和bi后，帮助该公司选择若干个项目开发，使获得的收益最大。思考：考虑净收益（收益-成本）；目标就是总的净收益最大；总的净收益最大化→最大流；如何建模？第五十四页，共197页。思路：令di=bi-ai为净收益A={i|di≥0}：可以获取利润的项目集合B={i|di<0}：亏损的项目集合构成网络图G=（V,E,c）1.两类顶点：N+2个顶点，源点为S，汇点为T，第i个项目为vi2.三种弧：如果i∈A，存在弧(i,t)，容量为di如果i∈B，存在弧(s,i)，容量为|di|如果i的前驱项目为j，存在弧(j,i)容量为+∞第五十五页，共197页。构造割cut(S,T)，如果i∈T，则i的前驱j∈T每个割对应一种方案；目标：求最大流f（即最小割）最大收益为：一种是做了B中任务就亏损；一种是没有做A中任务的期望亏损；收入亏损跟t相连的结点是需要完成的项目第五十六页，共197页。S-T割：割中没有正向容量为∞的弧因为跟T相连的结点是需要完成的项目，如果有正向边，意味着它的前驱项目在S集合中；S集合中的项目是不进行的，则计划不可行，而反向边是无所谓的。说明：和S连接的项目，做了就是亏损→做就是让这些结点跟S断开；和T连接的项目，不做就是亏损→不做就是让这些结点跟T断开；第五十七页，共197页。最小费用最大流最小费用流问题最大流向问题仅涉及流的值，没有涉及费用；实际生活中，不仅要求流量最大，而且还要费用最小；1.交通运输往往要求在完成运输任务的前提下，要找出费用最少的方案；2.在网络中，信息从源传送到目标时，也可寻找最小费用方案，即满足流量要求，又实现费用最节省以实现最佳的分配。求最小费用流就是在流量最大的前提下，求出费用最小的那一个最大流。第五十八页，共197页。基本理论网流G的边不仅有容量限制，还要考虑单位流量的费用；目标：求其最大流的同时，使其费用最低，也称最佳流，是最大流问题的推广；描述：在网络抽象图G(V,E,C,f,w)中，w(e)为边e上单位流量的费用，f(e)为边e上分配的流量；则在给定的可行流fst的条件下，通过流量的分配使费用最小；即minw(f)=min{∑w(e)f(e)}第五十九页，共197页。最小费用增广路算法残量网络中费用的定义：对于原图中的边w(u,v)，残量网络中w’(u,v)=w(u,v),w’(v,u)=-w(u,v)在残量网络中求最小费用路，即以w’为权值的从s到t的最短路（利用Bellman-Ford）；沿最小费用路增广，直到不能找到s-t路为止。最后得到的就是最小费用流。第六十页，共197页。消圈算法残留网络中费用的定义：对于原图中的边w(u,v)；残留网络中w’(u,v)=w(u,v)，w’(v,u)=-w(u,v)先在网络中求出一个最大流，然后再在网络中寻找可增流的负圈，找到了就增流，就可以使最大流的费用减少。当残留网络中不存在负费用圈的时候，这个最大流就是最小费用最大流。第六十一页，共197页。例题分析GoingHome(Poj2195)地图N*M（可用N*M矩阵表示）在地图上有K个人、K间房子，每个人每步只能走到相邻的格子中，每走一步的花费是1；那要这K个人分别走到地图上的K个房间里的总花费是多少？说明：每一个房间可以容纳一个人；一个人也可以站在房间所在的格子中而不进入到房间里去。第六十二页，共197页。例题分析由K个人走到K个房间，可以考虑为可行流问题，这题每个源点或是汇点的流量都为1，而且题目要求的是最小的花费；地图上每两个相邻的点上连接上两条边，容量为K花费为1；把人作为一个顶点集合U，房间作为另一个顶点集合V，把U中所有点到V中所有点连线，构成一个多源多汇的二分图。HHMM第六十三页，共197页。构造一个超级源s和超级汇t：超级源s与U中所有点相连，费用为0（这是显然的），容量为1；V中所有点与超级汇t相连，费用为0（这是显然的），容量为1；至于其它不连通的点，费用与容量均为0。容量为0的边，可以理解为饱和边，不再连通；而上述的所有边之所以容量初始化为1，是因为每间房间只允许入住1个人；而与超级源（汇）相连的边的费用之所以为0，是为了现在所构造的单源单汇网络流最终所求的最小费用等于原来的多源多汇网络流的最小费用。第六十四页，共197页。HHMMst第六十五页，共197页。对偶图在最大流中的应用狼抓兔子现在小朋友们最喜欢的“喜羊羊与灰太狼”，话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：兔子们要从左上角(1,1)的窝跑到右下角(N,M)的窝，狼王开始伏击这些兔子，为了保险起见，如果一条道路上最多通过的兔子数为K，狼王需要安排同样数量的K只狼，才能完全封锁这条道路；问题：设计一个伏击方案，使得在将兔子一网打尽的前提下，参与的狼的数量要最小。左上角(1,1)和右下角(N,M)为兔子的两个窝（图中N=3,M=4)。有三种类型道路：1:(x,y)<==>(x+1,y)2:(x,y)<==>(x,y+1)3:(x,y)<==>(x+1,y+1)道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的；

第六十六页，共197页。思路：第一眼看到这题，显然是找最小割：根据最大流最小割定理，找最大流，也就是最小割；但问题是：找最小割的复杂度是O(n2∗m)；但是观察到地形图是一个平面图，平面图有很多好的性质：对偶图。第六十七页，共197页。如果网络流中的图G可以转化为一个平面图，那么其对偶图G‘中的环对应G中的割，利用最大流最小割定理转化模型，根据平面图G’与其对偶图的关系，先求出最小割；首先连接s和t，如下图蓝色虚线，得到一个附加面，设附加面对应的点为s‘，无界面对应的点为t’，求该图的红色的对偶图G‘，最后删去s’和t‘之间的边。一条从s'到t'的路径，就对应了一个s-t割，更进一步，如果我们令每条边的长度等于它的容量，那么最小割的容量就等于最短路的长度。这样时间复杂度大大降低了。使用二叉堆优化的Dijkstra算法求最短路，时间复杂度为O(nlog2n)

spfa还能更快一些。第六十八页，共197页。利用最短路求最小割对于一个s-t平面图，我们对其进行如下改造：连接s和t，得到一个附加面对于一个s-t平面图，我们对其进行如下改造：求该图的对偶图G*，令附加面对应的点为s*，外部面对应的点为t*对于一个s-t平面图，我们对其进行如下改造：删去s*和t*之间的边123456781*3*2*4*5*7*6*8*sts*t*第六十九页，共197页。利用最短路求最小割一条从s*到t*的路径，就对应了一个s-t割！更进一步，如果令每条边的长度等于它的容量，那么最小割的容量就等于最短路的长度！123456781*3*2*4*5*7*6*8*sts*t*时间复杂度：使用二叉堆优化的Dijkstra算法求最短路，时间复杂度为O(nlog2n)；找最小割的复杂度是O(n2∗m)。第七十页，共197页。利用最短路求最小割一条从s*到t*的路径，就对应了一个s-t割！更进一步，如果我们令每条边的长度等于它的容量，那么最小割的容量就等于最短路的长度！分析一下时间复杂度新图中的点数和边数都是O(n)的使用二叉堆优化的Dijkstra算法求最短路，时间复杂度为O(nlog2n)123456781*3*2*4*5*7*6*8*sts*t*第七十一页，共197页。可以把画的线看作一条连通这条边两侧方块（如果在网格图中）的边，而且你会发现，要使起点和终点不连通，我们就会画出一串可以相连的线；所以解法应该就是在平面图上求最小割，即就是在这一串的割线上找最短路。构建一个对偶图：对于每一条边，必定会有两个面在其左右侧。将左右侧两个面连一条边，且其权值为原来那条边的权值。即对于图中的一条权值为5的边，在对偶图中对应的就是一条由1连向2的权值为5的边。第七十二页，共197页。这个时候就有个问题了：旁边的边怎么办？解决方法：可以将左下方部分设为一个超级源点，右上方部分设为一个超级汇点；这样，对偶图就很好理解了：从超级源点到超级汇点找最短路就行了。第七十三页，共197页。网络编码传统的通信网络传送数据的方式是存储转发，即除了数据的发送节点和接收节点以外的节点只负责路由，而不对数据内容做任何处理；中间节点扮演着转发器的角色；长期以来，人们普遍认为在中间节点上对传输的数据进行加工不会产生任何收益。真是这样吗？第七十四页，共197页。实际上，从信息理论的观点来说，网络结点可以不仅进行存储和转发，还可以收到的信息进行一定的线性或非线性操作（编码），然后再发送出去，起着编码器的作用；存储+转发→存储+编码+转发网络编码正是根据这思想而产生的；在接收节点上，通过一定的运算，译出信源所发的信息。第七十五页，共197页。网络编码的提出最大流最小割定理：网络端对端的最大流量是由最小割决定的，并且最大流的值等于最小割的容量。2000年R.Ahlswede，Cai.N等人发表论文：NetworkInformationflows，IEEETransInfotheory提出网络编码（NetworkCoding）的概念，通过路由器对信息流进行编码，可以达到该上界。但是，目前传统路由器的存储转发模式不可能达到上界，即不能达到最小割。第七十六页，共197页。基本原理：以1信源2信宿、蝴蝶网络为例，每条链路容量为1；由最大流最小割定理，该多播（multicast）的最大的理论传输流量为2；即理论上Y和Z应该能同时收到S发出的2个单元的信息，即同时收到b1、b2。【多源多汇的情况】加超级源和超级汇，超级源向每个源点连容量无限大的边，每个汇点向超级汇连容量为无限大的边。最小割第七十七页，共197页。传统的转发方式：链路WX、XY和XZ上传输的信息均为b1；虽然z收到b1、b2，但Y只能收到b1；因此不能实现最大传输。原因：W结点只有1个出口，只能转发b1或者b2第七十八页，共197页。采用网络编码的转发方式：W对b1、b2进行编码，发出编码b1+b2包给X；X把b1+b2转发给Y和Z；然后Y、Z可解码出原始的数据包b1、b2。编码运算“+”是抽象意义的运算，实际中可以选择多种运算第七十九页，共197页。第八十页，共197页。网络编码的提出网络编码带来的好处：使组播传输速率达到网络容量的上限；最小割最大流决定；节省网络带宽、资源消耗；节省无线网络结点电量消耗传输次数减少：无线信号传输比编码计算更加耗电均衡网络负载；提高网络鲁棒性。缺点：消耗计算资源；中间结点可以对数据进行处理，因此可能有安全问题。有没有缺点呢？第八十一页，共197页。网络编码的发展过程2000年，Ahlswede等提出了网络编码的概念；2002年，Koetter等给出了网络编码的代数构造算法，是指数时间算法（集中式）；2002年，Cai等提出了基于网络编码的网络纠错码概念；2002年，Cai等提出了采用网络编码时的信息完安全性问题；2003年，Sander等给出了网络编码的多项式时间算法（集中式）；2003年，Chou等提出了分布式网络编码，通过仿真得到其性能；2003年，Ho等也提出了随机网络编码（分布式）；2004年，Wu等将网络编码应用于无线网络以节省能量。第八十二页，共197页。网络编码的数学描述信息传输网络可用图表示信源节点集：信宿节点集：边的头节点用表示边的尾节点用表示假设每条边容量为1比特/单位时间（可通过合适选取单位时间大小和将链路进行拆分实现）第八十三页，共197页。网络编码的数学描述网络编码的数学描述(适用于组播和非组播传输）对边集E中的每条边，存在一种映射：

这是对应于每条边的编码函数；目的节点为了得到所需信息，存在映射：是对应于目的节点

的第

个信源符号的译码函数。第八十四页，共197页。网络编码基本方法异或编码、线性编码对于多播，线性编码得到性能上界（maximumcapacitybounds），编码和解码能在多项式时间内完成；Ho等人证明上述结论对于线性编码在随机系数的情况下也成立；第八十五页，共197页。网络编码应用网络传输（有线、无线）内容分发安全分布式存储传输差错控制第八十六页，共197页。无线组播中的网络编码可以实现以网络的最大流传输信息；这是网络中容量的理论上限；可以降低无线网络中的能量消耗；这对以电池为能源供给的无线网络来说，是至关重要的；系统转移矩阵中的变量个数由指数级降为多项式级；从而大大降低了实现网络编码算法的复杂度；在降低网络编码实现算法复杂度的同时，并没有增加网络编码字母表的大小。传统方法基于网络编码的方法第八十七页，共197页。网络编码在无线多跳网络中的应用S.Katti,H.Rahul,W.Hu,D.Katabi,M.Medard,J.Crowcroft,“XORsintheAir:PracticalWirelessNetworkCoding,”

ACMSIGCOMMConference,(September2006).无线网络特性：wifi、zigbee等1广播；（不考虑定向天线）2不稳定、丢包率高；3同信道干扰。第八十八页，共197页。无线多跳网络（Wirelessmultihopnetworks）Ad-Hoc、WMN、WSN、MANETWirelessmeshnetworks（WMN）传统的无线网络的节点通过接入点（AP）才能进行通信，即使两个节点距离很近；（星型拓扑）无线Mesh网络中，每个节点都可以与一个或者多个对等节点进行直接通信；（网状拓扑）提供便宜、广泛的互联网接入；但是目前的连接质量比较低；Roofnet中一半的operational链接的丢包率超过30%.第八十九页，共197页。WirelessSensorNetwork（WSN）由大量的静止或移动的传感器以自组织和多跳的方式构成的无线网络，以协作地感知、采集、处理和传输网络覆盖地理区域内被感知对象的信息，并最终把这些信息发送给网络所有者的；传感器可探测包括地震、电磁、温度、湿度、噪声、光强度、压力、土壤成分、移动物体的大小、速度和方向等参数；应用领域军事、航空、防爆、救灾、环境、医疗、保健、家居、工业、商业等。第九十页，共197页。COPE协议Inter-flownetworkcoding（流间编码）ConsidermultipleunicastflowsGeneralizeAlice-BobscenarioExploitsSharedNatureofWirelessMediumStoreOverheardPacketsforShortTimeThesepacketsareusedfordecodingperspectivepacketsOpportunisticCodingOverhearneighbors’transmissionsStorethesepacketsinabufferPacketPoolforashorttimeReportthepacketpoolinfo.toneighborsDeterminewhatpacketstocodebasedontheinfo.Sendencodedpackets第九十一页，共197页。COPE特点第一个将networkcoding用于无线网络大大增加网络性能（吞吐量）实现简单COPE适用范围全向天线（Omni-directionalantenna）对网络节点性能要求：内存、CPU、电源要求overhear成功率高（干扰、链路冲突）要求链路质量高：出错后重传代价大延迟可能会增加：要等另一个流的数据包双方数据包大小不同的话，对性能有影响第九十二页，共197页。Allassumingperfectoverhearing第九十三页，共197页。左图中的问题是无线网线冲突、干扰，如果B、D不能overhear到a(或b)，则不能解码，重传则更浪费；右图的例子不用考虑overhear丢包的问题，但是这种情况较少，如果只考虑这种情况，则减少了编码机会。传统：4次转发，NC：3次转发Codinggain:theratioofthenumberoftransmissionsrequiredbythecurrentnon-codingapproach,totheminimumnumberoftransmissionsusedbyCOPEtodeliverthesamesetofpackets.第九十四页，共197页。MORE协议TradingStructureforRandomnessinWirelessOpportunisticRouting,SzymonChachulskiMichaelJenningsSachinKattiDinaKatabi,MITCSAIL,SIGCOMM’07传统路由在发送数据包之前选择下一跳节点（不管是先验式还是反应式）；当链接质量低的时候，下一跳节点接收到数据包的概率比较低（意味着要发送多次）；机会路由（Opportunisticrouting）允许距离目的节点比较近的、接收到数据的任何节点（无线通信中数据是广播方式发出的）参与数据包的转发；在链接丢包比较严重的情况下，提供比传统路由更高的吞吐量。第九十五页，共197页。EXOR：S.Biswas,R.Morris,“ExOR:OpportunisticMulti-HopRoutingforWirelessNetworks,”

ACMSIGCOMMConference,(August2005).Biswas和Morris证明了：这种更加弹性的下一跳节点的选择方法可以较大地提高吞吐量；问题：需要节点间协同；多个节点可能接收并且转发同样的数据包，造成资源浪费；第九十六页，共197页。N1N3N5N7N6N2N4N8SDTraditionalPathTraditionalroutingmustcompromisebetweenhopstochooseonesthatarelongenoughtomakegoodprogressbutshortenoughforlowlossrateWithExOReachtransmissionmayhavemoreindependentchancesofbeingreceivedandforwardedIttakesadvantageoftransmissionsthatreachunexpectedlyfar,orfallunexpectedlyshort第九十七页，共197页。Traditionalrouting:1/0.25+1=5transmissionsExOR:1/(1–(1–0.25)4)+1=2.5transmissionsAssumesindependentlossesN1srcdstN2N3N425%25%25%25%100%100%100%100%第九十八页，共197页。MORE简介MAC-independentOpportunisticRouting&Encoding；MORE在发送数据包之前将它们randomly

mixes，这保证了同时接收到相同数据的节点不会转发相同的数据包；数据包随机编码（randomlycodedpackets）后发生重复的概率已经被证明exponentiallylow；效果：MORE不需要特别设定的调度机制，它直接运行在802.11之上。思考：为什么要随机编码？第九十九页，共197页。随机编码在实际网络中无控制中心，因此需要实现分布式网络编码：各个节点不需要中心分配编码系数，而是在某个范围内随机选择一组元素作为编码系数，随机系数的线性相关概率比较低；随机编码系数的选择范围越大，随机网络编码有效的概率就越高；为了方便处理，随机编码系数一般取自于Galois（伽罗瓦）域；域：对乘法运算可换、有单位元、除零元外有逆元的环，如(R,+,x)；一个域的元素有限就是有限域，这种域又称为伽罗瓦(Galois)域；定理：F为有限域，则存在素数p，自然数m≥1，使|F|=pm；定义：一个具有pm个元素的有限域称为pm阶伽罗瓦域，记为GF(pm)，其中p为素数，m1为自然数；网络编码中，随机系数取值范围GF(28)，则线性相关概率1/28。第一百页，共197页。MORE设计思想MORE的设计是基于网络编码理论（theoryofnetworkcoding）；通过两个例子来说明机会路由和网络编码之间的协同工作原理；TheUnicastCase；TheMulticastCaseP1orP2？第一百零一页，共197页。如图1，传统路由在传输数据之前先要确定传输路径：src→R→dest，

因为它有最高的转发概率；（最短路径）由于无线通信是广播方式，因此当一个节点发送数据时，一个距离目的节点比下一跳节点更近的节点也有可能接收到数据包；例如：假设源节点发出2个数据包p1、p2，下一跳节点R都接收到了，而目的节点也接收到了p1，这时如果R仍然转发p1则是浪费资源。这个就是设计ExOR的原因；第一百零二页，共197页。存在问题ExOR需要节点之间的协同，这个在大型网络中是很难做到的；转发节点R只需要转发p2，因为p1已经被目的节点接收到，但是在没有和目的节点协商之前，R不知道他应该转发哪个数据包，这个问题在大型网络中是很难解决的；机会路由允许这些节点参与转发他们听到（接收到）的数据包，但是如果没有协同机制，多个节点可能会转发同一个数据包；ExOR没有用到网络编码第一百零三页，共197页。ExOR采用运行在802.11上的特定的调度机制来解决这个问题：

调度程序循环运行，在任意时间为一个转发节点保留无线介质（也就是说为一个转发节点分配一个特定的时间段来访问无线介质）；

其余的节点监听数据包，由于这个严格的调度机制，距离目的节点很远的节点必须等到距离目的节点比较近的节点完成数据发送后才能发送数据，而如果采用了空间复用，则它们可以同时发送数据；因此，（全局）调度程序的副作用是阻碍了利用无线通信的空间复用性质。问题：全局调度很难实现！第一百零四页，共197页。Idea：采用网络编码在上个例子中，目的节点接收到了p1，但是R不知道，可以采用网络编码，R转发接收到的数据包的线性组合；例如：R发送p1+p2，目的节点收到后，从p1+p2中减去p1就可以得到p2，然后发送接收到数据的ACK消息，R不需要知道目的节点到底接收到了哪个数据包；实际上，R需要发送的是两个数据包的随机线性组和：路由节点创建一个所有它接收到的数据包的线性组合，采用随机系数；目的节点当接收到整个数据后，沿着逆向路径发送ACK消息；优点：不需要节点的协同，并且保留了空间复用。

思考：为什么用随机线性组合？第一百零五页，共197页。TheMulticastCase第一百零六页，共197页。第二个例子说明网络编码和多播之间的协作；源节点多播4个数据包到3个目的节点研究发现：不同节点的无线信号接收是高度独立的；假设每个目的节点的接收情况为：thefirstdestinationreceivesp1andp2,theseconddestinationreceivesp2andp3,thelastdestinationreceivesp3andp4.其中没有一个数据包被所有节点接收到；第一百零七页，共197页。在这种情况下，如果没有进行编码，则发送者必须重新发送所有丢失的数据包；如果进行网络编码，只需要发送两个随机编码后的数据包即可：

p1’=p1+p2+p3+p4P2’=p1+2p2+3p3+4p4不管哪个目的节点丢失了哪个数据包，它都能通过下面的公式计算出来它没有接收到的数据包。重发次数由4减少到2，提高了吞吐量。其实应该也考虑后来发送的编码数据包也有丢失的情况第一百零八页，共197页。Each

routerforwardsrandomcombinationsofpacketssrcR1dstR2α

P1+

ß

P2γ

P1+

δ

P2RandomnesspreventsduplicatesNoscheduler;NocoordinationSimpleandexploitsspatialreuseP1P2P1P2第一百零九页，共197页。RandomCodingBenefitsMulticastsrcdst1dst2dst3P1P2P3P4P1P2P2P3P3P4P3P4P1P4P1P2Withoutcodingsourceretransmitsall4packets第一百一十页，共197页。RandomCodingBenefitsMulticastsrcdst1dst2dst3P1P2P3P4P1P2P2P3P3P48

P1+5

P2+

P3+3

P47

P1+3P2+6P3+P4P3P4P1P4P1P2Withoutcodingsourceretransmitsall4packetsWithrandomcoding2packetsaresufficientRandomcombinationsRandomcodingismoreefficientthan

globalcoordination第一百一十一页，共197页。难点每个节点应该转发多少数据包？传统的最优路径路由中，一个节点向下一跳节点发送数据包，或者发送成功，或者一直发送直到超过重发次数；在机会路由中，没有确定的下一跳节点，所有距离目的节点比当前节点近的节点都可以参与转发；现在的问题是：多少次的转发能保证至少一个节点接收到这个数据包？多发了浪费资源，少发了则不够用第一百一十二页，共197页。一个节点在什么情况下停止发送，并清空数据？通过网络编码，路由器发送线性组合后的数据包，只要目的节点有数量足够的编码后的数据包，它就能解码得到原始数据包。当目的节点接受到数据后，我们需要尽快停止发送，并清空转发节点中的相关数据；节点如何有效编码？网络编码优化的目的是更好地利用无线介质，但是编码需要节点进行加法和乘法运算，需要优化算法来节省CPU的计算资源。第一百一十三页，共197页。MORE是针对静态无线mesh网络的协议，如Roofnet和communitywirelessnetworks；这些网络中的节点是性能比较好的PCs；基本上不太考虑计算问题；对于无线传感器结点来说，就不是太合适；MORE位于IP层之下，802.11MAC之上，提供可靠的文件传输服务，特别适合于传输中型和大型文件（8个或更多数据包）；对于小文件或者控制数据，采用标准的最优路径路由。第一百一十四页，共197页。相关术语原始数据包（NativePacket）没有编码的数据包；编码数据包（CodedPacket）原始数据包的随机线性组合；编码向量（CodeVector）将原始数据包通过线性组合得到编码数据包时用到的参数向量；创新数据包（

innovativepacket）和一个节点以前收到的数据包线性独立的数据包；距离目的节点更近根据到目的节点的ETX来比较；新的信息第一百一十五页，共197页。源节点源节点把文件分割成K个原始数据包；就是一个batch，长度固定当802.11MAC做好发送准备，源节点在当前batch中创建一个由K个原始数据包随机线性组合的数据包，然后将其发送出去；发送节点在每个数据包的头部附加一个MORE包头，其中包含本数据包的编码向量、batchID、源和目的IP、参与转发的节点列表；第一百一十六页，共197页。计算转发列表节点周期性地互相Ping，然后估计每个链接的发送概率，通过这个概率来计算到目的节点的ETX：ETX（expectedtransmissioncount）是将一个数据包发送到目的节点的期望传输次数；发送节点的转发列表中包括那些比自己距离目的节点更近（在ETX指标下）的那些节点，并且根据距离排序；发送节点持续发送当前batch编码后的数据包，直到整个batch被目的节点确认接收到，然后发送者处理下一个batch。收到目的节点对该batch的ACK第一百一十七页，共197页。第一百一十八页，共197页。转发节点转发节点监听所有的数据传输，当一个节点监听到一个数据包，它检查自己是否在这个数据包的转发列表中；也就是该节点是不是被允许转发这个数据包；如果是，然后检查这个数据包中是不是一个创新数据包:包含新的信息，即：和以前接收到的数据包线性独立；可采用简单的代数方法判断（如GaussianElimination）；节点保存创新数据包，而忽略非创新数据包；第一百一十九页，共197页。转发节点如果节点在转发节点列表中，接收到的新数据包会触发节点广播一个编码数据包这个编码数据包是已经接收到的同一个batch里面的所有数据包的一个随机线性组合；注意：编码数据包的线性组合也同样是原始数据包的一个线性组合；第一百二十页，共197页。目的节点对接收到的每一个数据包，目的节点检查它是否是一个创新数据包，丢弃非创新数据包；这个操作和转发节点类似；一旦目的节点接收到K个创新数据包，就可以通过如下方法得到原始数据包：问题：矩阵运算的运算量大！第一百二十一页，共197页。目的节点解码出整个batch，它马上发一个ACK到源节点，提示源节点可以开始发送下一个batch；（一次数据传输分成多个batch，然后按顺序传输）ACKs消息用最优路径路由来发送：因为MORE不适合于小数据量的数据传输，因此采用传统的最优路径路由；最优路径路由在这里能工作的原因是MORE采用标准的802.11，并且能和最短路径路由共存；ACKs消息比在每个节点上的数据包优先级高；第一百二十二页，共197页。实际的挑战一个转发节点转发多少个数据包？传统的最优路径路由中，一个节点向下一跳节点发送数据包，或者发送成功，或者一直发送直到超过重发次数；在机会路由中，没有确定的下一跳节点所有的距离目的节点比当前节点近的节点都可以参与转发，现在的问题是：多少次的转发能保证至少一个节点接收到这个数据包？这是一个仍未解决的问题，以前的工作只考虑一个简单并且理论化的问题，该问题假设流量是平滑的，并且无线网络的带宽是无限的；但是即使在这个假设之下，上述方法也需要解决前面提到的凸优化问题，这个优化问题的约束条件随着听到广播的节点数的指数方式增长；第一百二十三页，共197页。在本节中，我们提出了该问题的一个基于启发式方法的实际解决方案，该解决方案有如下特点：低复杂度；分布式；自然地和802.11集成，并保留了空间复用性质；实用性：只需要链接的平均丢失率；没有假设无限的带宽、平滑的流量。第一百二十四页，共197页。(a)Approach定义节点i到目的节点d的距离（i的ETX）节点i沿着最优路径发送一个数据包到目的节点d的期望发送次数；把一个数据包从源节点s路由到目的节点d的启发式方法：（类似于ExOR）当一个节点发送一个数据包，在ETX指标下距离目的节点最近的接收到数据包的节点转发数据包；距离目的节点最近的节点转发数据包，减少了期望传输次数，因此提高了总体的吞吐量。第一百二十五页，共197页。设网络中节点数为N，对于任意两个节点i和j，i<j表示i比j距离目的节点更近，即i的ETX值比j的小；设eij表示从i到j发送一个数据包的丢失概率；（这里考虑的是双向的丢失率相同）设zi是在所有节点采用上述启发式路由的情况下，转发节点i把一个数据包从源节点s路由到目的节点d的期望传输次数（不管之前和之后，反正就是接收到一个数据包后，把它发出去的次数）；假设不同节点的无线数据接收是相互独立的；这在

一些文献中已经通过实际测量验证了。第一百二十六页，共197页。我们注意从源节点发送一个数据包到目的节点；需要计算：在把一个数据包从源节点s发送到目的节点d的过程中，转发节点j必须转发的数据包的数量；如果转发节点不转发这个数据包呢？虽然在转发列表中，但是ETX更小的节点已经转发了（这个问题下一页讨论）；节点j从ETX值更高的节点得到的数据包的期望数量为：（不管经历了多少跳，最终都是从