Tournament网络节点的排序算法

林馨

摘要：在組合网络理论中，常将网络节点抽象为图的节点，借助图来研究网络的性质。本文将Tournament网络抽象为图，并以网络中节点输出的信息量为依据，重点探讨了双向连通Tournament网络节点的排序问题，并给出相应的算法。

关键词：tournament;网络;排序

中图分类号：O157.5 文献标识码：A 文章编号：1007-9416（2019）02-0124-02

0 引言

在组合网络理论中，常将网络节点抽象为图的节点，借助图来研究网络的性质[1]。若从节点A到节点B有信息传输，则对应的图上有从顶点A到顶点到B的有向边。图中，若存在从顶点A至顶点C的一条有向路径，则认为在网络中节点A的信息能传输至节点C。以节点在网络中输出的信息量为依据，对网络节点的重要性进行排序[2]。

考虑一类特殊的网络：Tournament网络。

相关定义：

任意两个顶点间都有边的无向图称为完全图。

每条边都有方向的图称为有向图。

有向完全图称为Tournament图[3]。

对任意一对顶点，若存在两条有向路径，使得两顶点可以互相连通，则这类有向图称为双向连通的。

若Tournament图存在唯一的完全路径（即经过所有顶点的有向路径），则按此完全路径的顶点顺序，可给出Tournament网络的节点排序。

1 主要结论

以下讨论双向连通Tournament网络（即每对顶点间存在两条有向路径，此时图上有不止一条完全路径）节点的排序问题。

定义n阶Tournament图的邻接矩阵：

考查以下6阶Tournament网络如图1所示。

该图具有两条完全路径：

以及，

因此为双向连通Tournament网络。

其邻接矩阵为：

为每个顶点计分以衡量其输出的信息量，则可得顶点的分数向量，其中是顶点i的分数。则结合邻接矩阵的定义，知。但由此分数向量对节点进行排序，只能反映出节点直接输出的信息量，而忽略了间接传输的信息量。为了得到更合理的排序，我们试图找一个分数向量，使它能综合全面的反映出节点输出的信息量。

令，进一步求，此分数向量表示每个顶点（作为出点）的邻接顶点在中的分数之和。继续求解，

，

，

，

...

当时，归一化后将收敛到某个极限分数向量，即邻接矩阵A的对应于最大特征值的特征向量t。

可算出邻接矩阵A的最大特征值，对应的最大特征向量归一化后得：

由此可得，节点排名为{6，2，3，1，4，5}

对n阶双向连通Tournament网络节点排序算法如下：

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. 输出排序后的节点。

2 结语

本文将Tournament网络抽象为图，并以网络中节点输出的信息量为依据，结合代数的知识，重点探讨了双向连通Tournament网络节点的排序问题，并给出相应的算法。此结论为进一步研究各类网络结构和性质提供了依据。

参考文献

[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].电子工业出版社，2001.

Sorting Algorithm of Tournament Network

LIN Xin

（Fujian Normal UniversityCollege of Mathematics and Informatics Fujian，Fuzhou 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