数学建模案例分析-- 图与网络方法建模2竞赛排名

一、竞赛图及其性质

1、竞赛图

在每条边上都标出方向的图称为有向图。每对顶点间都有一条边相连的有向图称为竞赛图。如何由竞赛图排出顶点的名次。

（1）两个顶点的竞赛图只有一种形式

1 2 2 （2）三个顶点的竞赛图只有两种形式

2

1 3

(1)

对（1），顶名次排序为{1,2,3}；对（2），三个顶点名次相同。

（3）四个顶点的竞赛图只有四种形式

1 (2)

3

4 1 2 3 (1)

4 1 2 3 4 (2)

1 2 3

1 2 4 3

(4)

(3)

对（1），有唯一的通过全部顶点的有向路径1234，称为完全路径。顶点名次排序是

{1,2,3,4}。对（2），顶点2排第1，其余3点名次相同。对（3），顶点2排最后，其余3点名次相同。对（4），有不只一条完全路径，如1234，3412，无法立即排出名次，具有（1）~（3）没有的性质：对于任何一对顶点，存在两条有向路径，使两顶点可以相互连通，这种有向图称为双向连通图。

一般n个顶点(n4)的竞赛图基本类型有三种：

10、具有唯一的完全路径，这时顶点排名顺序与路径方向一致； 20、双向连通图；

30、不属 于10和20。

2、双向连通图的名次排序

以下讨论n(n4)个顶点的双向连通图名次排序。 重新定义邻接矩阵A(aij)nn如下：

1存在从顶点i到j的有向边 aij0否则例如：

1 2 4 3

00的邻接矩阵为 A011000110001 10记顶点的得分向量为S(1)(S1,S2,,Sn)T，其中Si是顶点i的得分。

(k)记S(2)AS(1),,S(k)AS(k1)Ak1S(1)，(k1,2,)。如果k时，S收敛 于某个

极限向量，则用这个向量中分量的大小作为排名次的依据。 定理：S(k)当k时将趋向A的对应于最大特征根的特征向量S。

二、应用举例

6支球队比赛结果用下图表示，为双向连通图。

6

1KKKKK2

邻接矩阵为

3 5 K4 001 A000101110011110100

000110100101000,0.164,0.231,0.113,0.15,0.104)。于是可排出最大特征根2.232，特征向量S(0.238名次为{1,3,2,5,4,6}。

三、其他情况（不属于1和2）下的名次排序

对于既没有唯一完全路径，又不是双向连通的竞赛图，通常可分解为若干个双向连通的子竞

赛图。

例如下图8个顶点的竞赛图分解为3个双向连通子竞赛图 G1，G2，G3。

00

4 1 2 3 G1 5 G3 8 G2

7 6 G1,G2,G3子图之间的边被简化了，实际上两子图的每对顶点之间都有边相连，而这些边的方向

必是一致的，否则相应的子图可以合并为更大的双向连通子竞赛图。

在每个这样的图中按上面介绍的方法排名次，而子图之间的名次不难由它们相连边的方向决定。例如：G1的名次为{1,2,4,3}，G2的名次5,6,7相同，G3只一个顶点8 ，故全部顶点的名次排列为{1,2,4,3,（5,6,7）,8}。