循环比赛排名模型
2019-01-23 本文已影响30人
萍水间人
问题如下，循环比赛排名，各队伍两两交锋，假设每场比赛只记胜负，不记得分，在比赛结束之后如何排名？
双向联通竞赛图一定能够排名
如题
如图
初始每个队伍记为1
经过一次计算之后，得到的序列为 2 2 1 1，即胜了多少场
再做一次计算， 即每个队伍的得分为他战胜的队伍的分数累加
为 3 2 1 2
第0次： 1 1 1 1
第1次： 2 2 1 1
第2次： 3 2 1 2
第3次： 3 3 2 3
第4次： 5 5 3 3
第5次： 8 6 3 5
这时候的数据已经能够排名了
当迭代次数越高，名次排序也越稳定，可将其较高的得分作为排名的依据，对其他双向连通竞赛图也可以采用类似的方法计算得到。
其实还有一种更为简便的方法
定理
只需要求出双向连通竞赛图的最大特征值的特征向量，通过特征向量进行排名。
结果
对于非双向连通竞赛图而言，则没有此结论
举例
