关于教材中双向连通竞赛图的排名方法的思考

秦小二

摘 要： 作者通过一个反例说明双向连通竞赛图的一种排名方法的局限性。

关键词： 双向连通竞赛图 排名 得分向量

若干支球队参加单循环比赛，各队两两交锋，假设每场比赛只计胜负，不计比分，在比赛结束后排名次。数学模型教材说比赛结果如果可以用双向连通竞赛图表示出来，就可以用该图对应的邻接矩阵A对应的最大特征根的特征向量s作为排名依据的得分向量。笔者经过研究发现，这种方法并不是对所有双向连通竞赛图都适用。

一、相关基础知识

定义：1：双向连通竞赛图：对于任何一对顶点，存在两条有向路径，使两顶点可以互相连通，这种有向图称为双向连通竞赛图。

定义2：对于n（n≥4）个顶点的双向连通竞赛图的邻接矩阵A，一定存在正整数r，使得A■>0，这样的A就称为素阵。

定理：Perron—Frobenius定理：素阵的最大特征根为正单根λ，λ对应正特征向量s，且有

■■=s？摇？摇？摇？摇？摇？摇？摇？摇（2）

二、应用举例

对一般性，记s■=A·e，s■=A·s■，…，s■=A·s■。则有：

s■=A·s■=A■·e（k=1，2，…）？摇？摇？摇？摇？摇？摇？摇？摇？摇？摇？摇？摇？摇（1）

当迭代次数越多，名次排定顺序越稳定。可将其较高级的得分作为排名依据。利用著名的Perron-Frobenius定理求出邻接矩阵A的最大特征根λ对应的正特征向量s，以s作为排名的依据。下面以4个队比赛结果的双向连通竞赛图为例说明如何应用这种方法。

图1 双向连通竞赛图

其对应的邻接矩阵为：

A=0？摇 1？摇 1？摇 00？摇 0？摇 1？摇 10？摇 0？摇 0？摇 11？摇 0？摇 0？摇 0

矩阵A的最大特征值及对应特征向量有：

λ■=1.3953，对应特征向量为（0.6256，0.5516，0.3213，0.4484）

我们容易得出其排名为：1->2->4->3。

三、应用反例

图2 5个顶点的双向连通竞赛图

其对应的邻接矩阵为：

0？摇 0？摇 1？摇 1？摇 11？摇 0？摇 0？摇 0？摇 00？摇 1？摇 0？摇 1？摇 00？摇 1？摇 0？摇 0？摇 10？摇 1？摇 1？摇 0？摇 0

矩阵A的最大特征值及对应特征向量有：

λ=1.8637，对应特征向量为（0.6394，0.3431，0.3972，0.3972，0.3972）

此例说明这种方法不是对所有双向连通竞赛图都适用，这种类型的图是无法排名的，从整体看3，4，5这三个顶点的实力相当。

参考文献：

[1]姜启源，谢金星，叶俊.数学模型（第三版）.北京：高等教育出版社，2003.8.

[2]刘来福等.数学模型与数学建模.北京师范大学出版社，1997.9.endprint

摘 要： 作者通过一个反例说明双向连通竞赛图的一种排名方法的局限性。

关键词： 双向连通竞赛图 排名 得分向量

若干支球队参加单循环比赛，各队两两交锋，假设每场比赛只计胜负，不计比分，在比赛结束后排名次。数学模型教材说比赛结果如果可以用双向连通竞赛图表示出来，就可以用该图对应的邻接矩阵A对应的最大特征根的特征向量s作为排名依据的得分向量。笔者经过研究发现，这种方法并不是对所有双向连通竞赛图都适用。

一、相关基础知识

定义：1：双向连通竞赛图：对于任何一对顶点，存在两条有向路径，使两顶点可以互相连通，这种有向图称为双向连通竞赛图。

定义2：对于n（n≥4）个顶点的双向连通竞赛图的邻接矩阵A，一定存在正整数r，使得A■>0，这样的A就称为素阵。

定理：Perron—Frobenius定理：素阵的最大特征根为正单根λ，λ对应正特征向量s，且有

■■=s？摇？摇？摇？摇？摇？摇？摇？摇（2）

二、应用举例

对一般性，记s■=A·e，s■=A·s■，…，s■=A·s■。则有：

s■=A·s■=A■·e（k=1，2，…）？摇？摇？摇？摇？摇？摇？摇？摇？摇？摇？摇？摇？摇（1）

当迭代次数越多，名次排定顺序越稳定。可将其较高级的得分作为排名依据。利用著名的Perron-Frobenius定理求出邻接矩阵A的最大特征根λ对应的正特征向量s，以s作为排名的依据。下面以4个队比赛结果的双向连通竞赛图为例说明如何应用这种方法。

图1 双向连通竞赛图

其对应的邻接矩阵为：

A=0？摇 1？摇 1？摇 00？摇 0？摇 1？摇 10？摇 0？摇 0？摇 11？摇 0？摇 0？摇 0

矩阵A的最大特征值及对应特征向量有：

λ■=1.3953，对应特征向量为（0.6256，0.5516，0.3213，0.4484）

我们容易得出其排名为：1->2->4->3。

三、应用反例

图2 5个顶点的双向连通竞赛图

其对应的邻接矩阵为：

0？摇 0？摇 1？摇 1？摇 11？摇 0？摇 0？摇 0？摇 00？摇 1？摇 0？摇 1？摇 00？摇 1？摇 0？摇 0？摇 10？摇 1？摇 1？摇 0？摇 0

矩阵A的最大特征值及对应特征向量有：

λ=1.8637，对应特征向量为（0.6394，0.3431，0.3972，0.3972，0.3972）

此例说明这种方法不是对所有双向连通竞赛图都适用，这种类型的图是无法排名的，从整体看3，4，5这三个顶点的实力相当。

参考文献：

[1]姜启源，谢金星，叶俊.数学模型（第三版）.北京：高等教育出版社，2003.8.

[2]刘来福等.数学模型与数学建模.北京师范大学出版社，1997.9.endprint

摘 要： 作者通过一个反例说明双向连通竞赛图的一种排名方法的局限性。

关键词： 双向连通竞赛图 排名 得分向量

若干支球队参加单循环比赛，各队两两交锋，假设每场比赛只计胜负，不计比分，在比赛结束后排名次。数学模型教材说比赛结果如果可以用双向连通竞赛图表示出来，就可以用该图对应的邻接矩阵A对应的最大特征根的特征向量s作为排名依据的得分向量。笔者经过研究发现，这种方法并不是对所有双向连通竞赛图都适用。

一、相关基础知识

定义：1：双向连通竞赛图：对于任何一对顶点，存在两条有向路径，使两顶点可以互相连通，这种有向图称为双向连通竞赛图。

定义2：对于n（n≥4）个顶点的双向连通竞赛图的邻接矩阵A，一定存在正整数r，使得A■>0，这样的A就称为素阵。

定理：Perron—Frobenius定理：素阵的最大特征根为正单根λ，λ对应正特征向量s，且有

■■=s？摇？摇？摇？摇？摇？摇？摇？摇（2）

二、应用举例

对一般性，记s■=A·e，s■=A·s■，…，s■=A·s■。则有：

s■=A·s■=A■·e（k=1，2，…）？摇？摇？摇？摇？摇？摇？摇？摇？摇？摇？摇？摇？摇（1）

当迭代次数越多，名次排定顺序越稳定。可将其较高级的得分作为排名依据。利用著名的Perron-Frobenius定理求出邻接矩阵A的最大特征根λ对应的正特征向量s，以s作为排名的依据。下面以4个队比赛结果的双向连通竞赛图为例说明如何应用这种方法。

图1 双向连通竞赛图

其对应的邻接矩阵为：

A=0？摇 1？摇 1？摇 00？摇 0？摇 1？摇 10？摇 0？摇 0？摇 11？摇 0？摇 0？摇 0

矩阵A的最大特征值及对应特征向量有：

λ■=1.3953，对应特征向量为（0.6256，0.5516，0.3213，0.4484）

我们容易得出其排名为：1->2->4->3。

三、应用反例

图2 5个顶点的双向连通竞赛图

其对应的邻接矩阵为：

0？摇 0？摇 1？摇 1？摇 11？摇 0？摇 0？摇 0？摇 00？摇 1？摇 0？摇 1？摇 00？摇 1？摇 0？摇 0？摇 10？摇 1？摇 1？摇 0？摇 0

矩阵A的最大特征值及对应特征向量有：

λ=1.8637，对应特征向量为（0.6394，0.3431，0.3972，0.3972，0.3972）

此例说明这种方法不是对所有双向连通竞赛图都适用，这种类型的图是无法排名的，从整体看3，4，5这三个顶点的实力相当。

参考文献：

[1]姜启源，谢金星，叶俊.数学模型（第三版）.北京：高等教育出版社，2003.8.

[2]刘来福等.数学模型与数学建模.北京师范大学出版社，1997.9.endprint