(此处缺图待补!) (1)有唯一的通过全部顶点的有向路径1→2→3→4,这种路径称为完全路径:4个队得分 为(3,2,1,0),名次排列无疑应为{1,2,3,4} (2)点2显然应排第1,其余3点如图(2)形式,名次相同:4个队得分为(1,3,1,1) (3)点2排在最后,其余3点1名次相同;得分为(2,0,2,2) (4)有不只一条完全路径,如1→2→3-4,3-44→1→2;得分为(2,2,1,1)。由这些我们无 法立即排出名次,但这种情形是研究的重点。还可以注意到,(4)具有(1)(3)所没有的 性质:对于任何一对顶点,存在两条有向路径(每条路径由一条或几条边组成),使两 顶点可以相互连通,这种有向图称为双向连通的。 5个顶点以上的竞赛图虽然更加复杂,但基本类型仍然如以上4个顶点给出的3种:具 有唯一的完全路径如图(1);双向连通如图(4);不属于这两种情况如图(2)、(3)。 一般的n个顶点的竞赛图具有以下性质 1)竞赛图必存在完全路径。(可用数学归纳法证明) 2)若存在唯一的完全路径,则由完全路径确定的顶点的顺序,与按得分多少排列相 致。(这里一个顶点的得分指由它按箭头方向引出的边的数目),若顶点集为 丿=(1,2,…,n),不妨设唯一的完全路径为1→2→.→n,则顶点i的得分为n-i (i=1,2,,n) 显然,性质2给出了具有唯一完全路径的竞赛图的排列名次方法。4个顶点中图(1)的 情况正是这样。 双向连通竞赛图的名次排序3个顶点的双向连通竞赛图,如上述4个顶点的竞赛图 (2),名次排序相同。以下讨论n(n≥4)个顶点的双向连通竞赛图。 首先,竞赛图的邻接矩阵A=(a)重新定义如下 存在从顶点i到j的有向边 0,否则 依此,图(4)的邻接矩阵为9 （此处缺图待补！） (1) 有唯一的通过全部顶点的有向路径 1→2→3→4，这种路径称为完全路径；4 个队得分 为(3, 2, 1, 0)，名次排列无疑应为{1, 2, 3, 4}. (2) 点 2 显然应排第 1，其余 3 点如图(2)形式，名次相同；4 个队得分为(1, 3, 1, 1)。 (3) 点 2 排在最后，其余 3 点 1 名次相同；得分为(2, 0, 2, 2). (4) 有不只一条完全路径，如 1→2→3→4，3→4→1→2；得分为(2, 2, 1, 1)。由这些我们无 法立即排出名次，但这种情形是研究的重点。还可以注意到，(4)具有(1)~(3)所没有的 性质：对于任何一对顶点，存在两条有向路径（每条路径由一条或几条边组成），使两 顶点可以相互连通，这种有向图称为双向连通的。 5 个顶点以上的竞赛图虽然更加复杂，但基本类型仍然如以上 4 个顶点给出的 3 种：具 有唯一的完全路径如图(1)；双向连通如图(4)；不属于这两种情况如图(2)、(3)。 一般的 n 个顶点的竞赛图具有以下性质： 1) 竞赛图必存在完全路径。（可用数学归纳法证明） 2) 若存在唯一的完全路径，则由完全路径确定的顶点的顺序，与按得分多少排列相 一致。（这里一个顶点的得分指由它按箭头方向引出的边的数目），若顶点集为 V=(1, 2, …，n)，不妨设唯一的完全路径为 1→2→…→ n, 则顶点 i 的得分为 n i − （i =1, 2, …，n）。 显然，性质 2 给出了具有唯一完全路径的竞赛图的排列名次方法。4 个顶点中图(1)的 情况正是这样。 双向连通竞赛图的名次排序 3 个顶点的双向连通竞赛图，如上述 4 个顶点的竞赛图 (2),名次排序相同。以下讨论n n( 4) ≥ 个顶点的双向连通竞赛图。 首先，竞赛图的邻接矩阵 ( ) A aij n n× = 重新定义如下： 1 0, i j i j a = ⎧ ⎨ ⎩ 存在从顶点 到 的有向边 否则 （1） 依此，图(4)的邻接矩阵为