工程硕士班《通信网理论基础》(2)

通信网理论基础第三部分图论基础与应用基本概念图G(V,E)由两个集合加以定义:–顶点(或节点)集合V={v1,v2,v3….vn};–边集合E={e1,e2,e3……em};G={V,E}边由一对直接关连的顶点的组合定义–如果:(i,j)E,则顶点i和j称为相邻的–顶点的数目称为图的“阶”;边的数目称为图的“尺寸”;许多图的算法的运行时间与图的“阶”和“尺寸”相关图的一个例子图的邻接矩阵邻接矩阵是用数学方式来表示图顶点编号:1,2,3,…,|V||V|x|V|邻接矩阵A=(ai,j)定义为:ai,j=1if(i,j)E(ij是图的一条边)0otherwise对于边没有方向性的图(即边的两顶点的顺序不影响边的性质),邻接矩阵A是对称矩阵.邻接矩阵一例Terminology关联同一对顶点的边称为:平行边关联同一顶点的边称为:环既无平行边,又无环的图称为:简单图顶点i到顶点j的路径是:顶点和边的交替序列–起于i,止于j;–每条边只与序列中直接在它前面和直接在它后面的顶点相连–简单路径:顶点和边在序列中只出现一次的路径在简单图中,简单路径可以由顶点序列来定义–每个顶点与序列中在其前面和后面的顶点相邻–序列中没有重复的顶点简单路径(1)由V1到V6(不完全)–V1,V2,V3,V4,V5,V6–V1,V2,V3,V5,V6–V1,V2,V3,V6–V1,V2,V4,V3,V5,V6–V1,V2,V4,V5,V6–V1,V3,V2,V4,V5,V6–V1,V3,V6–V1,V4,V3,V6总共14条(其余的请自行列出)简单图(2)两顶点间的所有路径中有一条最短路径,如:V1,V3,V6顶点间的距离是所有路径中边数最少的路径的边的数目回路是起于和止于同一顶点的路径–例如:.V1,V3,V4,V1有向图边有方向性的图有向图G(V,E)的边由一对顶点的有序组合来定义代表边的线段用箭头表示其方向允许存在平行边,只要它们的方向相反便于用图表示通信网络–每条有向边表达一个方向上的数据流仍然可用邻接矩阵表示–除非每对相邻的顶点用平行边连接,否则邻接矩阵是不对称的加权图或加权有向图每条边有一与之关联的数(权值w)-------便于说明路由算法邻接矩阵定义为:ai,j=wi,jif(i,j)E0otherwisewi,j是与边(i,j)关联的权值路径长度是权值之和最短距离路径不一定是长度最短路径(见下面两张PPT)加权图与邻接矩阵V1至V6的路径距离和路径长度路径距离长度V1,V2,V3,V4,V5,V6511V1,V2,V3,V5,V648V1,V2,V3,V6310V1,V2,V4,V3,V5,V6510V1,V2,V4,V5,V647V1,V3,V2,V4,V5,V6516V1,V3,V6210V1,V4,V5,V634树树是图的子集以下几项定义是等效的:*树是一种简单图,顶点i和j之间只有一条简单路径*N个顶点的简单图如果只有N-1条边,没有回路*N个顶点的简单图如果只有N-1条边,而且是连通的可以指定一个顶点为“根”–根通常画在上部–与根邻接的顶点画在下一层这些顶点可以到达树根,路径距离为1树中顶点的等级关系每个顶点(除根外)有一个父顶点–靠根一边的邻接顶点每个顶点有0个或几个子顶点–离根远的邻接顶点–没有子顶点的顶点称为叶层次等级–直接在根下面的顶点是第一层–第一层顶点的子顶点是第二层树的例子图从图G中选择一些边和顶点构成G的子图–每条被选上的边的两个关联顶点必须同时选上图G’(E’,V’)是图G(E,V)的子图,如果:–V’V,E’E并且–对每一条E’中的边e’.如果e’关联v’andw’,则v’,w’V’生成树图G的子图T是一颗生成树,如果:–T是树包含G的所有顶点从图G中删去一些边,使所有的回路不复存在,但保持图的连通性:图G的生成树通常并不唯一生成树的例子生成树的“先广搜索”算法将顶点划分成不同的层次在处理下一层之前,先处理完本层的所有顶点从任一顶点x开始指定它为0层–所有它的邻接顶点属于1层–设Vi1,Vi2,Vi3,…Vij,是i层的顶点–所有Vi1的邻接顶点中不属于1,2,…,i层的顶点指定为(i+1)层–所有Vi2的邻接顶点中不属于1,2,3,…,i,(i+1)层的顶点也指定为(i+1)层–直到所有顶点被处理完毕例选择顶点顺序–如:V1,V2,V3,V4,V5,V6选择“根”–例如V1现在树T只包含一个顶点V1,不含边在树上增加边(V1,x)和顶点x,但不要形成回路:将边(V1,V2),(V1,V3),(V1,V4)和顶点V1,V2,V3加入到树中,这是第一层在第一层的顶点上按序重复上述过程,得到第二层–是否所有顶点都处理完?–如果没有,在第二层的顶点上重复处理过程,得到第三层….…上例的图示AvoidingLoopsLAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)AvoidingLoopsLAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)SpanningTreeAlgorithm1.Selectarootbridgeamongallthebridges.•rootbridge=thelowestbridgeID.2.Determinetherootportforeachbridgeexcepttherootbridge•rootport=portwiththeleast-costpathtotherootbridge3.SelectadesignatedbridgeforeachLAN•designatedbridge=bridgehasleast-costpathfromtheLANtotherootbridge.•designatedportconnectstheLANandthedesignatedbridge4.Allrootportsandalldesignatedportsareplacedintoa“forwarding”state.Thesearetheonlyportsthatareallowedtoforwardframes.Theotherportsareplacedintoa“blocking”state.LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)(1)(1)(1)(2)(2)(2)(2)(3)LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)(1)(1)(1)(2)(2)(2)(2)(3)Bridge1selectedasrootbridgeLAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)(1)(1)(1)(2)(2)(2)(2)(3)RootportselectedforeverybridgeexceptrootportRRRR最短距离路径的距离BFS算法可以得到从根顶点s到所有其他顶点的最短距离路径和距离δ(s,v)任何从s到v的路径中BFS给出的路径是距离最短的,即该路径边数之和最小。最短长度路径分组交换,帧中继,ATM等网络可以看作一张图–每个节点是图中一顶点–每一链路是一对平行边对于互联网(Internet或intranet)–每个路由器是一个顶点–如路由器直接相连,双向连接相当于一对平行边–如多于两个路由器,则由多对平行边构成表示网络的图–一对边连接一对路由器为将分组由源送到目的,需要路由决策–等效于在图上找出路径路由决策基于最小代价–最少跳数(hop)每条边(一跳)的权重为1相当于最短距离路径–或者,每跳有一相关联的代价(见下一PPT)–路径的代价是路径中各链路的代价之和–需要找出最小代价路径相当于加权图中的最小长度路径一跳的代价反比于路径的容量正比于当前的负荷链路的货币价值几种因素的组合在不同方向上的代价可能不同Dijkstra算法(1)–定义N=网络顶点的集合s=源顶点(起始点)T=到目前为止算法已经用到的顶点的临时集合Tree=T中顶点组成的生成树,它包括从s到T中每个顶点的最小代价路径上的边w(i,j)=从顶点i到顶点j的链路代价,–w(i,i)=0–w(i,j)=ifi,j不直接连接–w(i,j)0ifi,j直接连接L(n)=当前知道的从s到n的最小代价路径的代价cost–运算结束是它就是从s到n的最小代价路径的代价Dijkstra算法(2)–步骤1.初始化a.T=Tree={s}–临时顶点集合中暂时只含源顶点b.L(n)=w(s,n)forns;到邻点的初始路径代价就是链路代价2.取下一个顶点a.找xT使L(x)=minL(j),jTb.将x加入到T和Tree中c.将关联x,且使L(x)成为最小代价的边加入到Tree中它是路径的最后一跳3.更新最小代价路径a.L(n)=min[L(n),L(x)+w(x,n)]nT如果后一项最小,从s到n的路径就是从s到x的路径与从x到n的边的连接Chapter14OverviewofGraphTheoryandLeast-CostPaths34Dijkstra算法原理图示TSNXnw(x,n)L(n)L(x)已算出最短路径的点的集合找xT使L(x)=minL(j),jTx→TL(n)=min[L(n),L(x)+w(x,n)]nT所以，S需要知道w(x,n)-----各点与其邻点间直接相连链路的代价因而需要与所有其他各点交换路由信息某点（s)已知网络中其他各点到其邻点的链路的代价值w(x,n),计算S到其他各点的最短路径Dijkstra’s算法(3)–说明当所有顶点都加入到T以后,算法结束需要|V|次迭代结束时–L(x)是s到x的最小代价路径的代价值–Tree是原图的一颗最小生成树定义了从s到其他顶点的最小代价路径每次迭代有一个新的顶点加入到T中,运行时间是|V|2量级Dijkstra算法用于例图Bellman-Ford算法(1)–定义s=源顶点(起始点)w(i,j)=从顶点i到顶点j的链路的代价值–w(i,i)=0–w(i,j)=如i,j不直接相连–w(i,j)0如i,j直接连接h=在算法的当前步骤中路径的最大链路数Lh(n)=从顶点s到n的最小代价路径的代价,限制条件是路径的链路数不超过hBellman-Ford算法(2)–步骤1.初始化a.L0(n)=nsb.Lh(s)=0hc.更新d.对每个相继的h0i.对每个ns,计算:Lh+1(n)=min[Lh(j)+w(j,n)],jii.找到实现最小值的顶点jiii.,将n与该前趋顶点j相连,iv.删除n与此前计算得到与j不同的前趋顶点的连接,v.从s到n的路径以j到n的链路结束Bellman-FordAlgorithm(3)–说明结果与Dijkstra算法的结果相同运行时间是|V|x|E|的量级Chapter14OverviewofGraphTheoryandLeast-CostPaths40Bellmin-Ford算法原理图示Sn已知n与其邻点间链路的代价值w(j,n);j到s的最短路径的代价值L(j);找n到s的最短路径；ji.对每个ns,计算:Lh+1(n)=min[Lh(j)+w(j,n)],jw(j,n)（已知，因为与n直连）L(n)L(j)n点在计算时需知其邻接点的L(j)—当前估计的到S的最短路径的长度，和它到自己的邻点的链路的代价值，所以为了求出到所有点的最短路径，每点需与其邻接点交换各自到所有其他点的最短路径长度的当前估计值Bellman-Ford算法用于例图Dijkstra和Bellman-Ford算法的运算结果比较所需要的信息–Bellman-Ford算法顶点n处的计算需要知道到所有邻接点的链路的代价,以及从源点到这些点的路径的总代价e每个顶点需要维持一个到网络中所有其他顶点的路径及其代价的表与其直接邻接顶点交换上述