【竞赛图理论】
拼译：theory of tournaments
竞赛图是一类特殊的有向图，它不但是体育比赛和科学实践中对比实验的数学模型，也是研究有向图时经常使用的一种模型，它的理论非常丰富又独具特色。竞赛图理论的研究有着悠久的历史，不过对竞赛图的组合性质的研究则是20世纪50年代才发展起来的。1968年出版了Moon的竞赛图理论的第1本专著，1978年Reid和Beineke的综述文章全面论述了该名著问世以来的进展，是进一步研究竞赛图的基础。竞赛图理论的研究主要围绕得分向量、圈、王、极端问题、自同构群和邻接矩阵等展开的。
n阶竞赛图Tn的n个顶点的得分依次记作r1，r2，…，rn，r1≤r2≤…≤rn，则R=(r1，r2，…，rn)是Tn的得分向量。所有得分向量为R的竞赛图集合记作
。对k=0，1，…，
，记Rk=(k，…，k，2k，2k+1，…，(n－2k－1)，n－k－1，…，n－k1)。1953年Landau证明，设R=(r1，r2，…，
)是非降的非负整数向量，则
的充要条件是，R被R0所优超。使
(R)≠Φ的向量R称为得分向量。所有n维得分向量集合记作
，它在向量间优超关系下是一个偏序集(poset)。1966年Harary和Moser证明，对于
，
为强(连通)的充要条件是，R被R1所优超。称得分向量R是强的，若R被R1优超，不是强的得分向量R称为可约的。由于同构的竞赛图具有相同的得分向量，而得分向量相同的竞赛图未必同构，因此得分向量是竞赛图的同构不变量，但不是全系不变量。所以得分向量的算术性质必然部分反映竞赛图的组合性质。这种反映的深度是一个值得研究的问题。设P是一个图论的性质。称
为蕴含P的，若存在具有性质P的
。称
是强迫的，叵所有
都具有性质P。20世纪80年代中期，Bagga和Beineke以及李炯生等独立地给出了蕴含2强得分向量的刻划。1985年J．S．Li等给出了蕴含k强得分向量的刻划。他们还刻划了强迫k强、蕴含k可约、强迫k可约、蕴含k边强和强迫k边强得分向量。多部竞赛图是竞赛图的自然推广。1962年Moon将上面提到的Landau定理和Harary-Moser定理推广到多部竞赛图，得到类似的结论。Bagga和Beineke考虑了蕴含2强二部得分序列的刻划。李炯生等刻划了蕴含k可约和强迫k可约m部得分序列。1954年Davis考虑了不同构竞赛图的计数问题。他应用Pólya计数定理给出了n个不同构竞赛图的个数T(n)的计数公式，并给出T(n)的母函数
和n阶不同构强竞赛图的个数t(n)的母函数
间的关系：
，从而解决了不同构强竞赛图和可约竞赛图的计数问题。于是问题进一步化为，对给定的
，求
。1984年Brualdi和李乔证明，若
是强的，即R被R1优超，则
；若
，则
，这里
是正则或拟正则的。又当n为奇数时，
；当n为偶数时，
1986年万宏辉和李乔证明，偏序集
上的函数
是Schur凹的。他们并证明，当n为奇数时，
；当n为偶数时，
。竞赛图中极端问题是竞赛图理论研究的一个热点问题，它和计数问题有着密切的联系。设
，
。Tn中k阶强子竞赛图的个数为σk(Tn)。记σk(R)=max｛σk(Tn)：Tn∈
，σ(k；n)=max｛σk(R)：
，早在20世纪40年代，Kendall等人就证明，对
，R=(r1，r2，…，rn)，有σ3
。从而σ3(Tn)=σ3(R)，并且当
时σ3(R)取到最大值σ(3；n)。1965年Beineke和Harary证明，对正整数k，3≤k≤n，σk(R)在
处取到最大值σ(k；n)，并给出它的值。同样，设R是强得分向量。对
，Tn中k阶传递子竞赛图的个数为τk(Tn)。记
，
；又记
，
。1966年Moon证明，对正整数k，3≤k≤n，定义在
中所有强得分向量构成的偏序子集
上的函数τk(R)在R=R1处取到最大值τ(k；n)，并给出它的值。1989年Reid给出α(4；n)的下界。至于偏序集
上的函数α4(R)是否在
处取到最小值α(4；n)以及它的确切值等问题仍未解决。同年Q．Li提出如下问题：
上函数σk(R)是否是Schur凹的?αk(R)是否是Schur凸的?
上函数τk(R)是否是Schur凸的?这些问题仍待解决。竞赛图中的圈结构对于研究竞赛图的组合性质具有基本的重要性。一个经典的结论是：竞赛图Tn为强(连通)的充要条件是Tn具有Hamilton圈。1968年Moon将这一结论推广为：对n阶强竞赛图Tn中每个顶点u，Tn中必有过顶点u的k圈，这里k=3，4，…，n。和Moon几乎同时，Alspach考虑了将顶点换成弧的相应问题。若对n阶竞赛图Tn中的每条弧uv，Tn必有一条由v到u(或u到v)的长为k的道路，则记Tn∈Pk(或Tn∈P′K)。若对每个k=2，3，…，n－1，有Tn∈Pk，则Tn称为弧泛圈的。Alspach证明，正则竞赛图是弧泛圈的。朱永津和田丰等人给出了使Tn∈Pk且(或)Tn∈Pk的一些充分条件。1982年Z．Wu、K．Zhang和Y．Zou证明Tn为弧泛圈充要条件是，Tn∈P2且Tn∈Pn－1。随后张克明进一步证明，对每个k=2，3，…，n－1，Tn∈Pk，
的充要条件是，Tn∈P2，
且
。张克明还考虑二部竞赛图的弧泛偶圈性。1991年张克明、宋增民和王建中讨论了Hamiltou二部竞赛图。竞赛图中m王问题与体育比赛如何排名次有关。设R∈
。对于
，Tn中m王的个数记为km(Tn)。1953年Landau证明，k2(Tn)≥1。1980年Maurer证明，若k2(Tn)≠2，则k2(Tn)≥3。记
，
上函数Km(R)与km(R)各具有什么性质，Km(R)之最大值K(m；n)和km(R)之最小值各是多少，都是值得进一步研究的。1991年Goddar等人考虑了多部竞赛图中m王问题。他们证明，不含传送点的二部竞赛图T同一部分顶点集中最大得分顶点一定是4王。同年Petrovic和Thomassen证明，不含传送点的多部竞赛图至少有一个4王，而且有无数个二部竞赛图，它们不含3王。最近新加坡K．M．Koh等人证明，不含传送点的二部竞赛图至少有4个4王，而不含传送点的三部竞赛图至少有3个4王。多部竞赛图的m王问题尚待进一步研究。竞赛图的邻接矩阵(即竞赛矩阵)的代数性质和竞赛图的组合性质间的联系既是竞赛图理论关注的一个问题，也是新兴的组合矩阵论研究的一个热点。从60年代末到70年代初，Brauer和Gentry以及Moon和Pullman证明，n阶竞赛矩阵Mn的特征值之实部在
与
之间，其Perron值为
的充要条件是Mn为正则的。Moon和Pullman还确定了本原竞赛矩阵的本原指数集。1989年Cean和Hoffman证明，Mn的秩至少是n－1，且正则竞赛矩阵是满秩的。1990年Maybee和Pullman证明，设λ是Mn的特征值，则Mn－λIn的秩为n－1，或者λ的实部为
，其中In是单位矩阵。1992年Caen，Maybee和Pullman证明，若λ的实部大于
，则λ的几何重数与代数重数相同。关于竞赛图的自同构群，1963年Moon证明，一个有限群为某个竞赛图的自同构群的充要条件是，其顶点数为奇数。1966年Goldberg给出了当n≤14时n阶竞赛图的自同构群的阶数之最大值g(n)，同年Goldber和Moon给出了g(n)的上界。之后人们开始考虑子竞赛图的同构性质对母竞赛图的组合性质的影响。对给定的k，称Tn具有Dk(或Ik)，若Tn中n－k阶子竞赛图都有相同得分向量(或都同构)。1969年Jean刻划了具有I2的竞赛图，1974年Müller和Pelant刻划了具有D2的竞赛图。1973年Kotzig提出刻划具有I1的竞赛图，1987年李炯生等刻划了具有D1的竞赛图，并给出具有I1的竞赛图的一个必要条件。1990年J．S．Li、D．D．Huang和Q．Pan刻划了具有Dk的有向图，k=1，2，和具有I2的有向图。至于刻划具有I1的有向图(或竞赛图)问题尚待解决。今后，竞赛图理论的主要研究方向是，(1)偏序集
(或
)上各种函数的Schur凸(Schur凹)性质；(2)对各种竞赛图的图论性质P，蕴含P(或强迫P)得分向量(m部得分序列)的刻划；(3)竞赛矩阵的组合性质；(4)竞赛图中其他有趣的问题：如m王问题，具有I1的竞赛图的刻划等。【参考文献】：1 Moon J W. Topics on Tournaments. New York,Holt , Rine-hart and Winston, 1968.1～1022 Reid K B, Beineke L W. Tournaments in Selected Topics in Graph Theory. Beineke L W & Wilson R J Ed,New York, Academic Press,1978. 169 ～2043 Li J S, HuangG X. Chinese Science Bulletin, 1985,30(7) : 9904 Li Q. Annals of the New York Academy of Sciences, 1989, 576:336～3435 张克明,宋增民,王建民,南京大学学报数学半年刊,1991,1:6-106 吴正声.应用数学学报,1987,10(3):284～2887 Tan S P, Koh K M. Kings in multipartite tournaments, to appear8 de Caen D.Gregory D A,Kirkland S J,Pullman N J,Maybee J S. Linear Algebra and its Applications, 1992,169:179 ～ 1939 Li J S, Huang D D, Pan Q. J Combinatorial Teory,Ser B, 1990,50(2) :288～298(中国科技大学李炯生教授撰)