北京化工大学：《数学建模》课程教学资源（课件讲稿）第五章 图论模型 第二节 循环比赛的名次

§2循环比赛的名次 6支球队比赛结果 ·n支球队循环赛，每场比赛 只计胜负，设有平局。 根据比赛结果排出各队名次

•n支球队循环赛，每场比赛 只计胜负，没有平局。 •根据比赛结果排出各队名次 1 2 3 4 5 6 6 支 球 队 比 赛 结 果 §2 循环比赛的名次

方法1： 寻找按箭头方向通过全部顶点的路径。 312456 146325 无法排名 方法2：计算得分：1队胜4场，2,3队各胜 3场，4,5队各胜2场，6队胜1场。 2,3队，4,5队无法排名 3→2,4→5 排名132456合理吗

方法2：计算得分：1队胜4场，2, 3 队各胜 3场，4, 5队各胜2场， 6队胜1场。 2, 3队， 4, 5队无法排名 3®2，4 ®5 排名 132456 合理吗 寻找按箭头方向通过全部顶点的路径。 312456 146325 … … 无法排名 方法1：

循环比赛的结果一竞赛图 每对顶点间都有边相连的有向图 3个顶点的竞赛图 (2) 名次1,2,3} {1,2,3)}并列

1 2 3 (1) 1 2 3 (2) 循环比赛的结果— — 竞赛图 每对顶点间都有边相连的有向图 3个顶点的竞赛图 名次 {1，2，3} {(1,2,3)}并列

4个顶点的竞赛图 (1) (2) 名次 {1,2,3,4} {2,1,3,4)} {1,3,4),2 {1,2),(3,4}{1,2,3,4}?

1 2 4 3 (1) 1 2 4 3 (2) 1 2 4 3 (3) 1 2 4 3 (4) {1, 2, 3, 4} {2,(1,3,4)} {(1,3,4), 2} 4个顶点的竞赛图 名次 {(1,2),(3,4)} {1, 2, 3, 4}?

2 竞赛图的3种形式 ·具有唯一的完全路径，如(1)；4 (4) ·双向连通图—任一对顶点存在两条有 向路径相互连通，如(4)； ·其他，如(2)，(3)

1 2 4 3 (1) 1 2 4 3 (2) 1 2 4 3 (3) 1 2 4 3 (4) 竞赛图的3种形式 •具有唯一的完全路径，如(1)； •双向连通图— — 任一对顶点存在两条有 向路径相互连通，如(4)； •其他，如(2)， (3)

竞赛图的性质 必存在完全路径； 若存在难一的完全路径，则由它确定的顶 点顺序与按得分排列的顺序一致，如()。 双向连通竞赛图G=(V,目的名次排序 邻接矩阵 0 1 1,,y,∈E 0 0 1 01 A 0 a 0 1 0,vv,庄E 0 00 0

竞赛图的性质 •必存在完全路径； •若存在唯一的完全路径，则由它确定的顶 点顺序与按得分排列的顺序一致，如(1) 。 î í ì Ï Î = v v E v v E a i j i j ij 0, 1, 1 2 4 3 (4) 双向连通竞赛图G=(V,E)的名次排序 邻接矩阵 ú ú ú ú û ù ê ê ê ê ë é = 1 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 A

得分向量 S=（(S1,S2,…,Sn) s=Ae,e=(1,1,…,1) s=Ae=(2,2,1,1)'~1级得分向量 s2)=As0=(3,2,1,2)'~2级得分向量 s6)=(3,3,2,3)7,s4=(5,5,3,3) s6)=(8,6,3,5),s6= (9,858) s7)=(13,13,8,9)7,s8)=(21,17,9,13) s()=As -=Ae k>0,s)→？

T s = Ae , e = (1,1,L,1) s (1) = Ae = (2,2,1,1) T ~ 1级得分向量 s ( 2) = As(1) = (3,2,1,2) T ~ 2级得分向量 T n s (s ,s , ,s ) 得分向量 = 1 2 L T T s (3,3,2,3) , s (5,5,3,3) (3) ( 4 ) = = s As A e k k k = = ( ) ( -1) , ? k ® ¥ s (k ) ® T T s (8,6,3,5) , s (9,8,5,8) (5) (6) = = LL T T s (13,13,8,9) ,s (21,17,9,13) (7 ) (8) = =

双向连通竞赛图的名次排序 s)=As=Ae ·府于(>3)个顶点的双向连通竞赛图，存在 正整数r,使邻接矩阵A满足A「>O,A称素阵 ·素阵A的最火特征根为正单 A'e lim 根入，对应正特征向量5，且 k oo k→>o,s(归一化局→s 用排名

双向连通竞赛图的名次排序 •对于n(>3)个顶点的双向连通竞赛图，存在 正整数r，使邻接矩阵A 满足Ar >0，A称素阵 s A e k k k = ® ¥ l lim •素阵A的最大特征根为正单 根l，对应正特征向量s，且 s As A e k k k = = ( ) ( -1) k s s ® ¥, (k ) (归一化后) ® 用s排名

0 0 0 01 A- 0 0 0 (4) 1 0 0 0 {1,2,3,42 2=1.4 s=(0.323,0.280,0.167.0.230) 排名为1,2,4,3}

ú ú ú ú û ù ê ê ê ê ë é = 1 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 A 排名为{1，2，4，3} T s (0.323,0.280,0.167,0.230) 1.4, = l = 1 2 4 3 (4) {1, 2, 3, 4}?

6支球队比赛结果 6 0 10111 0 00111 0 10100 A 00001 001 001 001 000

úúúúúúúûù êêêêêêêëé = 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 1 1 1 0 1 0 1 1 1 A 1 2 3 4 5 6 6 支球队 比赛结果