双弧竞赛图的若干问题

《双弧竞赛图的若干问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一个顶点的出度就是该选手在整个比赛中所得的分数之和，称为该选手的得分．”个顶点的双弧竞赛图的得分向量，简称双弧得分向量，定义为由其顶点的出度(即诸选手的得分)为分量所成的tit维向量．为了区别于双弧竞赛图，本文把竞赛图称为单弧竞赛图．在E14]中，候研究了几类具有特殊得分向量的竞赛矩阵(双弧竞赛图的邻接矩阵)数目，并给出了当得分向量是强有效时，竞赛矩阵数目的下界及达到该界的得分向量的刻画．本文的第二章研究双弧竞赛图得分向量的计数问题，给出了若干类型的得分向量数的计数公式及递推公式．第三章给出了双弧竞赛图数目的生成函数，并利用该函数研究具有给定得分向量的双弧竞赛

2、图的数目．所得结果表明，该数目与得分向量的偏序关系有着密切联系，由此得到具有给定得分向量的双弧竞赛图的数目的上界．为了进一步揭示双弧竞赛图之间的关系，在第四章我们引入了圈变换与变换图这两个概念．研究了交换图的连通性及直径，并证明变换图是连通的且连通度不小于其直径的一半．第五章研究了可平局单循环比赛的排名问题．本文所涉及的术语，除特别给出定义外，均以文【7】为准．2、。籼第二章得分向量的计数问题设S=(s。，^，⋯，s。)为一得分向量，不失一般性，以下我们总假设s。≤q≤⋯≤s。，用与【22】完全类似的方法，易得如下结果：引理2．1(候耀平【14】)向量(s。，

3、q，⋯，s。)(％s五s⋯≤5。)是某个n维双弧竞赛图的得分向量当且仅当对一切i，0si兰n-2，50+J。+⋯+毛≥f(f+1)且so+sl-I-⋯-I-s“=n(n一1)．记J(n)为n维双弧得分向量数目；s(n，i)，0≤i≤Ⅳ一1，为第一个分量为i的疗维双弧得分向量的数目；J+(^，i)，0si≤H，为分量恰取i个不同值的n维双弧得分向量的数目；h(n)为分量严格递增的n维双弧得分向量的数目；s1(n)为H维单弧竞赛图得分向量的数目；s’(n，i)，0茎i茎n，为有i个不同分量的H维单弧得分向量的数目．对于较小的抖与l，直接计算可得s(H)，J(n，0

4、，J+(n，0，．jI(n)，s1(n，0的值如下：I疗l2345『J(一)l251659裂jOl234121l3214564151620166l；+(n焱iN01234121312414745l421249hI2345l^(^)l2494、÷●{。≯、。，、^，P裂l0123412013101403015l0701由s(n)，s(n，0，5’(n，0，h(n)，st(H)及s’0，f)的定义不难得到下面的性质．性质2．1(1)J(n)2s(n，0'+J(月，1)+·-·+s(n，力-1)．(2)s(n，r／一1)=1．(3)当村≥2时，s(甩，0)=s(玎-

5、1，O)+s(n一1，1)+⋯+s(n一1，以一2)=s0—1)．(4)s’(n'1)一定理2．1s(n，n一2)=p(n)一1．证明：设再维得分向量0。，吼，⋯，sd)7满足j。=B--2，令t，=毛一0—2)(0sisn-1)，则0=tostIsf2s⋯st¨且由引理2．1得tj+t2+⋯+f-．I2fo+fl⋯+f-一t=so+屯+⋯+s．-l—n(n-2)=n(n-I)一n(n-2)=打．即fl+f2+⋯+f“=n为n的一个划分且至多划分成竹一1项．反之，若fI+f2+⋯+‘一I=刀(0s^St2s⋯s，膏一1)是露的一个划分且至多H—l项．令so=n

6、一2，毛=tf+0—2)(1≤fsH-1)则由引理2．1得(J。，^，⋯，s。)是第一分量为H一2的一个得分向量．又因为n只有一个项数大于n一1的划分(即划分为"个1)，、立得s(n，n一2)=p(n)-1．故定理得证．定理2．2s(n，n一3)=p(2n)一p(弹)一p(n一1)一2(p(n一2)+⋯+p@9)即等于2H分成至多n一1项，每项至多n+1的划分数．在证明定理2．2之前，我们先证明下面的命题．命题2．12n划分为至多n一1项，最大项不超过栉+l的划分数等于p(2n)一p(n)一p(n一1)一2(p(n一2)+···+p(0))．证明：考虑2n的下

7、述两种类型的划分：(i)至少n项；(ii)至多n-1项，但最大项不超过n+1．由文【3】的定理343，类(i)的划分数等于2^的最大项至少n的划分数．最大项为f(n≤i≤2n)的划分数．tI+f2+⋯+“=2n(气=f)与2n-i的划分，1+，2+⋯+tt—I=2n一，一一对应，故这类划分数等于p(n)+p(n—1)十⋯+p(o)．同理，类(ii)中最大项为_，(押十l

8、+⋯+p(O))一(p(n一2)+r(