赛程安排的图论模型_2002年全国大学生数学建模竞赛D题

北京建筑工程学院学报 第 19卷第 4期 2003年 12月 JOURNAL OF BEIJING INST ITUTE OF CIVIL ENGINEERING AND ARCHITECTURE Vol. 19 No. 4 Dec. 2003 文章编号: 1004- 6011(2003) 04- 0072- 05 赛程安排的图论模型 ) ) ) 2002年全国大学生数学建模竞赛 D 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 y 代西武 李群高 李秀琴 (基础部,北京 100044) 摘 要:通过建立赛程安排的图论模型, 圆满解决了 2002年全国大学生数学建模竞赛 D题的前三个问 题。提出了对于任意 n 支球队进行单循环比赛的赛程编制方法,该方法简单易行, 只须手工编排,并证 明了该方法编制的赛程使得各队每两场比赛最小相隔的场次数达到了理论上限。 关键词:完美匹配; Haimlton ) 圈;单循环赛 中图分类号: O226 文献标识码:A 1 原题重述 今有 5支球队在同一块场地上进行单循环赛, 共要进行 10场比赛,如何安排赛程使得对各队来说 都尽量公平呢? 下面是随便安排的一个赛程:记 5 支球队为 A, B, C, D, E,在下 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 左半部分的右上三角 的 10个空格中, 随手填上 1, 2, , , 10, 就得到一个 赛程,即第1场A对 B, 第2场B对 C, , ,第 10场 C 对 E。为方便起见将这些数字沿对角线对称地填入 左下三角。 这个赛程的公平性如何呢,不防只看看各队每 两场比赛中间得到的休整时间是否均等, 表的右半 部分是各队每两场比赛间相隔的场次数, 显然这个 赛程对A, E有利, 对 D则不公平。 A B C D E 每两场比赛间相隔场次数 A X 1 9 3 6 1 2 2 B 1 X 2 5 8 0 2 2 C 9 2 X 7 10 4 1 0 D 3 5 7 X 4 0 0 1 E 6 8 10 4 X 1 1 1 从上面的例子出发讨论以下问题: 1) 对于 5支球队的比赛,给出一个各队每两场 比赛中间都至少相隔一场的赛程; 2) 当 n支球队比赛时,各队每两场比赛最小相 隔场次数的上界是什么; 3) 在达到 2)的上限的条件下,给出 n= 8, n= 9 的赛程,并说明它们的编制过程; 4) 除了每两场比赛间相隔场次数这一指标外, 你还能给出哪些指标来衡量一个赛程的优劣,并说 明 3)中给出的赛程达到这些指标的程度。 2 n 支球队比赛时, 各队每两场比赛 中间都至少相隔的场次数的上限 符号说明: 0, 1, 2, , , ( n- 1) :表示 n支球队; ( i, j) :表示球队 i与球队 j进行的一 场比赛; [ x] :表示不超过实数 x的最大整数。 定理 1 当 n 支球队比赛时, 各队每两场比赛 中间都至少相隔的场次数的上限是: n + 12 - 2。 证明: 因 n + 12 - 2 = m - 2,当 n = 2m 时 m - 1,当 n = 2m + 1时,所以 分两种情形来证明。 情形1 当 n = 2m为偶数时,这2m支球队为 y 收稿日期: 2003- 09- 26 作者简介:代西武( 1963年 ) ) ,男,理学硕士,副教授,从事图论、数学建模、计算机科学等方面的研究工作。 0, 1, 2, , , (2m - 1)。顺次安排( m + 1) 场比赛需要 2( m + 1) 支球队参加, 由鸽笼原理, 必然有重复出 现的球队,由单循环赛知,重复出现的球队中一定存 在某球队,其两场比赛中间相隔的场次数最多为 m - 2。 情形2 当 n = 2m+ 1为奇数时,这2m+ 1支 球队为 0, 1, 2, , , 2m。顺次安排( m + 1) 场比赛需 要 2( m + 1) 支球队参加,由鸽笼原理, 必然有重复 出现的球队,则该球队的两场比赛中间相隔的场次 数最多为 m - 1。 定义 1:当 n 支球队比赛时,若安排的赛程使得 各队每两场比赛中间都至少相隔 n + 12 - 2 场比 赛,则称该赛程为完美赛程。称条件/各队每两场比 赛中间都至少相隔 n + 12 - 2场0为完美要求。 3 图论模型的建立 有关的图论术语符号, 可参阅[1]。 定义2:定义图 G( V, E ) , 其中顶点集 V = {0, 1, 2, , , ( n - 1) } 是 n 支球队的集合, 边集 E = {( i , j ) | i , j I V},即任意二球队的比赛是一条边, 称此图 G( V, E ) 为 n 支球队的比赛图。 显然, n 支球队的比赛图 G( V, E ) 是完全图 Kn。 311 当参赛队数 n = 2m为偶数时的情形 定理 2 当 n = 2m时, 比赛图 K2m 可表示为 ( 2m- 1) 个边不重的完美匹配的并图。 证明: K2m 的顶点为: 0, 1, 2, , , ( 2m - 1)。将 0 放在正( 2m- 1)边形的中心,而将1, 2, , , ( 2m- 1) 顺次放在正( 2m- 1) 边形的顶点上,则每条径向边 ( 0, j) 与垂直于它的各边一起构成一个完美匹配。共 有( 2m - 1) 个这样的完美匹配M1, M2, , , M2m- 1, 其边是互不相重的,并且 K2m恰好是它们的并图。 对于K2m的( 2m- 1) 个边不重的完美匹配M1, M2, , , M2m- 1,可按径向边( 0, j) 顺次写出如下: M1= { ( 0, 1) , ( 2, 2m- 1) , ( 3, 2m- 2) , ( 4, 2m- 3) , , , , ( m- 1, m+ 2) , ( m, m+ 1) } M2= { ( 0, 2) , ( 3, 1) , ( 4, 2m- 1) , ( 5, 2m- 2) , , , , ( m, m+ 3) , ( m+ 1, m+ 2) } M3= { ( 0, 3) , ( 4, 2) , ( 5, 1) , ( 6, 2m- 1) , , , , ( m+ 1, m+ 4) , ( m+ 2, m+ 3) } s M2m- 2= { (0, 2m- 2) , ( 2m- 1, 2m- 3) , ( 1, 2m- 4) , ( 2, 2m- 5) , , , , ( m- 3, m) , ( m- 2, m- 1) } M2m- 1= { (0, 2m- 1) , ( 1, 2m- 2) , ( 2, 2m- 3) , ( 3, 2m- 4) , , , , ( m- 2, m+ 1) , ( m- 1, m) } 定理 3 当 n = 2m(偶数) 支球队进行单循环 赛时,存在完美赛程。 证明:将 K 2m的(2m - 1) 个边不重的完美匹配 M1, M2, , , M2m- 1 中的边顺次编号 1, 2, 3, , , m(2m - 1) , 即是使得各队每两场比赛中间都至少 相隔( m - 1) 场的赛程,即是完美赛程。下面证明此 结论。 每一完美匹配 Mi ( i = 1, 2, , , 2m - 1) 中边的 顺次编号(即安排比赛) 不会有重复的球队, 所以只 须考虑相邻的完美匹配 Mi , Mi+ 1( i = 1, 2, , , 2m - 2) 中的边的顺次编号所相隔的场次数。由于 M1, M2, , , M2m- 1的结构相同,所以只须研究 M1, M2, 中的边的顺次编号所相隔的场次数。 M1= { ( 0, 1) , ( 2, 2m- 1) , ( 3, 2m- 2) , ( 4, 2m- 3) , , , , ( m- 1, m+ 2) , ( m, m+ 1) } 编号: 1 2 3 4 , , m- 1 m M2= { ( 0, 2) , ( 3, 1) , ( 4, 2m- 1) , ( 5, 2m- 2) , , , , ( m, m+ 3) , ( m+ 1, m+ 2) } 编号: m+ 1 m+ 2 m+ 3 m+ 4 , , 2m- 1 2m 我们观察可以发现:第 m+ 1场比赛的参赛队 是球队0和球队2,而此二队在第3 ~ m场比赛中未 出现,所以第 m+ 1场比赛的安排满足完美要求。第 ( m + i) , ( i = 2, 3, , , m- 1) 场比赛的参赛球队正 好是第( i - 1) 与第( i + 1) 场比赛中的球队,此二队 在第( i+ 1) ~ ( m+ i- 1) 场比赛中未出现,所以这 些场比赛的安排满足完美要求。第 2m 场比赛的参 赛球队是球队( m + 1) 和球队( m + 2) ,也满足完美 73第 4 期 代西武 李群高等:赛程安排的图论模型 要求。 312 当参赛队数 n = 2m+ 1为奇数时的情形 定理4 当n = 2m+ 1时, 比赛图K2m+ 1可表示 为 m个边不重的 Hamilton - 圈的并图。 证明: K2m+ 1 的顶点为: 0, 1, 2, , , 2m。将 0放在 单位圆的圆心, 而将 1, 2, , , 2m顺次等距地放在圆 周上,则 C1= (0, 1, 2, 2m, 3, 2m- 1, 4, 2m- 2, , , m, m+ 2, m+ 1, 0) 就是 K 2m+ 1的一个Hamilton- 圈。考虑将C1绕顶点 0旋转( m - 1) 次,可以得到其它的 Hamil ton - 圈, 共有 m 个Hamilton - 圈: C1, C2, , , Cm ,其边是互 不相重的,并且 K 2m+ 1恰好是它们的并图。 对于K 2m+ 1的 m个边不重的Hamilton- 圈 C1, C2, , , Cm ,可按旋转的顺序写出如下: C1= ( 0, 1, 2, 2m, 3, 2m- 1, 4, 2m- 2, , , m, m+ 2, m+ 1, 0) C2= ( 0, 2, 3, 1, 4, 2m, 5, 2m- 1, , , m+ 1, m+ 3, m+ 2, 0) C3= ( 0, 3, 4, 2, 5, 1, 7, 2m, , , m+ 2, m+ 4, m+ 3, 0) s Cm- 1= ( 0, m- 1, m, m- 2, m+ 1, m- 3, m+ 2, m- 4, , , 2m- 2, 2m, 2m- 1, 0) Cm= ( 0, m, m+ 1, m- 1, m+ 2, m- 2, m+ 3, m- 3, , , 2m- 1, 1, 2m, 0) 定理 5 当 n= 2m+ 1(奇数)支球队进行单循 环赛时,存在完美赛程。 证明:对 K2m+ 1的 Hamilton - 圈 C1 中的边按 如下方法编号: 类似地, 对 C2, , , Cm 中的边顺次继续编号 (2m+ 2)、(2m+ 3)、, 、m(2m+ 1) ,这样的编号即 是使得各队每两场比赛中间都至少相隔( m - 1) 场 的赛程,即是完美赛程。下面证明此结论。 显然,在每一Hamilton- 圈 Ci ( i = 1, 2, , , m) 内部,其边的顺次编号(即安排比赛) 使得各球队的 两比赛中间至少相隔( m - 1) 场。所以只须考虑相 邻的 Hamilton - 圈 Ci、Ci+ 1( i = 1, 2, , , m - 1) 中 的边的顺次编号所相隔的场次数。由于 C1, C2, , , Cm的结构相同, 所以只须研究 C1, C2 中的边的顺 次编号所相隔的场次数, 事实上, 只须研究 C2 中的 第(2m+ 2) ~ (3m+ 2) 场比赛即可。 研究可以发现:第2m+ 2场比赛的参赛队是球 队0和球队2,而此二队在第( m+ 3) ~ (2m+ 1) 场 比赛中未出现,所以第2m+ 2场比赛的安排满足完 美要求。第( 2m+ i) , ( i = 3, 4, , , m+ 1) 场比赛的 参赛球队正好是第( m+ i - 1)与第( m+ i) 场比赛 中的球队,此二队在第( m + i + 1) ~ (2m+ i - 1) 场比赛中未出现, 所以这些场比赛的安排满足完美 要求。第3m+ 2场比赛的参赛队是球队( m + 2) 和 球队 0,也满足完美要求。 4 完美赛程的编制方法 对于 m = 2m(偶数) 支球队进行单循环赛,根 据定理2 ~ 3,我们得到编制完美赛程的一种简单方 法,叙述如下: 第一步:顺次写出 K 2m的(2m- 1) 个边不重的 完美匹配 M1, M2, , , M2m- 1如下: 74 北京建筑工程学院学报 第 19 卷 M1= { ( 0, 1) , ( 2, 2m- 1) , ( 3, 2m- 2) , ( 4, 2m- 3) , , , , ( m- 1, m+ 2) , ( m, m+ 1) } M2= { ( 0, 2) , ( 3, 1) , ( 4, 2m- 1) , ( 5, 2m- 2) , , , , ( m, m+ 3) , ( m+ 1, m+ 2) } M3= { ( 0, 3) , ( 4, 2) , ( 5, 1) , ( 6, 2m- 2) , , , , ( m+ 1, m+ 4) , ( m+ 2, m+ 3) } s M2m- 2= { (0, 2m- 2) , ( 2m- 1, 2m- 3) , ( 1, 2m- 4) , ( 2, 2m- 5) , , , , ( m- 3, m) , ( m- 2, m- 1) } M2m- 1= { (0, 2m- 1) , ( 1, 2m- 2) , ( 2, 2m- 3) , ( 3, 2m- 4) , , , , ( m- 2, m+ 1) , ( m- 1, m) } 第二步: 顺次将配 M1, M2, , , M2m- 1 中的边 编号 1, 2, 3, , , m(2m - 1) , 此即是所要的完美赛 程。 当 n = 8时,根据上述方法,完美赛程的编制过 程如下: 完美匹配 M1= {( 0, 1) , ( 2, 7) , ( 3, 6) , ( 4, 5) } 匹配中边的编号 1 2 3 4 完美匹配 M2= {( 0, 2) , ( 3, 1) , ( 4, 7) , ( 5, 6) } 匹配中边的编号 5 6 7 8 完美匹配 M3= {( 0, 3) , ( 4, 2) , ( 5, 1) , ( 6, 7) } 匹配中边的编号 9 10 11 12 完美匹配 M4= {( 0, 4) , ( 5, 3) , ( 6, 2) , ( 7, 1) } 匹配中边的编号 13 14 15 16 完美匹配 M5= {( 0, 5) , ( 6, 4) , ( 7, 3) , ( 1, 2) } 匹配中边的编号 17 18 19 20 完美匹配 M6= {( 0, 6) , ( 7, 5) , ( 1, 4) , ( 2, 3) } 匹配中边的编号 21 22 23 24 完美匹配 M7= {( 0, 7) , ( 1, 6) , ( 2, 5) , ( 3, 4) } 匹配中边的编号 25 26 27 28 用矩阵表达此完美赛程如下: 0 1 2 3 4 5 6 7 每两场比赛间相隔场次数 0 X 1 5 9 13 17 21 25 3, 3, 3, 3, 3, 3, 1 1 X 20 6 23 11 26 16 4, 4, 4, 3, 2, 2, 2 5 20 X 24 10 27 15 2 2, 4, 4, 4, 3, 2, 3 9 6 24 X 28 14 3 19 2, 2, 4, 4, 4, 3, 4 13 23 10 28 X 4 18 7 2, 2, 2, 4, 4, 4, 5 17 11 27 14 4 X 8 22 3, 2, 2, 2, 4, 4, 6 21 26 15 3 18 8 X 12 4, 3, 2, 2, 2, 4, 7 25 16 2 19 7 22 12 X 4, 4, 3, 2, 2, 2, 对于n= 2m+ 1(奇数)支球队进行单循环赛,根 据定理 4~ 5,我们得到编制完美赛程的一种简单方 法,叙述如下: 第一步: 顺次写出 K2m+ 1的 m 个边不重的 Hamilton- 圈 C1, C2, , , Cm如下: C1= ( 0, 1, 2, 2m, 3, 2m- 1, 4, 2m- 2, , , m, m+ 2, m+ 1, 0) C2= ( 0, 2, 3, 1, 4, 2m, 5, 2m- 1, , , m+ 1, m+ 3, m+ 2, 0) C3= ( 0, 3, 4, 2, 5, 1, 7, 2m, , , m+ 2, m+ 4, m+ 3, 0) s Cm- 1= ( 0, m- 1, m, m- 2, m+ 1, m- 3, m+ 2, m- 4, , , 2m- 2, 2m, 2m- 1, 0) Cm= ( 0, m, m+ 1, m- 1, m+ 2, m- 2, m+ 3, m- 3, , , 2m- 1, 1, 2m, 0) 第二步,按如下方法对Hamilton- 圈 C1 中的边顺次编号: 类似地,对 C2, , , Cm 中的边顺次继续编号( 2m + 2) , ( 2m+ 3) , , , m( 2m+ 1) , 这样的编号即是所 需要的完美赛程。 当 n= 9时, 根据上述方法, 完美赛程的编制过 程如下: 75第 4 期 代西武 李群高等:赛程安排的图论模型 C1= 0, 1, 2, 8, 3, 7, 4, 6, 5, 0 ) 边的编号: 1 6 2 7 3 8 4 9 5 C2= 0, 2, 3, 1, 4, 8, 5, 7, 6, 0 ) 边的编号: 10 15 11 16 12 17 13 18 14 C3= 0, 3, 4, 2, 5, 1, 6, 8, 7, 0 ) 边的编号: 19 24 20 25 21 26 22 27 23 C4= 0, 4, 5, 3, 6, 2, 7, 1, 8, 0 ) 边的编号: 28 33 29 34 30 35 31 36 32 用矩阵表达此完美赛程如下: 0 1 2 3 4 5 6 7 8 每两场比赛间相隔场次数 0 X 1 10 19 28 5 14 23 32 3, 4, 3, 4, 3, 4, 3, 1 1 X 6 11 16 21 26 31 36 4, 4, 4, 4, 4, 4, 4, 2 10 6 X 15 20 25 30 35 2 3, 3, 4, 4, 4, 4, 4, 3 19 11 15 X 24 29 34 3 7 3, 3, 3, 3, 4, 4, 4, 4 28 16 20 24 X 33 4 8 12 3, 3, 3, 3, 3, 3, 4, 5 5 21 25 29 33 X 9 13 17 3, 3, 3, 3, 3, 3, 3, 6 14 26 30 34 4 9 X 18 22 4, 4, 3, 3, 3, 3, 3, 7 23 31 35 3 8 13 18 X 27 4, 4, 4, 4, 3, 3, 3, 8 32 36 2 7 12 17 22 27 X 4, 4, 4, 4, 4, 4, 3, 同样可以编制当 n = 5时的完美赛程。(略) 5 其它问题 1) 将 完 美 匹 配 M1, M2, , , M2m- 1( 或 Hamilton - 圈 C1, C2, , , Cm) 顺序滚动重排后, 按 照上面给出的赛程编制方法, 可以得到其它的完美 赛程。 2) 将 赛 程 按 照 完 美 匹 配 M1, M2, , , M2m- 1(或Hamilton - 圈 C1, C2, , , Cm) 分成若干 轮,一支球队出场的轮次越靠后面越有利,在同一轮 次里出场的顺序越靠后越有利。按照这种思想, 可给 出衡量一个赛程优劣的另一指标。 参考文献: [ 1] J. A. 邦迪,U . S. R.默蒂 1 图论及其应用[ M ]1 北京:科学出 版社, 1984 [ 2] 卢开澄 1 组合数学[ M ]1北京:清华大学出版社, 1991 The Graph Model of Match Scheduling Dai Xiwu Li Qungao Li Xiuqin ( Dept . of Basic Sciences, Beijing 100044) Abstr act: Establishing the graph model of match scheduling, the first three questions of problem D of 2002. s Chinese mathematical contest in modeling are solved sat isfactorily. A method to schedule a single- round robin of N teams is proposed. T he method is simple and it can be done by hand. Moreover, the following conclusion is proved: In the match schedule made by the method, the minimum number of matches between every two matches of each team reaches the theoret ical upper bound. Key words: perfect matching; hamilton cycle; single- round robin 76 北京建筑工程学院学报 第 19 卷