1.3 竞赛图应用

问题描述 某锦标赛采用循环赛制，若干选手两两互相竞赛.得出竞赛成绩后，应该怎样排列参赛者的名次呢?

思路分析 如表1.3所示是一次比赛中6位选手之间的比赛成绩，我们用数字1～6来表示这6名选手，其中“胜”字所在行的选手战胜所在列的选手，“负”字所在行的选手输给了所在列的选手.

模型建立 我们用点来表示运动员，对于任意两名运动员的比赛结果，我们用一条由胜者到负者的有向边表示.这样我们就得到了图1.14所示的这张有向图，记为D，该图中任意两点之间都由唯一一条有向边连接，我们可以将它看作对完全图中各条边的一个定向，即为竞赛图.

一个自然的想法是排名靠前的选手应该击败了排名靠后的选手，因此排参赛者名次的一个可能的办法是寻找这个竞赛图中的哈密顿路（由1.1.2节，我们知道这样的路是存在的），然后按照参加者对应的顶点在这条路中的位置排列名次.例如，有向哈密顿路（3,1，2,4,5,6）表明选手3是冠军，选手1是亚军，等等.可是这种排名显然经不起进一步推敲，因为一个竞赛图一般有许多条有向哈密顿路；我们的例子中就有（1,2,4,5,6,3）,（1,4,6,3,2,5）以及若干别的有向路.另外，这样给出的排名会出现在两两对决中获胜的选手排在了落败的选手之后的情况.

另一个办法看似很合理，即计算得分（即获胜场次的数目），并对其进行比较，根据得分由高到低给出排名.在上面的例子中这样做，按照选手顺序分别写出其获胜场数，得到得分向量

s1=（4,3,3,2,2,1），

然后按照该向量各位选手的得分大小给出对应的排名，比如在s1中第一个位置的数最大，因此1号选手应该为冠军，这里读者立刻就发现这个排名法是有缺陷的，即这个向量不能区别选手2和选手3的得分高低，尽管选手3打败了得分高的选手.于是我们导出第二级得分向量

s2=（8,5,9,3,4,3），

其中每个选手的第二级得分是被他打败的选手的得分之和，例如，3号选手在二级分量中的数值是计算了他所击败的选手在第一级得分分量中的数值之和，即9=4+3+2.我们可以看出3号选手的得分在第二级得分向量中最大，因此名列第一.继续进行该过程，选手下一级得分分量中的得分等于上一级得分向量中被他击败的选手的得分之和，进一步地，我们得到了如下向量

s3=（15,10,16,7,12,9），

s4=（38,28,32,21,25,16），

s5=（90,62,87,41,48,32），

s6=（183,121,193,80,119,87）.

看来选手名次的排列有点波动，例如选手3和选手1竞争第一名的情况就是这样.但是，由图论知识我们知道，如果竞赛图是双连通的，并且至少有4个顶点时，这个程序总是收敛于一个固定的排列.这将导出在任何竞赛中排选手名次的一个好方法.

模型求解 我们看到竞赛图的等级得分向量由

si=AiJ

给出，这里A是D的邻接矩阵，J是由1组成的列向量.有向图D的邻接矩阵A（D）=（aij）中各项元素的取值满足如果连接点vi和vj的有向弧是从vi指向vj,aij=1，否则为0.在本例中，图D的邻接矩阵为

由于A是本原的，根据Perron-Frobenius定理（参见参考文献[4]），设A具有最大绝对值的特征值是正实数r，则

这里s是对应于r的正特征向量.在上例中，我们近似地求得

r=2.232,s=（0.238,0.164,0.231,0.150,0.104）

于是，用这个方法给出的选手的名次排列为1,3,2,5,4,6.

若竞赛图不是双连通的，它的各个双向连通分支可以按优胜顺序排列.于是在一般的循环赛中可以按下列程序排出名次.

（1）在4个或者更多个顶点的各个双向分支中，利用特征向量s排选手的名次；在3个顶点的双向分支中，3个选手的排名采用其他方式.

（2）把这些双向连通分支按优胜次序排列成D1,D2,…,Dm，即若i＜j，则凡是一个端点在Di中，另一个端点在Dj中的每条弧，其头部都在Dj中.

（3）综合（1）和（2）的排名，得到总排名.