【数学建模】离散模型（循环比赛的名次）

问题描述

• 若干支球队参加单循环比赛，各队两两交锋，假设每场比赛只计胜负，不计比分，且不允许平局。在循环赛结束后怎样根据他们的比赛结果排列名次呢？
• 一种表述比赛结果的办法是，用图的顶点表示球队，用连接两个顶点的、有方向的边表示两支球队的比赛结果，如下图，1队战胜2，4，5，6队，而输给了3队。
  

问题分析

• 根据比赛结果排名次的一个方法是在图中顺箭头方向寻找一条通过全部6个顶点的路径，如3->1->2->4->5->6，于是3队为冠军，1队为亚军等等。但是还可以找出其他路径，如1->4->6->3->2->5，所以用这种方法显然不能决定谁是冠亚军。
• 另一个办法是计算得分，即每支球队获胜的场次，但如果场次相同则便无法进行排序。

竞赛图及其性质

• 每对顶点之间都有一条边相连的有向图称为竞赛图。
  
• 4个顶点的竞赛图共有4种形式：
  (1) 有唯一的通过全部顶点的有向路径 1->2->3->4，这种路径称为 完全路径；4个队的得分为 (3,2,1,0)，名次排序为{1,2,3,4}。
  (2) 点2应排第一，4个队的得分为 (1,3,1,1)，名次排序为{2,(1,3,4)}。
  (3) 同理，名次排序为{(1,3,4),2}。
  (4) 有不止一条完全路径，此为研究的重点。具有性质：对于任何一对顶点，存在两条有向路径，使两顶点可以相互连通，这种有向图称为双向连通的。
• 一般的 $n$ 个顶点的竞赛图具有以下性质：
  1）竞赛图必存在完全路径；
  2）若存在唯一的完全路径，则由完全路径确定的顶点的顺序，与按得分多少排列的顺序相一致。

双向连通竞赛图的名次排序

• 定义竞赛图的邻接矩阵 $A={(a_{ij})}_{n\times n}$，如下：
  $$\begin{gathered} a_{ij}=\{\begin{array}{l}1,\text{ 存在从顶点 }i\text{ 到 }j\text{ 的有向边 }\\ 0,\text{ 否则 }\end{array} \\ \mathbf{A}=\left[\begin{array}{cccc}0& 1& 1& 0\\ 0& 0& 1& 1\\ 0& 0& 0& 1\\ 1& 0& 0& 0\end{array}\right] \end{gathered}$$
• 若及顶点的得分向量为 $\mathbf{s}=(s_1,s_2,...,s_n{)}^T$，其中 $s_i$ 是顶点 $i$ 的得分，则不难知道：
  $$\mathbf{s}=\mathbf{A}1,1=(1,1,\cdots ,1{)}^{\mathrm{T}}$$
• 记 $s=s^{(1)}$，称为1级得分向量，进一步计算2级得分向量：
  $$s^{(2)}=\mathbf{A}{s}^{(1)}$$
  进而得到 $k$ 级得分向量。
• 如果 $k\to \infty$（归一化后），$s^{(k)}$ 收敛于某个极限得分向量，那么就可以用这个向量作为排名次的依据。