一類k-正則圖的生成樹數(shù)目與熵

賈環(huán)身，吳廷增

(青海民族大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，西寧 810007)

生成樹是反映復(fù)雜網(wǎng)絡(luò)可靠性的一個(gè)重要物理指標(biāo)，網(wǎng)絡(luò)中生成樹越多，則網(wǎng)絡(luò)越健壯[1-5].對(duì)于一個(gè)連通網(wǎng)絡(luò)，在保持節(jié)點(diǎn)數(shù)不變的情況下，其生成樹具有最好的同步能力.熵是從信息論中借用的一個(gè)術(shù)語.它是對(duì)“信息量”或信息傳遞的“不確定”的度量.圖的熵，是對(duì)有無圖結(jié)構(gòu)的一種測(cè)量.信息的基本單位是比特.因此, 熵是圖中“隨機(jī)性”的比特?cái)?shù)；熵越高，網(wǎng)絡(luò)的隨機(jī)性就越高[6-10].文獻(xiàn)[11]中，給出了一類4-正則圖生成樹的計(jì)算算法，本文推廣了該結(jié)果，給出了k-正則圖的生成樹數(shù)目和熵.為了證明該結(jié)果，先給出一些定義和引理.

圖G[12]是指一個(gè)有序三元組(V(G),E(G),ΨG)，其中V(G)表示頂點(diǎn)集，E(G)表示邊集，ψG是關(guān)聯(lián)函數(shù).若e是一條邊，而u和v是使得ψG(e)=uv的頂點(diǎn)，則稱e連接u和v；頂點(diǎn)u和v稱為e的端點(diǎn).圖G的頂點(diǎn)v的度dG(v)是指G中與v關(guān)聯(lián)的邊的數(shù)目.若各頂點(diǎn)的度均相同的無向簡(jiǎn)單圖稱為正則圖.各頂點(diǎn)度均為k的正則圖稱為k-正則圖.若圖存在其中1個(gè)點(diǎn)的度數(shù)為(k-1)，分別只與其他(k-1)個(gè)點(diǎn)相連，稱這樣的圖為k個(gè)頂點(diǎn)的星圖Sk.不包含圈的圖稱為無圈圖，連通的無圈圖稱為樹.圖G的一個(gè)生成子圖T如果是樹，則稱它為G的一棵生成樹，生成樹T是一個(gè)連通圖G的一個(gè)極小連通子圖，包含G的所有n個(gè)頂點(diǎn)，有(n-1)條邊的連通圖.若T為森林，則稱它為G的一個(gè)生成森林.為了方便，圖G中生成樹的個(gè)數(shù)記為NST(Gt).

引理1[3](Cayley公式)若e是Gt的邊，則NST(Gt)=NST(Gt-e)+NST(gt·e).

下面使用迭代法構(gòu)造一類k-正則圖.具體構(gòu)造步驟如下：

1)當(dāng)t=0時(shí)給出一個(gè)星Sk-1，記為F0，使得F0為一個(gè)k個(gè)節(jié)點(diǎn)連接k-1條邊的k-1叉樹；

2)當(dāng)t=1時(shí)，取F0的一個(gè)拷貝并一一對(duì)應(yīng)粘貼葉子節(jié)點(diǎn)，使得最底層的每個(gè)葉子節(jié)點(diǎn)的度為k，記為F1；

3)當(dāng)t≥2時(shí)，在(t-1)步生成的(k-1)叉樹Ft-1的每個(gè)葉子節(jié)點(diǎn)再生出(k-1)個(gè)葉子節(jié)點(diǎn)并復(fù)制Ft-1，粘貼兩個(gè)Ft-1的最底層葉子節(jié)點(diǎn)使得它們的度為k，記為Ft(t≥2)(如圖1).

圖1 Ft(t=0、1、2)的前三步迭代構(gòu)造

圖2 Gt(t=0、1、2)的前三步迭代構(gòu)造

直徑指網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)之間最小距離的最大值,它反映網(wǎng)絡(luò)最大最大傳遞延遲的屬性.小的直徑與小世界網(wǎng)絡(luò)的概念是一致的,這里用直徑代替平均路徑長(zhǎng)度來說明網(wǎng)絡(luò)的小世界特性.D(t)用表示本網(wǎng)絡(luò)模型的時(shí)間步t時(shí)的直徑.網(wǎng)絡(luò)的直徑為：D(t)=2t+1

觀察Gt, 不難發(fā)現(xiàn)Ft和Gt的關(guān)系，見圖3.假設(shè)ST(Ft)表示在Ft中第t步時(shí)的生成樹數(shù)目，SF(Ft)表示在Ft中第t步時(shí)具有兩個(gè)分支的生成森林?jǐn)?shù)目，那么通過計(jì)算Ft的生成樹數(shù)目來求得原模型Gt的生成樹數(shù)目.

定理1 設(shè)Gt為k-正則圖(k≥3)，則

證明：由圖3～5可得出，F(xiàn)t在第t步時(shí)的生成樹數(shù)目是通過迭代的方法由(t-1)步得到，并且t步的生成樹是由(t-1)步生成樹和生成森林共同構(gòu)成，F(xiàn)t有以下幾種情形：

圖3 t步時(shí)的網(wǎng)絡(luò)Ft和Gt

ST(Gt)=2ST2(Ft)+2ST(Ft)·SF(Ft)

(1)

(2)

其中：ST(F0)=1,SF(F0)=k-1

圖4 每一類Ft的生成樹

圖5 每一類Ft中具有兩個(gè)分支的生成森林

(3)

SF(Ft)=(k-1)(k-1)t·

(4)

根據(jù)式(3),(4)可推出公式(1)得到Gt的生成樹數(shù)目，即：

由生成樹數(shù)目，則的生成樹的熵為：