最优单循环赛程编排方法

下面以 n=8 为例袁说明改进的贝格尔编排法
收稿日期院2018-10 -17 作者简介院谢 晓敏渊1984要冤袁女袁陕西宝鸡人袁川北幼儿师范高等专科学校初等教育系讲师袁研究方向院高等数学教育教学和数学建模遥
第2期
谢晓敏:最优单循环赛程编排方法
89
的编排过程遥 第 1 轮的编排与固定 1 逆时针轮转法相同袁
[ ] 场比赛最小相隔场次数的上界是 n-3 遥 很多文 圆 献都对此结论用或繁或简的方法进行了证明[2-4]遥 并 且 按 照文 献 [4-5]的 编 排 方 法 袁 结 论 可 以 推 广 到 n 渊n逸5冤支球队袁当 n 为偶数时袁每两场比赛相隔 场次数只有 n -2, n -1, n 曰当 n 为奇数时袁每两
单循环赛袁是指所有参赛队在竞赛中均能相 遇一次袁最后按各队在竞赛中的得分多少尧胜负 场次排列名次遥 这种赛制下袁参加竞赛的各队都 有相遇比赛的机会袁是一种比较公平合理的比赛 制度遥
假设有 n 支足球队在同一场地上进行单循 环比赛袁 如何安排赛程对各队来说都尽量公平 呢钥 各队每两场比赛最小相隔场次达到上界时袁 最大相隔场次数越小袁公平性越好[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袁于是 第 圆 轮第 圆 场比赛就是 1要6遥 其余的同理袁赛程 表如表 1 所示遥 各队每两场比赛间隔的场次数和 总场次数如表 2 所示遥
第一轮的编排按照 1 至 n 的顺序逆时针按
U 形走向分成均等两边遥
第二步院安排 n 号队遥
n 号队一直出现在每轮第 1 场比赛中遥 第 1 轮 n 在右边袁第 2 轮 n 要换到左边袁第 3 轮又换 到右边袁这样反反复复袁到第 1 轮又回到右边遥
第三步院安排第 2 轮至第 n-1 轮第 1 场比赛 中的另一个队伍遥
222 场比赛相隔场次数为 n-3 袁 n-1 [6]遥
22 本文作者根据现有文献和自己的研究分别 给出了 n 为奇数和 n 为偶数时符合最优相隔场 次数的编排方法遥
1.参赛队数 n 为偶数
单循环赛程比较经典的编排方法有两种院固 定 1 逆时针轮转法和贝格尔编排法[7]遥
固定 1 逆时针轮转法的优点是院参赛各队比 赛进度一致袁编排方法简单袁易操作袁便于检查遥 但是当参赛队伍超过 5 支时袁 对抽签为倒数第 2 的队伍极不公平袁因为从第四轮开始袁此队伍每 次都对战上一轮轮空的队伍遥
理编排法的编排过程遥 第一步院 按照每两场比赛相隔场次数公式
n-3 袁 n-1 计算袁可得间隔分别为 2,3遥 考虑 1 22
号队与其余的队伍都要进行比赛袁 那么就有 6 场比赛袁这 6 场比赛每两场中间至少插入两场 比赛遥 而 2 号队与除了 1 号队外的其余队伍要 进行 5 场比赛袁 这 5 场比赛刚好可以插入刚才 6 场比赛中遥 从第 2 轮开始 2 号队与 1 号队比 赛的队伍相同袁 于是第 1 轮 2 号队与最后一个 队伍 7 号队比赛遥第一步安排结果如表 4 所示遥
公 式 n -2, n -1, n 计算袁 可得间隔分别 为
2
2
2
2,3,4袁说明我们上述的编排方法是最优的遥
2.改进的贝格尔编排法编排步骤
当 n逸5 为偶数时袁 单循环赛程的总场次数
为
Cn2=
n(n-1) 2
场袁总轮数为
n-1
轮袁每轮
n 2
场比
赛袁改进的贝格尔编排方法编排步骤如下遥
第一步院编排第 1 轮遥
表 1 改进的贝格尔编排法编制的赛程表
1要8 2要7 3要6 4要5
8要7 1要6 2要5 3要4
6要8 7要5 1要4 2要3
8要5 6要4 7要3 1要2
4要8 5要3 6要2 7要1
8要3 4要2 5要1 6要7
2要8 3要1 4要7 5要6
表 2 各队每两场比赛间隔场次数和总场次数
当 n=8 时袁 按照每两场比赛相隔场次数
圆园员9 年 6 月 ZUO UNIVERSITY
晕o.2 June 2019
最优单循环赛程编排方法
谢晓敏
渊川北幼儿师范高等专科学校初等教育系袁四川 广元 628017冤
摘要院针对单循环赛程编排问题袁探讨参赛队伍数目 n 分别为奇数和偶数的情形遥 当 n(n逸5) 为偶数时袁给出了改进的贝格尔编排法袁保证每两场间隔场次数只有 n -2, n -1, n 遥 重点讨
222 论了当 n(n逸5)为奇数时的情形袁用构造推理法和图论的方法分别给出了每两场间隔场次数 只有 n-3 袁 n-1 的编排方法的全过程袁这两种方法都简单袁易于实现遥 作为特例袁给出了 n=8
22 和 n=7 的赛程编排遥 关键词院单循环曰赛程编排曰贝格尔编排法曰构造推理法曰图论 中图分类号院O29 文献标志码院A 文章编号院员园园愿原苑圆缘苑渊圆园员9冤园2原园088原园6
贝格尔编排法是目前单循环赛应用比较广 泛的一种编排方法遥 国际联排所举办的世界排球 锦标赛尧世界杯排球赛尧奥运会排球赛及世界青 年排球锦标赛袁国内的一些球类项目及棋类项目 也采用贝格尔编排法遥 但是袁贝格尔编排法编制 的赛程表并未达到最优赛程要求的每两场比赛 相隔场次数遥 于是袁我们改进贝格尔编排法袁使其 达到最优赛程的要求袁得到 n 为偶数时的单循环 赛程表遥 1.改进的贝格尔编排法编制 n=8 的赛程表
前一轮第 2 场比赛右边的队伍提到本轮第 一场比赛袁与 n 号队完成一场比赛袁其余队伍按 照逆时针轮转编排就可以了遥 编排的赛程表如表 3 所示遥
表 3 n 为偶数时的改进贝格尔编排法
圆援参赛队数 n 为奇数
圆援员 构造推理编排法编排 n=7 的赛程表 下面以 n=7 为例袁说明 n 为奇数时的构造推