Tournament網(wǎng)絡(luò)節(jié)點(diǎn)的排序算法

林馨

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

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

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

0 引言

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

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

相關(guān)定義：

任意兩個(gè)頂點(diǎn)間都有邊的無向圖稱為完全圖。

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

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

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

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

1 主要結(jié)論

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

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

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

該圖具有兩條完全路徑：

以及，

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

其鄰接矩陣為：

為每個(gè)頂點(diǎn)計(jì)分以衡量其輸出的信息量，則可得頂點(diǎn)的分?jǐn)?shù)向量，其中是頂點(diǎn)i的分?jǐn)?shù)。則結(jié)合鄰接矩陣的定義，知。但由此分?jǐn)?shù)向量對(duì)節(jié)點(diǎn)進(jìn)行排序，只能反映出節(jié)點(diǎn)直接輸出的信息量，而忽略了間接傳輸?shù)男畔⒘俊榱说玫礁侠淼呐判?，我們?cè)噲D找一個(gè)分?jǐn)?shù)向量，使它能綜合全面的反映出節(jié)點(diǎn)輸出的信息量。

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

，

，

，

...

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

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

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

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

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.計(jì)算矩陣A的最大特征值和對(duì)應(yīng)的特征向量.

Step6.對(duì)特征向量的各分量排序[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é)點(diǎn)。

2 結(jié)語

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

參考文獻(xiàn)

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

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

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

[4] 蘇德富，鐘誠.計(jì)算機(jī)算法設(shè)計(jì)與分析[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