图论补充内容.

图论补充内容

图的连通性网络流网络编码图着色超图

图的连通性之前介绍过割点、割边、连通图的概念；这里再补充一些概念和理论。在连通图中，连通的程度也是有高有低；
定义一种参数来度量连通图连通程度的高低。

割点定义：设，如果，则称v为G的一个割点。 w(G)表示图G的连通分支数。去掉v后，连通分支增加了 u v

点割集（顶点割集）定义：说明 u v 对图G，若V(G)的子集V’使得，则称V’为图G的一个点割集；
含有k个顶点的点割集称为k-点割集；若V’是图G的一个点割集，而V’减少任意一个点都不再是G的点割集，则称V’是G的一个极小点割集； G中含点数最少的点割集称为G的最小点割集。说明割点是1－顶点割集；完全图没有点割集。 u {u,v}是2-点割集 v

连通度定义：连通度为是G的顶点割集} 完全图的连通度定义为，空图的连通度定义为0；使得的顶点割集V’就是G的最小点割集；
完全图的连通度定义为，空图的连通度定义为0；使得的顶点割集V’就是G的最小点割集；若，则称G为k连通的；若G不连通，则；若G是平凡图，则；所有非平凡连通图都是1-连通的。

割边定义：设，如果，则称e为G的一条割边。 u v 边e是G的割边当且仅当e不在G的任何回路中；
一个连通图是树当且仅当它的每条边都是割边。

边割集定义：对图G，若E(G)的子集E’使得，则称E’为图G的一个边割集。含有k条边的边割集称为k-边割集。
一条割边构成一个1－边割集；设，，，记号[S,S’] 表示一端在S中另一端在S’中的所有边的集合。对图G的每个边割集，必存在非空的，使得是G的一个边割集，其中。若E’是图G的一个边割集，而E’减少任意一条边都不再是G的边割集，则称E’是G 的一个极小边割集； G中含边数最少的边割集称为G的最小边割集。

边连通度：定义：定理：完全图的边连通度定义为；空图的边连通度定义为0；对平凡图或不连通图G，；
完全图的边连通度定义为；空图的边连通度定义为0；对平凡图或不连通图G，；若图G是含有割边的连通图，则；若，则称G为k－边连通的；所有非平凡连通图都是1－边连通的；使得的边割集E’就是G的最小边割集。定理：图G的结点中最小的度点连通度边连通度

可靠通信网络的设计问题描述：可靠网络设计问题：给定赋权图G和正整数m，求G的具有最小权的m连通生成子图；
要设计一个有线通讯网，使得敌人炸坏几通讯站后，其余的通讯站仍然可彼此通话；显然，有两个要求是必要的：一是不怕被敌人炸坏站的数目要多，一是整个造价要小。可靠网络设计问题：给定赋权图G和正整数m，求G的具有最小权的m连通生成子图；当m=1时，就是求最小生成树问题；当m>1时，问题尚未解决；当G=Kn且每边权皆为1时，问题成为：求Kn中边数最少的m-连通生成子图。这一问题于1962年由Harary解决。

网络流简介网络流理论是图论中的一种理论与方法，研究网络上的一类最优化问题；
1955年，T.E.哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R.福特和D.R.富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论；目前网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题；网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。

2019年5月2日星期四10时54分21秒引例：运输方案连接产品产地V1和销地V6的交通网，每一条边（Vi，Vj）表示从Vi到Vj的运输线，产品经这条边由Vi输送到Vj，边上的数字表示这条运输线的最大通行能力（简称容量）；产品经过交通网从V1输送到V6，现要求制定一个输送方案，使得从V1运到V6的产品数量最多。 1 2 3 4 5 8 产地 6 销地 7 12

产地销地下面考虑可行的输送方案，用边上方框内的数字表示该运输线的实际运输量（单位：吨）：运输方案：
2019年5月2日星期四10时54分21秒下面考虑可行的输送方案，用边上方框内的数字表示该运输线的实际运输量（单位：吨）：运输方案： 2吨产品沿有向路P1（V1，V2，V4，V6）运到销地； 1吨产品沿有向路P2（V1，V2，V5，V6）运到销地； 2吨产品沿有向路P3（V1，V3，V5，V6）运到销地。 2 4 4 2 4 7 1 2 1 1 产地 2 1 8 6 销地 2 2 2 1 4 3 2 5 3 2 注意：需要满足实际的物理限制！ 13

2 4 4 2 4 7 1 2 1 1 产地 2 1 8 6 销地 2 2 2 1 4 3 2 5 3 2 合并各个边上的运输量，得到运输方案总共有5吨产品从V1运到V6 1 2 3 4 5 8 产地 6 销地 7

产地销地可行的运输方案必须满足以下三个条件：实际运输量不能是负的；每条边的实际运输量不能大于该边的容量；
2019年5月2日星期四10时54分21秒可行的运输方案必须满足以下三个条件：实际运输量不能是负的；每条边的实际运输量不能大于该边的容量；除了起点V1和终点V6，对其它结点（中间点）来说，不能囤积物资，即运到它那儿的物资是多少，从它那儿运走的物资也应该是多少。思考：有没有可能改进运输方案？即根据这个运输网，是否可增大运输量？ 1 2 3 4 5 8 产地 6 销地 7 15

产地销地产地销地 2 4 7 1 8 6 5 3 可以找到一条有向路： P4（V1,V2,V3,V4,V6）能再增加1吨运输量 2
2019年5月2日星期四10时54分21秒 1 2 3 4 5 8 产地 6 销地 7 可以找到一条有向路： P4（V1,V2,V3,V4,V6）能再增加1吨运输量 1 2 3 4 5 8 产地 6 销地 7 16

产地销地产地销地思考：还能再增加运输量吗？ 2 4 7 1 8 6 P5（V1，V3，V4，V6）也可再增加1吨运输量 5 3 2
2019年5月2日星期四10时54分21秒 1 2 3 4 5 8 产地 6 销地 7 P5（V1，V3，V4，V6）也可再增加1吨运输量 1 2 3 4 5 8 产地 6 销地 7 思考：还能再增加运输量吗？ 17

观察有向路P6（V1，V3，V2，V4，V6）产地销地正方向的边（V1，V3）、（V2，V4）、（V4，V6）都可增加运输量；
2019年5月2日星期四10时54分21秒观察有向路P6（V1，V3，V2，V4，V6）正方向的边（V1，V3）、（V2，V4）、（V4，V6）都可增加运输量；反方向的边（V3，V2）的运输量为1； 2 4 4 2 4 7 4 1 1 产地 4 1 8 1 6 销地 3 2 3 2 4 3 2 5 3 2 18

2019年5月2日星期四10时54分21秒如果将反向边（V3，V2）的运量调到正向边（V2，V4）上去完成，这样有向路P6（V1，V3，V2，V4，V6）的运量可增加1。 1 2 3 4 5 8 产地 6 销地 7 反向边上流量含义：节点2需要发出1吨货物，而节点3需要接收1吨货物；可以让该路径上的节点3前一条边增加流量，保持节点3的总进入流量不变；同时让该路径上节点2之后的边上也增加流量，保持节点2的出发流量不变。 19

产地销地产地销地这里要注意，节点4到节点6一定还应该有剩余的运输能力。 2 4 7 1 8 6 5 3
2019年5月2日星期四10时54分21秒这里要注意，节点4到节点6一定还应该有剩余的运输能力。 1 2 3 4 5 8 产地 6 销地 7 再找不到可“改进”的有向路了，该交通网的最大运输量为8吨。 1 2 3 4 5 8 产地 6 销地 7 20

通过上述实例分析，包含了流量因素的问题，是一类特殊的图；
2019年5月2日星期四10时54分21秒通过上述实例分析，包含了流量因素的问题，是一类特殊的图；引例给出的交通网，其实具体的物理模型是多种多样的：网络的有向边可以表示为城市之间的公路、电信网之间的通讯线路、天然气站之间的输气管道等；边的容量则可以表示为允许通过的物资数量、汽车数量、速率或最大信号流量等。这一类特殊的图，称为网络流图；网络流图中需要解决的基本问题最大流问题最大流最小割问题最小费用最大流问题 21

流网络G=(V,E)是一个有向图，其中每条边(u,v)∈E均有一个非负容量c(u,v)>=0；
2019年5月2日星期四10时54分21秒流网络G=(V,E)是一个有向图，其中每条边(u,v)∈E均有一个非负容量c(u,v)>=0；如果(u,v)不属于E，则假定c(u,v)=0；流网络中有两个特别的顶点：源点s和汇点t； 1 2 3 4 5 6 s t 一个流网络的实例（红色数字表示边的最大容量，蓝色数字表示边上的实际流量） 22

定义：带权的有向图G=(V,E)，满足以下条件，则称为网络流图(flow network)：
（1）仅有一个入度为0的顶点s，称s为源点(source)或出发点；（2）仅有一个出度为0的顶点t，称t为汇点(sink) 或结束点；（3）每条边(u,v)的权值都为非负数，称为该边的容量，记作c(u,v)；满足上述的条件的图称为网络流图，也可以记作记为G=(V,E,c)

例：一个网络流图：容量 s t a b c d 4 3 2 1 汇点源点中间点中间点

对一个流网络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：流入量 = 整个网络的流量中间点：总流入量 = 总流出量那么整个网络中的流量称为一个可行流。这个是真实的实体网络中的情况，如果针对通信网络来说，不一定满足这样的条件：比如对于汇点来说，流入量可能大于整个网络的流量（当然多的那些是重复的，但是它们还是占用了网络资源）

s t a b c d 例：一个网络流图上的可行流：容量容许流fat (2,1) (3,0) (2,2) (3,2) (4,4)
(4,3) (3,2) (3,0) (2,1) (2,2) (4,4) (1,1) 容许流fat

|f|=∑f(s,v)(v∈V) 或 |f|=∑f(u,t)(u∈V) 『三个重要性质』
整个流网络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)。即从源出发的所有流的总和或到达汇的所有流的总和流量平衡方程

fsb+fcb+fab＝fba+fbt+fbd (4) fsc＝fcb+fcd (5) fbd+fcd＝fdt (6)
根据各点流量守恒的关系，可得下列各式： 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≥0 s t a b c d 4 3 2 1

2.最大流对于一个流网络G=(V,E,c)，在其可行流中，流量最大的一个流就是最大流；注意：最大流可能不止一个。 1 2 3 4 5
6 s t 1 2 3 4 5 6 s t 一个可行流一个可行流（也是最大流）

2019年5月2日星期四10时54分21秒残留网络对于给定的一个流网络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)。注意：反向边注意：正向边注意：两个条件可能同时都成立，因此就对应两条边。 30

流网络G 残留网络G* 当flow(v,w)>0时，(w,v)是G*中的一条边，该边的容量为cap*(w,v)=flow(v,w)；
1 2 3 4 5 6 s t 1 2 3 4 5 6 s t 当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中的边(v,w)是一条零流边时，残留网络G
按照残留网络的定义，当原网络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)。都是可以使用的，一种是可以直接被利用的，一种是可以调到其它边上的。相同点：都可以（需要）减少。

增广路径增广路径在残留网络Gf中从s到t的一条简单路径称为增广路径；
2019年5月2日星期四10时54分21秒增广路径增广路径在残留网络Gf中从s到t的一条简单路径称为增广路径；若边(u,v)的方向与该路径的方向一致，称(u,v)为正向边（正向弧），正向边的全体记为P+；若边(u,v)的方向与该路径的方向相反，称为逆向边（反向弧），逆向边的全体记为P-。有向路P6（V1，V3，V2，V4，V6）正向边（V1，V3）、（V2，V4）、（V4，V6）；反向边（V3，V2）的运输量为1；思考：增广路径的实际意义？ 33

增广路径上所有的边满足：对所有正向边有：f(u,v)<c(u,v) 对所有逆向边有：f(u,v)>0
2019年5月2日星期四10时54分21秒增广路径上所有的边满足：对所有正向边有：f(u,v)<c(u,v) 即P+中的每一条边都是非饱和边；对所有逆向边有：f(u,v)>0 即P-中的每一条边都是非零流边。逆向边流量大于0，意味着逆向边上有流量；正向边流量小于容量，意味着逆向边的流量可以调过来。如果将反向边（V3，V2）的运量调到正向边（V2，V4）上去完成，这样有向路P6（V1，V3， V2，V4，V6）的运量可增加1。 34

cf(p)=min{cf(u,v)|(u,v)在增广路径上}
2019年5月2日星期四10时54分21秒增广路径将增广路径中最大容量为p的残留网络定义为： cf(p)=min{cf(u,v)|(u,v)在增广路径上} 简单路径：13245中，(1,3)、(2,4)、(4,5)是正向边，(3,2)是逆向边。 1 2 3 4 5 6 s t 35

增广路径两条路径：1235、1245 两条增广路径：135、13245 2 3 4 2 4 2 2 s 1 2 2
2019年5月2日星期四10时54分21秒增广路径 2 3 4 2 4 2 2 s 1 2 2 5 2 6 2 5 t 3 4 两条路径：1235、1245 两条增广路径：135、13245 36

2019年5月2日星期四10时54分21秒割（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)的容量；注意：不同割的容量不同。割是一个割边的集合 37

顶点集合S={1，2，3}和T={4，5}构成一个割；割的容量为：3+4=7。
2019年5月2日星期四10时54分21秒 s 1 2 3 4 5 6 t 2 3 4 3 4 4 s 1 2 1 5 3 1 6 2 5 t 3 4 源点：s=1；汇点：t=5 框外是容量，框内是流量顶点集合S={1，2，3}和T={4，5}构成一个割；割的容量为：3+4=7。 38

容量只考虑正向边，流量要考虑两个方向。 2 3 4 3 4 4 s 1 2 1 5 3 1 6 2 5 t 3 4
2019年5月2日星期四10时54分21秒 2 3 4 3 4 4 s 1 2 1 5 3 1 6 2 5 t 3 4 顶点集合S={1，3}和T={2，4，5}构成一个割；正向割边：12；35 逆向割边：23 割的容量：4+4=8 割的正向流量：4+2=6 逆向割的流量：1 容量只考虑正向边，流量要考虑两个方向。 39

顶点集合S={1，3，5}和T={2，4}能否构成一个割？
2019年5月2日星期四10时54分21秒 2 3 4 3 4 4 s 1 2 1 5 3 1 6 2 5 t 3 4 s和t应该分属两个集合顶点集合S={1，3，5}和T={2，4}能否构成一个割？ 40

s s t t 顶点集合S={1，3，4}和T={2，5}能否构成一个割？同构变形 1 2 3 4 5 6 1 2 3 4 5 6
2019年5月2日星期四10时54分21秒 1 2 3 4 5 6 s t 1 2 3 4 5 6 s t 顶点集合S={1，3，4}和T={2，5}能否构成一个割？同构变形 41

2019年5月2日星期四10时54分21秒最大流问题『最大流定理』可行流f为最大流，当且仅当不存在关于f的增广路径。证明：若f是最大流，但图中存在关于f的增广路径，则可以沿该增广路径增广，得到的是一个更大的流，与f是最大流矛盾。所以，最大流不存在增广路径。『增广路定理』当且仅当由当前的流f压得的残留网络中不存在增广路径时，流f的流量|f|达到最大。 42

最大流问题『Ford-Fulkerson方法』具体步骤如下：
2019年5月2日星期四10时54分21秒最大流问题『Ford-Fulkerson方法』根据增广路定理，可以设计出最基本的求最大流的方法——Ford-Fulkerson方法；开始将流网络G=(V,E)中的流f置为零流，即对于(u,v)∈E时，f(u,v)=0；然后构建残留网络，寻找增广路径增广，再修改残留网络，重复此过程，直到无法找到增广路径。具体步骤如下：（1）如果存在增广路径，就找出一条增广路径；（2）然后沿该条增广路径进行更新流量（增加流量）。其实就是不停往流网络中加流量，直到加不进去为止 43

最大流问题开始流量为：sum=0 一条增广路径: 1235 d=min{4,2,4}=2 增加流量：2 sum=2 1 2 3 4
2019年5月2日星期四10时54分21秒最大流问题 1 2 3 4 5 6 1 2 3 4 5 6 s s t t 开始流量为：sum=0 一条增广路径: 1235 d=min{4,2,4}=2 增加流量：2 sum=2 44

最大流问题一条增广路径: 1245 d=min{4-2,3,5}=2 增加流量：2 sum=2+2=4 2 3 2 3 4 4 4
2019年5月2日星期四10时54分21秒最大流问题 2 3 2 3 4 4 4 2 4 2 s 2 2 s 1 2 2 5 1 2 2 5 2 6 6 2 5 t 2 5 t 3 3 4 4 一条增广路径: 1245 d=min{4-2,3,5}=2 增加流量：2 sum=2+2=4 45

最大流问题一条增广路径: 23减少1，加到24 13245 23减的1由13补充1
2019年5月2日星期四10时54分21秒最大流问题 2 3 2 3 4 2 4 4 2 4 s 1 2 2 2 2 s 1 2 2 5 1 2 2-1=1 2 5 2 1 1 6 6 2 5 t 2 5 t 3 3 4 4 一条增广路径: 13245 d=min{6,2,3-2,5-2}=1 增加流量：1 sum=4+1=5 23减少1，加到24 23减的1由13补充1 46

最大流问题还能再增加吗？为什么？一条增广路径: 135 d=min{6-1,4-2}=2 增加流量：2 sum=5+2=7 2 3
2019年5月2日星期四10时54分21秒最大流问题 2 3 2 3 4 2 4 4 2 4 1 1 2 s 2 2 2 s 1 2 2-1=1 2 5 1 2 2-1=1 2 5 1 1 1 1 2 6 6 2 2 5 t 2 5 t 3 3 4 4 一条增广路径: 135 d=min{6-1,4-2}=2 增加流量：2 sum=5+2=7 还能再增加吗？为什么？ 47

最大流问题基于DFS的Ford-Fulkerson方法找一条增广路径： 1、先设d为为正无穷（d为可增加流）若（u,v）是正向边：
2019年5月2日星期四10时54分21秒最大流问题基于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。 48

最大流问题基于BFS的Edmonds-Karp（EK）算法找一条增广路径：类似用BFS实现的还有Dinic算法。
2019年5月2日星期四10时54分21秒最大流问题基于BFS的Edmonds-Karp（EK）算法找一条增广路径： EK算法是基于Ford-Fulkerson方法，唯一的区别是用BFS（宽度优先搜索）来实现对增广路径p的计算；对于EK算法，每次用一遍BFS寻找从源点s到汇点t的最短路作为增广路径，然后增广流量f并修改残量网络，直到不存在新的增广路径； EK算法的理论时间复杂度为：O(nm2)，由于BFS要搜索全部小于最短距离的分支路径之后才能找到终点，因此频繁的BFS效率是比较低的；类似用BFS实现的还有Dinic算法。 49

基于SAP算法（最短增广路算法）找一条增广路径：
2019年5月2日星期四10时54分21秒基于SAP算法（最短增广路算法）找一条增广路径：定义距离标号为到汇点距离的下界；在初始距离标号的基础上，不断沿可行弧找增广路增广，一般采用DFS深度优先。可行弧定义为： {(i,j)|h[i]=h[j]+1} 遍历当前节点完成后，为了使下次再来的时候有路可走，重标号当前节点为： min{h[j]|(i,j)}+1 （注意要满足距离标号的性质：不超过真实距离）重标号后当前节点处理完毕。当源点被重标号后，检查其距离标号，当大于顶点数时，图中已不存在可增广路，此时算法结束；否则再次从源点遍历；理论时间复杂度为：O(n2m)。 50

最小割问题『流与割的关系』割正逆 1 6 2 5 3 4 网络流量：5 割的流量：可以看到什么规律？ 2 3 1 2 4 4 s
2019年5月2日星期四10时54分21秒最小割问题『流与割的关系』网络流量：5 割的流量： 2 3 1 s 1 2 3 4 5 6 t 割正逆 1 6 2 5 3 4 4 可以看到什么规律？ 51

最小割问题『定理一』『推论一』『推论二』
2019年5月2日星期四10时54分21秒最小割问题『定理一』如果f是网络中的一个流，CUT(S,T)是任意一个割，那么f的值等于正向割边的流量与负向割边的流量之差。『推论一』如果f是流网络中的一个流，CUT(S,T)是流网络中一个割，那么f的值不超过割CUT(S,T)的容量。『推论二』流网络中的最大流不超过任何割的容量。 52

最小割问题『定理二』『定理三：最大流最小割定理（Ford-Fulkerson定理）』
2019年5月2日星期四10时54分21秒最小割问题『定理二』在任何网络中，如果f是一个流，CUT(S,T)是一个割，且f的值等于割CUT(S,T)的容量，那么f是一个最大流，CUT(S,T)是一个最小割（容量最小的割）。『定理三：最大流最小割定理（Ford-Fulkerson定理）』在任何的网络中，最大流的值等于最小割的容量。 53

例：plan问题某软件公司有n个可选的软件项目，其中第i个项目，需要项目资金ai元，开发成功后可以获取收益为bi元；
但是这些项目之间不是相互独立的：开发第i个项目之前必须开发完成一些其他项目；这些项目称为项目i的前驱项目；目标：在给出所有项目的前驱项目及每个项目的ai和bi后，帮助该公司选择若干个项目开发，使获得的收益最大。思考：考虑净收益（收益-成本）；目标就是总的净收益最大；总的净收益最大化→最大流；如何建模？

思路：构成网络图G=（V,E,c）令di=bi-ai为净收益 A={i|di≥0}：可以获取利润的项目集合
B={i|di<0}：亏损的项目集合构成网络图G=（V,E,c） 1.两类顶点： N+2个顶点，源点为S，汇点为T，第i个项目为vi 2.三种弧：如果i∈A，存在弧(i,t)，容量为di 如果i∈B，存在弧(s,i)，容量为|di| 如果i的前驱项目为j，存在弧(j,i)容量为+∞

构造割cut(S,T)，如果i∈T，则i的前驱j∈T 每个割对应一种方案；目标：求最大流f（即最小割）最大收益为：
一种是做了B中任务就亏损；一种是没有做A中任务的期望亏损；亏损收入

S-T割：割中没有正向容量为∞的弧说明：因为跟T相连的结点是需要完成的项目，如果有正向边，意味着它的前驱项目在S集合中；
和S连接的项目，做了就是亏损→做就是让这些结点跟S断开；和T连接的项目，不做就是亏损→不做就是让这些结点跟T断开；

最小费用最大流最小费用流问题最大流向问题仅涉及流的值，没有涉及费用；实际生活中，不仅要求流量最大，而且还要费用最小；
1.交通运输往往要求在完成运输任务的前提下，要找出费用最少的方案； 2.在网络中，信息从源传送到目标时，也可寻找最小费用方案，即满足流量要求，又实现费用最节省以实现最佳的分配。求最小费用流就是在流量最大的前提下，求出费用最小的那一个最大流。

基本理论描述：网流G的边不仅有容量限制，还要考虑单位流量的费用；目标：求其最大流的同时，使其费用最低，也称最佳流，是最大流问题的推广；
在网络抽象图G(V,E,C,f,w)中，w(e)为边e上单位流量的费用，f(e)为边e上分配的流量；则在给定的可行流fst的条件下，通过流量的分配使费用最小；即min w(f)=min{∑w(e)f(e)}

最小费用增广路算法残量网络中费用的定义：在残量网络中求最小费用路，即以w’为权值的从s到t的最短路（利用Bellman-Ford）；
对于原图中的边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) 先在网络中求出一个最大流，然后再在网络中寻找可增流的负圈，找到了就增流，就可以使最大流的费用减少。当残留网络中不存在负费用圈的时候，这个最大流就是最小费用最大流。

例题分析 Going Home(Poj 2195) 地图N*M（可用N*M矩阵表示）
在地图上有K个人、K间房子，每个人每步只能走到相邻的格子中，每走一步的花费是1；那要这K个人分别走到地图上的K个房间里的总花费是多少？说明：每一个房间可以容纳一个人；一个人也可以站在房间所在的格子中而不进入到房间里去。

例题分析由K个人走到K个房间，可以考虑为可行流问题，这题每个源点或是汇点的流量都为1，而且题目要求的是最小的花费；
把人作为一个顶点集合U，房间作为另一个顶点集合V，把U 中所有点到V中所有点连线，构成一个多源多汇的二分图。 H M

构造一个超级源s和超级汇t：超级源s与U中所有点相连，费用为0（这是显然的），容量为1；
V中所有点与超级汇t相连，费用为0（这是显然的），容量为1；至于其它不连通的点，费用与容量均为0。容量为0的边，可以理解为饱和边，不再连通；而上述的所有边之所以容量初始化为1，是因为每间房间只允许入住1个人；而与超级源（汇）相连的边的费用之所以为0，是为了现在所构造的单源单汇网络流最终所求的最小费用等于原来的多源多汇网络流的最小费用。

t H H M M s

对偶图在最大流中的应用狼抓兔子现在小朋友们最喜欢的“喜羊羊与灰太狼”，话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：兔子们要从左上角(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) 道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的；

思路：第一眼看到这题，显然是找最小割：根据最大流最小割定理，找最大流，也就是最小割；但问题是：找最小割的复杂度是O(n2∗m)；
但是观察到地形图是一个平面图，平面图有很多好的性质：对偶图。

利用最短路求最小割对于一个s-t平面图，我们对其进行如下改造：对于一个s-t平面图，我们对其进行如下改造：
求该图的对偶图G*，令附加面对应的点为s*，外部面对应的点为t* t* 8* 2 5 5* 7* 6* s t 1 3 6 8 3* 2* 4* 4 7 1* s*

利用最短路求最小割一条从s*到t*的路径，就对应了一个s-t割！
更进一步，如果令每条边的长度等于它的容量，那么最小割的容量就等于最短路的长度！ t* 8* 2 5 时间复杂度：使用二叉堆优化的 Dijkstra算法求最短路，时间复杂度为O(nlog2n)；找最小割的复杂度是 O(n2∗m)。 5* 7* 6* s t 1 3 6 8 3* 2* 4* 4 7 1* s*

可以把画的线看作一条连通这条边两侧方块（如果在网格图中）的边，而且你会发现，要使起点和终点不连通，我们就会画出一串可以相连的线；
所以解法应该就是在平面图上求最小割，即就是在这一串的割线上找最短路。构建一个对偶图：对于每一条边，必定会有两个面在其左右侧。将左右侧两个面连一条边，且其权值为原来那条边的权值。即对于图中的一条权值为5的边，在对偶图中对应的就是一条由1连向2的权值为5的边。

这个时候就有个问题了：旁边的边怎么办？解决方法：可以将左下方部分设为一个超级源点，右上方部分设为一个超级汇点；这样，对偶图就很好理解了：从超级源点到超级汇点找最短路就行了。

网络编码传统的通信网络传送数据的方式是存储转发，即除了数据的发送节点和接收节点以外的节点只负责路由，而不对数据内容做任何处理；
中间节点扮演着转发器的角色；长期以来，人们普遍认为在中间节点上对传输的数据进行加工不会产生任何收益。真是这样吗？

在接收节点上，通过一定的运算，译出信源所发的信息。
实际上，从信息理论的观点来说，网络结点可以不仅进行存储和转发，还可以收到的信息进行一定的线性或非线性操作（编码），然后再发送出去，起着编码器的作用；存储 + 转发 → 存储 + 编码 + 转发网络编码正是根据这思想而产生的；在接收节点上，通过一定的运算，译出信源所发的信息。

但是，目前传统路由器的存储转发模式不可能达到上界，即不能达到最小割。
网络编码的提出最大流最小割定理：网络端对端的最大流量是由最小割决定的，并且最大流的值等于最小割的容量。 2000年R. Ahlswede，Cai. N等人发表论文： Network Information flows，IEEE Trans Info theory 提出网络编码（Network Coding）的概念，通过路由器对信息流进行编码，可以达到该上界。但是，目前传统路由器的存储转发模式不可能达到上界，即不能达到最小割。

基本原理：以1信源2信宿、蝴蝶网络为例，每条链路容量为1；由最大流最小割定理，该多播（multicast）的最大的理论传输流量为2；
即理论上Y和Z应该能同时收到S发出的2个单元的信息，即同时收到b1、b2。最小割【多源多汇的情况】加超级源和超级汇，超级源向每个源点连容量无限大的边，每个汇点向超级汇连容量为无限大的边。

传统的转发方式：链路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。编码运算“+”是抽象意义的运算，实际中可以选择多种运算

网络编码的提出网络编码带来的好处：缺点：使组播传输速率达到网络容量的上限；节省网络带宽、资源消耗；节省无线网络结点电量消耗
最小割最大流决定；节省网络带宽、资源消耗；节省无线网络结点电量消耗传输次数减少：无线信号传输比编码计算更加耗电均衡网络负载；提高网络鲁棒性。缺点：消耗计算资源；中间结点可以对数据进行处理，因此可能有安全问题。有没有缺点呢？

网络编码的发展过程 2000年，Ahlswede等提出了网络编码的概念；
2002年，Koetter等给出了网络编码的代数构造算法，是指数时间算法（集中式）； 2002年，Cai等提出了基于网络编码的网络纠错码概念； 2002年，Cai等提出了采用网络编码时的信息完安全性问题； 2003年，Sander等给出了网络编码的多项式时间算法（集中式）； 2003年，Chou等提出了分布式网络编码，通过仿真得到其性能； 2003年，Ho等也提出了随机网络编码（分布式）； 2004年，Wu等将网络编码应用于无线网络以节省能量。

网络编码的数学描述信息传输网络可用图表示信源节点集：信宿节点集：边的头节点用表示边的尾节点用表示
信息传输网络可用图表示信源节点集：信宿节点集：边的头节点用表示边的尾节点用表示假设每条边容量为1比特/单位时间（可通过合适选取单位时间大小和将链路进行拆分实现）

网络编码的数学描述网络编码的数学描述 (适用于组播和非组播传输）对边集E中的每条边，存在一种映射：这是对应于每条边的编码函数；
目的节点为了得到所需信息，存在映射：是对应于目的节点的第个信源符号的译码函数。

网络编码基本方法异或编码、线性编码对于多播，线性编码得到性能上界（maximum capacity bounds），编码和解码能在多项式时间内完成； Ho等人证明上述结论对于线性编码在随机系数的情况下也成立；

网络编码应用网络传输（有线、无线）内容分发安全分布式存储传输差错控制

网络编码在无线多跳网络中的应用 S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, J. Crowcroft, “XORs in the Air: 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网络中，每个节点都可以与一个或者多个对等节点进行直接通信；（网状拓扑）提供便宜、广泛的互联网接入；但是目前的连接质量比较低； Roofnet中一半的operational链接的丢包率超过30%.

Wireless Sensor Network（WSN）
由大量的静止或移动的传感器以自组织和多跳的方式构成的无线网络，以协作地感知、采集、处理和传输网络覆盖地理区域内被感知对象的信息，并最终把这些信息发送给网络所有者的；传感器可探测包括地震、电磁、温度、湿度、噪声、光强度、压力、土壤成分、移动物体的大小、速度和方向等参数；应用领域军事、航空、防爆、救灾、环境、医疗、保健、家居、工业、商业等。

COPE协议 Inter-flow network coding（流间编码） Consider multiple unicast flows
Generalize Alice-Bob scenario Exploits Shared Nature of Wireless Medium Store Overheard Packets for Short Time These packets are used for decoding perspective packets Opportunistic Coding Overhear neighbors’ transmissions Store these packets in a buffer Packet Pool for a short time Report the packet pool info. to neighbors Determine what packets to code based on the info. Send encoded packets

COPE特点 COPE适用范围第一个将network coding用于无线网络大大增加网络性能（吞吐量）实现简单
全向天线（Omni-directional antenna）对网络节点性能要求：内存、CPU、电源要求overhear成功率高（干扰、链路冲突）要求链路质量高：出错后重传代价大延迟可能会增加：要等另一个流的数据包双方数据包大小不同的话，对性能有影响

All assuming perfect overhearing

左图中的问题是无线网线冲突、干扰，如果B、D不能overhear到a(或b)，则不能解码，重传则更浪费；
传统：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 deliver the same set of packets.

MORE协议 Trading Structure for Randomness in Wireless Opportunistic Routing, Szymon Chachulski Michael Jennings Sachin Katti Dina Katabi, MIT CSAIL, SIGCOMM’07 传统路由在发送数据包之前选择下一跳节点（不管是先验式还是反应式）；当链接质量低的时候，下一跳节点接收到数据包的概率比较低（意味着要发送多次）；机会路由（Opportunistic routing）允许距离目的节点比较近的、接收到数据的任何节点（无线通信中数据是广播方式发出的）参与数据包的转发；在链接丢包比较严重的情况下，提供比传统路由更高的吞吐量。

EXOR： S. Biswas, R. Morris, “ExOR: Opportunistic Multi- Hop Routing for Wireless Networks,” ACM SIGCOMM Conference, (August 2005). Biswas和Morris证明了：这种更加弹性的下一跳节点的选择方法可以较大地提高吞吐量；问题：需要节点间协同；多个节点可能接收并且转发同样的数据包，造成资源浪费；

S N1 N2 N3 N4 N5 N6 N7 N8 D Traditional Path Traditional routing must compromise between hops to choose ones that are long enough to make good progress but short enough for low loss rate With ExOR each transmission may have more independent chances of being received and forwarded It takes advantage of transmissions that reach unexpectedly far, or fall unexpectedly short

Traditional routing: 1/0.25 + 1 = 5 transmissions
25% 100% N2 25% 100% src dst 25% 100% N3 25% 100% N4 Traditional routing: 1/ = 5 transmissions ExOR: 1/(1 – (1 – 0.25)4) + 1 = 2.5 transmissions Assumes independent losses

MORE简介 MAC-independent Opportunistic Routing & Encoding；
MORE在发送数据包之前将它们randomly mixes，这保证了同时接收到相同数据的节点不会转发相同的数据包；数据包随机编码（randomly coded packets）后发生重复的概率已经被证明exponentially low；效果：MORE不需要特别设定的调度机制，它直接运行在之上。思考：为什么要随机编码？

随机编码在实际网络中无控制中心，因此需要实现分布式网络编码：随机编码系数的选择范围越大，随机网络编码有效的概率就越高；
各个节点不需要中心分配编码系数，而是在某个范围内随机选择一组元素作为编码系数，随机系数的线性相关概率比较低；随机编码系数的选择范围越大，随机网络编码有效的概率就越高；为了方便处理，随机编码系数一般取自于Galois（伽罗瓦）域；域：对乘法运算可换、有单位元、除零元外有逆元的环，如(R,+,x)；一个域的元素有限就是有限域，这种域又称为伽罗瓦(Galois)域；定理：F为有限域，则存在素数p，自然数m≥1，使|F|=pm；定义：一个具有pm个元素的有限域称为pm阶伽罗瓦域，记为GF(pm)，其中p为素数，m1为自然数；网络编码中，随机系数取值范围GF(28)，则线性相关概率1/28。

MORE设计思想 MORE的设计是基于网络编码理论（theory of network coding）；
通过两个例子来说明机会路由和网络编码之间的协同工作原理； The Unicast Case； The Multicast Case P1 or P2？

如图1，传统路由在传输数据之前先要确定传输路径：src→R→dest，因为它有最高的转发概率；（最短路径）
由于无线通信是广播方式，因此当一个节点发送数据时，一个距离目的节点比下一跳节点更近的节点也有可能接收到数据包；例如：假设源节点发出2个数据包p1、p2，下一跳节点 R都接收到了，而目的节点也接收到了p1，这时如果R 仍然转发p1则是浪费资源。这个就是设计ExOR的原因；

存在问题 ExOR需要节点之间的协同，这个在大型网络中是很难做到的；
转发节点R只需要转发p2，因为p1已经被目的节点接收到，但是在没有和目的节点协商之前，R不知道他应该转发哪个数据包，这个问题在大型网络中是很难解决的；机会路由允许这些节点参与转发他们听到（接收到）的数据包，但是如果没有协同机制，多个节点可能会转发同一个数据包；

ExOR采用运行在802.11上的特定的调度机制来解决这个问题：
调度程序循环运行，在任意时间为一个转发节点保留无线介质（也就是说为一个转发节点分配一个特定的时间段来访问无线介质）；其余的节点监听数据包，由于这个严格的调度机制，距离目的节点很远的节点必须等到距离目的节点比较近的节点完成数据发送后才能发送数据，而如果采用了空间复用，则它们可以同时发送数据；因此，（全局）调度程序的副作用是阻碍了利用无线通信的空间复用性质。问题：全局调度很难实现！

Idea：采用网络编码在上个例子中，目的节点接收到了p1，但是 R不知道，可以采用网络编码，R转发接收到的数据包的线性组合；
例如：R发送 p1 + p2，目的节点收到后，从p1 + p2中减去p1就可以得到 p2，然后发送接收到数据的ACK消息， R不需要知道目的节点到底接收到了哪个数据包；实际上，R需要发送的是两个数据包的随机线性组和：路由节点创建一个所有它接收到的数据包的线性组合，采用随机系数；目的节点当接收到整个数据后，沿着逆向路径发送ACK消息；优点：不需要节点的协同，并且保留了空间复用。思考：为什么用随机线性组合？

The Multicast Case

第二个例子说明网络编码和多播之间的协作；源节点多播4个数据包到3个目的节点
研究发现：不同节点的无线信号接收是高度独立的；假设每个目的节点的接收情况为： the first destination receives p1 and p2, the second destination receives p2 and p3, the last destination receives p3 and p4. 其中没有一个数据包被所有节点接收到；

其实应该也考虑后来发送的编码数据包也有丢失的情况
在这种情况下，如果没有进行编码，则发送者必须重新发送所有丢失的数据包；如果进行网络编码，只需要发送两个随机编码后的数据包即可： p1’ = p1 + p2 + p3 + p4 P2’ = p1 + 2p2 + 3p3 + 4p4 不管哪个目的节点丢失了哪个数据包，它都能通过下面的公式计算出来它没有接收到的数据包。重发次数由4减少到2，提高了吞吐量。其实应该也考虑后来发送的编码数据包也有丢失的情况

Each router forwards random combinations of packets
α P1+ ß P2 P2 src dst P1 R2 γ P1+ δ P2 P2 Randomness prevents duplicates No scheduler; No coordination Simple and exploits spatial reuse

Random Coding Benefits Multicast
P1 P2 src P3 P4 dst1 dst2 dst3 P1 P3 P4 P1 P2 P2 P2 P3 P3 P4 Without coding  source retransmits all 4 packets

Random Coding Benefits Multicast
Random combinations P1 P2 8 P1+5 P2+ P3+3 P4 src P3 7 P1+3 P2+6 P3+ P4 P4 dst1 dst2 dst3 P1 P3 P4 P1 P2 P2 P2 P3 P3 P4 Random coding is more efficient than global coordination Without coding  source retransmits all 4 packets With random coding  2 packets are sufficient

难点每个节点应该转发多少数据包？传统的最优路径路由中，一个节点向下一跳节点发送数据包，或者发送成功，或者一直发送直到超过重发次数；
在机会路由中，没有确定的下一跳节点，所有距离目的节点比当前节点近的节点都可以参与转发；现在的问题是：多少次的转发能保证至少一个节点接收到这个数据包？多发了浪费资源，少发了则不够用

一个节点在什么情况下停止发送，并清空数据？
通过网络编码，路由器发送线性组合后的数据包，只要目的节点有数量足够的编码后的数据包，它就能解码得到原始数据包。当目的节点接受到数据后，我们需要尽快停止发送，并清空转发节点中的相关数据；节点如何有效编码？网络编码优化的目的是更好地利用无线介质，但是编码需要节点进行加法和乘法运算，需要优化算法来节省CPU的计算资源。

MORE是针对静态无线mesh网络的协议，如 Roofnet 和community wireless networks；
这些网络中的节点是性能比较好的PCs；基本上不太考虑计算问题；对于无线传感器结点来说，就不是太合适； MORE位于IP层之下， MAC之上，提供可靠的文件传输服务，特别适合于传输中型和大型文件（8个或更多数据包）；对于小文件或者控制数据，采用标准的最优路径路由。

相关术语原始数据包（Native Packet）没有编码的数据包；编码数据包（Coded Packet）原始数据包的随机线性组合；
编码向量（ Code Vector ）将原始数据包通过线性组合得到编码数据包时用到的参数向量；创新数据包（ innovative packet ）和一个节点以前收到的数据包线性独立的数据包；距离目的节点更近根据到目的节点的ETX来比较；新的信息

源节点源节点把文件分割成K个原始数据包；
就是一个batch，长度固定当 MAC做好发送准备，源节点在当前 batch中创建一个由K个原始数据包随机线性组合的数据包，然后将其发送出去；发送节点在每个数据包的头部附加一个MORE包头，其中包含本数据包的编码向量、batch ID、源和目的IP、参与转发的节点列表；

发送节点持续发送当前batch编码后的数据包，直到整个batch被目的节点确认接收到，然后发送者处理下一个batch。
计算转发列表节点周期性地互相Ping，然后估计每个链接的发送概率，通过这个概率来计算到目的节点的ETX： ETX（ expected transmission count ）是将一个数据包发送到目的节点的期望传输次数；发送节点的转发列表中包括那些比自己距离目的节点更近（在ETX指标下）的那些节点，并且根据距离排序；发送节点持续发送当前batch编码后的数据包，直到整个batch被目的节点确认接收到，然后发送者处理下一个batch。收到目的节点对该batch的ACK

转发节点转发节点监听所有的数据传输，当一个节点监听到一个数据包，它检查自己是否在这个数据包的转发列表中；
也就是该节点是不是被允许转发这个数据包；如果是，然后检查这个数据包中是不是一个创新数据包: 包含新的信息，即：和以前接收到的数据包线性独立；可采用简单的代数方法判断（如Gaussian Elimination）；节点保存创新数据包，而忽略非创新数据包；

转发节点如果节点在转发节点列表中，接收到的新数据包会触发节点广播一个编码数据包
这个编码数据包是已经接收到的同一个batch里面的所有数据包的一个随机线性组合；注意：编码数据包的线性组合也同样是原始数据包的一个线性组合；

目的节点对接收到的每一个数据包，目的节点检查它是否是一个创新数据包，丢弃非创新数据包；
这个操作和转发节点类似；一旦目的节点接收到K个创新数据包，就可以通过如下方法得到原始数据包：问题：矩阵运算的运算量大！

ACKs消息比在每个节点上的数据包优先级高；
目的节点解码出整个batch，它马上发一个ACK到源节点，提示源节点可以开始发送下一个batch；（一次数据传输分成多个batch，然后按顺序传输） ACKs消息用最优路径路由来发送：因为MORE不适合于小数据量的数据传输，因此采用传统的最优路径路由；最优路径路由在这里能工作的原因是MORE采用标准的802.11，并且能和最短路径路由共存； ACKs消息比在每个节点上的数据包优先级高；

实际的挑战一个转发节点转发多少个数据包？
传统的最优路径路由中，一个节点向下一跳节点发送数据包，或者发送成功，或者一直发送直到超过重发次数；在机会路由中，没有确定的下一跳节点所有的距离目的节点比当前节点近的节点都可以参与转发，现在的问题是：多少次的转发能保证至少一个节点接收到这个数据包？这是一个仍未解决的问题，以前的工作只考虑一个简单并且理论化的问题，该问题假设流量是平滑的，并且无线网络的带宽是无限的；但是即使在这个假设之下，上述方法也需要解决前面提到的凸优化问题，这个优化问题的约束条件随着听到广播的节点数的指数方式增长；

在本节中，我们提出了该问题的一个基于启发式方法的实际解决方案，该解决方案有如下特点：低复杂度；分布式；
自然地和802.11集成，并保留了空间复用性质；实用性：只需要链接的平均丢失率；没有假设无限的带宽、平滑的流量。

(a) Approach 定义节点i到目的节点d的距离（i的ETX）
把一个数据包从源节点s路由到目的节点d的启发式方法：（类似于ExOR）当一个节点发送一个数据包，在ETX指标下距离目的节点最近的接收到数据包的节点转发数据包；距离目的节点最近的节点转发数据包，减少了期望传输次数，因此提高了总体的吞吐量。

设网络中节点数为N，对于任意两个节点i和j，i < j 表示i比j距离目的节点更近，即i的ETX值比j的小；
设eij表示从i到j发送一个数据包的丢失概率；（这里考虑的是双向的丢失率相同）设zi是在所有节点采用上述启发式路由的情况下，转发节点i把一个数据包从源节点s路由到目的节点 d的期望传输次数（不管之前和之后，反正就是接收到一个数据包后，把它发出去的次数）；假设不同节点的无线数据接收是相互独立的；这在一些文献中已经通过实际测量验证了。

我们注意从源节点发送一个数据包到目的节点；需要计算：在把一个数据包从源节点s发送到目的节点d的过程中，转发节点j必须转发的数据包的数量；
如果转发节点不转发这个数据包呢？虽然在转发列表中，但是 ETX更小的节点已经转发了（这个问题下一页讨论）；节点j从ETX值更高的节点得到的数据包的期望数量为：（不管经历了多少跳，最终都是从ETX值更高的节点发过来的）所有ETX比j小的节点都收不到i发出的数据包的概率

则：节点j必须转发的数据包的期望数量Lj：
对于节点j接收到的每个数据包，j只有在没有ETX值更低的节点接收到该数据包的情况下，才转发该数据包；（如果ETX值更低的节点接收到该数据包，那么就由那个节点转发数据包）这种情况的发生概率是：则：节点j必须转发的数据包的期望数量Lj：注意：因为源节点产生数据包，因此Ls = 1。所有E比j小的节点都收不到i发出的数据包的概率所有路径过来的、必须转发的数据包的总和

现在来考虑节点j必须的转发次数的期望值；节点j应该发送（向ETX更低的节点）每一个数据包，直到一个更低ETX的节点接收到这个数据包；
这个概率就是在ETX值上比节点j低（即距离目的节点更近）的那些节点接收到这个数据包的概率；知道了节点j必须转发的数据包的（期望）数量（Lj），可以得到节点j必须的转发次数的期望值：

(b) Low Complexity 计算每个节点转发一个数据包需要的转发次数的期望值zi的算法；

首先，忽略那些到目的节点的ETX比源节点大的那些节点，因为它们在转发数据包的过程中不起作用；（因为它们距离更远）
然后，我们根据到目的节点的ETX值对节点进行顺序排序，并根据顺序对它们重新编号，即：d = 1，s = n；从源节点开始，设Ln = 1，然后计算Lj和zj，一直计算到目的节点；考虑Lj（因为计算zi的公式里面用到），如果我们想一次就计算出来结果，我们需要对每个i > j计算乘积：

思路：计算所有更低ETX值的节点j的Lj（即：迭代计算），而不是计算和累加节点i的贡献，则我们只需要更新乘积（算法中用P表示）即可；
说明：在计算Lj的公式中，是对所有比j大的节点求和，当j距离目的节点越近，则这些节点越多，因此迭代时从源节点开始计算；上述算法的复杂度是O(N2) ，其中N是网络中的节点数量；这是因为outer loop执行至多n次，每个 iteration of the inner loop 需要O(n)次 operations，其中n是比源节点距离目的节点近（ETX指标下）的节点的数量； N的上界是网络中的节点数量。

停止条件在MORE中，流量是由源节点发出的，转发节点不产生流量，除非它接收到新的数据包；
因此当目的节点接收到足够的数据包后，应该马上停止源节点的数据发送；因此，一旦目的节点接收到第K个创新数据包，在解码整个batch之前，它发出一个 ACK到算节点；为了加快ACK的发送，采用最短路径路由；并且ACK设置为比所有节点上的数据包的优先级都高，并且在每一跳采用本地重传（ local retransmission ）来确保可靠传输；

当发送节点接收到当前batch的ACK消息，它停止转发这个batch中的俄数据包；
如果传输（是否一次传输分为多个batch）还没有完成，发送节点开始发送下一个batch的数据包；转发节点被新到达的数据包触发，只要发送节点停止某个 batch的发送，该节点也停止发送这个batch中的数据包，该batch会超时并被从内存中清除；并且，听到ACK消息的转发节点；最后，到达的新batch会引起转发节点清空那些batch ID比当前batch的ID小的被缓冲的数据包；

多播 MORE中的多播是单播的一个自然扩展； 1 源节点等到所有的目的节点都接收到当前batch后，再开始进行下一个batch；
2 节点列表和他们的TX_credits是不同的，源节点计算TX_credits and the forwarder list for hypothetical unicast flows from itself to each of the destinations in the multicast group. The forwarder list of the multicast flow is the union of the forwarders of the unicast flows. The TX credit of each forwarder is computed using Eq. (3) where each zi is the maximum of what forwarder i gets in each of the hypothetical unicast flows.

多播 3 对于多播，转发节点的TX_credit具有动态特性，特别的，当持续处理当前batch时，越来越多的目的节点可以解码，则有些转发节点会暂时不被使用；这些转发节点是：转发节点列表中的，并且其目的节点已经把 batch解码。因此，无论什么时候，只要目的节点对为当前batch发出确认接收消息ACK，源节点重新计算转发节点的 TX_credits，作为最大TX_credit，taken over only the hypothetical unicast flows to the destinations that have not yet decoded the batch. 听到数据包中新TX_credit的转发节点相应地更新它们的信息；

GreedyCode Inter-flow netwrok coding Intra-flow netwrok coding Xor编码
需要链路质量好 Intra-flow netwrok coding 线性编码对本flow编码更加适用于链路质量不好的情况

Background Greedy Strategy for Network Coding Based Reliable Broadcast in Wireless Mesh Networks, Globecom 2012 Reliable broadcast Dissemination of identical information from one source node to all the other nodes in the network. 传输中的差错一般都是由噪声引起的，噪声有随机热噪声和冲击噪声。随机噪声：信道固有的，持续存在的；冲击噪声：外界特定的短暂原因造成的；其中冲击噪声是传输差错的主要原因。

Background Traditional solutions Automatic Repeat reQuest (ARQ)
接收端检测出有差错时，就设法通知发送端重发，直到正确的码字收到为止； Forward Error Correction (FEC) 接收端不但能发现差错，而且能确定二进制码元发生错误的位置，从而加以纠正。优点：不需要反向信道、不需要重传、快。缺点：冗余信息需更多带宽。 Combinations of ARQ and FEC

Motivation Weakness of Traditional solutions
treat wireless links as point-to-point cannot take advantage of the broadcast nature of wireless transmissions leads to duplicate transmissions.

Related Works Network coding
The core notion of network coding is to allow and encourage mixing of data at intermediate network nodes. Widely recognized as a promising approach to improve the performance of wireless networks. Reliable broadcast based on network coding MORE Pacifier: can be regard as an upgrade version of MORE R-Code AdapCode: design for WSN

最短路径树最小生成树

GreedyCode Insight Previous works
do not consider the specific characteristic of reliable broadcast do not fully exploit the broadcast nature of wireless transmissions do not fully exploit the opportunistic reception The construction of tree structure will ignore some wireless links

Basic idea Does not adopt tree structure
try to take full advantage of all wireless links; Multicast graph instead of multicast tree Dynamically select the forwarders Base on the current reception status of the destinations; Only the nodes with the maximum transmission efficiency will be activated to broadcast encoded packets to the neighboring nodes. 用多播图代替多播树

Forwarder Selection

Workflow

Source Rate Limiting An activated node is the only one node which has the largest OBT value among its neighborhood; When it transmits data packets, all of its neighbors just listen and there will be no transmission collisions; If a neighbor get whole batch, this neighbor may become a new sender, so our greedy strategy can achieve the source rate limiting adaptively.

Performance Evaluation
We use NS2 simulator in our simulations. The network consists of a 4 multiply 4 grid of static odes, where the grid size is equal to 100m. The source is fixed to be node 0 and the batch size is set to 8, 16, 32 and 64, respectively.

Conclusion Maximize throughput greedily Design a new metric
Forwarders with the maximum transmission efficiency is activated. Design a new metric One-hop Broadcast Throughput (OBT) Measure the transmission efficiency of a node. Distributed realized GreedyCode only needs the information of its one-hop neighbors.

网络编码的安全问题熵攻击拜占庭攻击污染攻击伪造一个非创新包（non-innovative packet）并发送到网络中；
不会破坏源数据包和附加编码向量之间的线性代数约束条件，但会降低目的节点成功解码率，因而影响网络性能；拜占庭攻击攻击节点作为一个背叛节点隐藏在网络中，删除、修改网络中传输的数据包，也可以注入错误的数据包；污染攻击向网络中注入污染信息，修改或者重放在网络中传播的消息；如果污染信息被发送者编码到合法消息中，那么发送者发出的消息将会被污染，如果没有采取措施，污染包会迅速在下游网络中扩散，最终直接导致目的节点无法正确解码原消息。

图着色问题来源：四色问题 19世纪50年代，英国学者提出了4色猜想：
任何一张地图都可以最多用四种颜色着色，使得具有共同边界的国家染上不同的颜色；简称为地图是4－可着色的；过了100多年，这个问题才由美国学者在计算机上证明，这就是著名的四色定理。这里具有共同边界是指有一整段共同边界

问题来源由地图的着色问题引申而来问题描述用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。
如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。

问题来源

图的着色通常所说的着色问题是指下述两类问题：图的边着色问题图的顶点着色问题
给定无环图G=(V,E)，用m种颜色为图中的每条边着色，要求每条边着一种颜色，并使相邻两条边有着不同的颜色。图的顶点着色问题给定无向图G=(V,E)，用m种颜色为图中的每个顶点着色，要求每个顶点着一种颜色，并使相邻两顶点之间有着不同的颜色。

用1、2、3、4代表四种颜色一张地图可看成是一个平面图G 作G的对偶图G* 对平面图地图G的域的着色可看成是G的对偶图G*的结点的着色。

顶点着色－基本概念独立集对图G=(V,E)，设S是V的一个子集，若其中任意两个顶点在G中均不相邻，则称S为G的一个独立集。极大独立集
如果一个独立集不是任何一个独立集的子集，那么称这个独立集是一个极大独立集。可以染同样的颜色

如果G不包含适合|S‘|＞|S|的独立集S’，则称S为G的最大独立集；（S’节点数量更多，不一定完全包含S）
最大独立集一定是极大独立集，但是极大独立集不一定是最大的独立集。最大独立集不一定唯一，比如{v3,v4,v6}

顶点着色－基本概念极大覆盖设K是G的一个独立集，并且对于V-K的任一顶点v，K+v都不是G的独立集，则称K是G的一个极大覆盖。
尽量少的点覆盖一个区域，每个节点覆盖范围大注意：定义中的K不一定是最大独立集。例：K={d1}是独立集，加上任意一个其它节点后，都不是独立集；而K也不是最大独立集，因为最大独立集有3个节点，比如{d2,d4,d6} ，

顶点着色－基本概念极小覆盖极大独立集的补集称为极小覆盖；
V的子集K是G的极小覆盖当且仅当：对于每个顶点v，或者v属于K，或者v的所有邻点属于K（但两者不同时成立）。 v在与之互补的那个独立集中 K={d1,d3,d5,d7}是极小覆盖极大独立集{d2,d4,d6}的补集

顶点着色－基本概念 K可着色： G的一个k顶点着色是指k种颜色1,2,…,k对于G各顶点的一个分配，如果任意两个相邻顶点都分配到不同的颜色，则称着色是正常的；即：无环图G的一个正常k顶点着色是把V分成k个（可能有空的）独立集的一个分类(V1,V2,…,Vk)；当G有一个正常k顶点着色时，就称G是k顶点可着色的。

顶点着色－基本概念 G的色数X(G) 显然有：指G为k可着色的k的最小值，若X(G)=k，则称G是k色的；
（1）两两子集中的顶点不同；（2）子集中的两两顶点不相邻。显然有：若G为平凡图，则X(G)=1 若G为二分图，则X(G)=2 对任意图G，有X(G) ≤Δ+1（Δ表示为顶点数最大值） v1 v2 v3 v4 v5 X(Kn)=n

顶点着色－求顶色数的算法设计思路：由“每个同色顶点集合中的两两顶点不相邻”可以看出，同色顶点集实际上是一个独立集；
当我们用第1种颜色上色时，为了尽可能扩大颜色1的顶点个数，逼近所用颜色数最少的目的，事实上就是找出图G的一个极大独立集并给它涂上颜色1；用第2种颜色上色时，同样选择另一个极大独立集涂色，...，当所有顶点涂色完毕，所用的颜色数即为所选的极大独立集的个数；当然，上述颜色数未必就是X(G)，而且其和能够含所有顶点的极大独立集个数未必唯一；于是我们必须从一切若干极大独立集的和含所有顶点的子集中，挑选所用极大独立集个数最小者，其个数即为所用的颜色数X(G)。 Step1：求G图的所有极大独立集； Step2：求出一切若干极大独立集的和含所有顶点的子集； Step3：从中挑选所用极大独立集个数最小值，即为X(G)。

图着色问题的应用－安排考试问题问题描述：分析：
学校共有n门功课需要进行期末考试，因为不少学生不止选修一门课，所以不能把一个同学选修的两门课安排在同一场次进行考试；问：该学校的期末考试最少需要多少场次才能完成？分析：可以建模为着色问题；节点是什么？边是什么？问题是什么？

图着色问题的应用－安排考试问题问题建模：
以每门功课为一个顶点，当且仅当两门功课被同一个学生选修时，在相应两个顶点之间连一条边，得到一个图G；问题：将n门功课划分成k个子集U1,U2,…,UK，两两子集的功课都不相同；即：顶点着色问题。说明每个子集Ui（1≤i≤k）的顶点两两子集不相邻，即子集内的任意两门功课都不能被一个学生选修。满足这种要求划分的子集数K必须最少，即不能划分成k-1个子集。对每个子集内的顶点涂一种颜色：同色顶点对应的课程安排在同一场次考试，颜色数即为学期考试所需要的最少场次数。

更加实际的问题：论文答辩分组某专业硕士研究生毕业答辩，需要分成多个小组进行，参加答辩的老师由该专业的导师组成，要满足如下条件：
每个答辩小组安排学生数6-8人；每个答辩小组4位老师，必须有一位正教授；导师不能参加自己学生的答辩；导师之间不能互审（即A导师的学生被B导师评审的话，则B导师的学生不能被A导师评审）；导师不是每天都有空。更进一步：有的导师分属于多个专业，需要跟其它专业进行协调。

图着色问题的应用－交通管理系统交通信号灯管理系统：思路：某交叉路口有A、B、C、D、E五条街道，设计一个交通信号灯管理系统。
单行道思路：对车辆的可能行驶方向分组，分组要求是使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。将通行方向作为结点，如果某些通行方向不能同时进行，则在相应的结点间连一条线；问题(图着色问题)：将结点分组，使得相邻结点不在同一组里。

图着色问题的应用－交通管理系统分析：首先考虑可以通行的方向红：AB，AC，AD，BA，DC，ED 绿：DA，DB 黄：EB，EC，EA
蓝：BC，BD

图着色问题的应用－交通管理系统接下来的通行方向为结点，考虑结点分组：

图着色问题的应用－变址寄存器问题描述：问题建模：
在编译器中，当把频繁使用的变量暂时保存在CPU的变址寄存器中，而不是保存在常现内存中时，可加速循环程序的执行；对于给定的循环来说，最少需要多少个变址寄存器？问题建模：设图的每个顶点表示循环中的一个变量，若在循环执行期间两个顶点所表示的变量必须同时保存在变址寄存器，则连一条边，即不能用一个寄存器保存这两个变量，则该图的色数就是变址寄存器的数目；因为当表示变量的顶点在图中相邻，就必须给这些变量分配不同的寄存器。

无线mesh网络的信道分配策略多信道例如：因为无线情况下，相同信道会冲突，为了提高网络性能，因此需要研究信道分配问题。
无线mesh网提供低成本的互联接入方案，并且覆盖范围大，为了提供无线mesh网络的容量，可以采用多信道多接入技术（multi-radio multi-channel）例如： 802.11b/g提供三个正交信道(无重叠) 802.11a提供12个正交信道因为无线情况下，相同信道会冲突，为了提高网络性能，因此需要研究信道分配问题。其实就是如何尽量充分使用网络资源

多跳网络中的信道分配问题：信道分配问题的约束： 1.使所有信道上的干扰降到最低，提高空间复用能力；流内干扰、流间干扰
2.确保无线mesh网络的稳定性信道分配问题的约束：可用信道数是有限的；路由器上配备的接口数量固定并且一般来说小于信道数目；互相通信的两个节点，必须有一对接口，并且采用相同的信道；每个信道的容量是有限的；

单信道单接口任何时候只有一条链路工作（不考虑multicast） 4个信道，最强连接性 2个接口/每结点不管如何信道分配，都不能让这5条链路同时工作 4个信道，最小干扰 2个接口/每结点可实现同时工作

连接图 1.假设各个无线结点都分布在一个平面上 2.每个结点配置一个或多个全向射频天线，并且射频具有覆盖范围和干扰范围；
一般来说，干扰范围 > 覆盖范围 3.如果一个接收结点处于另外的两个发射结点都可覆盖的位置，则数据包的传输在该节点处会发生干扰；

冲突图：描述各条链路之间的冲突情况；即每个连接图上的边是冲突图上的一个点；如果连接图上的两个链路会发生冲突，则在冲突图上有一条边；
冲突图，即单接口多信道

多射频链路和冲突图 1.在多射频链路图中，不是考虑结点的覆盖范围，而是考虑接口（射频端）的的覆盖范围；
如前面图中，给Z配备两个射频接口，而其余结点都是一个，则所射频连接图为：

信道分配约束可看作一个有约束的着色问题 1.信道总数固定； 2.路由器上配备的radio固定数量；
4.每个信道容量是固定的通信量不能超过这个值。可看作一个有约束的着色问题有可能无解，则找干扰最少的策略。

其它方法：信道分配方案 1.基于树的方法 2.理论推导方法：固定方案：信道分配方案是不变化的
分层思想 2.理论推导方法：线性规划，可以实现全局最优，但很难分布式实现信道分配方案固定方案：信道分配方案是不变化的动态方案：动态调整信道分配方案以提高网络的性能混合方案：一部分射频端采用固定方案一部分采用的动态方案

蜂窝中的信道分配如果两个小区距离足够远，即相互不会发生干扰，则可是用相同信道共用了7个信道

频率复用 Frequency Reuse 基站控制着收发器的发射功率频率复用：发射功率要足够大，以覆盖整个小区；
发射功率又要足够小，以避免影响邻近的蜂窝区；邻近的蜂窝被分配给不同的频率，以免干扰或串音。频率复用：在彼此相距某些距离的蜂窝区重复使用相同的频率；核心问题在于：为了使两个使用相同频率的小区不互相干扰而需要在这两个小区之间插入几个小区。相同的频率通道在相距较远的小区内可以被复用=〉提高资源利用率

频率复用 Frequency Reuse 考虑一个共有S个可用的双向信道的蜂窝系统。如果每个小区都分配k 个信道（k≤S）；
并且S 个信道在N 个小区中分为各不相同的、各自独立的信道组，而且每个信道组有相同的信道数目，那么可用无线信道的总数为：S = kN；共同使用全部可用频率的N 个小区，也即区群，在整个系统中共复制了M 次，则双向信道的总数C，可以作为容量的一个度量：C = MkN = MS；因子N 为区群的大小，也叫做复用因子。区群内的频率不复用；整个系统内，每个频率被用了M次。

频率复用 Frequency Reuse

最经典的“无字证明” 一些定理的直观理解虽然毫无逻辑可言，完全算不上是数学证明，但这些精巧而欢乐的视角，依然让数学家们如痴如醉；
1989 年的《美国数学月刊》（American Mathematical Monthly）上有一个貌似非常困难的数学问题：由一个个小三角形组成的正六边形棋盘，现在请你用右边的三种（仅朝向不同的）菱形把整个棋盘全部摆满（图中只摆了其中一部分），证明当你摆满整个棋盘后，你所使用的每种菱形数量一定相同。

“证明”：把每种菱形涂上一种颜色，整个图形瞬间有了立体感，看上去就成了一个个立方体在墙角堆叠起来的样子。三种菱形分别是从左侧、右侧、上方观察整个立体图形能够看到的面，它们的数目显然应该相等。
严格地说，这个本来不算数学证明的。但它把一个纯组合数学问题和立体空间图形结合在了一起，实在让人拍案叫绝。因此，这个问题及其鬼斧神工般的“证明”流传甚广，深受数学家们的喜爱。

超图(Hypergraph) 简单图一条边只能连接两个顶点

超图图的一条边（edge）只能和两个顶点关联，超图的边（超边，hyperedge）可以和任意个数的顶点连接。

为什么引入超图(一个例子) 顶点代表文章，每条边代表两个顶点（文章）享有同一个作者
简单图版本丢失了“同一作者的多篇文章”这一信息，而超图版本则保存了这一信息。

为什么引入超图(一个例子) 假设有三篇文章v1、v2、v3，它们的作者分别是：v1:A,B、 v2:B,C、v3:C,D

超图的表示关键是超边如何表示：用一个点集来表示；
令V是一个顶点集合V={v1, v2, v3, v4,v5,v6,v7}；则每一条超边都是V的一个子集； E = {e1,e2,e3,e4} = {{v1,v2,v3},{v2,v3}, {v3,v5,v6},{v4}}

超图的矩阵表达顶点的度d(v) 超边的度超图的矩阵表达

超图的邻接矩阵超图的邻接矩阵A()，A(i,i)为0，A(i,j)为vi和vj共享的所有超边的权值和。
其中W是一对角阵，对角线元素为各超边的权值，A是超图的邻接矩阵； Dv为一对角阵，对角线元素为各顶点的度d(v)。

超图的应用无线网络多播（multicast）

图论补充内容.

Similar presentations

Presentation on theme: "图论补充内容."— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

图论补充内容.

Similar presentations

Presentation on theme: "图论补充内容."— Presentation transcript:

Similar presentations

About project

反馈