图论与网络模型及其应用 (二 )
循环比赛的名次若干支球队参加单循环比赛,他们两两互相交锋,假设每场比赛只计胜负,且不允许平局,在循环比赛结束后怎样根据他们的比赛成绩排列名次?
考虑用点表示球队,胜负用带箭头的弧表示,如 1队胜 2队,表示为,
12
12
63
54
如图,1胜 4场,2,3各胜 3场,4,5各胜 2
场,6队胜 1场,
2,3名难产,4,5名难产,
有向图,在每条边上都标出方向的图,
竞赛图,每对顶点之间都有一条边相连的有向图,
两个顶点的竞赛图的排名不成问题,
三个顶点的竞赛图只有两种形式,
四个顶点的竞赛图只有四种形式,
通过全部顶点的有向路径称为完全路径,
有唯一完全路径的竞赛图,此完全路径确定的顶点的顺序与按得分多少排列的顺序是一致的,
对于任何一对顶点,存在两条有向路径 (每条路径由一条或几条边组成 ),使两顶点可以互相连通,这种有向图称为 双向连通的,
双向连通竞赛图的名次排序,
.
,0
,1
)(
的有向边到从顶点否则存在定义为竞赛图的邻接矩阵
ji
a
aA
ij
nnij
如对图
0001
1000
1100
0110
A
1
2
34
.
,),...,( 21
的得分是顶点其中若顶点的得分向量为
is
ssss
i
T
n?
TeAes )1,.,.1,1(,则
,( 2,2,1,1 ) Ts?对 上 图
,.,,)2,1(,)1()()1( keAAssss kkk记
k 级得分向量
,.,.)9,8,13,13(,)8,5,8,9(
,)5,3,6,8(,)3,3,5,5(
,)3,2,3,3(,)2,1,2,3(
)7()6(
)5()4(
)3()2(
TT
TT
TT
ss
ss
ss
.
.?,)(
作为排名的得分向量把时当
s
ssk k
这种得分向量体现的什么样的排名原理?
Perron-Frobenius定理若存在正整数 r,使得 A满足 Ar>0,称 A为 素阵,
而且 n>3时,双向连通竞赛图的邻接矩阵一定为素阵,
.lim
,,
s
eA
sA
k
k
k
且有对应正特征向量的最大特征根为正单根素阵
.3,4,2,1
)230.0,167.0,280.0,323.0(,4.1:
从而确定名次排列为上例 s
由于 4胜了强队 1,虽然输给了 3,我们还是认为 4
队更强些,
对我们开始提到的六各队的单循环比赛结果,可以看出这个竞赛图是双向连通的,其邻接矩阵为
000100
100100
110000
001011
111000
111010
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)讨论,数据应具备什么样的条件,用你的方法才能排出诸队的名次,
足球队比赛成绩,
T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12
T1 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
T2 2:0
0:1
1:3
0:0
2:0
0:0
1:1 2:1 1:1 0:0 2:0 0:2
T3 4:2
1:1
0:0
2:1 3:0 1:0 0:1 1:0 0:1
T4 2:3 0:1 0:5
2:3
2:1
1:3
0:1
0:0
0:1
1:1
T5 0:1 1:0
1:2
0:1
1:1
T6
T7
T8
1:2 1:1
T6
T7 1:0
2:0
0:0
2:1
3:0
1:0
3:1
3:0
2:2
3:1 2:0
T8 0:1
1:2
2:0
1:1
1:0
0:1
3:1 0:0
T9 3:0
1:0
0:0
1:0 1:0
T10 1:0 2:0
T11 1:1
1:2
1:1
T12
从表上成绩看,数据是不整齐的,某些队之间有三场比赛的成绩,另外某些队之间则只有两场或一场比赛的成绩,
还有一些队之间没有比赛成绩,
(一篇特等奖的论文简介 )
1.合理的假设
(1)排名仅根据现有的比赛结果,不考虑其他因素,
(2)每场比赛对于估计排名的重要程度是一样的,
具有相同的可信度,不同的比赛相互独立,
(3)有些队之间没有比赛,完全是由于比赛安排的原因,不是由于球队在以前比赛的胜负造成的,
2.问题的分析目前足球比赛的排名或者是联赛制的,或者是同一场赛事,
本题的关键是数据不完整,按简单的积分不能准确给出每队的名次,特别这些数据可能有在比赛中避开强队的情况,
处理数据的残缺是解决问题的关键,
3.初步的排名方案模型 1 (总积分法 ) 按两分制计算各队在所有比赛中的总的积分,给出各队的名次,
T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12
积分 24 16 19 8 6 4 29 16 17 18 4 8
名次 2 6 3 8 10 11 1 6 5 4 11 8
这样的排名由于比赛场次的多少不同,显然是不能很好反应各队的水平,
下面改用平均积分法,
模型 2 (平均积分法 ) 将每队的总积分除以该队参加比赛的场数,
T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12
平均积分
1.33
3
1.07 1.2
07
0.4
21
0.66
6
0.8 1.70 0.9 1 1.06 0.44
4
0.88
88
名次 2 4 3 12 10 9 1 7 6 5 11 8
模型 3 (特征向量法 )
得分矩阵 A的构造,
.0.
,)( 1212
ijji
jiijij
aTT
TTaaA
没有比赛过时取与当算出的平均得分各场比赛按二分制对是其中得分矩阵只反应了两队成绩的差,存在一定的不准确性,
0
3
4
00100
2
3
0000
3
2
00000010000
220
3
1
1
3
1
00
2
1
221
22
3
5
0
3
4
000
2
1
000
121
3
2
0
3
1
001211
22
3
5
2
3
5
0002012
000000022000
2
1
10000002010
00
2
1
2
1
10000
3
2
3
2
0
00020222
3
4
0
3
4
1
00021121
3
4
3
2
01
001210222110
A
)0(
,)(
1212
a
aa
aa
b
bB
ji
ij
ij
ij
其中水平比矩阵
.
lim
:
的最大特征值为此时积分向量为
B
eB
X
m
m
m
利用 mathematica数学软件可以计算
T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12
名次 2 4 3 12 9 8 1 7 6 5 11 10
T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12
平均积分
1.33
3
1.07 1.2
07
0.4
21
0.66
6
0.8 1.70 0.9 1 1.06 0.44
4
0.88
88
名次 2 4 3 12 10 9 1 7 6 5 11 8
经计算,水平比矩阵的特征向量排名为
循环比赛的名次若干支球队参加单循环比赛,他们两两互相交锋,假设每场比赛只计胜负,且不允许平局,在循环比赛结束后怎样根据他们的比赛成绩排列名次?
考虑用点表示球队,胜负用带箭头的弧表示,如 1队胜 2队,表示为,
12
12
63
54
如图,1胜 4场,2,3各胜 3场,4,5各胜 2
场,6队胜 1场,
2,3名难产,4,5名难产,
有向图,在每条边上都标出方向的图,
竞赛图,每对顶点之间都有一条边相连的有向图,
两个顶点的竞赛图的排名不成问题,
三个顶点的竞赛图只有两种形式,
四个顶点的竞赛图只有四种形式,
通过全部顶点的有向路径称为完全路径,
有唯一完全路径的竞赛图,此完全路径确定的顶点的顺序与按得分多少排列的顺序是一致的,
对于任何一对顶点,存在两条有向路径 (每条路径由一条或几条边组成 ),使两顶点可以互相连通,这种有向图称为 双向连通的,
双向连通竞赛图的名次排序,
.
,0
,1
)(
的有向边到从顶点否则存在定义为竞赛图的邻接矩阵
ji
a
aA
ij
nnij
如对图
0001
1000
1100
0110
A
1
2
34
.
,),...,( 21
的得分是顶点其中若顶点的得分向量为
is
ssss
i
T
n?
TeAes )1,.,.1,1(,则
,( 2,2,1,1 ) Ts?对 上 图
,.,,)2,1(,)1()()1( keAAssss kkk记
k 级得分向量
,.,.)9,8,13,13(,)8,5,8,9(
,)5,3,6,8(,)3,3,5,5(
,)3,2,3,3(,)2,1,2,3(
)7()6(
)5()4(
)3()2(
TT
TT
TT
ss
ss
ss
.
.?,)(
作为排名的得分向量把时当
s
ssk k
这种得分向量体现的什么样的排名原理?
Perron-Frobenius定理若存在正整数 r,使得 A满足 Ar>0,称 A为 素阵,
而且 n>3时,双向连通竞赛图的邻接矩阵一定为素阵,
.lim
,,
s
eA
sA
k
k
k
且有对应正特征向量的最大特征根为正单根素阵
.3,4,2,1
)230.0,167.0,280.0,323.0(,4.1:
从而确定名次排列为上例 s
由于 4胜了强队 1,虽然输给了 3,我们还是认为 4
队更强些,
对我们开始提到的六各队的单循环比赛结果,可以看出这个竞赛图是双向连通的,其邻接矩阵为
000100
100100
110000
001011
111000
111010
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)讨论,数据应具备什么样的条件,用你的方法才能排出诸队的名次,
足球队比赛成绩,
T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12
T1 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
T2 2:0
0:1
1:3
0:0
2:0
0:0
1:1 2:1 1:1 0:0 2:0 0:2
T3 4:2
1:1
0:0
2:1 3:0 1:0 0:1 1:0 0:1
T4 2:3 0:1 0:5
2:3
2:1
1:3
0:1
0:0
0:1
1:1
T5 0:1 1:0
1:2
0:1
1:1
T6
T7
T8
1:2 1:1
T6
T7 1:0
2:0
0:0
2:1
3:0
1:0
3:1
3:0
2:2
3:1 2:0
T8 0:1
1:2
2:0
1:1
1:0
0:1
3:1 0:0
T9 3:0
1:0
0:0
1:0 1:0
T10 1:0 2:0
T11 1:1
1:2
1:1
T12
从表上成绩看,数据是不整齐的,某些队之间有三场比赛的成绩,另外某些队之间则只有两场或一场比赛的成绩,
还有一些队之间没有比赛成绩,
(一篇特等奖的论文简介 )
1.合理的假设
(1)排名仅根据现有的比赛结果,不考虑其他因素,
(2)每场比赛对于估计排名的重要程度是一样的,
具有相同的可信度,不同的比赛相互独立,
(3)有些队之间没有比赛,完全是由于比赛安排的原因,不是由于球队在以前比赛的胜负造成的,
2.问题的分析目前足球比赛的排名或者是联赛制的,或者是同一场赛事,
本题的关键是数据不完整,按简单的积分不能准确给出每队的名次,特别这些数据可能有在比赛中避开强队的情况,
处理数据的残缺是解决问题的关键,
3.初步的排名方案模型 1 (总积分法 ) 按两分制计算各队在所有比赛中的总的积分,给出各队的名次,
T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12
积分 24 16 19 8 6 4 29 16 17 18 4 8
名次 2 6 3 8 10 11 1 6 5 4 11 8
这样的排名由于比赛场次的多少不同,显然是不能很好反应各队的水平,
下面改用平均积分法,
模型 2 (平均积分法 ) 将每队的总积分除以该队参加比赛的场数,
T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12
平均积分
1.33
3
1.07 1.2
07
0.4
21
0.66
6
0.8 1.70 0.9 1 1.06 0.44
4
0.88
88
名次 2 4 3 12 10 9 1 7 6 5 11 8
模型 3 (特征向量法 )
得分矩阵 A的构造,
.0.
,)( 1212
ijji
jiijij
aTT
TTaaA
没有比赛过时取与当算出的平均得分各场比赛按二分制对是其中得分矩阵只反应了两队成绩的差,存在一定的不准确性,
0
3
4
00100
2
3
0000
3
2
00000010000
220
3
1
1
3
1
00
2
1
221
22
3
5
0
3
4
000
2
1
000
121
3
2
0
3
1
001211
22
3
5
2
3
5
0002012
000000022000
2
1
10000002010
00
2
1
2
1
10000
3
2
3
2
0
00020222
3
4
0
3
4
1
00021121
3
4
3
2
01
001210222110
A
)0(
,)(
1212
a
aa
aa
b
bB
ji
ij
ij
ij
其中水平比矩阵
.
lim
:
的最大特征值为此时积分向量为
B
eB
X
m
m
m
利用 mathematica数学软件可以计算
T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12
名次 2 4 3 12 9 8 1 7 6 5 11 10
T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12
平均积分
1.33
3
1.07 1.2
07
0.4
21
0.66
6
0.8 1.70 0.9 1 1.06 0.44
4
0.88
88
名次 2 4 3 12 10 9 1 7 6 5 11 8
经计算,水平比矩阵的特征向量排名为
