路灯树型网络拓扑结构的边魔幻全标号算法

谢建民，赵廷刚，洪文梅

（1.兰州城市学院 信息工程学院，甘肃兰州 730070；2.兰州城市学院 幼儿师范学院，甘肃兰州 730020）

网络通信和数据安全有效传送是计算机网络的重要功能，是计算机网络实现社会、经济、服务功能的基础.在网络优化设计中，网络拓扑结构的选择对网络通信功能、数据传输功能的效率起着至关重要的作用，而计算机网络拓扑结构的魔幻性质对网络设计和通信费用等方面有重要影响，总线型网络拓扑结构、星型网络拓扑结构和环型网络拓扑结构是三种具有魔幻标号性质的基本网络拓扑结构，其魔幻性质为网络系统的优化设计奠定了必要的理论基础.但是，它们结构单一性又严重影响着现实生活中实用网络结构的设计.因此，将两种或两种以上的单一拓扑结构有机结合构成新型的混合拓扑结构，已经成为科研人员、特别是网络分析、设计人员的重要研究课题.到目前为止,已有大量关于特定网络拓扑结构魔幻性质的研究文章发表[1-6].本文给出一类混合网络拓扑结构——路灯树型网络拓扑结构的定义，利用算法分析与设计的思想设计了“路灯树型网络拓扑结构的边魔幻全标号算法”，证明了算法的正确性、时间复杂度及时间最优性，从而证明了路灯树型网络拓扑结构的边魔幻性.

1 预备知识

本文讨论的网络拓扑结构G=（V，E）为无向简单网络拓扑结构.其中，网络拓扑结构G 的节点集和边集分别用V 和E 表示，p，q 则表示网络拓扑结构G所含的节点数和边数.记号[m,n]表示非负整数集{m,m+1,m+2,…,n}，其中m 和n 均为整数，且满足0≤m≤n；记号[k,l]e表示非负偶数集{k,k+2,k+4,…,l}，其中k 和l 均为偶数，且满足0≤k≤l；记号[s,t]o表示非负奇数集{s,s+2,s+4,…,t}，其中s 和t均为奇数且满足0≤s≤t.未说明的符号及术语参见文献[7].

定义1[7]对于网络拓扑结构G（V，E），如果存在常数k 及一个映射

则称G 为一个边魔幻网络拓扑结构，f 为网络拓扑结构G 的一个边魔幻全标号，λ 为魔幻常数.

定义2由一个总线型网络拓扑结构Pm和m个星型网络拓扑结构Si，n（i∈[1，m]）组合而成混合型网络拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）称为路灯树型网络拓扑结构.

2 路灯树型网络拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）的边魔幻全标号算法

任给正偶数m 与正整数n，设路灯树型网络拓扑结构

其中节点集合

则路灯树型网络拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）的节点标定拓扑结构见图1.

图1 路灯树型网络拓扑结构的节点标定拓扑结构

由定义2 易知，对于任意给定的正偶数m 与正整数n，路灯树型网络拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）含节点数p=m（n+1），边数q=m（n+1）－1.因此，对路灯树型网络拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）构造边魔幻全标号的算法见算法1（路灯树型网络拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）边魔幻全 标号算法简记为：STREETLAMP_EMTL 算法）.

下面讨论“STREETLAMP_EMTL 算法”的正确性及时间复杂度.

定理1给定正偶数m、正整数n以及N节点路灯树型网络拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）（N=m（n+1）），“STREETLAMP_EMTL 算法”能够在时间O（N）内确定拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）的一个边魔幻全标号.

证明：根据算法1，对拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）的节点及边做分类标号f 如下：

由f（Vt）（t∈[1，4]）与f（Et）（t∈[1，2]）的表达式可知，它们任意两个集合均不相交，所以标号f 是网络拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）的节点集V与边集E到数集

满足定义1 中的（4）.

所以，f 是网络拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）的一个边魔幻全标号，即“STREETLAMP_EMTL 算法”能够确定网络拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）的一个边魔幻全标号.

在网络拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）中确定一个边魔幻全标号，基本运算是对拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）中每个节点标号运算.设W（N）表示“STREETLAMP_EMTL 算法”对于规模为N 的输入所做的标号次数.该算法的（2）～（7）步是对网络拓扑结构T (Pm，S1,n，S2,n，…，Sm，n) 中每个节点及边标号运算过程，该过程需要做m（n+1）次标号运算.因此，

所以，该算法的时间复杂度为

综上所述，给定正偶数m、正整数n 以及N 节点路灯树型网络拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）（N=m（n+1）），“STREETLAMP_EMTL 算法”能够在时间O（N）内确定拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）的一个边魔幻全标号.

由定理1 易得推论1.

推论1对于任意正偶数m 和正整数n，路灯树型网络拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）都是边魔幻网络拓扑结构.

定理2“STREETLAMP_EMTL 算法”是确定路灯树型网络拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）的一个边魔幻全标号的时间最优算法.

证明：要确定路灯树型网络拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）的一个边魔幻全标号，就必须标出该拓扑结构每一个节点及边的标号.由于网络拓扑结构T（Pm，S1，n，S2，n，…，Sm，n）有

个节点，所以至少进行N 次标号运算才能确定T（Pm，S1，n，S2，n，…，Sm，n）的一个边魔幻 全标号.由定理1可知，算法1 仅需要做N 次标号运算，就能确定该网络拓扑结构的一个边魔幻全标.所以，“STREETL AMP_EMTL 算法”是该算法类中时间上最优的算法.