网络信息传输 二部图网络信息传输的最短时间
摘要:本文利用图论中的匹配、边着色等原理,探讨了二分图网络传输信息的最佳方案,并给出相应的算法,使得网络总的传输时间最短。 关键词:二分图 网络匹配边色数
1 引言
对于计算机网络,人们最关心的通常是它的传输效率,也就是以最短的时间传送最多的信息量。例如,一个单位的各部门每天都需要共享信息,即需要用网络进行信息传输。于是,如何设计传输方案,使得把所有的文件都传输完毕的时间最短就显得极为重要。
本文通过探讨二分图网络传输信息的方法,结合图论中的匹配、边着色等原理,给出了相应的算法,并得到此类网络传输信息的最佳方案,从而解决树状网络、棋盘网络、蜂巢网络等常见的二分图状网络的信息传输优化问题。
2 预备知识
定义1设G是无环图,,若M中任意两条边在G中都不相邻,则称M是图G的一个匹配。
定义2 若对图G的任意匹配 ,均有 ,则称M为图G的最大匹配,且M中的边数称为匹配数。
定义3 设M是图G的匹配,G中与M中的边关联的顶点称为M饱和点,否则称为非M饱和点。
定义4 设M是图G的匹配,P是G的一条路,且在P中M的边和 的边交替出现,则称P是G的一条M交错路。若M交错路P的两个端点为M非饱和点,则称P为M可增广路。
定义5 图G的边色数(记作 )是指给G的边着色,使得相邻边的颜色都不同,所需的最少颜色数。
性质1:若G是连通的简单图,G的最大顶点度为 ,则 。
性质2:若G是二分图图,则 。
性质3:图G的边不交匹配的最小数目即为图G的边色数。
3 主要结果
3.1问题描述
某单位各部门每天都要使用二分图网络传输信息,网络用图G表示,其中各部门(计算机)用顶点 表示,两个部门(计算机)之间要传输的文件用边 表示。假定:任一文件的传输时间都为1,任一计算机可以同时传输的最大文件数目为1; 每个文件的传输以一个连续的整体进行,文件传输无优先权,即文件一旦开始,不得中断直到所有文件传输完毕;传输的切换时间可以忽略;所有计算机不给自身传输文件。我们要设计一种最佳的传输方案,使网络总的传输时间最短。
3.2算法描述
根据问题的描述,我们可以得到不同的传输方案,但无论怎样传输,一对正传输一个文件的计算机都不能进行另外一个文件的传输。因此,我们可以通过选择网络中适当的边,得到某种匹配。当把每个时间单位分开考虑时,就会得到边不交的多个匹配,这些匹配恰好覆盖了整个图。由此得到,最小的传输时间就等于产生整个图的最少匹配数。
由于G是二分图,所以由性质2、性质3知,G的边不交的最少匹配数就等于G顶点的最大度。下面,我们结合二分图的最大匹配生成法,给出找G的边不交的最少匹配的算法。设G具有二部划分( )。
BEGIN
Step1. 令 ;
Step2. 任给 初始匹配M, 若M不存在,则结束,否则转step3;
Step3. 若M饱和 , 则M是最大匹配,输出M,转step8 ;否则转step4;
Step4. 在 中找一非M饱和点x,置 , ;
Step5. 若 ,则停止;否则任选一点 ;
Step6. 若y为M饱和点,则转step7;
否则作一条从x到y得M可增广路P,置 ,转step3;
Step7. 由于y是M饱和点,故M中存在边yu,置 , ,转step5;
Step8. 置 , 转step2.
END
设图G有n个顶点,m条边,且顶点最大度为 。在找最大匹配时,该算法最多找n条可增广路,每找一条可增广路,最多比较m条边,又由前面的分析知,总共找到的匹配数等于图G的顶点最大度。因而该算法的时间复杂度为 ,故该算法为有效算法。由性质3知,该算法得到的匹配数也就是传输完所有文件所需的最少时间。同时,每次找图的最大匹配也使得单位时间内传输的文件数最多,故应用该算法可得最优传输方案。
3.3实例求解
某单位有22个部门,每个部门一台计算机(分别用图1中G的22个顶点表示),每天需传送24个文件(分别用图1中G的24条边表示)。假定:任一文件的传输时间都为1,任一计算机可以同时传输的最大文件数目为1。我们设计一种传输方案,使得网络总的传输时间最短。G是一个二分图,利用以上算法,可依次得到G的4个匹配为:
A. e1, e4, e7, e8, e11, e14, e18, e21
B. e2, e5, e9, e12, e15, e17, e20, e24
C. e3, e6, e10, e13, e16, e19
D. e22, e23
从而我们得到该网络的一个传输方案,如表1。
时间 被传输的文件
0 e1, e4, e7, e8, e11, e14, e18, e21
1 e2, e5, e9, e12, e15, e17, e20, e24
2 e3, e6, e10, e13, e16, e19
3 e22, e23
4 结语
本文结合最大匹配的生成算法,给出了二分图网络信息传输的最优方案。该方案不仅使得所有文件传输完毕的时间最短,还保证了在任意时刻之前传送的文件量最大,从而解决了树状网络、棋盘网络、蜂巢网络等常见的二分图状网络的信息传输优化问题。
参考文献
[1] 卜月华.图论及其应用.南京:东南大学出版社,2002.
[2] 殷剑宏,吴开亚.图论及其算法.合肥:中国科学技术大学出版社,2005.
[3] Bondy,J.A. and Murty,U.S.R., Graph theory with applications, The Macmillan Press Ltd,1976.
基金项目:福建省高校服务海西建设重点项目----基于数学的信息化技术研究
作者简介:林馨 (1981.9)、女、硕士、研究方向:应用数学;
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文