循环比赛的名次

1、我们经常在电视中看到各种比赛，那么，在比赛之后，如何根据参赛者的比赛结果排列名次呢？现在，我们一起来了解一下单循环比赛的名次排列规则。单循环赛就是所有参加比赛的队均能相遇一次，最后按各队在全部比赛中的积分、得失分率排列名次。 题：题：若一次比赛中有6支球队参加，并进行单循环比赛，每场比赛只计胜负，没有平局。比赛结果如右图所示。（图中箭头所指方为战败的一方） 问：问：怎样对比赛的名次进行排列？1234566支球队比赛结果支球队比赛结果方法一：方法一：寻找按箭头方向通过全部顶 点的路径。123456则我们可以找出125634和146325这些排列方法。所以按照这种我们无法所以按照这种我们无法排列出

2、正确的名次。排列出正确的名次。6支球队比赛结果支球队比赛结果方法二：计算得分方法二：计算得分 从图中我们可以看出1队胜4场，2, 3队各胜3场，4, 5队各胜2场，6队胜1场。 2、 3队， 4、5队无法排名。但由于3胜2，4胜了5，所以照132456的顺序排名。 很显然这样没有考虑和其他队比很显然这样没有考虑和其他队比赛的结果，所以结果是不正确的。赛的结果，所以结果是不正确的。 下面我们就运用图论的相关知识下面我们就运用图论的相关知识来解决这个问题。来解决这个问题。1234566支球队比赛结果支球队比赛结果循环比赛的结果循环比赛的结果竞赛图竞赛图 竞赛图竞赛图：在每条边上都标出方向的图称为有

3、向图。每对顶点之间都只有一条边相连的有向图称为竞赛图。 只有胜负，没有平局的单循环赛可以用竞赛图表示。 所以我们可以知道两个顶点的竞赛图为一条带箭头的线，所以排名次不成问题。 123(1)123(2)三个顶点的竞赛图三个顶点的竞赛图 1，2，3(1，2，3）并列并列循环比赛的结果循环比赛的结果竞赛图竞赛图名次名次1234(1)1234(2)1234(3)1234(4)1, 2, 3, 42,(1,3,4)(1,3,4), 2四个顶点的竞赛图四个顶点的竞赛图(1,2),(3,4)1, 2, 3, 4?循环比赛的结果循环比赛的结果竞赛图竞赛图名次名次得分排序得分排序完整路径完整路径12341234

4、1234(1)(2)(3)1234(4)竞赛图的竞赛图的3种形式种形式 完全路径图：完全路径图：具有唯一的完全路径，如具有唯一的完全路径，如(1)； 双向连通图：双向连通图：任一对顶点存在两条有向路任一对顶点存在两条有向路 径相互连通，如径相互连通，如(4)； 其他其他：如如(2)， (3) 。循环比赛的结果循环比赛的结果竞赛图竞赛图竞赛图的性质竞赛图的性质1、必存在完全路径（可以用归纳法证明）2、若存在唯一的完全路径，则由它确定的顶点 顺序与按得分排列的顺序一致，如(1) 。注：这里顶点的的得分数指由它按箭头方向引出的边的数目。显然性质性质2只给出了完全路径图的名次排列方法只给出了完全路径图

5、的名次排列方法，所以下面对双向连通图进行讨论。双向连通竞赛图的名次排序双向连通竞赛图的名次排序 3个顶点的双向连通竞赛图，用两种方法排名所得的结果相同。下面讨论n3的情况。 为了用代数方法进行研究，定义竞赛图的邻接矩阵邻接矩阵A=（ ）nn如下： 存在从顶点i到j的有向边 否则根据右图可以得到（4）的邻接矩阵如下：ija01ija0001100011000110A1234(4)（1）（2）若记顶点的得分向量为Tnssss).,(21?其中 是顶点i的得分，则由公式（1）可知道：Si正如前面所分析的，由正如前面所分析的，由S无法排除全部名次。无法排除全部名次。记 称为1级得分向量，进行下一步计算

6、。 ， 称为2级得分向量。每个球队的2级得分是他战胜其他各个球队的得分之和，比1级得分向量更有理由作为名次排列的依据。根据(2)，(3)式可知图(4)的得分向量是：（3）TAs)1.1 , 1(1, 1TAs)1 , 1 ,2,2(1 ?) 1 (ss)1()2(Ass)2(s对于图(4),已知 , 。继续这个程序，得到k级得分向量， 。对于图(4)有：1) 1()(kkkAAssTTss)3,3,5,5(,)3,2,3,3()4()3(TTss)8 , 5 , 8 , 9(,)5 , 3 , 6 , 8()6()5(TTss)13,9 ,17,21(,)9 ,8 ,13,13()8()7(T

7、s)2 , 1 , 2 , 3()2(?Ts) 1 , 1 , 2 , 2() 1 (k越大，用越大，用 作为排名次的依据越合理作为排名次的依据越合理，如果 时， 收敛于某个极限得分向量极限得分向量，那么就可用这个极限得分向量作为排名次的依据。)(ks)(ksk那么极限得分向量是否存在呢？答案是肯定的。答案是肯定的。对于n(3)个顶点的双向连通竞赛图，存在正整数r，使邻接矩阵A 满足 0，A称素阵素阵。再利用在第一节里面学过的配朗配朗弗罗比尼斯定理弗罗比尼斯定理，素阵素阵A的最大特征根为正单根的最大特征根为正单根 ，对应正特征向量，对应正特征向量s，且且有有： ，与 比较可知，k级得分向量 ，当 时(归一化后)将趋向A的最大特征根的特征向量s，s就是作为排名次依据的极限得分向量。rAsAkkk1lim1) 1()(kkkAAss)(ksk用所得的结论来解题用所得的结论来解题1234(4)0001100011000110ATs)140. 0 ,150. 0 ,113. 0 ,231. 0 ,164. 0 ,238. 0 (232. 2?所以根据Si的大小来排名次，排出的名次为1，2，4，3最大的特征值对应特征向量现在对最开始所求的问题进行求解：现在对最开始所求的问题进行求解：123456000100100100110000001010111