图论及其应用论文

《图论及其应用论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

论在多播生成树快速算法的应用摘要：为了有效地支持多播通信路由（路径）选择是一个关键问题。路由选择负责对源与目的结点间的多条可行路径根据某种目标加以选择、例如网络资源消耗最低化就是路由选择的重要目标。解决多播路由的方法涉及到〃树"的构造，如果能构造出合理的多播树,就可以在满足业务需要的前提下，尽量少占用网络资源。本篇论文以图论为基础，主要探讨和研究了多播生成树问题。主要探讨了单约束的单树多播这种情况，介绍了经典的Dijkstra算法，并在此基础上提出了动态最短路径树算法。关键词:图论路由最短路径多播树Dijkstra算法1•多播生成树问题的提出随着Internet的爆炸性发展，在Internet上产生了许多新的应用，其中有很多是高带宽的多媒体应用,这就带来了带宽的急剧消耗和网络拥挤问题。为了缓解这一问题，人们提岀了IP多播技术。多播技术是一种允许一个或多个发送者（多播源）发送单一的数据包到多个接收者的网络技术。该技术有助于缓解当前Internet的业务量而导致的拥塞问题。为了有效地支持多播通信，路由（或路径）选择是一个需要讨论的关键问题。路由选择负责对源与目的结点间的多条可行路径根据某种目标加以选择。路由选择算法是计算机网络中的一个重要硏究课题，它直接关系到网络效率、传输延迟和吞吐量等通信网络的主要技术性能指标。路由选择算法的设计一般包括以下内容:首先对一个网络的链路进行准确描述，定义链路代价函数（一般可由信道容量、信道利用率或报文延迟时间这几种因素确定），计算最短路径,建立路由选择表或路由数据库。根据网络拓扑和子网款式选择适当算法，并设计出实现算法的过程，模拟测试和运行。其中计算最短路径是整个设计过程中较为关键的一环。多播路由选择要保证实现的目标是，数据能够到达所有的接收者。同时，在整个通信网络的任何一条链路上数据最多传送一次。在一条链路上是否传输数据依赖于此链路上是否有该数据的接收者。多播之所以能节约带宽,就是因为在网络的任何一条链路上数据最多传送一次。要实现这个目标，多播的传输就不能像单播一样点到点地传输，而要采用树的传输方式。一般采用多播生成树来描述多播数据包在网络中经过的路径。将多播路径基于树结构有两点理由： (1)信息可以沿着树枝并行地传送至怀同的目的地；(2)仅在树叉处复制信息，传送信息的拷贝数最小，从而使网络流量最｛氐，占用的网络资源最少。多播树的质量评价一般有两个尺度，最短路径和最小代价。最短路径和最小代价可以被表述为不同的函数，如最小代价可以表述为使用缓冲区的数量、占用信道的所需交纳的费用，包丢失率等;最短路径可以表述为传输、处理、排队时延的结合。多播生成树算法沿着优化这两个尺度(最短路径和最小代价)的方向,己经有了很大的发展。2.多播生成树问题的图论基础2・1•树给定一个图G=(V,E),如果它不含任何回路，我们就叫它是林，如果G又是连通的，即这个林只有一个连通支，就称它是树。树是图论中最重要的概念之一，在自然和社会科学中的许多领域都有广泛的应用。定义1〜不含田可回路的连通图称为树，用T表示。T中的边称为树枝，度为1的结点称为树叶。树的每条边都不会属刊北可回路。这样的边叫割边。定义2设e是图G的一条边,若G、=G-e比G的连通支数增加，则称e是G的一条割边。显然图G删去割边=0(u,v)之后結点u和v分属于不同的连通支。定理1e=(u,v)是割边，当且仅当e不属于G的田可回路。定理2设T是结点数为n>2的树，则下列性质等价：1.T连通且无回路。2T连通且每条边都是割边。3.T连通且有条边。4.T有n-1条边且无回路。5.T的任意两结点间有唯一道路。6.T无回路，但在任两结点间加上一条边后恰有一个回路. 定理3树T中一定存在树叶结点。定义3如果T是图G的支撑子图，而且又是一棵树，则称r是G的一棵支撑树，或称生成树，又简称为G的树。2・2・多播网络模型为简化对问题的讨论，我们通常将一个通信网络表示为一个带权无向图G=(V,E,C),其中V代表网络中结点(Node)的集合;E是一组边(edge)的集合,|V|和|E|分别代表结点和边的数目。每条边用对应的两个结点u,v来表示:(u,v)—对结点对应的两条边口(")和(3)费用相等，即这两条边对称;C是各边对应费用(cost)的集合。图G中结点v的度(degree)是指与v关联的边的条数。在多播网络中数据包由源结点seV生成,并发送给所有的多播组成员，多播组成员结点他称为端结点)的集合McV。由无向图G=(V,E,C)中生成一棵有向树T=(%,址)若满足以下三个条件则称其为多播生成树：^)VtQVfEtQEo2)源结点S到每一个端结点都有通路，并且S的入度为0。，树中其余结点的入度为1。3)端结点的出度大于或等于0,其余结点的出度均大于或等于1。一棵多播树T的总费用是指树T中各边费用之和。定义1最小代价多播生成树是所有生成树中，总费用最小的生成树。多播树中源结点S和端结点〃以外的结点称为Steiner结点。定义2最短路径:结点u,vUV之间的最短路径是指从u到v代价最小的路径，用P(u,v)表示。结点u到树的最短路径是指该结点到树的各结点最短路径中代价最小的那条，该路径用PS(u,v)表示(uwV-6%),其中结点v被称为结点u的最小接应结点。结点到树的最短路径也被称为树到结点的最短路径，结点到树最短路径的代价称为结点到树的最小距离。定义3最短路径(最小时延)多播生成树是所有生成树中，源结点:到所有端结点的路径都是最短路径的生成树。即在给定的带权无向图G=(V,E,C)中,G的关于结点s的最短路径树是具有以下性质的G的一个子图T=(WC)。1V=K2T是连通且无回路的。结点s到T中的其余结点(即V・s)的路径都是带权无向图G中的最短路径。 定义4路径结点:结点u（uGV-%）到生成树的最短路径上，结点与最小接应结点之间的Steiner结点称为该结点的路径结点。定义5卫星结点:在生成树中,7端结点与邻近端结点之间的Steiner结点称为该端结点的卫星结点。3•多播生成树基本算法构建最短路径树和最小生成树在图论中最基本的算法是Dijkstra算法和Prim算法，这两个经典算法几乎是所有其他单约束的单树多播算法的源泉和理论基础，本文主要介绍了Dijkstra算法。Dijkstra算法给定个一个带权无向图G=（V,E,C）,源结点为s,构建最短路径树可以采用图论中的Dijkstra算法实现。Dijkstra是解决关于带权图的最短路径问题的一种贪心算法,它要一个个地找出从源结点⑸出发到所有其他结点的最短路径。Dijkstra算法的本质特征是能够确定路径）11游，按照加权长度顺序首先找出最短路径，直至最后找出从源结点到所有结点的最短路径中最长的那一条最短路径。首先，引进一个辅助向量D,它的每个分量D[i]表示当前所找到的从源点s到每个终点巩的最短路径的长度。它的初态为:若从s到可有弧，则D[i]为弧上的权值;否则置D[i]为8。显然长度为D[j]=min{D[i]|vzGV]的路径就是从s出发长度最短的一条最短路径。此路径为（s,可）。假设改次最短路径的终点是4，则可想而知，这条路径或者是（S,4）,或者是（S,切玫）。它的长度或者是从s到玖的弧上的权值,或者是D[H和从巧到4的弧上的权值之和。一般情况下，假设T为已求得最短路径的终点的集合，则可证明:下一条最短路径（设其终点为x）或者是弧（v,x）,或者是中间只经过T中的顶点而最后到达顶点x的路径。在一般情况下，下一条长度次短的最短路径的是D[j]=min{D[i]|VjeV-T}其中,D[i]或者是弧（s,q）上的权值,或者是D[k]（欣6T）和弧（％可）上的权值之和。根据以上分析，可以得到如下描述的算法:(1)设用带权的邻接矩阵arcs来表示带权图,arcs[i][j]表示弧(族，可)上的权值。若(珈可)不存在,则置arcs[i]U]为8(在计算机上可用允许的最大值代替)。T为已找到从s岀发的最短路径的终点的集合，它的初始状态为空集。那么，从s出发到图上其余各顶点(终点)v,.可能达到的最短路径长 度的初值为:D[i]=arcs{LocateVex(G,v)}[i]VtGV(2)选择耳・，使得D[j]=min{D[i]|VieV-T}巧就是当前求得的一条从s岀发的最短路径的终点。令T=Tu{j}(1)修改从s岀发到集合V-T上任一顶点珂可达的最短路径的长度。如果D[j]+arcs[/][k]arcs[T2{J]T2j]+DisT^j]则DisT2[/]>arcsT2j]T2j+DisT^j],DisT2[j]是集合工中任一点，重复执行第7步。Dijkstra算法的时间复杂度是O(n2),DMDT算法的时间复杂度为O(nk),k为生成树中可能改变的结点个数，在最坏情况下,k=n・1，但在实际应用中，最坏情况几乎不可能岀现，一般情况下,k远远小于n,相比Dijkstra算法,DMDT算法只是需要增加一个长度为w的数组（w为生成树的结点数）。由此可见,相对于DMDT算法所取得的计算效率提高来说，所付出的存储开销是很小的。结束语IP多播是一种为了优化使用网络资源而产生的技术，有着广泛的应用前景。本文针对动态变 化的网络环境提出了一种快速的动态最短路径算法DMNT,该算法在网络环境发生变化的情况下,最大限度的利用了已经存在的最短路径树，获得了较高的计算效率。该算法的提出为最短路径树的动态计算提供了一种新的选择，做出了有效的改进。