《图论补充内容课件.pptx》由会员分享，可在线阅读，更多相关《图论补充内容课件.pptx（197页珍藏版）》请在三一办公上搜索。
1、图论补充内容,图的连通性网络流网络编码图着色超图,图的连通性,之前介绍过割点、割边、连通图的概念；这里再补充一些概念和理论。在连通图中，连通的程度也是有高有低；定义一种参数来度量连通图连通程度的高低。,割点定义：设，如果，则称v为G的一个割点。w(G)表示图G的连通分支数。,u,v,去掉v后，连通分支增加了,点割集（顶点割集）定义：对图G，若V(G)的子集V使得，则称V为图G的一个点割集；含有k个顶点的点割集称为k-点割集；若V是图G的一个点割集，而V减少任意一个点都不再是G的点割集，则称V是G的一个极小点割集；G中含点数最少的点割集称为G的最小点割集。说明割点是1顶点割集；完全图没有点割集。
2、,u,v,u,v是2-点割集,连通度 定义：连通度为 是G的顶点割集完全图的连通度定义为，空图的连通度定义为0；使得 的顶点割集V就是G的最小点割集；若，则称G为k连通的；若G不连通，则；若G是平凡图，则；所有非平凡连通图都是1-连通的。,割边定义：设，如果，则称e为G的一条割边。,边e是G的割边当且仅当e不在G的任何回路中；一个连通图是树当且仅当它的每条边都是割边。,u,v,边割集定义：对图G，若E(G)的子集E使得，则称E为图G的一个边割集。含有k条边的边割集称为k-边割集。对非平凡图G，若E是一个边割集，则 不连通；一条割边构成一个1边割集；设，记号S,S 表示一端在S中另一端在S中的所
3、有边的集合。对图G的每个边割集，必存在非空的，使得 是G的一个边割集，其中。,若E是图G的一个边割集，而E减少任意一条边都不再是G的边割集，则称E是G的一个极小边割集；G中含边数最少的边割集称为G的最小边割集。,边连通度：定义：完全图的边连通度定义为；空图的边连通度定义为0；对平凡图或不连通图G，；若图G是含有割边的连通图，则；若，则称G为k边连通的；所有非平凡连通图都是1边连通的；使得 的边割集E就是G的最小边割集。定理：,图G的结点中最小的度,点连通度,边连通度,可靠通信网络的设计问题描述：要设计一个有线通讯网，使得敌人炸坏几通讯站后，其余的通讯站仍然可彼此通话；显然，有两个要求是必要的：
4、一是不怕被敌人炸坏站的数目要多，一是整个造价要小。可靠网络设计问题：给定赋权图G和正整数m，求G的具有最小权的m连通生成子图；当m=1时，就是求最小生成树问题；当m1时，问题尚未解决；当G=Kn且每边权皆为1时，问题成为：求Kn中边数最少的m-连通生成子图。这一问题于1962年由Harary解决。,网络流简介,网络流理论是图论中的一种理论与方法，研究网络上的一类最优化问题；1955年，T.E.哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R.福特和D.R.富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论；目前网络流的理论和应用在不断发
5、展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题；网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。,引例：运输方案,连接产品产地V1和销地V6的交通网，每一条边（Vi，Vj）表示从Vi到Vj的运输线，产品经这条边由Vi输送到Vj，边上的数字表示这条运输线的最大通行能力（简称容量）；产品经过交通网从V1输送到V6，现要求制定一个输送方案，使得从V1运到V6的产品数量最多。,下面考虑可行的输送方案，用边上方框内的数字表示该运输线的实际运输量（单位：吨）：运输方案：2吨产品沿有向路P1（V1，V2，V4，V6）运到销地；1吨产品沿
6、有向路P2（V1，V2，V5，V6）运到销地；2吨产品沿有向路P3（V1，V3，V5，V6）运到销地。,1,2,3,4,5,4,4,8,4,2,产地,6,销地,1,2,7,3,2,2,2,1,2,2,1,1,2,注意：需要满足实际的物理限制！,1,2,3,4,5,4,4,8,4,2,产地,6,销地,1,2,7,3,2,2,2,1,2,2,1,1,2,合并各个边上的运输量，得到运输方案,总共有5吨产品从V1运到V6,可行的运输方案必须满足以下三个条件：实际运输量不能是负的；每条边的实际运输量不能大于该边的容量；除了起点V1和终点V6，对其它结点（中间点）来说，不能囤积物资，即运到它那儿的物资是多
7、少，从它那儿运走的物资也应该是多少。,思考：有没有可能改进运输方案？即根据这个运输网，是否可增大运输量？,可以找到一条有向路：P4（V1,V2,V3,V4,V6）能再增加1吨运输量,P5（V1，V3，V4，V6）也可再增加1吨运输量,思考：还能再增加运输量吗？,观察有向路P6（V1，V3，V2，V4，V6）正方向的边（V1，V3）、（V2，V4）、（V4，V6）都可增加运输量；反方向的边（V3，V2）的运输量为1；,1,2,3,4,5,4,4,8,4,2,产地,6,销地,1,2,7,3,4,3,2,1,2,2,4,3,1,如果将反向边（V3，V2）的运量调到正向边（V2，V4）上去完成，这样有
8、向路P6（V1，V3，V2，V4，V6）的运量可增加1。,反向边上流量含义：节点2需要发出1吨货物，而节点3需要接收1吨货物；可以让该路径上的节点3前一条边增加流量，保持节点3的总进入流量不变；同时让该路径上节点2之后的边上也增加流量，保持节点2的出发流量不变。,这里要注意，节点4到节点6一定还应该有剩余的运输能力。,再找不到可“改进”的有向路了，该交通网的最大运输量为8吨。,通过上述实例分析，包含了流量因素的问题，是一类特殊的图；引例给出的交通网，其实具体的物理模型是多种多样的：网络的有向边可以表示为城市之间的公路、电信网之间的通讯线路、天然气站之间的输气管道等；边的容量则可以表示为允许通过
9、的物资数量、汽车数量、速率或最大信号流量等。这一类特殊的图，称为网络流图；网络流图中需要解决的基本问题最大流问题最大流最小割问题最小费用最大流问题,流网络G=(V,E)是一个有向图，其中每条边(u,v)E均有一个非负容量c(u,v)=0；如果(u,v)不属于E，则假定c(u,v)=0；流网络中有两个特别的顶点：源点s和汇点t；,一个流网络的实例（红色数字表示边的最大容量，蓝色数字表示边上的实际流量）,定义：带权的有向图G=(V,E)，满足以下条件，则称为网络流图(flow network)：（1）仅有一个入度为0的顶点s，称s为源点(source)或出发点；（2）仅有一个出度为0的顶点t，称t
10、为汇点(sink)或结束点；（3）每条边(u,v)的权值都为非负数，称为该边的容量，记作c(u,v)；满足上述的条件的图称为网络流图，也可以记作记为G=(V,E,c),例：一个网络流图：,源点,容量,汇点,中间点,中间点,对一个流网络G=(V,E,c)，每条边(u,v)上给定一个实数f(u,v)，满足：0f(u,v)c(u,v)，则f(u,v)称为边(u,v)上的流量。其中满足f(u,v)=c(u,v)的边称为饱和边。如果有一组流量满足条件：源点s：流出量=整个网络的流量汇点t：流入量=整个网络的流量中间点：总流入量=总流出量那么整个网络中的流量称为一个可行流。,这个是真实的实体网络中的情况，
11、如果针对通信网络来说，不一定满足这样的条件：比如对于汇点来说，流入量可能大于整个网络的流量（当然多的那些是重复的，但是它们还是占用了网络资源）,例：一个网络流图上的可行流：,容量,容许流fat,整个流网络G的流量为：|f|=f(s,v)(vV)或|f|=f(u,t)(uV)三个重要性质容量约束：对所有的u,vV，要求f(u,v)=c(u,v)；平衡约束（反对称性）：对所有的u,vV，要求f(u,v)=-f(v,u)；流守恒性：对所有uV-s,t，要求f(u,v)=0(vV)。,流量平衡方程,即从源出发的所有流的总和或到达汇的所有流的总和,根据各点流量守恒的关系，可得下列各式：fsa+fsb+f
12、sc=w(1)fat+fbt+fdt=w(2)fsa+fbafat+fab(3)fsb+fcb+fabfba+fbt+fbd(4)fscfcb+fcd(5)fbd+fcdfdt(6)0fsa4，0fsb3，0fsc4，0fab2，0fba3，0fat3，0fbt2，0fbd2，0fcb1，0fcd2，0fdt2，w0,2.最大流对于一个流网络G=(V,E,c)，在其可行流中，流量最大的一个流就是最大流；注意：最大流可能不止一个。,一个可行流,一个可行流（也是最大流）,残留网络,对于给定的一个流网络G及其上的一个流flow，网络G关于流flow的残留网络G*与G有相同的顶点集V，而网络G中的每一
13、条边对应于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)。,注意：两个条件可能同时都成立，因此就对应两条边。,注意：反向边,注意：正向边,流网络G 残留网络G*,当flow(v,w)0时，(w,v)是G*中的一条边，该边的容量为cap*(w,v)=flow(v,w)；当flow(v,w)cap(v,w)时，(v,w)是G*中的一条边，该边的容量为cap
14、*(v,w)=cap(v,w)-flow(v,w)。,按照残留网络的定义，当原网络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)。,都是可以使用的，一种是可以直接被利用的，一种是可以调到其它边上的。相同点：都可以（需要）减少。,增广路径,
15、有向路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-。,思考：增广路径的实际意义？,如果将反向边（V3，V2）的运量调到正向边（V2，V4）上去完成，这样有向路P6（V1，V3，V2，V4，V6）的运量可增加1。,增广路径上所有的边满足：对所有正向边有：f(u,v)0即P-中的每一条
16、边都是非零流边。,逆向边流量大于0，意味着逆向边上有流量；正向边流量小于容量，意味着逆向边的流量可以调过来。,增广路径,将增广路径中最大容量为p的残留网络定义为：cf(p)=mincf(u,v)|(u,v)在增广路径上简单路径：13245中，(1,3)、(2,4)、(4,5)是正向边，(3,2)是逆向边。,增广路径,两条路径：1235、1245两条增广路径：135、13245,1,2,3,4,5,4,3,2,6,2,5,2,4,2,2,2,2,s,t,割（CUT）,流网络中顶点的一个划分；它把流网络G(V,E)中的所有顶点划分成两个顶点集合S和T（T=V-S），其中源点sS，汇点tT，记为CU
17、T(S,T)；如果一条边（弧）的两个顶点分别属于顶点集S和T（即一个顶点在S中，另一个顶点在T中），那么这条边称为割CUT(S,T)的一条割边；从S指向T的割边是正向割边；从T指向S的割边是逆向割边。割CUT(S,T)中所有正向割边的容量之和为割CUT(S,T)的容量；注意：不同割的容量不同。,割是一个割边的集合,顶点集合S=1，2，3和T=4，5构成一个割；割的容量为：3+4=7。,1,2,3,4,5,4,3,2,6,2,5,4,4,3,1,1,3,s,t,源点：s=1；汇点：t=5框外是容量，框内是流量,1,2,3,4,5,4,3,2,6,2,5,4,4,3,1,1,3,s,t,顶点集合S
18、=1，3和T=2，4，5构成一个割；正向割边：12；35逆向割边：23,割的容量：4+4=8割的正向流量：4+2=6逆向割的流量：1,容量只考虑正向边，流量要考虑两个方向。,1,2,3,4,5,4,3,2,6,2,5,4,4,3,1,1,3,s,t,顶点集合S=1，3，5和T=2，4能否构成一个割？,顶点集合S=1，3，4和T=2，5能否构成一个割？同构变形,最大流问题,最大流定理可行流f为最大流，当且仅当不存在关于f的增广路径。证明：若f是最大流，但图中存在关于f的增广路径，则可以沿该增广路径增广，得到的是一个更大的流，与f是最大流矛盾。所以，最大流不存在增广路径。增广路定理当且仅当由当前的
19、流f压得的残留网络中不存在增广路径时，流f的流量|f|达到最大。,最大流问题,Ford-Fulkerson方法根据增广路定理，可以设计出最基本的求最大流的方法Ford-Fulkerson方法；开始将流网络G=(V,E)中的流f置为零流，即对于(u,v)E时，f(u,v)=0；然后构建残留网络，寻找增广路径增广，再修改残留网络，重复此过程，直到无法找到增广路径。具体步骤如下：（1）如果存在增广路径，就找出一条增广路径；（2）然后沿该条增广路径进行更新流量（增加流量）。,其实就是不停往流网络中加流量，直到加不进去为止,最大流问题,开始流量为：sum=0,一条增广路径:1235d=min4,2,4=
20、2增加流量：2sum=2,s,t,s,t,最大流问题,一条增广路径:1245d=min4-2,3,5=2增加流量：2sum=2+2=4,1,2,3,4,5,4,3,2,6,2,5,2,4,2,s,t,1,2,3,4,5,4,3,2,6,2,5,2,4,2,s,t,2,2,2,最大流问题,1,2,3,4,5,4,3,2,6,2,5,2,4,2-1=1,s,t,2,2,2,1,2,3,4,5,4,3,2,6,2,5,2,4,2,s,t,2,2,2,1,1,1,一条增广路径:13245d=min6,2,3-2,5-2=1增加流量：1sum=4+1=5,23减少1，加到2423减的1由13补充1,最大
21、流问题,1,2,3,4,5,4,3,2,6,2,5,2,4,2-1=1,s,t,2,2,2,1,1,1,一条增广路径:135d=min6-1,4-2=2增加流量：2sum=5+2=7,1,2,3,4,5,4,3,2,6,2,5,2,4,2-1=1,s,t,2,2,2,1,1,1,2,2,还能再增加吗？为什么？,最大流问题,基于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(
22、u,v)+d；若（u,v）是逆向边，f(u,v)=f(u,v)-d；增广后，总流量增加了d。,最大流问题,基于BFS的Edmonds-Karp（EK）算法找一条增广路径：EK算法是基于Ford-Fulkerson方法，唯一的区别是用BFS（宽度优先搜索）来实现对增广路径p的计算；对于EK算法，每次用一遍BFS寻找从源点s到汇点t的最短路作为增广路径，然后增广流量f并修改残量网络，直到不存在新的增广路径；EK算法的理论时间复杂度为：O(nm2)，由于BFS要搜索全部小于最短距离的分支路径之后才能找到终点，因此频繁的BFS效率是比较低的；类似用BFS实现的还有Dinic算法。,基于SAP算法（最短
23、增广路算法）找一条增广路径：定义距离标号为到汇点距离的下界；在初始距离标号的基础上，不断沿可行弧找增广路增广，一般采用DFS深度优先。可行弧定义为：(i,j)|hi=hj+1遍历当前节点完成后，为了使下次再来的时候有路可走，重标号当前节点为：minhj|(i,j)+1（注意要满足距离标号的性质：不超过真实距离）重标号后当前节点处理完毕。当源点被重标号后，检查其距离标号，当大于顶点数时，图中已不存在可增广路，此时算法结束；否则再次从源点遍历；理论时间复杂度为：O(n2m)。,最小割问题,流与割的关系网络流量：5割的流量：,可以看到什么规律？,最小割问题,定理一如果f是网络中的一个流，CUT(S,
24、T)是任意一个割，那么f的值等于正向割边的流量与负向割边的流量之差。推论一如果f是流网络中的一个流，CUT(S,T)是流网络中一个割，那么f的值不超过割CUT(S,T)的容量。推论二流网络中的最大流不超过任何割的容量。,最小割问题,定理二在任何网络中，如果f是一个流，CUT(S,T)是一个割，且f的值等于割CUT(S,T)的容量，那么f是一个最大流，CUT(S,T)是一个最小割（容量最小的割）。定理三：最大流最小割定理（Ford-Fulkerson定理）在任何的网络中，最大流的值等于最小割的容量。,例：plan问题某软件公司有n个可选的软件项目，其中第i个项目，需要项目资金ai元，开发成功后可
25、以获取收益为bi元；但是这些项目之间不是相互独立的：开发第i个项目之前必须开发完成一些其他项目；这些项目称为项目i的前驱项目；目标：在给出所有项目的前驱项目及每个项目的ai和bi后，帮助该公司选择若干个项目开发，使获得的收益最大。,思考：考虑净收益（收益-成本）；目标就是总的净收益最大；总的净收益最大化最大流；如何建模？,思路：令di=bi-ai为净收益A=i|di0：可以获取利润的项目集合B=i|di0：亏损的项目集合构成网络图G=（V,E,c）1.两类顶点：N+2个顶点，源点为S，汇点为T，第i个项目为vi2.三种弧：如果iA，存在弧(i,t)，容量为di如果iB，存在弧(s,i)，容量为
26、|di|如果i的前驱项目为j，存在弧(j,i)容量为+,构造割cut(S,T)，如果iT，则i的前驱jT每个割对应一种方案；目标：求最大流f（即最小割）最大收益为：,一种是做了B中任务就亏损；一种是没有做A中任务的期望亏损；,收入,亏损,跟t相连的结点是需要完成的项目,S-T割：割中没有正向容量为的弧因为跟T相连的结点是需要完成的项目，如果有正向边，意味着它的前驱项目在S集合中；S集合中的项目是不进行的，则计划不可行，而反向边是无所谓的。,说明：和S连接的项目，做了就是亏损做就是让这些结点跟S断开；和T连接的项目，不做就是亏损不做就是让这些结点跟T断开；,最小费用最大流,最小费用流问题最大流向
27、问题仅涉及流的值，没有涉及费用；实际生活中，不仅要求流量最大，而且还要费用最小；1.交通运输往往要求在完成运输任务的前提下，要找出费用最少的方案；2.在网络中，信息从源传送到目标时，也可寻找最小费用方案，即满足流量要求，又实现费用最节省以实现最佳的分配。求最小费用流就是在流量最大的前提下，求出费用最小的那一个最大流。,基本理论网流G的边不仅有容量限制，还要考虑单位流量的费用；目标：求其最大流的同时，使其费用最低，也称最佳流，是最大流问题的推广；描述：在网络抽象图G(V,E,C,f,w)中，w(e)为边e上单位流量的费用，f(e)为边e上分配的流量；则在给定的可行流fst的条件下，通过流量的分配
28、使费用最小；即min w(f)=minw(e)f(e),最小费用增广路算法残量网络中费用的定义：对于原图中的边w(u,v)，残量网络中w(u,v)=w(u,v),w(v,u)=-w(u,v)在残量网络中求最小费用路，即以w为权值的从s到t的最短路（利用Bellman-Ford）；沿最小费用路增广，直到不能找到s-t路为止。最后得到的就是最小费用流。,消圈算法残留网络中费用的定义：对于原图中的边w(u,v)；残留网络中w(u,v)=w(u,v)，w(v,u)=-w(u,v)先在网络中求出一个最大流，然后再在网络中寻找可增流的负圈，找到了就增流，就可以使最大流的费用减少。当残留网络中不存在负费用圈
29、的时候，这个最大流就是最小费用最大流。,例题分析,Going Home(Poj 2195)地图N*M（可用N*M矩阵表示）在地图上有K个人、K间房子，每个人每步只能走到相邻的格子中，每走一步的花费是1；那要这K个人分别走到地图上的K个房间里的总花费是多少？,说明：每一个房间可以容纳一个人；一个人也可以站在房间所在的格子中而不进入到房间里去。,例题分析,由K个人走到K个房间，可以考虑为可行流问题，这题每个源点或是汇点的流量都为1，而且题目要求的是最小的花费；地图上每两个相邻的点上连接上两条边，容量为K花费为1；把人作为一个顶点集合U，房间作为另一个顶点集合V，把U中所有点到V中所有点连线，构成一
30、个多源多汇的二分图。,构造一个超级源s和超级汇t：超级源s与U中所有点相连，费用为0（这是显然的），容量为1；V中所有点与超级汇t相连，费用为0（这是显然的），容量为1；至于其它不连通的点，费用与容量均为0。容量为0的边，可以理解为饱和边，不再连通；而上述的所有边之所以容量初始化为1，是因为每间房间只允许入住1个人；而与超级源（汇）相连的边的费用之所以为0，是为了现在所构造的单源单汇网络流最终所求的最小费用等于原来的多源多汇网络流的最小费用。,H,H,M,M,s,t,对偶图在最大流中的应用,狼抓兔子现在小朋友们最喜欢的“喜羊羊与灰太狼”，话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔
31、子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：兔子们要从左上角(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)道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的；,思路：第一眼看到这题，显然是找最
32、小割：根据最大流最小割定理，找最大流，也就是最小割；但问题是：找最小割的复杂度是O(n2m)；但是观察到地形图是一个平面图，平面图有很多好的性质：对偶图。,如果网络流中的图G可以转化为一个平面图，那么其对偶图G中的环对应G中的割，利用最大流最小割定理转化模型，根据平面图G与其对偶图的关系，先求出最小割；首先连接s和t，如下图蓝色虚线，得到一个附加面，设附加面对应的点为s，无界面对应的点为t，求该图的红色的对偶图G，最后删去s和t之间的边。,一条从s到t的路径，就对应了一个s-t割，更进一步，如果我们令每条边的长度等于它的容量，那么最小割的容量就等于最短路的长度。这样时间复杂度大大降低了。,使用
33、二叉堆优化的Dijkstra算法求最短路，时间复杂度为O(nlog2n)spfa还能更快一些。,利用最短路求最小割,对于一个s-t平面图，我们对其进行如下改造：连接s和t，得到一个附加面,对于一个s-t平面图，我们对其进行如下改造：求该图的对偶图G*，令附加面对应的点为s*，外部面对应的点为t*,对于一个s-t平面图，我们对其进行如下改造：删去s*和t*之间的边,1,2,3,4,5,6,7,8,1*,3*,2*,4*,5*,7*,6*,8*,s,t,s*,t*,利用最短路求最小割,一条从s*到t*的路径，就对应了一个s-t割！更进一步，如果令每条边的长度等于它的容量，那么最小割的容量就等于最短
34、路的长度！,1,2,3,4,5,6,7,8,1*,3*,2*,4*,5*,7*,6*,8*,s,t,s*,t*,时间复杂度：使用二叉堆优化的Dijkstra算法求最短路，时间复杂度为O(nlog2n)；找最小割的复杂度是O(n2m)。,利用最短路求最小割,一条从s*到t*的路径，就对应了一个s-t割！更进一步，如果我们令每条边的长度等于它的容量，那么最小割的容量就等于最短路的长度！分析一下时间复杂度新图中的点数和边数都是O(n)的使用二叉堆优化的Dijkstra算法求最短路，时间复杂度为O(nlog2n),1,2,3,4,5,6,7,8,1*,3*,2*,4*,5*,7*,6*,8*,s,t,
35、s*,t*,可以把画的线看作一条连通这条边两侧方块（如果在网格图中）的边，而且你会发现，要使起点和终点不连通，我们就会画出一串可以相连的线；所以解法应该就是在平面图上求最小割，即就是在这一串的割线上找最短路。,构建一个对偶图：对于每一条边，必定会有两个面在其左右侧。将左右侧两个面连一条边，且其权值为原来那条边的权值。即对于图中的一条权值为5的边，在对偶图中对应的就是一条由1连向2的权值为5的边。,这个时候就有个问题了：旁边的边怎么办？解决方法：可以将左下方部分设为一个超级源点，右上方部分设为一个超级汇点；这样，对偶图就很好理解了：从超级源点到超级汇点找最短路就行了。,网络编码,传统的通信网络传
36、送数据的方式是存储转发，即除了数据的发送节点和接收节点以外的节点只负责路由，而不对数据内容做任何处理；中间节点扮演着转发器的角色；长期以来，人们普遍认为在中间节点上对传输的数据进行加工不会产生任何收益。,真是这样吗？,实际上，从信息理论的观点来说，网络结点可以不仅进行存储和转发，还可以收到的信息进行一定的线性或非线性操作（编码），然后再发送出去，起着编码器的作用；存储+转发 存储+编码+转发网络编码正是根据这思想而产生的；在接收节点上，通过一定的运算，译出信源所发的信息。,网络编码的提出,最大流最小割定理：网络端对端的最大流量是由最小割决定的，并且最大流的值等于最小割的容量。2000年R.Ah
37、lswede，Cai.N等人发表论文：Network Information flows，IEEE Trans Info theory提出网络编码（Network Coding）的概念，通过路由器对信息流进行编码，可以达到该上界。,但是，目前传统路由器的存储转发模式不可能达到上界，即不能达到最小割。,基本原理：以1信源2信宿、蝴蝶网络为例，每条链路容量为1；由最大流最小割定理，该多播（multicast）的最大的理论传输流量为2；即理论上Y和Z应该能同时收到S发出的2个单元的信息，即同时收到b1、b2。,【多源多汇的情况】加超级源和超级汇，超级源向每个源点连容量无限大的边，每个汇点向超级汇连容
38、量为无限大的边。,最小割,传统的转发方式：链路WX、XY和XZ上传输的信息均为b1；虽然z收到b1、b2，但Y只能收到b1；因此不能实现最大传输。,原因：W结点只有1个出口，只能转发b1或者b2,采用网络编码的转发方式：W对b1、b2进行编码，发出编码b1+b2包给X；X把b1+b2转发给Y和Z；然后Y、Z可解码出原始的数据包b1、b2。,编码运算“+”是抽象意义的运算，实际中可以选择多种运算,网络编码的提出,网络编码带来的好处：使组播传输速率达到网络容量的上限；最小割最大流决定；节省网络带宽、资源消耗；节省无线网络结点电量消耗传输次数减少：无线信号传输比编码计算更加耗电均衡网络负载；提高网络
39、鲁棒性。缺点：消耗计算资源；中间结点可以对数据进行处理，因此可能有安全问题。,有没有缺点呢？,网络编码的发展过程,2000年，Ahlswede等提出了网络编码的概念；2002年，Koetter等给出了网络编码的代数构造算法，是指数时间算法（集中式）；2002年，Cai等提出了基于网络编码的网络纠错码概念；2002年，Cai等提出了采用网络编码时的信息完安全性问题；2003年，Sander等给出了网络编码的多项式时间算法（集中式）；2003年，Chou等提出了分布式网络编码，通过仿真得到其性能；2003年，Ho等也提出了随机网络编码（分布式）；2004年，Wu等将网络编码应用于无线网络以节省能量
40、。,网络编码的数学描述,信息传输网络可用图 表示信源节点集：信宿节点集：边 的头节点用 表示边 的尾节点用 表示,假设每条边容量为1比特/单位时间（可通过合适选取单位时间大小和将链路进行拆分实现）,网络编码的数学描述,网络编码的数学描述(适用于组播和非组播传输）对边集E中的每条边，存在一种映射：这是对应于每条边的编码函数；目的节点 为了得到所需信息，存在映射：是对应于目的节点 的第 个信源符号的译码函数。,网络编码基本方法,异或编码、线性编码对于多播，线性编码得到性能上界（maximum capacity bounds），编码和解码能在多项式时间内完成；Ho等人证明上述结论对于线性编码在随机系
41、数的情况下也成立；,网络编码应用,网络传输（有线、无线）内容分发安全分布式存储传输差错控制,无线组播中的网络编码,可以实现以网络的最大流传输信息；这是网络中容量的理论上限；可以降低无线网络中的能量消耗；这对以电池为能源供给的无线网络来说，是至关重要的；系统转移矩阵中的变量个数由指数级降为多项式级；从而大大降低了实现网络编码算法的复杂度；在降低网络编码实现算法复杂度的同时，并没有增加网络编码字母表的大小。,传统方法,基于网络编码的方法,网络编码在无线多跳网络中的应用,S.Katti,H.Rahul,W.Hu,D.Katabi,M.Medard,J.Crowcroft,“XORs in the A
42、ir:Practical Wireless Network Coding,”ACM SIGCOMM Conference,(September 2006).无线网络特性：wifi、zigbee等1 广播；（不考虑定向天线）2 不稳定、丢包率高；3 同信道干扰。,无线多跳网络（Wireless multihop networks）Ad-Hoc、WMN、WSN、MANET,Wireless mesh networks（WMN）传统的无线网络的节点通过接入点（AP）才能进行通信，即使两个节点距离很近；（星型拓扑）无线Mesh网络中，每个节点都可以与一个或者多个对等节点进行直接通信；（网状拓扑）提供便
43、宜、广泛的互联网接入；但是目前的连接质量比较低；Roofnet中一半的operational链接的丢包率超过30%.,Wireless Sensor Network（WSN）由大量的静止或移动的传感器以自组织和多跳的方式构成的无线网络，以协作地感知、采集、处理和传输网络覆盖地理区域内被感知对象的信息，并最终把这些信息发送给网络所有者的；传感器可探测包括地震、电磁、温度、湿度、噪声、光强度、压力、土壤成分、移动物体的大小、速度和方向等参数；应用领域军事、航空、防爆、救灾、环境、医疗、保健、家居、工业、商业等。,COPE协议,Inter-flow network coding（流间编码）Consi
44、der multiple unicast flowsGeneralize Alice-Bob scenarioExploits Shared Nature of Wireless MediumStore Overheard Packets for Short TimeThese packets are used for decoding perspective packets Opportunistic CodingOverhear neighbors transmissionsStore these packets in a buffer Packet Pool for a short ti
45、meReport the packet pool info.to neighborsDetermine what packets to code based on the info.Send encoded packets,COPE特点第一个将network coding用于无线网络大大增加网络性能（吞吐量）实现简单COPE适用范围全向天线（Omni-directional antenna）对网络节点性能要求：内存、CPU、电源要求overhear成功率高（干扰、链路冲突）要求链路质量高：出错后重传代价大延迟可能会增加：要等另一个流的数据包双方数据包大小不同的话，对性能有影响,All assu
46、ming perfect overhearing,左图中的问题是无线网线冲突、干扰，如果B、D不能overhear到a(或b)，则不能解码，重传则更浪费；右图的例子不用考虑overhear丢包的问题，但是这种情况较少，如果只考虑这种情况，则减少了编码机会。,传统：4次转发，NC：3次转发Coding gain:the ratio of the number of transmissions required by the current non-coding approach,to the minimum number of transmissions used by COPE to deli
47、ver the same set of packets.,MORE协议,Trading Structure for Randomness in Wireless Opportunistic Routing,Szymon Chachulski Michael Jennings Sachin Katti Dina Katabi,MIT CSAIL,SIGCOMM07传统路由在发送数据包之前选择下一跳节点（不管是先验式还是反应式）；当链接质量低的时候，下一跳节点接收到数据包的概率比较低（意味着要发送多次）；机会路由（Opportunistic routing）允许距离目的节点比较近的、接收到数据的任
48、何节点（无线通信中数据是广播方式发出的）参与数据包的转发；在链接丢包比较严重的情况下，提供比传统路由更高的吞吐量。,EXOR：S.Biswas,R.Morris,“ExOR:Opportunistic Multi-Hop Routing for Wireless Networks,”ACM SIGCOMM Conference,(August 2005).Biswas和Morris证明了：这种更加弹性的下一跳节点的选择方法可以较大地提高吞吐量；问题：需要节点间协同；多个节点可能接收并且转发同样的数据包，造成资源浪费；,N1,N3,N5,N7,N6,N2,N4,N8,S,D,Traditiona
49、l Path,Traditional routing must compromise between hops to choose ones that are long enough to make good progress but short enough for low loss rateWith ExOR each transmission may have more independent chances of being received and forwardedIt takes advantage of transmissions that reach unexpectedly
50、 far,or fall unexpectedly short,Traditional routing:1/0.25+1=5 transmissionsExOR:1/(1(1 0.25)4)+1=2.5 transmissionsAssumes independent losses,N1,src,dst,N2,N3,N4,25%,25%,25%,25%,100%,100%,100%,100%,MORE简介,MAC-independent Opportunistic Routing&Encoding；MORE在发送数据包之前将它们randomly mixes，这保证了同时接收到相同数据的节点不会
