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

这篇具有很好参考价值的文章主要介绍了【数学建模】离散模型（循环比赛的名次）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

根据比赛结果排名次的一个方法是在图中顺箭头方向寻找一条通过全部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}$ ，如下：
$a_{i j}=\left\{\begin{array}{l} 1, \text { 存在从顶点 } i \text { 到 } j \text { 的有向边 } \\ 0, \text { 否则 } \end{array}\right.\\ \boldsymbol A=\begin{bmatrix} 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 \end{bmatrix}$
若及顶点的得分向量为 $\boldsymbol s=(s_1,s_2,...,s_n)^T$ ，其中 $s_i$ 是顶点 $i$ 的得分，则不难知道：
$\boldsymbol s=\boldsymbol A \boldsymbol 1, \quad \boldsymbol 1=(1,1, \cdots, 1)^{\mathrm{T}}$
记 $s=s^{(1)}$ ，称为1级得分向量，进一步计算2级得分向量：
$s^{(2)}=\boldsymbol As^{(1)}$
进而得到 $k$ 级得分向量。
如果 $\rightarrow \infty$ （归一化后）， $s^{(k)}$ 收敛于某个极限得分向量，那么就可以用这个向量作为排名次的依据。