Tournament網絡節(jié)點的排序算法

林馨

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

關鍵詞：tournament;網絡;排序

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

0 引言

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

考慮一類特殊的網絡：Tournament網絡。

相關定義：

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

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

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

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

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

1 主要結論

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

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

考查以下6階Tournament網絡如圖1所示。

該圖具有兩條完全路徑：

以及，

因此為雙向連通Tournament網絡。

其鄰接矩陣為：

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

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

，

，

，

...

當時，歸一化后將收斂到某個極限分數向量，即鄰接矩陣A的對應于最大特征值的特征向量t。

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

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

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

Step1..，.

Step2. 若i到j存在有向邊，則令，轉step3;否則轉step3.

Step3.若，則j：=j+1;否則轉step4.

Step4.若，則，轉step2;否則，轉step5.

Step5.計算矩陣A的最大特征值和對應的特征向量.

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 結語

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

參考文獻

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

[2] 張瑩.運籌學基礎[M].清華大學出版社，2004.

[3] 耿素云.離散數學[M].北京大學出版社，2015.

[4] 蘇德富，鐘誠.計算機算法設計與分析[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