最優(yōu)單循環(huán)賽程編排方法

謝曉敏

（川北幼兒師范高等?？茖W校初等教育系，四川 廣元628017）

單循環(huán)賽，是指所有參賽隊在競賽中均能相遇一次，最后按各隊在競賽中的得分多少、勝負場次排列名次。這種賽制下，參加競賽的各隊都有相遇比賽的機會，是一種比較公平合理的比賽制度。

假設(shè)有n支足球隊在同一場地上進行單循環(huán)比賽，如何安排賽程對各隊來說都盡量公平呢？各隊每兩場比賽最小相隔場次達到上界時，最大相隔場次數(shù)越小，公平性越好[1]。而各隊每兩場比賽最小相隔場次數(shù)的上界是很多文獻都對此結(jié)論用或繁或簡的方法進行了證明[2-4]。并且按照文獻[4-5]的編排方法，結(jié)論可以推廣到n（n≥5）支球隊，當n為偶數(shù)時，每兩場比賽相隔場次數(shù)只有當n為奇數(shù)時，每兩場比賽相隔場次數(shù)為

本文作者根據(jù)現(xiàn)有文獻和自己的研究分別給出了n為奇數(shù)和n為偶數(shù)時符合最優(yōu)相隔場次數(shù)的編排方法。

1.參賽隊數(shù)n為偶數(shù)

單循環(huán)賽程比較經(jīng)典的編排方法有兩種：固定1逆時針輪轉(zhuǎn)法和貝格爾編排法[7]。

固定1逆時針輪轉(zhuǎn)法的優(yōu)點是：參賽各隊比賽進度一致，編排方法簡單，易操作，便于檢查。但是當參賽隊伍超過5支時，對抽簽為倒數(shù)第2的隊伍極不公平，因為從第四輪開始，此隊伍每次都對戰(zhàn)上一輪輪空的隊伍。

貝格爾編排法是目前單循環(huán)賽應用比較廣泛的一種編排方法。國際聯(lián)排所舉辦的世界排球錦標賽、世界杯排球賽、奧運會排球賽及世界青年排球錦標賽，國內(nèi)的一些球類項目及棋類項目也采用貝格爾編排法。但是，貝格爾編排法編制的賽程表并未達到最優(yōu)賽程要求的每兩場比賽相隔場次數(shù)。于是，我們改進貝格爾編排法，使其達到最優(yōu)賽程的要求，得到n為偶數(shù)時的單循環(huán)賽程表。

1.改進的貝格爾編排法編制n=8的賽程表

下面以n=8為例，說明改進的貝格爾編排法的編排過程。

第1輪的編排與固定1逆時針輪轉(zhuǎn)法相同，即按照1至8的順序逆時針按U形走向分成均等兩邊。

接下來先安排8號隊，第1輪8在右邊，第2輪8要換到左邊，第3輪又換到右邊，這樣反反復復，到第7輪8又回到右邊。

然后安排其余的隊伍。貝格爾編排法是將前一輪右下角的數(shù)字提到本輪第一行來，其余隊伍按照逆時針輪轉(zhuǎn)。改進的貝格爾編排法是將前一輪第二行右邊的數(shù)字提到本輪第一行來，其余隊伍按照逆時針輪轉(zhuǎn)編排就可以了。例如：第1輪第2行右邊數(shù)字是7，應該提到第2輪第1行，第2輪的第1場比賽就是8—7。按照逆時針方向看，7的后面是6，前面是8,8的前面是1，于是第2輪第2場比賽就是1—6。其余的同理，賽程表如表1所示。各隊每兩場比賽間隔的場次數(shù)和總場次數(shù)如表2所示。

表1 改進的貝格爾編排法編制的賽程表

表2 各隊每兩場比賽間隔場次數(shù)和總場次數(shù)

2.改進的貝格爾編排法編排步驟

第一步：編排第1輪。

第一輪的編排按照1至n的順序逆時針按U形走向分成均等兩邊。

第二步：安排n號隊。

n號隊一直出現(xiàn)在每輪第1場比賽中。第1輪n在右邊，第2輪n要換到左邊，第3輪又換到右邊，這樣反反復復，到第1輪又回到右邊。

第三步：安排第2輪至第n-1輪第1場比賽中的另一個隊伍。

前一輪第2場比賽右邊的隊伍提到本輪第一場比賽，與n號隊完成一場比賽，其余隊伍按照逆時針輪轉(zhuǎn)編排就可以了。編排的賽程表如表3所示。

表3 n為偶數(shù)時的改進貝格爾編排法

2.參賽隊數(shù)n為奇數(shù)

2.1 構(gòu)造推理編排法編排n=7的賽程表

下面以n=7為例，說明n為奇數(shù)時的構(gòu)造推理編排法的編排過程。

表4 n=7時編排方法第一步結(jié)果

第二步：按照要求每個參賽隊的間隔場次數(shù)至少為2，表4中每輪的兩場比賽中也要至少插入2場比賽。剩余的比賽場次數(shù)為場，按要求前5輪比賽每兩場之間應該平均地插入2場比賽。此時n=7的賽程編排框架就搭建好了，如表5所示。

表5 n=7賽程編排框架

第三步：因為1至5輪只有1支隊伍可以出現(xiàn)2次，其余只能出現(xiàn)1次，否則必然不滿足相隔至少兩場的要求。剩余10場比賽分別為：3—4，3—5，3—6，3—7，4—5，4—6，4—7，5—6，5—7，6—7。對于3—5而言，既不能出現(xiàn)在第2輪，也不能出現(xiàn)在第4輪。注意到1—3的位置，3—5不能出現(xiàn)在第1輪第3場。2—3的位置決定3—5不能出現(xiàn)在第3輪第2場，1—5的位置決定3—5不能出現(xiàn)在第3輪第3場，2—5決定3—5不能出現(xiàn)在第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場比賽總場數(shù)為11場，而第2場到第13場之間只有10場。故只能將3—5安排在第5輪第3場。于是第5輪第1場只能安排4—7。編排結(jié)果如表6所示。

表6 第5輪賽程編排

第四步：根據(jù)3—5的位置，第4輪第3場必須安排3號隊參與比賽，否則與3—5的間隔就會大于3，有3號隊參與的比賽還剩3—4，3—6，3—7，根據(jù)1—6的位置，此場比賽不能安排3—6。若安排3—7，則第4輪第2場必為4—6，與2—4的位置不符合間隔至少2場的要求。所以，第4輪第3場必須安排3—4，第4輪第2場只能安排6-7。安排結(jié)果如表7所示。

表7 第4輪賽程編排

第五步：根據(jù)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。安排結(jié)果如表8所示。

表8 第3輪賽程編排

第六步：3—6不能安排在第2輪，只能安排在第1輪，1—3的位置決定不能安排在第1輪第3場，只能安排在第1輪第2場，第1輪第3場必為4—5。安排結(jié)果如表9所示。

表9 第1輪賽程編排

第七步：最后剩的兩場比賽為4—6和5—7，根據(jù)1—4的位置，決定第2輪第3次不能安排4—6，只能安排5—7，第2輪第2場就只能4—6。到此賽程安排結(jié)束，最終的最優(yōu)賽程表如表10所示，各隊每兩場比賽間隔的場次數(shù)和總場次數(shù)如表11所示。

表10 n=7的最優(yōu)賽程表

表11 各隊每兩場比賽間隔場次數(shù)和總場次數(shù)

2.2 構(gòu)造推理編排法編排步驟

此編排方法我們可以推廣到n(n≥5)為任意奇數(shù)，編排方法如下。

第一步：構(gòu)造出編排框架，如表12所示。

表12 構(gòu)造推理法編排框架

第二步：第1至n-2輪將平均插入場比賽。第n-1輪只有一場比賽，于是我們只需要編排第1至n-2輪。規(guī)定：賽程中同一場比賽的兩支隊伍左邊參賽隊的編號永遠比右邊小。編排結(jié)果如表13所示。

表13 n(n≥5)為任意奇數(shù)第1至(n-2)輪編排結(jié)果

2.3 圖論解釋

n=7的單循環(huán)賽程編排可以看成是圖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組編排圖

三組圖無重合，合在一起是一個完全圖。每組編排的圖，無論從哪個點開始都可以經(jīng)過所有的點一次回到起始點。

2.4 單循環(huán)賽程n為奇數(shù)的圖論模型

n支球隊用點v1，v2,……,vn表示，由于n支球隊的單循環(huán)賽每兩支球隊之間均需比賽一場，即任意兩點之間都有一條邊相連，所以n支球隊的單循環(huán)賽對應一個無向完全圖Kn。完全圖Kn有條邊，對應n支球隊的場賽比賽程。場比賽分成組，每組n場比賽。每組的編排方法基本類似，第1組編排方法如下。

第一步：把n個點v1，v2,……,vn按順時針方向排列成一個由n個孤立點構(gòu)成的一個“圈”[8]。

第二步：確定奇數(shù)個參賽隊中不參加比賽的隊伍，可以是任意一個隊伍。剩余隊伍數(shù)目為偶數(shù)個，以不參賽隊所處點為參照點，安排分別從順、逆時針方向看，處在“圈”上對稱位置的兩個隊伍完成一場比賽，按照由近及遠或由遠及近的順序均可，每隊只能參加一場比賽，共計場比賽。

第三步：第二步中未參加比賽的隊伍與第1場比賽中號數(shù)較小的隊伍完成一場比賽，為第場比賽。從第1場比賽中號數(shù)較小的隊伍代表的頂點開始按照圖中有線的路徑行走，若走到?jīng)]有路徑的地方，則按向第二步第2場比賽中較小號數(shù)所在頂點方向行走，增加一條路徑，每增加一條路徑則安排一場比賽。如此反復，直到走到第二步第場比賽號數(shù)較大的頂點，共安排場比賽。從剛才結(jié)束的頂點最終走到第二步未參加比賽的隊伍所處頂點，再安排一場比賽，即第n場比賽。

第二步：在“圈”中除去第1組第二步未參加比賽的隊伍所代表的點，此時剩余偶數(shù)個點，分別從順、逆時針方向選擇與本組第1場比賽對稱的點安排一場比賽，共計場。

第三步：本組未參加比賽的隊伍與本組第1場比賽中號數(shù)較大的隊伍安排一場比賽。從本組第1場比賽中號數(shù)較大的隊伍開始沿本組第1場比賽的方向行走，到?jīng)]有路徑的時候則向本組第2場比賽號數(shù)較小的隊伍方向行走，增加一條路徑，安排一場比賽。若已經(jīng)與較小號數(shù)隊伍進行過比賽，則向號數(shù)較大的隊伍行走，安排一場比賽，如此反復，最終走到本組第場號數(shù)較大隊伍所在的頂點，共安排場比賽。從剛才結(jié)束的頂點最終走到本組第二步未參加比賽的隊伍所處頂點，再安排一場比賽，即第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場比賽中號數(shù)較小的隊伍，即1號隊進行一場比賽。然后從1開始走到6,6出發(fā)就沒有路徑了，按照向第二步第2場比賽較小號碼的方向行走，增加路徑為6—2，即安排一場比賽。繼續(xù)往下走，到5號沒有路徑，按要求向3號走，安排一場比賽，即5—3。繼續(xù)走到4，最后應該走向第二步?jīng)]參賽的7號隊，安排一場比賽4—7，共計安排7場。如圖5所示。

n=7時,第二組賽程安排過程：

第二步：除了7號點外，分別從順、逆時針方向3—6，4—5與1—2的位置對稱，由近及遠安排兩場比賽,如圖6所示。

第三步：未參加比賽的7號隊與第1場中號數(shù)較大的隊伍安排一場比賽7—2。從2號點沿本組第1場比賽1—2的方向走到1號點，然后向本組第2場比賽較小號數(shù)點3走，安排一場比賽1—3。從3走到6，向本組第3場比賽號數(shù)較小的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場中號數(shù)較大的隊伍安排一場比賽7—3。從3號點沿本組第1場比賽2—3的方向走到2號點，然后向本組第2場比賽較大號數(shù)點4走，安排一場比賽2—4。從4走到1，向本組第3場比賽號數(shù)較小的5號隊走，安排一場比賽1—5。從5走到6，最后從6走到7，安排一場比賽6—7,如圖9所示。

圖8 第3組前二步編排圖

圖9 第3組賽程編排圖

用圖論的方法，n=7時編排的賽程表如表14所示，各隊每兩場比賽間隔的場次數(shù)和總場次數(shù)如表15所示。

表14 n=7時圖論方法編排的賽程表

表15 各隊每兩場比賽間隔的場次數(shù)和總場次數(shù)

對比表15與表11，7號隊的間隔場次數(shù)和總場次數(shù)完全相同，1隊與2隊、2隊與3隊、3隊與4隊、4隊與5隊、5隊與6隊、6隊與1隊的間隔場次數(shù)和總場次數(shù)完全相同，說明兩種編排方法都達到了最優(yōu)。

同一場地的單循環(huán)比賽中，若參賽隊伍數(shù)為奇數(shù)，則用構(gòu)造推理法或圖論的方法都能得到最優(yōu)結(jié)果，且兩種方法都有操作簡單易于實現(xiàn)的優(yōu)點。