谈循环比赛名次的确定

1、谈循环比赛名次的确定谈循环比赛名次的确定摘 要：在每场比赛都不允许平局的单循环比赛中，名次排列主要是依据各个参赛队的胜负场次所胜场次最多的即为冠军，当两队胜负场次相同时则由两队比赛结果决定两队名次，当比赛结果无法确定名次时则由净胜分或得失分率来决定两队名次，这样就没有考虑各队所胜或所负对手的实力，同时也不能完全避免有多组并列的情况这将影响名次排列的公正性与合理性通过对竞赛图的分析判定，结合邻接矩阵的最大特征根的计算可以解决上述问题首先依据循环比赛的结果做出竞赛图，若竞赛图只存在唯一一条通过各顶点的路径,则直接可得到各参赛队的名次；若竞赛图是双向连通的，通过计算竞赛图的邻接矩阵的极限得分向量,是

2、在考虑了各队所胜对手的实力的情况下得到的结果，因此作为排列名次的依据更加合理最后，将得到的名次排列方法推广到单场比赛允许平局的单循环比赛中关键词：循环赛；邻接矩阵；名次排列；竞赛图IIITHE DETERMINATION OF THE CYCLE RACE CLASSIFICATIONAbstract: In the round robin competition where every game does not allow a draw,the ranking order is the outcome of screening based on each team's win st

3、reak.Who wins the most is the champion，if there are two teams outcome of screening is the same, positions will be determined by the results of both teams.When the results of the two teams competition can not determine the ranking, then we determine the two teams ranking by scoring margin or loss rat

4、e to.So that we did not consider the strength of the opponent each team wins or negative, at the same time we can not completely avoid the multiple sets of parallel.This will affect the fairness of the ranking order.In order to solve the problems above this subject make the tournament based on the r

5、esults of the cyclic competition.If there is only one path through each vertex in the tournament, we can directly obtain each teams place; If the tournament is a double arc tournaments,firstly we can contest the adjacency matrixof the double arc tournaments, then we get the limit score vectorof the

6、adjacency matrix.The elements represented each team in the Limit score vector are the summation of the teams they wined in the score vector before. Sois obtained in the case of taking each teams strength and as a basis for ranking it is more reasonable .Then the calculation method is extended to all

7、ow a draw of the game.Keywords: Cycle Race; Adjacency Matrix; Ranking Order; Tournament目 录摘 要IAbstractII1 绪论12 预备知识22.1 图论相关知识22.2 竞赛图及其性质33 单路径循环赛名次排列43.1 问题引入及分析43.2 实践应用94 双路径循环比赛的名次排列12结语13参考文献14致谢15杜倩：谈循环比赛名次的确定第 VII 页 共 5 页1 绪论当今的许多比赛为了比赛的公平、公正都采用了循环赛制循环赛是指各个参赛队在比赛的过程中轮流比赛，这样每两支参赛队在比赛的过程中都会相遇循

8、环赛可以分为单循环赛、双循环赛以及分组循环赛三种形式单循环赛则是指在比赛的过程中,每两支参赛队只会相遇一次的比赛；双循环赛则是指在比赛的过程中，每两支参赛队都会相遇两次.当参赛队比较少时，或者各队希望比赛的场次较多时就会采用双循环比赛；分组循环赛是指先将所有的参赛队分成若干个小组进行第一阶段的预赛，然后再将各组的优胜队选出，在各优胜队之间进行第二阶段的决赛，决定第1名和以下的名次在分组预赛采用的是单循环赛，在决赛中一般采用的是单循环赛或者交叉赛等，因此分组循环赛也可称为“两阶段制”或混合循环制当参赛队比较多时，想在短时间内完成比赛并且公正合理一般采用的是分组循环赛 比赛的场次是指在比赛的整个过

9、程中比赛的总场数由于本文后面用到的竞赛图需要用一条连线代表一场比赛，因此当参赛对较多时比赛场次就越多，竞赛图中的连线也就越密集，这样在计算时就容易漏掉比赛，于是计算比赛的场次至关重要，这样可以检验计算过程是否正确在单循环比赛中比赛场次的计算公式为：其中指比赛的场次，指的是参赛队的数量，例如当有6支参赛队时,比赛的场次为15经过场比赛后就面临着名次排列的问题当今的循环制比赛中，名次排列主要是依据各队所胜的总场次，所胜场次最多的即为冠军，当两支参赛队所胜场次相同，则由这两队的比赛结果决定两队名次，胜者在前，如果有不少于两支参赛队的所胜场次相同，则由得失分率决定名次高低2 预备知识2.1 图论相关知

10、识在我们的日常生活以及科学研究中，常常将某事物表示为一个点，用点与点之间的连线来表示事物之间存在的某种关系，我们就将点与点之间的连线组成的图形称为图本文大部分使用的是图论中的知识，因为图论涵盖了丰富的思想，图形漂亮可以将复杂的问题简单化，其涉及的问题也非常广泛，解决问题方法也比较灵活，许多问题都可以用图论来解决图可以用多种形式来表示，例如集合、图形当然还可以用矩阵来表示这里只对图的图形表示以及矩阵表示做简单介绍 图用图形来表示一般分为无向图与有向图，下面分别对二者作简单介绍：定义11 是一个有序的二元组，其中是一个非空有穷集，我们称其为顶点集，把它的元素称为顶点或结点是无序积的有穷多重子集，称

11、其为边集，把它的元素称为无向边，也可简称为边定义21 图是一个有序的二元组，其中是一个非空有穷集，我们称其为顶点集，把它的元素称为顶点或结点.是笛卡尔积的有穷多重子集，称为边集，其元素称为有向边，简称边本篇论文用到的主要是有向图无向图和有向图通常表示为下述图形：顶点表示为小圆圈或实心点，顶点之间的连线表示的是无向边，带箭头的连线表示的是有向边用矩阵来表示图则需要指定顶点或者边的顺序,使其成为标定图定义3123图，是指邻接到边的条数，我们就称为的邻接矩阵，记作，也可简记为 定义414无向标定图，中顶点与边的交替顺序就称为到的通路，其中,为的端点，分别称为的始点和终点若有,则称为回路若所有边各异，

12、则称为简单通路若又有,则称为简单回路若所有顶点（除与可能相同外）各异，所有边也各异，则称为初级通路或路径设无向图，若之间存在通路，则称是连通的设为一个有向图，若从到存在通路，则称可达，记作.规定总是可达自身的，即若且，则称和是相互可达的，记作，且若有向图的基图是连通图，则称是弱连通图，简称为连通图，若,与至少成立其一，则称是单向连通图2.2 竞赛图及其性质如果一个有向图，图中每一对不同的顶点之间都有一条弧相连接则这个有向图就是单弧竞赛图也可简称为竞赛图35 单弧竞赛图的每一个顶点代表一支参赛队，从顶点到顶点的一条弧就可以表示队战胜队双弧竞赛图则是指每一对不同的顶点之间都有两条弧相连接的有向图5

13、双弧竞赛图描述的单循环比赛虽然也是任意两支参赛队只比赛一次但是它是允许平局的，当队战胜队时，则从顶点到顶点连接两条弧，这样队得两分，队不得分;当队与队打成平局时则由顶点到以及顶点到各连一条弧，这样两队各得一分5因此，参赛队，的总得分就是指顶点的出度 含有个顶点的竞赛图一般具有以下性质：性质1 竞赛图中各顶点间一定存在一条完全路径；性质2 如果竞赛图中各顶点间存在唯一的一条完全路径，则根据完全路径得到的顶点的顺序与根据各队得分多少排列得到的顺序是相一致的3 单路径循环赛名次排列3.1 问题引入及分析下图图3-1给出了5支参赛队参加的单循环比赛的比赛结果，由图可知队战胜队、队以及队而输给了队；队战

14、胜队与队，而输给队与队等等 图 3-1对循环比赛排名次的一种方法是计算各队的得分，也就是各队所胜的场次，胜一场记一分，输一场不得分由竞赛图可知队、队与队各胜2场，队胜1场，队胜3场由此上可认为队为冠军，但是队、队与队之间还无法决定名次高低因为在排名时可以将队排在队前面，队排在队前面，但是又有所以以上排名是不合理的 另一种根据比赛结果来排列名次的方法就是设法在图中寻找一条完全通过全部5个顶点的路径，图3-1中就存在这条路径，这就表示队胜了队,队胜了队，则可以说冠军是队，亚军为队等等，但是我们还可以找到其他完全经过5个顶点的路径，如还有.因此用这种方法就无法对循环比赛进行合理的名次排列. 下面利用

15、前面介绍的图论的知识来解决以上的名次排列问题 经过分析可以得到有支参赛队参加的单循环比赛的比赛结果的竞赛图在不考虑顶点符号的情况下共有（是指参赛队的数量）种形式，我们只需考虑实际比赛的结果符合哪种形式就可以了当时比赛结果的竞赛图只有一种形式，就是由2个顶点以及两点间的一条带箭头的连线组成，如图 3-2，这种比赛结果的名次排列显然不成问题 图 3-2当时，竞赛图有种形式，如下图所示，对于图3-3每支参赛队各胜一场，因此这三支参赛队名次并列对于图3-4,队胜两场，队胜一场，队未胜输两场，则三支参赛队的名次为. 图 3-3 图 3-4当时，竞赛图有种形式，下面针对每种形式进行讨论图 3-5 图 3-

16、6 图 3-7 图 3-8对于图3-5知各队的得分向量为，由此可得名次排列为通过对图3-5的分析也可得到则可知竞赛图存在唯一一条通路连接四个顶点即由以上可以判定当竞赛图只存在唯一一条路径时，则只需通过此路径就可以对比赛进行名次排列，即路径经过的各点名次依次降低对于图3-6进行分析得到竞赛的得分向量为，则可知，队得分相等，无法通过各队的胜负场次来决定名次排列通过对图3-6的分析也可得到，以及则不存在唯一的一条路径经过四个顶点，因此综上由于队胜3场所以只能确定队为冠军，但是没有办法确定其它三支参赛队的名次对图3-7进行分析得到得分向量，则队与队各胜一场，队与队各胜两场，因此由各队的胜负场次无法判定

17、名次排列通过对图的分析也可得到则不存在唯一的一条路径经过四个顶点，则名次排列只可初步记为对于图3-8进行分析得到得分向量为，队与队各胜一场，队与队各胜两场，因此目前无法对比赛进行名次排列通过对图3-8分析可以得到多条通路，、，通过这几条通路可以判定任意两点间都存在两条有向路径，使相互连通，我们称这种有向图为双向连通的（Biconnected）通过以上讨论比赛名次只可初步记为当时，竞赛图有种形式，如下所示，图 3-9 图 3-10 图 3-11图 3-12 图 3-13 图 3-14下面针对以上6种形式的每种形式依照当时的分析方法进行分析，由图3-9可以得到得分向量为，由此可判定循环比赛的名次排

18、列为，由时的规律可知，此时竞赛图只有唯一一条路径经过各顶点，经过核实得到路径 对图3-10分析可以得到得分向量为，则由以上规律可判定比赛的名次排列为，并可得知竞赛图3-10只存在唯一一条路径，经过对其分析得到路径通过对图3-11分析可以得到得分向量为，可知队，队与队所胜场次相同，通过时的规律，这里可以猜想竞赛图图3-11存在不止一条路径，经过分析得到路径以及，猜想成立 通过对图3-12分析可得得分向量，则队与队，队与队得分相同，无法判定各队名次，并且由以上验证的规律可知竞赛图存在多条经过各顶点的路径，这里可以得到如以及 对于图3-13分析后可得到得分向量为，则队与队，队与队得分相同，由可知图3

19、-13存在多条经过各顶点的路径，这里可以得到以及，由这两条路径可以确定图3-13是双向连通的双向连通竞赛图是一种特殊情形，下面会做详细介绍 对于图3-14分析后可以得到得分向量为，则只能判定为冠军，队，队与队得分相同，由可知图3-14存在多条经过各顶点的路径，通过分析后得到、等由此可知图3-14亦是双向连通竞赛图经过以上对，以及时竞赛图的各种形式的讨论可以知道竞赛图的基本类型有3种，第一种类型的竞赛图存在唯一一条经过各个顶点的通路；第二种类型的竞赛图为双向连通竞赛图；第三种类型的竞赛图有不止一条经过各个顶点的通路但是不是双向连通竞赛图由以上的分析也可得到对于第一种类型竞赛图可以通过唯一一条路径

20、得到比赛名次，对于第三种类型竞赛图无法确定全部参赛队的名次，如果有并列的情况还需要继续比赛.第二种类型的竞赛图是一种特殊情形，因为它是双向连通的，下面就针对这种类型的竞赛图的名次排列进行讨论为了计算方便我们以情况下的竞赛图3-8为例由邻接矩阵的定义可得图3-8的邻接矩阵为 通过计算可顶点的得分向量为，则我们不难得到 则可知无法根据得分向量得出各个参赛队的名次，因此只记称其为1级得分向量接下来继续进行计算2级得分向量则可知每支参赛队的2级得分是指他所战胜的其它各个参赛队的1级得分之和，因此与级得分向量相比2级得分向量作为排列名次的依据更加合理，因为它考虑了每支参赛队所胜或者所负对手的实力则对于图

21、3-8，有,继续这个程序，可以得到级得分向量 由以上规律不难发现当越大时，依据来排列名次就越恰当合理当，就收敛于某个极限得分向量，那么就可以用这个向量作为排列名次的依据首先我们令为正整数，如果存在使得则称矩阵为素阵对于一个含个顶点的双向连通竞赛图，它的邻接矩阵就是一个素阵素阵的最大特征根对应的特征向量满足 通过以上讨论可知级得分向量，当将趋于矩阵的对应于最大特征根的特征向量，就是所要求的作为排名次依据的极限得分向量对于图3-8可以得出其邻接矩阵的最大特征根以及它对应的特征向量 从而确定名次排列为通过以上讨论我们已经可以确定循环比赛的名次排列，对于问题引入是提到的关于支参赛队参加的比赛，可以初步

22、判定竞赛图是双向连通的，所以可用以上方法来解决名次排列问题.首先得出邻接矩阵为 计算出各级得分向量，得,又以上可知要想的到极限得分向量需要求出矩阵的最大特征根，则得到对应于最大特征跟的特征向量为（0.4251,0.3771,0.5798,0.5143,0.2765），因此名次排列为3.2 实践应用例1 已知以下介绍的围棋比赛有6名选手参加，比赛采用单循环赛制，根据比赛的结果绘制竞赛图，如图3-15所示，接下来通过讨论竞赛图3-15来确定围棋比赛的各名选手的名次排列 图 3-15根据邻接矩阵的定义得到邻接矩阵为 由顶点的得分向量的定义可知，其中，由此可得本次比赛的得分向量为，则可以看出与的得分相

23、同，与的得分相同，则由竞赛图的类型规律可知通过1级得分向量不易排出全部参赛者的名次，只能初步确定为冠军，为最后一名下面分析竞赛图3-15，由级得分向量可知竞赛图3-15存在多条经过各个顶点的路径，通过对其分析可得,以及等由此可确定竞赛图3-15是双向连通竞赛图下面根据双向连通竞赛图的特点进行计算记为2级得分向量，2级得分向量中每位参赛者的得分分向量是其所战胜的全部选手的1级得分分向量之和，因此2级得分向量是在考虑了各个选手所胜或者所负对手的实力的情况下得到的结果，因此2级得分向量比级得分向量更适合作为名次排列的依据由此可得 ,继续计算得到级得分向量 与级得分向量相比，级得分向量，显然越大，作为

24、名次排列的依据就越合理,当时，就会收敛于一个极限得分向量，那么就可以用这个向量作为排列名次的依据.首先我们令为正整数，如果存在使得则称矩阵为素阵对于一个含有个顶点的双向连通竞赛图，它的邻接矩阵就是一个素阵素阵的最大特征根对应的特征向量满足通过以上讨论可知级得分向量，当时将趋于矩阵的对应于最大特征根的特征向量，就是所要求的作为排名次依据的极限得分向量下面通过MATLAB软件6计算邻接矩阵的最大特征根为及最大特征根对应的特征向量为,依据特征向量得到名次排列为4 双路径循环比赛的名次排列前面讨论的是不允许平局出现的单循环比赛的名次排列问题，并说明了极限得分向量作为名次排列依据的合理性，下面就讨论在允

25、许平局情况出现的单循环比赛名次排列允许平局出现的单循环比赛的竞赛图采用的是双弧竞赛图，前面竞赛图及其性质一节中已经对双弧竞赛图做了简单介绍当=3时，由于顶点数少，因此可以直接分析出排名情况当时，如果竞赛图是双向连通的则可以用极限得分向量对比赛进行排名，那么，可以猜想得到，如果可以判断出双弧竞赛图是否连通的，就可以应用前面所介绍的计算方法，得到双弧竞赛图的邻接矩阵的极限得分向量，极限得分向量就是比赛名次排名的依据.因此，允许平局出现的单循环比赛的名次排列最关键的就是判断竞赛图的连通性类似于单弧竞赛图，双弧竞赛图也可以分为3种类型考虑第一种类型是指双弧竞赛图存在唯一一条通路，这时可以依据各个顶点出

26、度的大小，也就是各个参赛队的得分对循环比赛进行排名；第二种类型是指双弧竞赛图不存在唯一一条通路则名次排列一定会存在并列的情况；第三种类型是指双弧竞赛图是双向连通的，则可以依照前面讨论得到的计算方法来进行名次排列，即先依定义得到双弧竞赛图的邻接矩阵，然后再计算邻接矩阵的极限得分向量，最后依据极限得分向量得到合理的名次排列如果非常大即参赛队较多时就不便于判断双弧竞赛图的连通性，则可以先分析竞赛图的得分向量来判断其是否属于第一类型，如果竞赛图属于第一类型则只需依据得分向量来对比赛进行名次排列如果竞赛图不属于第一类型，再判断双弧竞赛图是否属于第三类型，如果双弧竞赛图是双向连通的，只需通过计算得到邻接矩阵的极限得分向量来进行名次排列就可以了结语通过以上对单循环比赛名次排列问题的讨论得知循环比赛名次排列的关键是判断竞赛图的类型，当竞赛图为第一种类型时，依据1级得分向量就可以确定名次排列；当竞赛图为第三种类型时，只需通过计算得到邻接矩阵的极限得分向量来进行名次排列就可以了;当竞赛图为第二种类型时，用此方法无法对全部参赛队进行名次排列通过讨论得到的计算方法对循环比赛进行名次排列考虑了各队所胜对手的强弱，是名次排列更加合理公正，同时可以避免并列情况的出现并且当竞赛图属于第一三类型时尽管比赛结果