《Petersen图互联网络拓扑构造研究.docx》由会员分享，可在线阅读，更多相关《Petersen图互联网络拓扑构造研究.docx（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Petersen图互联网络拓扑构造研究摘要:设计了一种基于广义Petersen图的互联网络拓扑构造，分析证实了该互联网络拓扑构造该构造的直径。通过分析比拟，得出设计的互联网络拓扑构造具有小连通度和小直径的特点。关键词:互联网络;广义Petersen图;网络直径一个FPk网络包括5k个节点，也就是k个Petersen图的笛卡尔积1。Das等把Petersen图嵌入Hypercube网络,构造了一种HP网络(HyperPetersenNetwork)。由于HP网络有非常小的直径,所以有很好的通讯效率2。Ohring等把Hypercube与Petersen图做笛卡尔积，构造了一种FPQn,k网络并分
2、析了其容错性和可靠性,给出了路由算法3。刘宏英等4分析了RCP(n)互联网络并给出了基于该网络的组播路由算法。刘方爱等和邢长明等分别构造了RP(k)和RPC(k)互联网络并给出了对应的路由算法5-7。主要构造了一类基于广义Petersen图GP(n,k)的互联网络构造EGP(k3,k2,k)，并分析了EGP(k3,k2,k)的直径和良好的通信性能。1预备知识设G=(V,E)为简单连通无向图。对任意的u,vV(G),dG(u,v)表示G中(u-v)最短路的长度，在不引起混淆的情况下，简记为d(u,v)。对任意的vV(G)和SV(G),顶点v到点集S的距离为d(v,S)=mind(v,u)|uS。
3、对任意的SV(G)和TV(G),点集S到点集T的距离为d(S,T)=mind(u,v)|uS,vT。定义1设n和k为两个正整数，且n2k，广义Petersen图P(n,k)共含有2n个顶点，其顶点集为V(P(n,k)=ui,wi|1in。边集为E(P(n,k)=uiui+1,uiwi,wiwi+k|1in,下标模n8。定义2设n,k,t为正整数，且n2k,kt，拓展的广义Petersen图(ExpendedGeneralizedPetersenGraphs)EGP(n,k,t)共含有2n个顶点，其顶点集为V(EGP(n,k,t)=ui,wi|1in,边集为E(EGP(n,k,t)=uiui+1
4、,uiwi,wiwi+k,wiwi+t|1in,下标模n。EGP(n,k,t)的构造方法：对于P(n,t)，在顶点wi和wi+k间连接边，其中i=pt,0pnt且p为整数，下标模n。2EGP(t3,t2,t)互联网络讨论一类特殊的EGP(n,k,t)，即EGP(t3,t2,t)(t2)网络，设U=u0u1u2ut3-1u0,W=w0wtw2twt3-tw0,T=w0wt2w2t2wt3-t2w0。则U,W,T为EGP(t3,t2,t)的三个圈，t=3时的EGP(33,32,3)如图1所示。此时EGP(33,32,3)的三个圈U,W,T(如图2所示)详细为U=u0u1u2u26u0,W=w0w3
5、w6w24w0,T=w0w9w18w0。引理1设vV(EGP(t3,t2,t)，则有d(v,U)1。引理2设vV(U)=u0,u1,.,ut3-1，则有d(v,W)1+t/2。证实对任意vu0,u1,.,ut3-1，不妨设v=ukt+r(0kt2-1,0rt-1)。1若rt/2，取(ukt-ukt+r)路，P=uktukt+1ukt+2ukt+r，则d(v,ukt)t/2，可得d(v,W)d(v,ukt)+d(ukt,wkt)t/2+1。2若rt/2，取(ukt+r-u(k+1)t-1)路，P=ukt+rukt+r+1ukt+r+2u(k+1)t，则d(v,u(k+1)t)t/2，可得d(v,
6、W)d(v,u(k+1)t)+d(u(k+1)t,w(k+1)t)t/2+1，综上得证。引理3设vV(W)=w0,wt,w2t,wt3-t，则有d(v,T)t/2。证实对任意vw0,wt,w2t,wt3-t，不妨设v=wkt2+rt(0kt-1,0rt-1)。1若rt/2，取(wkt2-wkt2+rt)路，P=wkt2wkt2+twkt2+2twkt2+rt，则d(v,wkt2)t/2，故d(v,T)d(v,wkt2)t/2。2若rt/2，取(wkt2+rt-w(k+1)t2)路，P=wkt2+rtwkt2+(r+1)twkt2+(r+2)tw(k+1)t2，则d(v,w(k+1)t2)t-r
7、t/2，故d(v,T)d(v,w(k+1)t2)t/2，综上得证。引理4设u,vV(T)=w0,wt2,w2t2,wt3-t2，则有d(u,v)t/2。证实对任意u,vV(T)=w0,wt2,w2t2,wt3-t2，不妨设u=wpt2,v=wqt2(0p,qt-1且pq)。1若q-pt/2，取(wpt2-wqt2)路，P=wpt2w(p+1)t2w(p+2)t2wqt2，则d(u,v)q-pt/2。2若q-pt/2，取(wqt2-wpt2)路，P=wqt2w(q+1)t2w(q+2)t2wt3-t2w0wt2w2t2wpt2，则d(u,v)(t-1)-q+(p+1)=t-(q-p)t/2，综上
8、得证。定理1对于任意不小于3的正整数t，EGP(t3,t2,t)网络的直径diam(EGP(t3,t2,t)=5t2+4。证实对任意u,vV(EGP(t3,t2,t)，根据引理1，2，3，4可有d(u,v)d(u,U)+d(U,W)+d(W,T)+t/2+d(W,T)+d(U,W)+d(v,U)1+t2+1+t2+t2+t2+1+1=5t2+4，故EGP(t3,t2,t)网络的直径diam(EGP(t3,t2,t)5t2+4。另一方面，取u=wt2，v=wt2t2+t2，则d(u,v)=5t2+4，故diam(EGP(t3,t2,t)5t2+4，综上可有diam(EGP(t3,t2,t)=5t
9、2+4。通过表1，能够看到，EGP(k3,k2,k)网络与RPC(k)网络和RP(k)网络的性能比拟，连接度是一样的，但网络直径更小，优于文献5中的RP(n)网络的直径，也优于6中的RPC(k)网络的直径。在广义Petersen图的基础上进行扩展，通过对广义Petersen图的重构构成了EGP(k3,k2,k)网络。与其它基于Petersen图构造的并行计算机互联网络(如RPC(k)网络和RP(k)网络)相比，EGP(k3,k2,k)网络具有高度近正则性和小直径特点，十分是网络直径方面，阶为O(n3)，优于RPC(k)网络和RP(k)网络的O(n)阶网络直径值，表明构造的EGP(k3,k2,k)互联网络具有更好的通信性能。