第十章 足球队排名问题(I)_竞赛图法.pptVIP

* * 表10-1(P_182) 给出我国12支球队在1988-1989年全国足球甲级联赛中的成绩,要求 (1)设计一个依据这些成绩排出诸名次的算法,并给出用该算法排名次的结果 (2)把算法推广到任意个队的情况 (3)讨论数据应具备什麽样的条件,用你的方法才能够排出诸队的名次 10 足球队排名问题 应用: 循环比赛的名次 n支球队循环赛，每场比赛只计胜负，没有平局。 根据比赛结果排出各队名次 1) 竞赛图法 完全图的定向图 G=(V,E) ---- 竞赛图 方法1：顺箭头方向寻找通过全部顶点的一条路径。 1 2 3 4 5 6 312456 146325 方法2：计算得分：1队胜4场，2, 3队各胜3场，4, 5队各胜2场， 6队胜1场。 无法排名 2, 3队， 4, 5队无法排名 6支球队比赛结果 …… 3?2，4 ?5 排名 132456 合理吗 例 1 2 3 (1) 1 2 3 (2) 1 2 3 4 (1) 1 2 3 4 (2) 1 2 3 4 (3) 1 2 3 4 (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}? 1 2 3 4 1 2 3 4 1 2 3 4 (1) (2) (3) 1 2 3 4 (4) 竞赛图的3种形式 具有唯一的完全路径，如(1)； 双向连通图——任一对顶点存在两条有向路径相互连通，如(4)； 其他，如(2)， (3) 。 竞赛图的性质 必存在完全路径； 若存在唯一的完全路径，则由它确定的顶点顺序与按得分排列的顺序一致，如(1) 。 1 2 3 4 (4) 双向连通竞赛图G=(V,E)的名次排序 邻接矩阵 得分向量 双向连通竞赛图的名次排序 对于n(3)个顶点的双向连通竞赛图，存在正整数r，使邻接矩阵A 满足Ar 0，A称素阵 素阵A的最大特征根为正单根?，对应单位正特征向量s，且 排名为{1，2，4，3} 用s排名 1 2 3 4 (4) {1, 2, 3, 4}? 1 2 3 4 5 6 6支球队比赛结果 排名次序为{1，3， 2，5，4，6} 一般竞赛图排名问题的算法： 当竞赛图既没有唯一完全路径，又不是双向连通图时，通常可以 将它分解为若干个双向连通的子竞赛图（只有一个顶点的 图可视为双向连通竞赛图的 特例）； 每个双向连通子图内的名次按其极限得分向量排名； 双向连通子图间的名次则由连接它们的边的方向决定. 2 1 3 4 5 6 7 8 一个分解成三个双向连通子图的例子 足球队排名的竞赛图方法： (1) 根据建边情况建立矩阵 (2) 计算得分向量 , 二级得分向量 以 为尾的边的数目 被 打败的球队的得分之和 (3) 完善邻接矩阵 (4) 根据邻接矩阵得到竞赛图 如果 与 之间没有边连接, 比较 与 若 , 建立边 若 , 建立边 若 , 比较 与