图论与网络模型 及其应用(二 循环比赛的名次
图论与网络模型 及其应用(二) 循环比赛的名次
若干支球队参加单循环比赛,他们两两互相交锋,假 设每场比赛只计胜负且不允许平局在循环比赛结 束后怎样根据他们的比赛成绩排列名次? 考虑用点表示球队胜负用带箭头的弧表示,如1队 胜2队,表示为: 如图:1胜场,2,3各 胜3场,4,5各胜2 场,6队胜1场 2,3名难产,4,5名难
若干支球队参加单循环比赛,他们两两互相交锋,假 设每场比赛只计胜负,且不允许平局.在循环比赛结 束后怎样根据他们的比赛成绩排列名次? 考虑用点表示球队,胜负用带箭头的弧表示,如1队 胜2队,表示为: 1• •2 1• •2 6• •3 5• •4 如图:1胜4场,2,3各 胜3场,4,5各胜2 场,6队胜1场. 2,3名难产,4,5名难 产
有向图在每条边上都标出方向的图 竞赛图每对顶点之间都有一条边相连的有向图 两个顶点的竞赛图的排名不成问题 三个顶点的竞赛图只有两种形式: 四个顶点的竞赛图只有四种形式 通过全部顶点的有向路径称为完全路径
有向图:在每条边上都标出方向的图. 竞赛图:每对顶点之间都有一条边相连的有向图. 两个顶点的竞赛图的排名不成问题. 三个顶点的竞赛图只有两种形式: • • • 四个顶点的竞赛图只有四种形式: • • • • • • • • • • • • • • • • 通过全部顶点的有向路径称为完全路径
有唯一完全路径的竞赛图,此完全路径确定的顶 点的顺序与按得分多少排列的顺序是一致的 对于任何一对页点存在两条有向路径每条路径 由一条或几条边组成使两顶点可以互相连通,这 种有向图称为双向连通的 双向连通竞赛图的名次排序 竞赛图的邻接矩阵4=(a;)定义为 「1,存在从顶点到的有向边 -(0,否则
有唯一完全路径的竞赛图,此完全路径确定的顶 点的顺序与按得分多少排列的顺序是一致的. 对于任何一对顶点,存在两条有向路径(每条路径 由一条或几条边组成),使两顶点可以互相连通,这 种有向图称为双向连通的. 双向连通竞赛图的名次排序: . 0, 1, ( ) 从顶点 到 的有向边 否则 存在 竞赛图的邻接矩阵 定义为 i j a A a ij ij n n = =
如对图 3 0110 0001 1000 若顶点的得分向量为s=(s1,2…n)y,其中 s;是顶点得分 则 Ae,e=(1,1,…41) 对上图,s=(2,2,1,1)
• • • 如对图 • = 1 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 A 1 2 4 3 . ( , ,... ) , 1 2 是顶点 的得分 若顶点的得分向量为 其中 s i s s s s i T = n T 则 s = Ae, e = (1,1,...1) , (2,2,1,1) T 对 上 图 s =
记s=s(,s6)=As-1)=Ake(k=1,2, k级得分向量 这种得分向量体现的什 么样的排名原理? s(2)=(3,2,1,2),s6)=(3,3,2,3) s4)=(5,5,3,3),s6)=(8,6,3,5)1, s6)=(9.8,5,8),s)=(13,13,8,9)2, 当k→∞时,s(→?。S 把s作为排名的得分向量
, ( 1,2,...) (1) ( ) ( 1) = = = = − s s s As A e k 记 k k k k 级得分向量 (9,8,5,8) , (13,13,8,9) ,... (5,5,3,3) , (8,6,3,5) , (3,2,1,2) , (3,3,2,3) , (6) (7) (4) (5) (2) (3) T T T T T T s s s s s s = = = = = = . , ?. ( ) 把 作为排名的得分向量 当 时 sk s s → k → 这种得分向量体现的什 么样的排名原理 ?
若存在正整数r,使得4满足4>0,称4为素阵 而且n>3时,双向连通竞赛图的邻接矩阵一定 为素阵. Perron- Frobenius定理 素阵A的最大特征根为正单根λ,对应正特征向量s, 且有 lim ak S。 k→)∞ 上例:=14,s=(0.323,0280,0167,0230) 从而确定名次排列为1,2,4,3 由于4胜了强队1,虽然输给了3,我们还是认为4 队更强些
Perron-Frobenius定理 若存在正整数r,使得A满足Ar>0,称A为素阵. 而且n>3时,双向连通竞赛图的邻接矩阵一定 为素阵. lim . , , s A e A s k k k = → 且有 素阵 的最大特征根为正单根 对应正特征向量 1,2,4,3. : 1.4, (0.323,0.280,0.167,0.230) 从而确定名次排列为 上例 = s = 由于4胜了强队1,虽然输给了3,我们还是认为4 队更强些
对我们开始提到的六各队的单循环比赛结 果可以看出这个竞赛图是双向连通的其 邻接矩阵为 010111 000 00 000011 001001 001000 可以算出,其最大正特征值为2232,相应的 特征向量为 s=(0.238,0.164,0231,0113,0.150,0.104),因 些排名为1,3,2,5,4,6
对我们开始提到的六各队的单循环比赛结 果,可以看出这个竞赛图是双向连通的,其 邻接矩阵为 = 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 1 1 1 A 可以算出,其最大正特征值为2.232,相应的 特征向量为 s=(0.238,0.164,0.231,0.113,0.150,0.104)T ,因 此排名为1,3,2,5,4,6
足球比赛的排名问题 1993年全国大学生数学建模竞赛B题 下表给出了我国12支足球队在1988-1989年全国足 球甲级队联赛中的成绩,要求: (1)设计一个依据这些成绩排出诸队名次的算法并 给出用该算法排名次的结果 (2)把算法推广到任意N个队的情况 (3)讨论数据应具备什么样的条件用你的方法才能 排出诸队的名次 足球队比赛成绩:
足球比赛的排名问题 • 1993年全国大学生数学建模竞赛B题 下表给出了我国12支足球队在1988-1989年全国足 球甲级队联赛中的成绩,要求: (1)设计一个依据这些成绩排出诸队名次的算法,并 给出用该算法排名次的结果. (2)把算法推广到任意N个队的情况. (3)讨论:数据应具备什么样的条件,用你的方法才能 排出诸队的名次. 足球队比赛成绩:
3 T4 Ts T6 T T8 TT12 0:1222:03:11:00:10:21:01:1 1:01:03:1 1:32:14:01:1 0:0021:0 2:00:01:1211:10:02:002 0:120 1:30:0 421|2:13:01:00:11:00:1 1:1 0:0 2:30:10:52:10:10:1 231:30:01:1 0:1 1:00:1 1:21:1
T 1 T 2 T 3 T 4 T 5 T 6 T 7 T 8 T 9 T10 T11 T12 T 1 0:1 1:0 0:0 2:2 1:0 0:2 2:0 3:1 1:0 3:1 1:0 0:1 1:3 0:2 2:1 1:0 4:0 1:1 1:1 T 2 2:0 0:1 1:3 0:0 2:0 0:0 1:1 2:1 1:1 0:0 2:0 0:2 T 3 4:2 1:1 0:0 2:1 3:0 1:0 0:1 1:0 0:1 T 4 2:3 0:1 0:5 2:3 2:1 1:3 0:1 0:0 0:1 1:1 T 5 0:1 1:0 1:2 0:1 1:1 T 6 T 7 T 8