现代科技综述知识文库：竞赛图理论

1、现代科技综述系列竞赛图理论科技是人类区别于动物的重要文明之一，是人类对自然规律研究和利用的学科。本文提供对科技基本概念“竞赛图理论”的解读，以供大家了解。竞赛图理论竞赛图是一类特殊的有向图，它不但是体育比赛和科学实践中对比实验的数学模型，也是研究有向图时经常使用的一种模型，它的理论非常丰富又独具特色。竞赛图理论的研究有着悠久的历史，不过对竞赛图的组合性质的研究则是20世纪50年代才发展起来的。1968年出版了Moon的竞赛图理论的第1本专着，1978年Reid和Beineke的综述文章全面论述了该名着问世以来的进展，是进一步研究竞赛图的基础。竞赛图理论的研究主要围绕得分向量、圈、王、极端问题、

2、自同构群和邻接矩阵等展开的。n阶竞赛图Tn的n个顶点的得分依次记作r1，r2，rn，r1r2rn，则R=(r1，r2，rn)是Tn的得分向量。所有得分向量为R的竞赛图集合记作。对k=0，1，记Rk=(k，k，2k，2k+1，(n2k1)，nk1，nk1)。1953年Landau证明，设R=(r1，r2，)是非降的非负整数向量，则的充要条件是，R被R0所优超。使(R)的向量R称为得分向量。所有n维得分向量集合记作，它在向量间优超关系下是一个偏序集(poset)。1966年Harary和Moser证明，对于，为强(连通)的充要条件是，R被R1所优超。称得分向量R是强的，若R被R1优超，不是强的得分

3、向量R称为可约的。由于同构的竞赛图具有相同的得分向量，而得分向量相同的竞赛图未必同构，因此得分向量是竞赛图的同构不变量，但不是全系不变量。所以得分向量的算术性质必然部分反映竞赛图的组合性质。这种反映的深度是一个值得研究的问题。设P是一个图论的性质。称为蕴含P的，若存在具有性质P的。称是强迫的，叵所有都具有性质P。20世纪80年代中期，Bagga和Beineke以及李炯生等独立地给出了蕴含2强得分向量的刻划。1985年JSLi等给出了蕴含k强得分向量的刻划。他们还刻划了强迫k强、蕴含k可约、强迫k可约、蕴含k边强和强迫k边强得分向量。多部竞赛图是竞赛图的自然推广。1962年Moon将上面提到的L

4、andau定理和Harary-Moser定理推广到多部竞赛图，得到类似的结论。Bagga和Beineke考虑了蕴含2强二部得分序列的刻划。李炯生等刻划了蕴含k可约和强迫k可约m部得分序列。1954年Davis考虑了不同构竞赛图的计数问题。他应用Plya计数定理给出了n个不同构竞赛图的个数T(n)的计数公式，并给出T(n)的母函数和n阶不同构强竞赛图的个数t(n)的母函数间的关系：，从而解决了不同构强竞赛图和可约竞赛图的计数问题。于是问题进一步化为，对给定的，求。1984年Brualdi和李乔证明，若是强的，即R被R1优超，则；若，则，这里是正则或拟正则的。又当n为奇数时，；当n为偶数时，198

5、6年万宏辉和李乔证明，偏序集上的函数是Schur凹的。他们并证明，当n为奇数时，；当n为偶数时，。竞赛图中极端问题是竞赛图理论研究的一个热点问题，它和计数问题有着密切的联系。设，。Tn中k阶强子竞赛图的个数为k(Tn)。记k(R)=maxk(Tn)：Tn，(k；n)=maxk(R)：，早在20世纪40年代，Kendall等人就证明，对，R=(r1，r2，rn)，有3。从而3(Tn)=3(R)，并且当时3(R)取到最大值(3；n)。1965年Beineke和Harary证明，对正整数k，3kn，k(R)在处取到最大值(k；n)，并给出它的值。同样，设R是强得分向量。对，Tn中k阶传递子竞赛图的个

6、数为k(Tn)。记，；又记，。1966年Moon证明，对正整数k，3kn，定义在中所有强得分向量构成的偏序子集上的函数k(R)在R=R1处取到最大值(k；n)，并给出它的值。1989年Reid给出(4；n)的下界。至于偏序集上的函数4(R)是否在处取到最小值(4；n)以及它的确切值等问题仍未解决。同年QLi提出如下问题：上函数k(R)是否是Schur凹的?k(R)是否是Schur凸的?上函数k(R)是否是Schur凸的?这些问题仍待解决。竞赛图中的圈结构对于研究竞赛图的组合性质具有基本的重要性。一个经典的结论是：竞赛图Tn为强(连通)的充要条件是Tn具有Hamilton圈。1968年Moon将

7、这一结论推广为：对n阶强竞赛图Tn中每个顶点u，Tn中必有过顶点u的k圈，这里k=3，4，n。和Moon几乎同时，Alspach考虑了将顶点换成弧的相应问题。若对n阶竞赛图Tn中的每条弧uv，Tn必有一条由v到u(或u到v)的长为k的道路，则记TnPk(或TnPK)。若对每个k=2，3，n1，有TnPk，则Tn称为弧泛圈的。Alspach证明，正则竞赛图是弧泛圈的。朱永津和田丰等人给出了使TnPk且(或)TnPk的一些充分条件。1982年ZWu、KZhang和YZou证明Tn为弧泛圈充要条件是，TnP2且TnPn1。随后张克明进一步证明，对每个k=2，3，n1，TnPk，的充要条件是，TnP2

8、，且。张克明还考虑二部竞赛图的弧泛偶圈性。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和Thomasse

9、n证明，不含传送点的多部竞赛图至少有一个4王，而且有无数个二部竞赛图，它们不含3王。最近新加坡KMKoh等人证明，不含传送点的二部竞赛图至少有4个4王，而不含传送点的三部竞赛图至少有3个4王。多部竞赛图的m王问题尚待进一步研究。竞赛图的邻接矩阵(即竞赛矩阵)的代数性质和竞赛图的组合性质间的联系既是竞赛图理论关注的一个问题，也是新兴的组合矩阵论研究的一个热点。从60年代末到70年代初，Brauer和Gentry以及Moon和Pullman证明，n阶竞赛矩阵Mn的特征值之实部在与之间，其Perron值为的充要条件是Mn为正则的。Moon和Pullman还确定了本原竞赛矩阵的本原指数集。1989年C

10、ean和Hoffman证明，Mn的秩至少是n1，且正则竞赛矩阵是满秩的。1990年Maybee和Pullman证明，设是Mn的特征值，则MnIn的秩为n1，或者的实部为，其中In是单位矩阵。1992年Caen，Maybee和Pullman证明，若的实部大于，则的几何重数与代数重数相同。关于竞赛图的自同构群，1963年Moon证明，一个有限群为某个竞赛图的自同构群的充要条件是，其顶点数为奇数。1966年Goldberg给出了当n14时n阶竞赛图的自同构群的阶数之最大值g(n)，同年Goldber和Moon给出了g(n)的上界。之后人们开始考虑子竞赛图的同构性质对母竞赛图的组合性质的影响。对给定的

11、k，称Tn具有Dk(或Ik)，若Tn中nk阶子竞赛图都有相同得分向量(或都同构)。1969年Jean刻划了具有I2的竞赛图，1974年Mller和Pelant刻划了具有D2的竞赛图。1973年Kotzig提出刻划具有I1的竞赛图，1987年李炯生等刻划了具有D1的竞赛图，并给出具有I1的竞赛图的一个必要条件。1990年JSLi、DDHuang和QPan刻划了具有Dk的有向图，k=1，2，和具有I2的有向图。至于刻划具有I1的有向图(或竞赛图)问题尚待解决。今后，竞赛图理论的主要研究方向是，(1)偏序集(或)上各种函数的Schur凸(Schur凹)性质；(2)对各种竞赛图的图论性质P，蕴含P(或

12、强迫P)得分向量(m部得分序列)的刻划；(3)竞赛矩阵的组合性质；(4)竞赛图中其他有趣的问题：如m王问题，具有I1的竞赛图的刻划等。【参考文献】： 1 Moon J W. Topics on Tournaments. New York,Holt , Rine-hart and Winston, 1968.1102 2 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 204 3 Li J S, HuangG X. Chinese Science Bulletin, 1985,30(7) : 990 4 Li Q. Annalsof the New York Academy of Sciences, 1989, 576:336 343 5 张克明,宋增民,王建民,南京大学学报数学半年刊,1991,1:6-10 6 吴正声.应用数学学报,1987,10(3):284288 7 Tan S P, Koh K M. Kings in multipartite tournaments, to appear 8