循环比赛排名分析

循环比赛的名次主讲：王茜6.2循环比赛排名模型•n支球队单循环赛，两两交锋.•每场比赛只计胜负，不计比分，没有平局。•根据比赛结果排出各队名次背景与问题1234566支球队比赛结果有向图（diagraph）1队胜4场；2队胜3场；3队胜3场；4队胜2场；5队胜2场；6队胜1场。无法排名？32，45排名132456合理吗？方法1：G=（V，E）53？1234566支球队比赛结果方法2：寻找按箭头方向通过全部顶点的路径。（哈密顿路或完全路径）312456146325无法排名……计算困难且不唯一！123(1)123(2)循环比赛的结果——竞赛图3个顶点的竞赛图:名次{1，2，3}{(1,2,3)}并列竞赛图：每对顶点间都有边相连的有向图。2个顶点的竞赛图:12得分（2，1，0）（1，1，1）1234(1)1234(2)1234(3)1234(4){1,2,3,4}{2,(1,3,4)}{(1,3,4),2}4个顶点的竞赛图:名次{(1,2),(3,4)}{1,2,3,4}?得分(3,2,1,0)(1,3,1,1)(2,0,2,2)(2,2,1,1)123412341234(1)(2)(3)1234(4)竞赛图的3种形式：•具有唯一的完全路径，如(1)；•双向连通图——任一对顶点存在两条有向路径相互连通，如(4)；•其他，如(2)，(3)。123412341234(1)(2)(3)1234(4)竞赛图的性质：•必存在完全路径；•若存在唯一的完全路径，则由它确定的顶点顺序与按得分排列的顺序一致，如(1)。TeAes)1,,1,1(,级得分向量1~)1,1,2,2()1(TAes0001100011000110AEvvEvvajijiij,0,11234(4)邻接矩阵Tnssss),,,(21得分向量双向连通竞赛图G=(V,E)的名次排序级得分向量1~)1,1,2,2()1(TAes级得分向量2~)2,1,2,3()1()2(TAss0001100011000110A1234(4)双向连通竞赛图G=(V,E)的名次排序TTss)3,3,5,5(,)3,2,3,3()4()3(eAAsskkk)1()(?,)(kskTTss)8,5,8,9(,)5,3,6,8()6()5(TTss)13,9,17,21(,)9,8,13,13()8()7(双向连通竞赛图的名次排序•对于n(3)个顶点的双向连通竞赛图，存在正整数r，使邻接矩阵A满足Ar0，A称素阵.seAkkklim•素阵A的最大特征根为正单根，对应正特征向量s，且eAAsskkk)1()(双向连通竞赛图的名次排序eAAsskkk)1()(0001100011000110A排名为{1，2，4，3}sskk)(,)(归一化后Ts)230.0,167.0,280.0,323.0(,3953.1用s排名1234(4){1,2,3,4}?seAkkklim000100100100110000001011111000111010ATTTTssss)16,25,21,32,28,38(,)9,12,7,16,10,15()3,4,3,9,5,8(,)1,2,2,3,3,4()4()3()2()1(1234566支球队比赛结果Ts)104.0,150.0,113.0,231.0,164.0,238.0(排名次序为{1，3，2，5，4，6},2324.22007年5月23到27日，第49届世界乒乓球单项锦标赛在萨格勒布进行，本次单项赛包括男、女单打、男、女双打和混双五个项目,共计可派出男女各12名选手。国家乒乓球球队在世乒赛等重大国际比赛前，往往进行队内大循环比赛，然后选出前几名队员直通。例1乒乓球循环比赛排名问题其中男单选拔规则如下：中国乒乓球男队的比赛共16人参加，比赛采用11分制，每场为5局3胜。在比赛中如出现伤病和其他不可预测的原因而中途退出比赛者，在此前的比赛成绩有效。根据规定，两次队内选拔赛积分相加获得前三名的运动员将获得参加第49届世乒赛男子单打比赛的资格，获得四至六名的运动员将获得第49届世乒赛的参赛资格。下面的表6.10和表6.11分别是两次大循环相互的比赛成绩，表格中1表示横向运动员赢了纵向运动员，反之则为0。请根据该成绩对所有对员进行排名。第一轮郝帅马琳张超王励勤王皓马龙陈玘雷振华李平单明杰张继科邱贻可王建军许昕李虎侯英超郝帅0010111111111111马琳1011011101001111张超0000011011111111王励勤1010100110111011王皓0110010110011111马龙0001001011110111陈玘0001100001101110雷振华0010011011001111李平0100001001111011单明杰0001100000011111张继科0100100101010001邱贻可0100001100001110王建军0000010000100111许昕0001000010100001李虎0000000000100100侯英超0000001000010010表6.10第一阶段循环比赛成绩第二轮郝帅马琳张超王励勤王皓马龙陈玘雷振华李平周斌张继科邱贻可王建军许昕李虎侯英超郝帅0111011011001011马琳0011101100111111张超0000001110001101王励勤0010111111101111王皓1010001101111111马龙0110101111111111陈玘0000000110011011雷振华1000000001100111李平0100100101011111周斌0110001000001000张继科1010001011011000邱贻可1011000101001110王建军0000000100000000许昕1000001001101011李虎0010000001101001侯英超0000000001111000表6.11第二阶段循环比赛成绩