《图论在通讯网中的应用.pdf》由会员分享,可在线阅读,更多相关《图论在通讯网中的应用.pdf(2页珍藏版)》请在三一文库上搜索。
1、2 0 0 9 年第3 期( 总第1 5 i 期)山东纺织经济 图论在通讯网中的应用 辛建亭1 胡萍2 ( 1 青岛市广播电视局山东青岛2 6 6 0 7 1 ;2 青岛飞洋职业技术学院山东青岛2 6 6 10 9 ) 摘要:通讯网络是现代日常生活和生产中最不可缺少的工具,而稳定和方便的通讯别需要相应 的通讯网络。通讯网络的建设应当在安全的前提下,尽可能方便每一个用户。本文从当前我国经济已经 进入到了一个以资源节约、提高效率为主的时代的前提出发,从节约资源的角度,利用图论中的最小生 成树理论,较好地解决了通讯网络的最优化铺设问题,并对这一类问题的解决提供一种新的思路。 关键词:通讯网络;最优化
2、;最小生成树 中图分类号:T N 9 1 5 0 2文献标识码:A d o i :1 0 3 9 6 9 j i s s n 1 6 7 3 - 0 9 6 8 2 0 0 9 0 3 0 6 5 T h eA p p l i c a t i o no fG r a p hT h e o r yi nt h eC o m m u n i c a t i o nN e t A b s t r a c t :C o m m u n i c a t i o nN e ti st h em o s ti m p o r t a n tt o o lt o d a y T om a k ef u l l
3、U S Co ft h i st o o lW en e e dt h e s a f ea n dc o n v e n i e n tC o m m u n i c a t i o nN e t I nt h i sp a p e r ,w eh a v et a k e nu s eo ft h eg r a p ht h e o r yt os o l v et h e c o n s t r u c t i o no ft h eC o m m u n i c a t i o nN e t ,a n ds h o w nt h eb e s tc o n c l u s i o n
4、K e yW o r d s :C o m m u n i c a t i o nN e t ,o p t i m i z e 、M i n i m u mS p a n n i n gT r e e 一前言 自一九七八年改革开放以来,我国经济快速发 展,以往的“高投入、高能耗、高污染”的粗放型 经济发展模式逐步被淘汰,转向以提高效率和节约 资源为主的新的经济模式。经济模式的转变,其根 本原因在于社会经济中的资源是有限的,而人们需 求则是无限的,这一矛盾伴随着人类发展的始终。 想要更好地发展,想要解决人类面临的资源稀缺性 与人们需求无限性的矛盾问题,就需要我们要一方 面要开源,另一方面则要节流
5、。随着生活水平和生 活质量的不断提高,通讯在人类生活中起着越来越 重要的作用,伴随而生的通讯网络的建设也越来越 多,规模越来越大。本文从针对生活和生产中通讯 网络铺设的随意性和浪费现象,利用图论的相关理 论,在不涉及安全性的前提下,寻求如何最优化利 用资源以部分缓解资源稀缺性问题,给出了一种较 好的系统的安排通讯网络的最优铺设方案。 二、图论中的相关理论 图论是运筹学的一个重要分支,它是将实际中 所面临的问题用抽象图的形式表示出来,从而研究 实际问题的一个学科,它在现代生活中得到越来越 多的应用。 本文中所研究的图,就是一个点和边构成的带 有某种联系的集合。假设平面上有n 个点v 。v , 收
6、稿日期:2 0 0 9 0 1 一1 6 v n ,把它们当中的任意两个点用曲线或直线连接起 来,不去考虑点的位置与连线的曲直长短,这样形 成的一个关系结构就是一个图。通常我们用G 来表 示一个图,它是一个偶对( V ,E ) ,其中集合V = v , v ,v 。 是非空有限集,其中的元素我们称为顶点, 集合E = e i = ( v ;,v ;) I v ;,V ;V ,E 中的元素称为边。 e i ;= ( v ;,v i ) 是顶点v ;连接v ;的边,v ;为该边的始点,称 v ;为该边的终点。图G 的一条路P 是指一个有限的、 非空的、顶点不同的点边交错序列P = v 。e v e
7、 , e 。v 。,称m 为路P 的长。如果V 。= V 。,即起点和终 点相同,则称其为圈。对于图G ( V ,E ) 的每条边e i i = ( v ;,v ;) ,赋以一个实数值W ”$ 1 J 称w ;为边e ;= ( V ;,V i ) 的 权,G 连同边上的权称为赋权图。如果G7 ( V7 ,E7 ) 是一个图,并且V cV ,E cE ,则称G 是G 的 子图。如果图G 的任意两个点之间均有路相连,则 称G 是一个连通图。若图G 是连通的,且不包含有 圈,则称该图G 为树。若G7 是包含G 的全部顶点的 子图,且又是树,则称G7 是G 生成树。关于树和生 成树我们有如下理论。 定
8、理l :树图的任意两个点之间都有唯一的一 条路相连。 定理2 :设G 是具有n 个顶点的连通图,G 有n l 条边的充分必要条件是G 是树。 定理3 :如果图G 是有限连通的图,则在G 中 必存在至少一个生成树。 1 6 3 万方数据 PDF Watermark Remover DEMO : Purchase from www.PDFWatermarkR to remove the watermark 山东纺织经济2 0 0 9 年第3 期( 总第1 5 1 期) 三通讯网络铺设问题的分析和解决方案 在通讯网络的铺设中,不妨假设该通讯网络中 有n 个用户,我们将每个用户用一个点表示,则得 顶点
9、集合V = v ,V ,v l 若某用户和另一用户之 间有线路相连则我们将这两点之间连上一条边,边 集合f l 口为E = e ;= ( v i ,V i ) I v ;,V ;V 。这样就利用点和 边将通讯网络抽象成图论当中的图,我们将其记为 G ( V ,E ) 。对于图G ( V ,E ) 的每条边e ;= ( v ;,v ;) 的权值 w ”我们就用这两点间所要铺设网络的实际长度来 表示。这样,要研究通讯网络的最优铺设问题,我 们只需要在由实际情况抽象成的赋权图G ( V ,E ) 上研 究即可。 首先,我们确保满足该通讯网络中的每个用户 的通讯需要,则需要图上任意两个点间皆有路相连。
10、 这样,只要确保图G 是一个连通图即可满足要求。 其次,如果两点间的边不止一条,即两个用户 之间的线路不止一条,则我们本着最优的原则必定 会选取线路短的那一条。因此,图G 中肯定不能有 重边,也就是图G 的任意两个点之间的边最多只有 一条。 再次,图G 中不应该含有圈。因为将圈中任一 条边去掉后,图G 仍然保持连通,所有用户的通讯 需求仍然满足。因此,将该圈中去掉一条边之后,相 当于是既保持了用户的通讯需要又节省了资源,而 且,在选择去掉一条边的时候我们可以选择该圈中 最长的那条边优先去掉,从而达到最优化的目的。 最后,在设计施工中,任意两个用户之间我们 都是可以连通的,所以图G 可是任意两个
11、点之间都 有边相连的完全图,又要满足我们的前三个条件, 则图G 变成了一个连通的且没有重边和圈的简单图, 这实际是一个树图,是原图G 的一个生成树。 通过以上讨论,我们可以得出这样一个结论: 对于实际通讯网络设计所抽象出来的图G 而言它是 一个完全图,本着最优化原则最终所要求的最优的 铺设方案即为求此图G 的最小权值的生成树。 对于最小权值的生成树问题,我们有如下的非 常实用的G r e e d y 算法: S t e p l :将图G 的边按照其权值从小到大排列 E = e l ,e 2 ,e n ; S t e p 2 :如果已经选定e ,e ,e ;,则从E = e 】, e ,e ;
12、选取其中权值最小的边e ;,使得令 e l , e ,e i U e ; 不含有圈; S t e p 3 :当S t e p 2 不能再继续执行时,停止。此 时已经得到图G 的最小权值生成树。 当该算法不能继续执行时停止,此时所选取的 】6 4 通过上面求解过程,我们发现最优方案不止一 个,而是有两个最优方案,但是最优值只有一个。很 容易求得整个通讯网络所用线路总长为 1 + 2 + 1 + 2 + 1 = 7 ( 百公里) 。 四。类似问题的研究讨论 对于上面通讯网络的铺设问题,我们是从节约 资源角度出发,寻求耗费资源最少的铺设方案。当 然,对于边上权值的不同意义,我们也可以用来求 解最少费
13、用的铺设方案,此时,只需要将边上的权 值用来表示在两个不同用户间架设线路的费用即可。 些类似的问题,例如要修建一个连接若干城 市的电力网,已知城市V ;与城市V ;之间连通电路所 需费用为C ”问应在哪些城市之间架设线路,既能 使所有城市之间都能自由用电,又要求架设的总费 用最小,及类似的道路修建等等这一类问题都可以 转化为求解抽象图的最小赋权生成树,这对于我们 的目前的现代化建设有着重要的借鉴意义。 参考文献: 1 】龚六堂动态经济学方法 M 】北京大学出版 社,2 0 0 2 【2 】孙麟平运筹引M 】科学出版社,2 0 0 5 5 】平狄克微观经济学【M 】中国人民大学出版 社,2 0 0 0 万方数据 PDF Watermark Remover DEMO : Purchase from www.PDFWatermarkR to remove the watermark
链接地址:https://www.31doc.com/p-3713782.html