循环比赛的名次.ppt

循环比赛的名次?n支球队循环赛,每场比赛只计胜负,没有平局。?根据比赛结果排出各队名次方法 1:寻找按箭头方向通过全部顶点的路径。 12345 6312456 146325 方法 2:计算得分: 1队胜 4场, 2, 3 队各胜 3场, 4, 5 队各胜 2场, 6队胜 1场。无法排名 2, 3 队, 4, 5 队无法排名 6支球队比赛结果…… 3?2,4 ?5 排名 132456 合理吗 1 23 (1)1 23 (2) 1234 (1) 1234 (2) 1234 (3) 1234 (4) 循环比赛的结果——竞赛图每对顶点间都有边相连的有向图 3个顶点的竞赛图名次{1,2,3} {(1,2,3)} 并列{1, 2, 3, 4} {2,(1,3,4)} {(1,3,4), 2} 4个顶点的竞赛图名次{(1,2),(3,4)} {1, 2, 3, 4}? 1234 1234 1234 (1) (2) (3) 1234 (4) 竞赛图的 3种形式?具有唯一的完全路径,如(1) ; ?双向连通图——任一对顶点存在两条有向路径相互连通,如(4) ; ?其他,如(2) , (3) 。竞赛图的性质?必存在完全路径; ?若存在唯一的完全路径,则由它确定的顶点顺序与按得分排列的顺序一致,如(1) 。 Te Ae s)1,,1,1(,???级得分向量 1~)1,1,2,2( )1(T Ae s??级得分向量 2~)2,1,2,3( )1()2(T As s???????????????0001 1000 1100 0110A ??????Evv Evva ji ji ij,0 ,1 1234 (4) 双向连通竞赛图 G=( V,E )的名次排序邻接矩阵 Tnssss),,,( 21??得分向量 T Tss)3,3,5,5(,)3,2,3,3( )4( )3(??eA As s kkk???)1()(?, )(??? ksk T Tss)8,5,8,9(,)5,3,6,8( )6( )5(???? T Tss) 13 ,9, 17 , 21 (,)9,8, 13 , 13 ( )8( )7(??双向连通竞赛图的名次排序?对于 n (>3) 个顶点的双向连通竞赛图,存在正整数 r,使邻接矩阵 A 满足 A r >0 ,A称素阵 s eA k kk???? lim ?素阵 A的最大特征根为正单根?,对应正特征向量 s,且