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

194200312JOURNALOFBEIJINGINSTITUTEOFCIVILENGINEERINGANDARCHITECTUREVol.19No.4Dec.2003:1004-6011(2003)04-0072-05)))2002D代西武李群高李秀琴(,100044):通过建立赛程安排的图论模型,圆满解决了2002年全国大学生数学建模竞赛D题的前三个问题提出了对于任意n支球队进行单循环比赛的赛程编制方法,该方法简单易行,只须手工编排,并证明了该方法编制的赛程使得各队每两场比赛最小相隔的场次数达到了理论上限:完美匹配;Haimlton)圈;单循环赛:O226:A15,10,?:5A,B,C,D,E,10,1,2,,,10,,1AB,2BC,,,10CE,,,A,E,DABCDEAX1936122B1X258022C92X710410D357X4001E68104X111:1)5,;2)n,;3)2),n=8,n=9,;4),,3)2n,:0,1,2,,,(n-1):n;(i,j):ij;[x]:x1n,:n+12-2:n+12-2=m-2,n=2mm-1,n=2m+1,1n=2m,2m:2003-09-26:(1963)),,,,0,1,2,,,(2m-1)(m+1)2(m+1),,,,,m-22n=2m+1,2m+10,1,2,,,2m(m+1)2(m+1),,,m-11:n,n+12-2,/n+12-203,[1]2:G(V,E),V={0,1,2,,,(n-1)}n,E={(i,j)|i,jIV},,G(V,E)n,nG(V,E)Kn311n=2m2n=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,,K2mK2m(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)}sM2m-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)}3n=2m(),:K2m(2m-1)M1,M2,,,M2m-11,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)}:1234,,m-1mM2={(0,2),(3,1),(4,2m-1),(5,2m-2),,,,(m,m+3),(m+1,m+2)}:m+1m+2m+3m+4,,2m-12m:m+102,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),734:312n=2m+14n=2m+1,K2m+1mHamilton-:K2m+1:0,1,2,,,2m0,1,2,,,2m,C1=(0,1,2,2m,3,2m-1,4,2m-2,,,m,m+2,m+1,0)K2m+1Hamilton-C10(m-1),Hamilton-,mHamilton-:C1,C2,,,Cm,,K2m+1K2m+1mHamilton-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)sCm-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)5n=2m+1(),:K2m+1Hamilton-C1:,C2,,,Cm(2m+2)(2m+3),m(2m+1),(m-1),,Hamilton-Ci(i=1,2,,,m),()(m-1)Hamilton-CiCi+1(i=1,2,,,m-1)C1,C2,,,Cm,C1,C2,,C2(2m+2)~(3m+2):2m+202,(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,4m=2m(),2~3,,::K2m(2m-1)M1,M2,,,M2m-1:7419M1={(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)}sM2m-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-11,2,3,,,m(2m-1),n=8,,:M1={(0,1),(2,7),(3,6),(4,5)}1234M2={(0,2),(3,1),(4,7),(5,6)}5678M3={(0,3),(4,2),(5,1),(6,7)}9101112M4={(0,4),(5,3),(6,2),(7,1)}13141516M5={(0,5),(6,4),(7,3),(1,2)}17181920M6={(0,6),(7,5),(1,4),(2,3)}21222324M7={(0,7),(1,6),(2,5),(3,4)}25262728:012345670X159131721253,3,3,3,3,3,11X206231126164,4,4,3,2,2,2520X2410271522,4,4,4,3,2,39624X28143192,2,4,4,4,3,413231028X41872,2,2,4,4,4,5171127144X8223,2,2,2,4,4,62126153188X124,3,2,2,2,4,7251621972212X4,4,3,2,2,2,n=2m+1(),4~5,,::K2m+1mHamilton-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)sCm-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,,:754:C1=0,1,2,8,3,7,4,6,5,0):162738495C2=0,2,3,1,4,8,5,7,6,0):101511161217131814C3=0,3,4,2,5,1,6,8,7,0):192420252126222723C4=0,4,5,3,6,2,7,1,8,0):283329343035313632:0123456780X110192851423323,4,3,4,3,4,3,11X61116212631364,4,4,4,4,4,4,2106X152025303523,3,4,4,4,4,4,3191115X242934373,3,3,3,4,4,4,428162024X3348123,3,3,3,3,3,4,5521252933X913173,3,3,3,3,3,3,61426303449X18224,4,3,3,3,3,3,7233135381318X274,4,4,4,3,3,3,832362712172227X4,4,4,4,4,4,3,n=5()51)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:,1991TheGraphModelofMatchSchedulingDaiXiwuLiQungaoLiXiuqin(Dept.ofBasicSciences,Beijing100044)Abstract:Establishingthegraphmodelofmatchscheduling,thefirstthreequestionsofproblemDof2002.sChinesemathematicalcontestinmodelingaresolvedsatisfactorily.Amethodtoscheduleasingle-roundrobinofNteamsisproposed.Themethodissimpleanditcanbedonebyhand.Moreover,thefollowingconclusionisproved:Inthematchschedulemadebythemethod,theminimumnumberofmatchesbetweeneverytwomatchesofeachteamreachesthetheoreticalupperbound.Keywords:perfectmatching;hamiltoncycle;single-roundrobin7619