謝建民，趙廷剛，洪文梅

（1.蘭州城市學(xué)院 信息工程學(xué)院，甘肅蘭州 730070；2.蘭州城市學(xué)院 幼兒師范學(xué)院，甘肅蘭州 730020）

網(wǎng)絡(luò)通信和數(shù)據(jù)安全有效傳送是計算機(jī)網(wǎng)絡(luò)的重要功能，是計算機(jī)網(wǎng)絡(luò)實現(xiàn)社會、經(jīng)濟(jì)、服務(wù)功能的基礎(chǔ).在網(wǎng)絡(luò)優(yōu)化設(shè)計中，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的選擇對網(wǎng)絡(luò)通信功能、數(shù)據(jù)傳輸功能的效率起著至關(guān)重要的作用，而計算機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的魔幻性質(zhì)對網(wǎng)絡(luò)設(shè)計和通信費用等方面有重要影響，總線型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、星型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和環(huán)型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是三種具有魔幻標(biāo)號性質(zhì)的基本網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，其魔幻性質(zhì)為網(wǎng)絡(luò)系統(tǒng)的優(yōu)化設(shè)計奠定了必要的理論基礎(chǔ).但是，它們結(jié)構(gòu)單一性又嚴(yán)重影響著現(xiàn)實生活中實用網(wǎng)絡(luò)結(jié)構(gòu)的設(shè)計.因此，將兩種或兩種以上的單一拓?fù)浣Y(jié)構(gòu)有機(jī)結(jié)合構(gòu)成新型的混合拓?fù)浣Y(jié)構(gòu)，已經(jīng)成為科研人員、特別是網(wǎng)絡(luò)分析、設(shè)計人員的重要研究課題.到目前為止,已有大量關(guān)于特定網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)魔幻性質(zhì)的研究文章發(fā)表[1-6].本文給出一類混合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)——路燈樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的定義，利用算法分析與設(shè)計的思想設(shè)計了“路燈樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的邊魔幻全標(biāo)號算法”，證明了算法的正確性、時間復(fù)雜度及時間最優(yōu)性，從而證明了路燈樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的邊魔幻性.

1 預(yù)備知識

本文討論的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)G=（V，E）為無向簡單網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).其中，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)G 的節(jié)點集和邊集分別用V 和E 表示，p，q 則表示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)G所含的節(jié)點數(shù)和邊數(shù).記號[m,n]表示非負(fù)整數(shù)集{m,m+1,m+2,…,n}，其中m 和n 均為整數(shù)，且滿足0≤m≤n；記號[k,l]e表示非負(fù)偶數(shù)集{k,k+2,k+4,…,l}，其中k 和l 均為偶數(shù)，且滿足0≤k≤l；記號[s,t]o表示非負(fù)奇數(shù)集{s,s+2,s+4,…,t}，其中s 和t均為奇數(shù)且滿足0≤s≤t.未說明的符號及術(shù)語參見文獻(xiàn)[7].

定義1[7]對于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)G（V，E），如果存在常數(shù)k 及一個映射

則稱G 為一個邊魔幻網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，f 為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)G 的一個邊魔幻全標(biāo)號，λ 為魔幻常數(shù).

定義2由一個總線型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Pm和m個星型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Si，n（i∈[1，m]）組合而成混合型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）稱為路燈樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).

2 路燈樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）的邊魔幻全標(biāo)號算法

任給正偶數(shù)m 與正整數(shù)n，設(shè)路燈樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

其中節(jié)點集合

則路燈樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）的節(jié)點標(biāo)定拓?fù)浣Y(jié)構(gòu)見圖1.

圖1 路燈樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的節(jié)點標(biāo)定拓?fù)浣Y(jié)構(gòu)

由定義2 易知，對于任意給定的正偶數(shù)m 與正整數(shù)n，路燈樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）含節(jié)點數(shù)p=m（n+1），邊數(shù)q=m（n+1）－1.因此，對路燈樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）構(gòu)造邊魔幻全標(biāo)號的算法見算法1（路燈樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）邊魔幻全 標(biāo)號算法簡記為：STREETLAMP_EMTL 算法）.

下面討論“STREETLAMP_EMTL 算法”的正確性及時間復(fù)雜度.

定理1給定正偶數(shù)m、正整數(shù)n以及N節(jié)點路燈樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）（N=m（n+1）），“STREETLAMP_EMTL 算法”能夠在時間O（N）內(nèi)確定拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）的一個邊魔幻全標(biāo)號.

證明：根據(jù)算法1，對拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）的節(jié)點及邊做分類標(biāo)號f 如下：

由f（Vt）（t∈[1，4]）與f（Et）（t∈[1，2]）的表達(dá)式可知，它們?nèi)我鈨蓚€集合均不相交，所以標(biāo)號f 是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）的節(jié)點集V與邊集E到數(shù)集

滿足定義1 中的（4）.

所以，f 是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）的一個邊魔幻全標(biāo)號，即“STREETLAMP_EMTL 算法”能夠確定網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）的一個邊魔幻全標(biāo)號.

在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）中確定一個邊魔幻全標(biāo)號，基本運算是對拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）中每個節(jié)點標(biāo)號運算.設(shè)W（N）表示“STREETLAMP_EMTL 算法”對于規(guī)模為N 的輸入所做的標(biāo)號次數(shù).該算法的（2）～（7）步是對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)T (Pm，S1,n，S2,n，…，Sm，n) 中每個節(jié)點及邊標(biāo)號運算過程，該過程需要做m（n+1）次標(biāo)號運算.因此，

所以，該算法的時間復(fù)雜度為

綜上所述，給定正偶數(shù)m、正整數(shù)n 以及N 節(jié)點路燈樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）（N=m（n+1）），“STREETLAMP_EMTL 算法”能夠在時間O（N）內(nèi)確定拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）的一個邊魔幻全標(biāo)號.

由定理1 易得推論1.

推論1對于任意正偶數(shù)m 和正整數(shù)n，路燈樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）都是邊魔幻網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).

定理2“STREETLAMP_EMTL 算法”是確定路燈樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）的一個邊魔幻全標(biāo)號的時間最優(yōu)算法.

證明：要確定路燈樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）的一個邊魔幻全標(biāo)號，就必須標(biāo)出該拓?fù)浣Y(jié)構(gòu)每一個節(jié)點及邊的標(biāo)號.由于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)T（Pm，S1，n，S2，n，…，Sm，n）有

個節(jié)點，所以至少進(jìn)行N 次標(biāo)號運算才能確定T（Pm，S1，n，S2，n，…，Sm，n）的一個邊魔幻 全標(biāo)號.由定理1可知，算法1 僅需要做N 次標(biāo)號運算，就能確定該網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的一個邊魔幻全標(biāo).所以，“STREETL AMP_EMTL 算法”是該算法類中時間上最優(yōu)的算法.