K_v的完備匹配M_i的算法

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



關鍵詞：完備匹配；完全圖；算法；邊矩陣；邊著色

中圖分類號：O157 文獻標識碼：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



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

1 基本思路

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

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

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

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

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

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

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

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

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

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

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

參考文獻

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

［2］ 侴萬禧.2n名選手循環賽安排問題［J］. 數學的認識與實踐， 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］ 田蓓藝，錢鋒.單循環賽賽程安排幾個參數的極值［J］. 數學的認識與實踐，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］ 唐保祥.單循環賽賽程安排的一個圖論方法［J］. 數學的認識與實踐， 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］ 謝德政，任善強.賽程中裁判分派問題的研究［J］. 數學的認識與實踐， 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］ 楊旭靜，楊欽文.基于離散刀位點的復合刀具路徑生成方法研究［J］. 湖南大學學報:自然科學版， 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］ 侴萬禧，李嘵毅.多面體平圖的4著色方法［J］.沈陽師范大學學報:自然科學版，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］ 侴萬禧，霍玉紅，李嘵毅.基于平圖的H圈分解的對偶圖的四著色［J］.沈陽師范大學學報:自然科學版， 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.