循环比赛的名次.ppt

《循环比赛的名次.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、离散模型：循环比赛的名次问题若干球队参加循环比赛，各队两两交锋，每场比赛只计胜负，不计比分，且不允许平局，循环比赛结束后怎样根据结果排名次呢？直观表示：用图的顶点表示球队，连接两个顶点的、以箭头标明方向的边表示比赛结果。6支球队比赛结果图由图可知：1队胜2，4，5，6队，负于3队；5队胜3，6队，负于1，2，4队。解决办法法一：顺着箭头方向寻找一条通过6个点的路径；（缺点：路径不唯一312456或146325等）法二：计算得分，即每队获胜场次；（缺点：得分相同无法判断（433221））法三：图论知识解决。有向图：每条边上标出方向的图；竞赛图：每对顶点之

2、间有一边相连的有向图（只计胜负，无平局）如何由竞赛图排出名次呢？3个顶点（不考虑顶点的标号）图（1）的名次：{1，2，3}；图（2）的三队名次相同。4个顶点(1)有唯一的通过全部顶点的有向路径名次为(2)点2排第一，其余三点名次相同，名次为(3)点2排最后，其余三点名次相同，名次为(4)有不止一条完全路径：名次为图(4)具有图(1)-(3)没有的性质：对于任何一对顶点，存在两条有向路径，使两顶点相互连通，这种图称为双向连通的。5个顶点以上的竞赛图基本类型仍为3种：第1种类型：有唯一完全路径的竞赛图，如(1)；第2种类型：双向连通竞赛图，如(4)；第3种

3、类型：不属于以上类型，如(2)(3)。双向连通竞赛图的名次排序定义竞赛图的邻接矩阵其中图(4)的邻接矩阵为记顶点的得分向量为其中是顶点的得分，则图(4)的得分向量为1级得分向量：2级得分向量：继续下去，得k级得分向量：2级得分是他战胜的各个球队的（1级）得分之和当时，收敛于某个极限得分向量（应归一化），以它作为排名次的依据。Perron-Frobenius定理：素阵的最大特征根为正单根，对应正特征向量，且有图(4)中，名次排序为素阵对于n（>3）个顶点的双向连通竞赛图，存在正整数r，使得邻接矩阵A满足Ar>0,这样的A称为素阵。6支球队循环比赛结果邻接

4、矩阵各级得分向量名次为MATLAB求解：[v,d]=eig(A)