最优单循环赛程编排方法

谢晓敏

（川北幼儿师范高等专科学校初等教育系，四川 广元628017）

单循环赛，是指所有参赛队在竞赛中均能相遇一次，最后按各队在竞赛中的得分多少、胜负场次排列名次。这种赛制下，参加竞赛的各队都有相遇比赛的机会，是一种比较公平合理的比赛制度。

假设有n支足球队在同一场地上进行单循环比赛，如何安排赛程对各队来说都尽量公平呢？各队每两场比赛最小相隔场次达到上界时，最大相隔场次数越小，公平性越好[1]。而各队每两场比赛最小相隔场次数的上界是很多文献都对此结论用或繁或简的方法进行了证明[2-4]。并且按照文献[4-5]的编排方法，结论可以推广到n（n≥5）支球队，当n为偶数时，每两场比赛相隔场次数只有当n为奇数时，每两场比赛相隔场次数为

本文作者根据现有文献和自己的研究分别给出了n为奇数和n为偶数时符合最优相隔场次数的编排方法。

1.参赛队数n为偶数

单循环赛程比较经典的编排方法有两种：固定1逆时针轮转法和贝格尔编排法[7]。

固定1逆时针轮转法的优点是：参赛各队比赛进度一致，编排方法简单，易操作，便于检查。但是当参赛队伍超过5支时，对抽签为倒数第2的队伍极不公平，因为从第四轮开始，此队伍每次都对战上一轮轮空的队伍。

贝格尔编排法是目前单循环赛应用比较广泛的一种编排方法。国际联排所举办的世界排球锦标赛、世界杯排球赛、奥运会排球赛及世界青年排球锦标赛，国内的一些球类项目及棋类项目也采用贝格尔编排法。但是，贝格尔编排法编制的赛程表并未达到最优赛程要求的每两场比赛相隔场次数。于是，我们改进贝格尔编排法，使其达到最优赛程的要求，得到n为偶数时的单循环赛程表。

1.改进的贝格尔编排法编制n=8的赛程表

下面以n=8为例，说明改进的贝格尔编排法的编排过程。

第1轮的编排与固定1逆时针轮转法相同，即按照1至8的顺序逆时针按U形走向分成均等两边。

接下来先安排8号队，第1轮8在右边，第2轮8要换到左边，第3轮又换到右边，这样反反复复，到第7轮8又回到右边。

然后安排其余的队伍。贝格尔编排法是将前一轮右下角的数字提到本轮第一行来，其余队伍按照逆时针轮转。改进的贝格尔编排法是将前一轮第二行右边的数字提到本轮第一行来，其余队伍按照逆时针轮转编排就可以了。例如：第1轮第2行右边数字是7，应该提到第2轮第1行，第2轮的第1场比赛就是8—7。按照逆时针方向看，7的后面是6，前面是8,8的前面是1，于是第2轮第2场比赛就是1—6。其余的同理，赛程表如表1所示。各队每两场比赛间隔的场次数和总场次数如表2所示。

表1 改进的贝格尔编排法编制的赛程表

表2 各队每两场比赛间隔场次数和总场次数

2.改进的贝格尔编排法编排步骤

第一步：编排第1轮。

第一轮的编排按照1至n的顺序逆时针按U形走向分成均等两边。

第二步：安排n号队。

n号队一直出现在每轮第1场比赛中。第1轮n在右边，第2轮n要换到左边，第3轮又换到右边，这样反反复复，到第1轮又回到右边。

第三步：安排第2轮至第n-1轮第1场比赛中的另一个队伍。

前一轮第2场比赛右边的队伍提到本轮第一场比赛，与n号队完成一场比赛，其余队伍按照逆时针轮转编排就可以了。编排的赛程表如表3所示。

表3 n为偶数时的改进贝格尔编排法

2.参赛队数n为奇数

2.1 构造推理编排法编排n=7的赛程表

下面以n=7为例，说明n为奇数时的构造推理编排法的编排过程。

表4 n=7时编排方法第一步结果

第二步：按照要求每个参赛队的间隔场次数至少为2，表4中每轮的两场比赛中也要至少插入2场比赛。剩余的比赛场次数为场，按要求前5轮比赛每两场之间应该平均地插入2场比赛。此时n=7的赛程编排框架就搭建好了，如表5所示。

表5 n=7赛程编排框架

第三步：因为1至5轮只有1支队伍可以出现2次，其余只能出现1次，否则必然不满足相隔至少两场的要求。剩余10场比赛分别为：3—4，3—5，3—6，3—7，4—5，4—6，4—7，5—6，5—7，6—7。对于3—5而言，既不能出现在第2轮，也不能出现在第4轮。注意到1—3的位置，3—5不能出现在第1轮第3场。2—3的位置决定3—5不能出现在第3轮第2场，1—5的位置决定3—5不能出现在第3轮第3场，2—5决定3—5不能出现在第5轮第2场。3-5只能安排在第1轮第2场或第5轮第3场。5号队在整个赛程中要参加6场比赛，目前赛程表中有2—5和1—5两场，如果3—5不排在第5轮第3场，注意到1—5是第13场比赛，它的前面还要安排4场5号队的比赛，5号队最早开始的比赛可以安排在第2场，2至13场之间不能安排出最小间隔为两场的3场比赛。因为3场比赛有4个间隔，4个间隔为8场，加上3场比赛总场数为11场，而第2场到第13场之间只有10场。故只能将3—5安排在第5轮第3场。于是第5轮第1场只能安排4—7。编排结果如表6所示。

表6 第5轮赛程编排

第四步：根据3—5的位置，第4轮第3场必须安排3号队参与比赛，否则与3—5的间隔就会大于3，有3号队参与的比赛还剩3—4，3—6，3—7，根据1—6的位置，此场比赛不能安排3—6。若安排3—7，则第4轮第2场必为4—6，与2—4的位置不符合间隔至少2场的要求。所以，第4轮第3场必须安排3—4，第4轮第2场只能安排6-7。安排结果如表7所示。

表7 第4轮赛程编排

第五步：根据3—4的位置，第3轮第3场比赛必须安排3号队参加比赛，否则与3—4的间隔就会大于3，有3号队参与的比赛还剩3—6和3—7，3—7既不能安排在第1轮也不能安排在第2轮，只能安排在第3轮，所以第3轮第3场只能安排3—7，第3轮第2场只能安排5—6。安排结果如表8所示。

表8 第3轮赛程编排

第六步：3—6不能安排在第2轮，只能安排在第1轮，1—3的位置决定不能安排在第1轮第3场，只能安排在第1轮第2场，第1轮第3场必为4—5。安排结果如表9所示。

表9 第1轮赛程编排

第七步：最后剩的两场比赛为4—6和5—7，根据1—4的位置，决定第2轮第3次不能安排4—6，只能安排5—7，第2轮第2场就只能4—6。到此赛程安排结束，最终的最优赛程表如表10所示，各队每两场比赛间隔的场次数和总场次数如表11所示。

表10 n=7的最优赛程表

表11 各队每两场比赛间隔场次数和总场次数

2.2 构造推理编排法编排步骤

此编排方法我们可以推广到n(n≥5)为任意奇数，编排方法如下。

第一步：构造出编排框架，如表12所示。

表12 构造推理法编排框架

第二步：第1至n-2轮将平均插入场比赛。第n-1轮只有一场比赛，于是我们只需要编排第1至n-2轮。规定：赛程中同一场比赛的两支队伍左边参赛队的编号永远比右边小。编排结果如表13所示。

表13 n(n≥5)为任意奇数第1至(n-2)轮编排结果

2.3 图论解释

n=7的单循环赛程编排可以看成是图1-3中的7个点，每两个点之间有一条线连接。我们可以从图论的角度解释刚才的编排方法。

n=7时总共有21场比赛，分成3组，每组7场。每组每个队都进行两场比赛。

先 编 排 第 一 组：1—2，3—6，4—5，2—7，1—3，4—6，5—7，如图1所示。

第二组：2—3，1—4，5—6，3—7，2—4，1—5，6—7，如图2所示。

第三组：3—4，2—5，1—6，4—7，3—5，2—6，1—7，如图3所示。

图1 第1组编排图

图2 第2组编排图

图3 第3组编排图

三组图无重合，合在一起是一个完全图。每组编排的图，无论从哪个点开始都可以经过所有的点一次回到起始点。

2.4 单循环赛程n为奇数的图论模型

n支球队用点v1，v2,……,vn表示，由于n支球队的单循环赛每两支球队之间均需比赛一场，即任意两点之间都有一条边相连，所以n支球队的单循环赛对应一个无向完全图Kn。完全图Kn有条边，对应n支球队的场赛比赛程。场比赛分成组，每组n场比赛。每组的编排方法基本类似，第1组编排方法如下。

第一步：把n个点v1，v2,……,vn按顺时针方向排列成一个由n个孤立点构成的一个“圈”[8]。

第二步：确定奇数个参赛队中不参加比赛的队伍，可以是任意一个队伍。剩余队伍数目为偶数个，以不参赛队所处点为参照点，安排分别从顺、逆时针方向看，处在“圈”上对称位置的两个队伍完成一场比赛，按照由近及远或由远及近的顺序均可，每队只能参加一场比赛，共计场比赛。

第三步：第二步中未参加比赛的队伍与第1场比赛中号数较小的队伍完成一场比赛，为第场比赛。从第1场比赛中号数较小的队伍代表的顶点开始按照图中有线的路径行走，若走到没有路径的地方，则按向第二步第2场比赛中较小号数所在顶点方向行走，增加一条路径，每增加一条路径则安排一场比赛。如此反复，直到走到第二步第场比赛号数较大的顶点，共安排场比赛。从刚才结束的顶点最终走到第二步未参加比赛的队伍所处顶点，再安排一场比赛，即第n场比赛。

第二步：在“圈”中除去第1组第二步未参加比赛的队伍所代表的点，此时剩余偶数个点，分别从顺、逆时针方向选择与本组第1场比赛对称的点安排一场比赛，共计场。

第三步：本组未参加比赛的队伍与本组第1场比赛中号数较大的队伍安排一场比赛。从本组第1场比赛中号数较大的队伍开始沿本组第1场比赛的方向行走，到没有路径的时候则向本组第2场比赛号数较小的队伍方向行走，增加一条路径，安排一场比赛。若已经与较小号数队伍进行过比赛，则向号数较大的队伍行走，安排一场比赛，如此反复，最终走到本组第场号数较大队伍所在的顶点，共安排场比赛。从刚才结束的顶点最终走到本组第二步未参加比赛的队伍所处顶点，再安排一场比赛，即第n场比赛。

注：若第1组安排的顺序为由近及远，那么所有组中的安排顺序皆为由近及远。

例如：n=7时，第1组编排过程如下：

第一步：先将7个队按逆时针方向排列成一个“圈”。

第二步：若确定7号队不参加比赛，以7号队为参照点，1与6,2与5,3与4处在其对称位置上。那么由近及远应该安排1—6,2—5,3—4三场比赛；若由远及近应该安排3—4,2—5,1—6三场比赛。如图4所示。

图4 第1组第一步编排图

图5 第1组赛程编排图

第三步：若第二步安排的三场比赛为：1—6,2—5,3—4。接下来安排未参加比赛的7号队与第二步第1场比赛中号数较小的队伍，即1号队进行一场比赛。然后从1开始走到6,6出发就没有路径了，按照向第二步第2场比赛较小号码的方向行走，增加路径为6—2，即安排一场比赛。继续往下走，到5号没有路径，按要求向3号走，安排一场比赛，即5—3。继续走到4，最后应该走向第二步没参赛的7号队，安排一场比赛4—7，共计安排7场。如图5所示。

n=7时,第二组赛程安排过程：

第二步：除了7号点外，分别从顺、逆时针方向3—6，4—5与1—2的位置对称，由近及远安排两场比赛,如图6所示。

第三步：未参加比赛的7号队与第1场中号数较大的队伍安排一场比赛7—2。从2号点沿本组第1场比赛1—2的方向走到1号点，然后向本组第2场比赛较小号数点3走，安排一场比赛1—3。从3走到6，向本组第3场比赛号数较小的4号队走，安排一场比赛6—4。从4走到5，最后从5走到7，安排一场比赛5—7,如图7所示。

图6 第2组前二步编排图

图7 第2组赛程编排图

n=7时,第3组赛程安排过程：

第二步：除了7号点外，分别从顺、逆时针方向1—4，5—6与2—3的位置对称，由近及远安排两场比赛,如图8所示。

第三步：未参加比赛的7号队与第1场中号数较大的队伍安排一场比赛7—3。从3号点沿本组第1场比赛2—3的方向走到2号点，然后向本组第2场比赛较大号数点4走，安排一场比赛2—4。从4走到1，向本组第3场比赛号数较小的5号队走，安排一场比赛1—5。从5走到6，最后从6走到7，安排一场比赛6—7,如图9所示。

图8 第3组前二步编排图

图9 第3组赛程编排图

用图论的方法，n=7时编排的赛程表如表14所示，各队每两场比赛间隔的场次数和总场次数如表15所示。

表14 n=7时图论方法编排的赛程表

表15 各队每两场比赛间隔的场次数和总场次数

对比表15与表11，7号队的间隔场次数和总场次数完全相同，1队与2队、2队与3队、3队与4队、4队与5队、5队与6队、6队与1队的间隔场次数和总场次数完全相同，说明两种编排方法都达到了最优。

同一场地的单循环比赛中，若参赛队伍数为奇数，则用构造推理法或图论的方法都能得到最优结果，且两种方法都有操作简单易于实现的优点。