K_v的完備匹配M_i的算法

摘 要：給出了邊矩陣的定義，提出了求解完備匹配Mi的2種算法.其中算法A是利用邊矩陣K′2n的Δ(G)-邊著色求Mi，算法B是利用邊矩陣K′2n的2×2子矩陣劃分及完全圖Kn的n-1個(gè)完備匹配M′i的求解，再求Mi.介紹了用算法A構(gòu)造循環(huán)賽圖K（i)20的過(guò)程和用算法B構(gòu)造循環(huán)賽圖K（i)20的過(guò)程.



關(guān)鍵詞：完備匹配；完全圖；算法；邊矩陣；邊著色

中圖分類(lèi)號(hào)：O157 文獻(xiàn)標(biāo)識(shí)碼：A

Algorithms of Determining Any Perfect Matching Mi of Kv



ZHENG Chang-bo1， LI Xiao-yi2， CHOU Wan-xi3

(1. Vocational and Technical College，Dalian Ocean Univ，Dalian， Liaoning 116300，China;

2. School of Mathematics and Systems Science， Shenyang Normal Univ， Shenyang， Liaoning 110034， China;

3. School of Civil Engineering and Architecture， Anhui Univ of Science and Technology， Huainan， Anhui 232001， China)

Abstract:A definition of edge-matrix was given. And two algorithms for determining perfect matching Mi were proposed， of which the algorithm A is determined by using Δ（G）-edge coloring of edge-matrix K′2n， and the algorithm B to perfectly match Mi is determined by partitioning edge-matrix K′v into 2×2 sub matrix and also by solving n-1 perfect matching M′i of a complete graph Kn .The procedures of constructing round-robin tournament K(i)20 by using the algorithm A and using algorithm B were presented respectively.

Key words:dual；perfect matching；complete graph；algorithm；edge matrix；edge coloring



設(shè)G為完全圖K6，完全圖K6也稱(chēng)為競(jìng)賽圖，但完全圖K6尚無(wú)助于6名棋手的循環(huán)賽的名單安排，尚若用Δ(G)=5種顏色對(duì)K6進(jìn)行Δ(G)-邊著色，則該完全圖K6就成為可用于循環(huán)賽安排的循環(huán)賽圖，并記為Ki6，i表示6名棋手的循環(huán)賽的輪次.但是，當(dāng)n>10時(shí)，針對(duì)高階的完全圖K2n實(shí)施Δ(G)-邊著色是不可能的［1-6］.為解決這一矛盾，本文提出了用Δ(G)種顏色A，B，C，…，X，Y等對(duì)K2n的三角形邊矩陣K′2n進(jìn)行Δ(G)-邊著色，使得n個(gè)同色的邊互不相鄰，且被著了色的邊以A，B，C，…，X，Y等符號(hào)取代，從而形成Δ(G)-邊著色的邊矩陣K″2n.

1 基本思路

由于n個(gè)A色邊構(gòu)成完備匹配M1，n個(gè)B色邊構(gòu)成完備匹配M2，…，n個(gè)Y色邊構(gòu)成完備匹配MΔ(G)，Δ(G)個(gè)完備匹配M1，M2，…，M2n－1會(huì)形成一個(gè)長(zhǎng)方形矩陣K(i)2n，所得的K(i)2n可用來(lái)安排2n名棋手的循環(huán)賽.此外，還提出依據(jù)2n階的循環(huán)賽圖K(i)2n求解4n階循環(huán)賽圖K(i)4n的一種算法［7-12］.其思路是：1）將K4n的E(G)個(gè)邊按自然順序排列成上三角陣——邊矩陣K′4n，使得K′4n的任意邊CiCj分別與頂Ci和頂Cj相關(guān)聯(lián)；2）將邊矩陣K′4n劃分出n(2n－1)個(gè)2×2子矩陣——完全二分圖K(i，j)2，2，從而形成由完全二分圖K(i，j)1，1及K(i，j)2，2構(gòu)成的三角形矩陣K″4n；3）依據(jù)已存在的循環(huán)賽圖K2n的完備匹配，將K″4n的三角陣重新排成長(zhǎng)方形矩陣K″4n，使得2n個(gè)K1，1位于K(i)4n的首行，而將K2n的完備匹配M1，M2，…，M2n－1置于長(zhǎng)方形矩陣K(i)4n的2，3，…，2n行［13-15］.

2 求K(i)v的Δ(G)-邊著色法

設(shè)v=20，則求循環(huán)賽圖K(i)20的關(guān)鍵是確定K20中的Δ(G)=19個(gè)完備匹配M1，M2，…，M19.算法的步驟是：

1）將K20的E(G)個(gè)邊按自然順序排成上三角形矩陣K′20，使K′20的任意邊CiCj分別與頂Ci和頂Cj相關(guān)聯(lián)；

2）將邊矩陣K′20中的C1行的邊分別著上A，B，C，…，Q，R等顏色，C19列的邊分別著上R，S，A，B，…，O，P等顏色，將C19左側(cè)上三角陣35條斜線(xiàn)上的邊分別著上A，B，C，…R，S，A，B，…，O，P等顏色.最后，將C20列的邊分別著上S，B，D，F(xiàn)，…，O，Q等顏色.從而得邊矩陣K′20的Δ(G)-邊著色，并記為K″20；

3 求K(i)v的完全二分圖劃分法

設(shè)v=4n，若2n階循環(huán)賽圖K(i)2n為已存在的，如10階循環(huán)賽圖K(i)10的矩陣表達(dá)式，是由9個(gè)完備匹配M1，M2，…，M9構(gòu)成，則4n階循環(huán)賽圖K(i)4n的求解，亦即求20階循環(huán)賽圖K(i)20，可借助于2n階的循環(huán)賽圖K(i)2n求4n階的循環(huán)賽圖K(i)4n，或者利用10階循環(huán)賽圖K(i)10求解20階循環(huán)賽圖K(i)20，算法的步驟：

1）與前一算法相同，求完全圖K20的邊矩陣K′20;

2）將邊矩陣K′20劃分出5×9個(gè)2×2的子矩陣，等價(jià)于將完全圖K20劃分成5×9個(gè)完全二分圖K(i，j)2，2和10個(gè)完全二分圖K(i)1，1.

3）依據(jù)已存在的10階循環(huán)賽圖K(i)10的9個(gè)完全匹配，將K′20的5×9個(gè)2×2子矩陣或完全二分圖K(i，j)2，2排成5×9的長(zhǎng)方形矩陣，而將10個(gè)完全二分圖K(i)1，1置于5×9長(zhǎng)方矩陣的上方，即得20階循環(huán)賽圖K(i)20的矩陣表達(dá)式：

至此，當(dāng)n>10時(shí)，高階的完全圖K2n實(shí)施Δ(G)-邊著色是可能的且可行的.

參考文獻(xiàn)

［1］ BRISKORN D， DREXL A， FRITS C R， et al. Round robin tournaments and three index assignment［M］. Berlin: Springer，2010:152-175.

［2］ 侴萬(wàn)禧.2n名選手循環(huán)賽安排問(wèn)題［J］. 數(shù)學(xué)的認(rèn)識(shí)與實(shí)踐， 2006，36(12):252-256.

CHOU Wan-xi.The round-robin tournament arrangement problem of 2n players［J］. Mathematics in Practice and Theory，2006，36(12):252-256.(In Chinese)

［3］ 田蓓藝，錢(qián)鋒.單循環(huán)賽賽程安排幾個(gè)參數(shù)的極值［J］. 數(shù)學(xué)的認(rèn)識(shí)與實(shí)踐，2005，35(7):141-146.

TIAN Bei-yi， QIAN Feng. The extreme values of some parameters about the single circle match［J］. Mathematics in Practice and Theory， 2005，35(7):141-146. (In Chinese)

［4］ 唐保祥.單循環(huán)賽賽程安排的一個(gè)圖論方法［J］. 數(shù)學(xué)的認(rèn)識(shí)與實(shí)踐， 2004，34(5):20-25.

TANG Bao-xiang. A way of graph theory of the competitive procedure arrangement for single cyclic match［J］. Mathematics in Practice and Theory， 2004，34(5):20-25. (In Chinese)

［5］ 謝德政，任善強(qiáng).賽程中裁判分派問(wèn)題的研究［J］. 數(shù)學(xué)的認(rèn)識(shí)與實(shí)踐， 2006，36(2):26-30.

XIE De-zheng， REN Shan-qiang. Study of the referee assignment in the course of game［J］. Mathematics in Practice and Theory，2006，36(2):26-30. (In Chinese)

［6］ BARTSCHA Thomas， ANDREAS Drexlc， STEFAN Krgerd. Scheduling the professional soccer leagues of Austria and Germany［J］. Computers and Operations Research， 2006， 33(7):1907-1937.

［7］ 楊旭靜，楊欽文.基于離散刀位點(diǎn)的復(fù)合刀具路徑生成方法研究［J］. 湖南大學(xué)學(xué)報(bào):自然科學(xué)版， 2009，36(10):35-39.

YANG Xu-jing ， YANG Qin-wen. A new approach to compound tool path generation based on discrete cutter locations［J］. Journal of Hunan University: Natural Sciences， 2009，36(10):35-39. (In Chinese)

［8］ 侴萬(wàn)禧，李嘵毅.多面體平圖的4著色方法［J］.沈陽(yáng)師范大學(xué)學(xué)報(bào):自然科學(xué)版，2009，28(2):148-150.

CHOU Wan-xi， LI Xiao-yi. A method of 4-colouring the polyhedron plane［J］.Journal of Shenyang Normal University：Natural Science， 2009，28(2):148-150. (In Chinese)

［9］ 侴萬(wàn)禧，霍玉紅，李嘵毅.基于平圖的H圈分解的對(duì)偶圖的四著色［J］.沈陽(yáng)師范大學(xué)學(xué)報(bào):自然科學(xué)版， 2009，27(4):390-392.

CHOU Wan-xi， HUO Yu-hong， LI Xiao-yi.4-colouring of the planar graph on the basis of decomposition into Hamiltonian cycle［J］.Journal of Shenyang Normal University：Natural Science， 2009，27(4):390-392. (In Chinese)

［10］BARTSCH T， DREXL A， KR?GER S. Scheduling the professional soccer leagues of austria and germany［J］.Computers and Operations Research， 2006， 33(7):1907-1937.

［11］BRISKORN D. Feasibility of home-away-pattern sets for round robin tournaments［J］. Operations Research Letters， 2008， 36(3): 283-284.

［12］BRISKORN D， DREXL A. A branching scheme for finding cost-minimal round robin tournaments［J］. European Journal of Operational Research， 2009， 197(1):68-76.

［13］RASMUSSEN R V， TRICK M A. A benders approach for the constrained minimum break problem［J］. European Journal of Operational Research， 2007， 177(1):198-213.

［14］RASMUSSEN R V. Scheduling a triple round robin tournament for the best danish soccer league［J］. European Journal of Operational Research， 2008， 185(2):795-810.

［15］DREXLA A， KNUSTB S. Sports league scheduling: graph and resource-based models［J］. Omega， 2007， 35(5):465-471.