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

§2 竞赛排名 一、竞赛图及其性质 1、竞赛图 在每条边上都标出方向的图称为有向图。每对顶点间都有一条边相连的有向图称为竞赛图。 如何由竞赛图排出顶点的名次。 （1）两个顶点的竞赛图只有一种形式 1 2 （2 ）三个顶点的竞赛图只有两种形式 2 2 1 3 1 3 (1) (2) 对（1），顶名次排序为{1,2,3}；对（2 ），三个顶点名次相同。 （3 ）四个顶点的竞赛图只有四种形式 1 1 1 1 2 2 2 2 4 3 4 3 4 3 4 3 (1) (2) (3) (4)    对（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) 一般 个顶点 的竞赛图基本类型有三种： 0 1 、具有唯一的完全路径，这时顶点排名顺序与路径方向一致； 20 、双向连通图； 0 0 0 3 1 2 、不属 于 和 。 2、双向连通图的名次排序 以下讨论n(n 4) 个顶点的双向连通图名次排序。 重新定义邻接矩阵A (a ) 如下： ij nn 1 存在从顶点i到j 的有向边 a  ij 0 否则  例如： 1 2 4 3 0 1 1 0   的邻接矩阵为 A 0 0 1 1  0 0 0 1    1 0 0 0 S (1) (S , S ,, S )T S i 记顶点的得分向量为