例如前述的5个选手进行乒乓球单循环赛比赛结果所对应的竞赛图d如图628d的邻接矩阵a以及可达性矩阵rr的算法见本节附录为s0编程序算到s32再由3132算出a的具有最大绝对值的特征值精确到0001的近似值r1859最后算出r对应的精确到0001的标准化特征向量208881000的分量可以看作反映5个选手线
解 容易验证，这12支球队的比赛是不可分的。按当时的惯例，在任何一场分出胜负的 比赛中，胜者得2分，负者不得分；两队打平，每队各得1分。 如果将第i队与第j队比赛的单场得分之和作为第i队的得分aij， 来构造得分矩阵A， 这样 会使比赛场次少的队吃亏。例如，假设甲队与乙队比赛了三场，都是平局，甲队将得3分。 丙队与乙队只比赛了一场，丙队获胜，丙队得2分。从比赛结果看，虽然丙队的水平比甲队 高，但丙队的得分却比甲队少。因此这样记分是不公平的。为了使记分尽量公平，可以采取 下面的记分方法。 设第i队与第j队共比赛了m场，第i队各场得分为 c1,c2,,cm ，令
则称aij为i，j两队比欧洲杯直播赛中第i队的平均得分。由此构造出比赛的平均得分矩阵A=（aij）1212 如下
到一定精确度的r的近似值。 这时可令特征向量s≈si， 我们就用s的标准化向量 s
分量分别作为D的各顶点的得分，称为各顶点的水平分。按水平分的大小次序排定各顶点的
四个顶点的竞赛图在同构意义下只有如图6.27的四个。 v1 v1 v1 v v4
图6.27 图6.27 (a)的排名为：v4第一，其余三个顶点并列第二。 图6.27 (b)的排名为：v4第四，其余三个顶点并列第一。 图6.27 (c)的排名顺序为：v1，v4，v3，v2。 图6.27 (d)是一个双向连通的竞赛图，名次无法立即排出。 对于四个或四个以上顶点的双向连通的竞赛图，我们用图论的知识给出以下排名方法。 定义6.12 包含有向图D的所有顶点的有向路称为D的有向哈密顿路，简称有向H路。包 含D的所有顶点的有向圈称为D的有向哈密顿圈，简称有向H圈。 有向图D的一条有向H路上各顶点的次序就是D的各顶点的一个排名顺序。任意有向图D 是否具有有向H路呢？不一定。 但是竞赛图一定具有有向H路， 这是根据图论中如下定理确定 的。 定理6.6 任意竞赛图都具有有向H路。 如果某竞赛图仅有一条有向 H 路，那么各顶点的名次就可以按此路上各顶点的顺序确 定。例如图 6.27 (c) 中四个顶点的名次就是这样排定的。但是当竞赛图具有不止一条有向 H 路，即具有有向 H 圈时，例如图 6.27 中的图(d)，这种方法就不适用了，必须用下述方法。 k k 定义6.13 设R为实数矩阵，若存在正整数k，使得R 的每个元素皆为正数，即R 0，则 称R是本原的。 定理6.7 当且仅当竞赛图D是双向连通的，且D的顶点数n≥4时，D的邻接矩阵A是本原 的。 定理6.8 设竞赛图D的邻接矩阵A是本原的， r是A的具有最大绝对值的特征值， 即A的譜 半径，则r0，且
将 D 的5个顶点按b,d,e,f,i的顺序排列，它的邻接矩阵正好是图6.28中的图D的邻接矩阵 2
名次。以上求譜半径的特征向量的方法称为乘幂法。 例如， 前述的5个选手进行乒乓球单循环赛， 比赛结果所对应的竞赛图D如图6.28,D的邻 接矩阵A以及可达性矩阵R（R的算法见本节附录）为 a
——竞赛图模型 目前正规的体育比赛有很多种赛制， 有单循环赛， 双循环赛， 分组循环赛和淘汰赛等等。 譬如乒乓球团体赛，预赛阶段通常采用分组循环赛，每个小组的第一名进入复赛。复赛的两 个小组的胜者进行决赛，决定冠军属于谁。而单打比赛，由于参赛人数较多，一般采用淘汰 赛。淘汰赛的名次是显而易见的，胜的场次越多名次越靠前，不败者为冠军。对于各种循环 赛的排名，要做到绝对公平合理，并不是那么容易。 我们先来看单循环赛的名次应该如何排定。例如有5个选手参加乒乓球单打比赛，比赛 是按单循环制进行。每场胜者得一分，负者得零分，5个选手分别用a,b,c,d,e表示，假定比 赛结果如下： a 胜 b,d,负于 c,e；b 胜 d,负于 c,e；c 负于 d,e；d 胜 e。 为了排出他们的名次， 我们计算出他们的得分依此是： 1， 2， 用向量s1=(2,1,2,2,3) 2， 2， 3， 表示他们的得分。如果按此得分排名次，则e第一，a,c,d并列第二，b第五。 这样排名是否合理呢？我们发现在三个并列第二的选手中，d负于得分最少的b，而a,c 均战胜了b，似乎d应排在这三人之尾。但是d虽然负于b，他却战胜了得分最高的e，而a和c 均负于了e，似乎d又应排在这三人之首。究竟应怎样排名才合理呢？ 为此， 我们把被某选手打败的所有选手得分之和作为该选手的第二级得分， 构造出第二 级得分向量s2=(3,2,3,5,5)， s2相当于每个选手的对手分。 如果按对手分排名， 则分不出d,e 的先后，也分不出a,c的先后。 再用被某选手打败的所有选手的第二级得分之和构造出第三级得分向量 s3=(7,5,5,8,8) ， s3 相 当 于 每 个 选 手 的 对 手 分 的 对 手 分 。 依 此 类 推 ， 构 造 出 s4=(13,8,12,13,17)，s5=(21,13,21,29,33)，s6=(42,29,34,54,55)。 s3 ，s4，s5中均出现某两个选手得分相同的情况，直到s6才出现各选手的得分都不相同， 依照得分从大到小有一个确定的次序。 但这个次序是否不会再改变呢？可以证明， 在一定条 件下当i趋于无穷大时，si的各分量将趋于一个固定的大小次序。下面介绍得出这一结论的 条件及采用的方法。 竞赛图及其排名 定义6.11 完全图的任意定向图称为竞赛图。 对于有n个选手参加的单循环赛， 如果用n个顶点表示n个选手， 凡是第i号选手战胜了第 j号选手，就从顶点vi向vj连一条有向边，这样就得到一个n个顶点的竞赛图。排定选手的名 次就等价于给竞赛图的各顶点排定名次。 我们先看两个顶点的竞赛图（如图6.26（a），有向边的尾的名次在前。三个顶点的竞 ） 赛图在同构意义下只有两个，如图6.26（b）和(c)；(b)图的排名顺序为：v2，v1，v3；(c) 图 的三个顶点名次相同。 v1
请排出从a——j的10位选手的名次。 解 分析矩阵B知，D含有四个极大双向连通子图，且它们的排列次序为
其中 D1 是三个顶点的双向连通图，所以顶点c,g,j的名次相同。 D 的顶点数不小于4，若 2
其中e是分量全为1的n维列向量，s是A的对应于r的一个非负特征向量。 由定理6.8计算s是一个极限过程， 一般很难求出s的各分量的精确值， 只能求其近似值， 方法如下（也是一种迭代法） ： 设n维列向量s0=(1,1,,1) ，
由R的元素全为1知D是双向连通的。用公式si=Asi-1=A s0编程序 算到s32，再由 r
图6.28 算出A的具有最大绝对值的特征值精确到0.001的近似值r=1.859，最
s 的分量可以看作反映5个选手真实水平的水平分。因此按他们的水平分由高到低排出的名
次是：e第一，d第二，a第三，c第四，b第五。 对于任意竞赛图D（不一定是双向连通的）排定名次的步骤如下： 1 给D的所有极大双向连通子图按优胜次序排列成 D1 ,D2 ,,Dm ，排在前面的子图名 次在前。排列原则如下，当ij时，凡是连接Di和Dj的有向边，其头都在Di中。 2 对于D的每个顶点数n≥4的极大双向连通子图， 用前面的乘幂法计算水平分， 排定子 图内各顶点的名次。 例6.1 有10个选手参加乒乓球单循环赛， 他们的比赛结果所对应的竞赛图D的邻接矩阵 为
本文由:欧洲杯体育用品官方提供