林馨

摘要：在組合網(wǎng)絡(luò)理論中，常將網(wǎng)絡(luò)節(jié)點抽象為圖的節(jié)點，借助圖來研究網(wǎng)絡(luò)的性質(zhì)。本文將Tournament網(wǎng)絡(luò)抽象為圖，并以網(wǎng)絡(luò)中節(jié)點輸出的信息量為依據(jù)，重點探討了雙向連通Tournament網(wǎng)絡(luò)節(jié)點的排序問題，并給出相應(yīng)的算法。

關(guān)鍵詞：tournament;網(wǎng)絡(luò);排序

中圖分類號：O157.5 文獻標(biāo)識碼：A 文章編號：1007-9416（2019）02-0124-02

0 引言

在組合網(wǎng)絡(luò)理論中，常將網(wǎng)絡(luò)節(jié)點抽象為圖的節(jié)點，借助圖來研究網(wǎng)絡(luò)的性質(zhì)[1]。若從節(jié)點A到節(jié)點B有信息傳輸，則對應(yīng)的圖上有從頂點A到頂點到B的有向邊。圖中，若存在從頂點A至頂點C的一條有向路徑，則認為在網(wǎng)絡(luò)中節(jié)點A的信息能傳輸至節(jié)點C。以節(jié)點在網(wǎng)絡(luò)中輸出的信息量為依據(jù)，對網(wǎng)絡(luò)節(jié)點的重要性進行排序[2]。

考慮一類特殊的網(wǎng)絡(luò)：Tournament網(wǎng)絡(luò)。

相關(guān)定義：

任意兩個頂點間都有邊的無向圖稱為完全圖。

每條邊都有方向的圖稱為有向圖。

有向完全圖稱為Tournament圖[3]。

對任意一對頂點，若存在兩條有向路徑，使得兩頂點可以互相連通，則這類有向圖稱為雙向連通的。

若Tournament圖存在唯一的完全路徑（即經(jīng)過所有頂點的有向路徑），則按此完全路徑的頂點順序，可給出Tournament網(wǎng)絡(luò)的節(jié)點排序。

1 主要結(jié)論

以下討論雙向連通Tournament網(wǎng)絡(luò)（即每對頂點間存在兩條有向路徑，此時圖上有不止一條完全路徑）節(jié)點的排序問題。

定義n階Tournament圖的鄰接矩陣：

考查以下6階Tournament網(wǎng)絡(luò)如圖1所示。

該圖具有兩條完全路徑：

以及，

因此為雙向連通Tournament網(wǎng)絡(luò)。

其鄰接矩陣為：

為每個頂點計分以衡量其輸出的信息量，則可得頂點的分?jǐn)?shù)向量，其中是頂點i的分?jǐn)?shù)。則結(jié)合鄰接矩陣的定義，知。但由此分?jǐn)?shù)向量對節(jié)點進行排序，只能反映出節(jié)點直接輸出的信息量，而忽略了間接傳輸?shù)男畔⒘?。為了得到更合理的排序，我們試圖找一個分?jǐn)?shù)向量，使它能綜合全面的反映出節(jié)點輸出的信息量。

令，進一步求，此分?jǐn)?shù)向量表示每個頂點（作為出點）的鄰接頂點在中的分?jǐn)?shù)之和。繼續(xù)求解，

，

，

，

...

當(dāng)時，歸一化后將收斂到某個極限分?jǐn)?shù)向量，即鄰接矩陣A的對應(yīng)于最大特征值的特征向量t。

可算出鄰接矩陣A的最大特征值，對應(yīng)的最大特征向量歸一化后得：

由此可得，節(jié)點排名為{6，2，3，1，4，5}

對n階雙向連通Tournament網(wǎng)絡(luò)節(jié)點排序算法如下：

Step1..，.

Step2. 若i到j(luò)存在有向邊，則令，轉(zhuǎn)step3;否則轉(zhuǎn)step3.

Step3.若，則j：=j+1;否則轉(zhuǎn)step4.

Step4.若，則，轉(zhuǎn)step2;否則，轉(zhuǎn)step5.

Step5.計算矩陣A的最大特征值和對應(yīng)的特征向量.

Step6.對特征向量的各分量排序[4]：

Begin

k=n;

flag=1;

While flag>0 do

Begin

k=k-1;

flag=0;

for i=1 to k do

if? then

Begin

;

;

;

flag=1;

End

End

End

Step8. 輸出排序后的節(jié)點。

2 結(jié)語

本文將Tournament網(wǎng)絡(luò)抽象為圖，并以網(wǎng)絡(luò)中節(jié)點輸出的信息量為依據(jù)，結(jié)合代數(shù)的知識，重點探討了雙向連通Tournament網(wǎng)絡(luò)節(jié)點的排序問題，并給出相應(yīng)的算法。此結(jié)論為進一步研究各類網(wǎng)絡(luò)結(jié)構(gòu)和性質(zhì)提供了依據(jù)。

參考文獻

[1] J.A Bondy and U.S.R Murty，“graph theory with applications”， 1st Edition， The MacMillan Press，1976.

[2] 張瑩.運籌學(xué)基礎(chǔ)[M].清華大學(xué)出版社，2004.

[3] 耿素云.離散數(shù)學(xué)[M].北京大學(xué)出版社，2015.

[4] 蘇德富，鐘誠.計算機算法設(shè)計與分析[M].電子工業(yè)出版社，2001.

Sorting Algorithm of Tournament Network

LIN Xin

（Fujian Normal UniversityCollege of Mathematics and Informatics Fujian，F(xiàn)uzhou Fujian? 350007）

Abstract：In combination network theory， we often consider nodes of a network as vertexes of a graph， so we can study the properties of networks via graphs. In this article， we will specifically study Bi-connected tournament network， based on the amount of information each node transmit， and give an algorithm to sort all nodes according to their importance in this network.

Key words：tournament;network;sorting