§2 竞赛排名。
一、竞赛图及其性质。
1、竞赛图。
在每条边上都标出方向的图称为有向图。每对顶点间都有一条边相连的有向图称为竞赛图。如何由竞赛图排出顶点的名次。
1）两个顶点的竞赛图只有一种形式。
2）三个顶点的竞赛图只有两种形式
对（1），顶名次排序为；对（2），三个顶点名次相同。
3）四个顶点的竞赛图只有四种形式
对（1），有唯一的通过全部顶点的有向路径1234，称为完全路径。顶点名次排序是。对（2），顶点2排第1，其余3点名次相同。
对（3），顶点2排最后，其余3点名次相同。对（4），有不只一条完全路径，如1234，3412，无法立即排出名次，具有（1）~（3）没有的性质：对于任何一对顶点，存在两条有向路径，使两顶点可以相互连通，这种有向图称为双向连通图。
一般个顶点的竞赛图基本类型有三种：
具有唯一的完全路径，这时顶点排名顺序与路径方向一致；
双向连通图；
不属于和。2、双向连通图的名次排序。
以下讨论个顶点的双向连通图名次排序。
重新定义邻接矩阵如下：
例如：的邻接矩阵为。
记顶点的得分向量为，其中是顶点的得分。
记，。如果时，收敛于某个极限向量，则用这个向量中分量的大小作为排名次的依据。
定理：当时将趋向的对应于最大特征根的特征向量。
二、应用举例。
6支球队比赛结果用下图表示，为双向连通图。
邻接矩阵为。
最大特征根，特征向量。于是可排出名次为。
三、其他情况（不属于和）下的名次排序。
对于既没有唯一完全路径，又不是双向连通的竞赛图，通常可分解为若干个双向连通的子竞赛图。
例如下图8个顶点的竞赛图分解为3个双向连通子竞赛图，，。
子图之间的边被简化了，实际上两子图的每对顶点之间都有边相连，而这些边的方向必是一致的，否则相应的子图可以合并为更大的双向连通子竞赛图。
在每个这样的图中按上面介绍的方法排名次，而子图之间的名次不难由它们相连边的方向决定。例如：的名次为，的名次5,6,7相同，只一个顶点8 ，故全部顶点的名次排列为。
数学建模案例分析 图与网络方法建模6习题七
习题七。1 某田径选拔赛共设六个项目的比赛，即跳高 跳远 标枪 铅球 100米和200米短跑。规定每个选手至多参加三个项目的比赛。现有七名选手报名，所报项目如下表所示。现在要求设计一个比赛日程安排表，使得在尽可能短的时间内完成比赛。提示 当且仅当两个项目同时有一人选报时，在相应的两个顶点间连一条边。...
数学建模案例分析 图与网络方法建模6习题七
习题七。1 某田径选拔赛共设六个项目的比赛，即跳高 跳远 标枪 铅球 100米和200米短跑。规定每个选手至多参加三个项目的比赛。现有七名选手报名，所报项目如下表所示。现在要求设计一个比赛日程安排表，使得在尽可能短的时间内完成比赛。提示 当且仅当两个项目同时有一人选报时，在相应的两个顶点间连一条边。...
数学建模案例分析 对策与决策方法建模2矩阵对策模型
2 矩阵对策模型。具有竞争或对抗性质的现象称为对策行为。在对策行为中，各方面要达到自己的目标，必须考虑对手的各种可能行动方案，从而选出对自己的最有利的策略。在一个对策行为中，有权决定自己的行动方案的对策参加者称为局中人。一般在一个对策中至少有两个局中人，我们把只有两个局中人的对策称为二人对策，而多于...