数学竞赛中的图论问题

20026192()JournalofFurtherEducationofShaanxiNormalUniversityJun.2002Vol.19No.2(710062):,9,,,:;:O157.5:A:1009-3826(2002)02-0100-03G(V(G),E(G),7G),7GE(G)V(G)V(2)(G)={(u,v)ûu,vV(G)},,V(G),E(G).,,,;,;,;,,,.,.,,,.,,,(IMO)64,206,212,324,333.,.,,.19A12,A2A34,A4A5A6A75,A8A96.93,.99,AiAj,(Ai,Aj).A96,AkA1A2A3,d(Ak)5.A95,AhAk,d(Ak)9-1-5=3,.A9AkAh3,.22n(n2),n,2n4,4,.2002-02-250012n2n,,,G.Gvi,d(vi)4,G.G=K2n,.GK2n,Gv1v2,d(v1)+d(v2)2n,Gv1v22n-2,(v3v4)v1v2,v1v2v3v4.,(),,?,.39,3,.3,31.v1v2v9,2,,G.32,G.,G.G,v1.d(v1)4,Gv19-1-4=4,v14,,v12,v2v3,.v1v2v33.d(v1)4,d(v1)5,v2v3v6v1.G,v2v3v4v5v6,d(v2)4,,.3,,,,.4,D2,kv1v2vk,v1v2,v2v3,,vk-1vk,vkv1.kD.,2,,G.GD,GkD.GL,Lv1,v1Dv2v3vD+1L,,L,L.Lv1v2vD+1v1,D,.52002,43,?2002G.,.,,vxV(G),d(x)=2001.,PxV(x),d(x)2001.Gxy,xy|E(G),G2000,u,ux,y,d(u)2001,Guv,{x,y,u,v}413,.ux,y,vx,y,{x,y,u,v}.ux,y,vx,y.vw(,d(v)=2001,),{x,y,v,w}.,?x1,,200143,,x22000,x1x2,x2G2001.x1x2x3,101,,4,,1.3,2002-3=1999.62001,,2.,.2001G,,1.,2.,,,,2.:7,.,,.k,k,,k.,.816,.,.,A.,A?1632,32G.,.A,E={0,1,,30}.kE,P(k),k.P(30),,,0,P(30)P(0).P(1),P(30),P(0)P(1)P(29),P(0)P(30),P(1)P(29).,P(j)P(30-j)(j=2,3,,14).AP(15),15.9100,67.:4,.100100,,100G,Pxv(G),d(x)67.,G4.Pxv(G),N(x)={yû(x,y)E(G)},N(x)67,yN(x),N(y)={zû(y,z)E(G)},N(y)67,ûN(x)N(y)ûûN(x)û+ûN(y)û-100=34,zN(x)N(y),N(z)67,ûN(z)N(x)N(y)ûûN(z)û+ûN(x)N(y)û-10067+34-100=1,,wN(x)N(y)N(z),G[{x,y,z,w}]K4,4.4,10067.67?.,n,4,nm,mn?45,?,,.201