竞赛图理论

---

竞赛图是一类特殊的有向图，它不但是体育比赛和科学实践中对比实验的数学模型，也是研究有向图时经常使用的一种模型，它的理论非常丰富又独具特色。

竞赛图理论的研究有著悠久的历史，不过对竞赛图的组合性质的研究则是20世纪50年代才发展起来的。1968年出版了Moon的竞赛图理论的第1本专著，1978年Reid和Beineke的综述文章全面论述了该名著问世以来的进展，是进一步研究竞赛图的基础。

竞赛图理论的研究主要围绕得分向量、圈、王、极端问题、自同构群和邻接矩阵等展开的。

n阶竞赛图T_n的n个顶点的得分依次记作r₁，r₂，…，r_n，r₁≤r₂≤…≤r_n，则R=(r₁，r₂，…，r_n)是T_n的得分向量。

所有得分向量为R的竞赛图集合记作。对k=0，1，…，，记R_k=(k，…，k，2k，2k+1，…，(n－2k－1)，n－k－1，…，n－k1)。

1953年Landau证明，设R=(r₁，r₂，…，)是非降的非负整数向量，则的充要条件是，R被R₀所优超。使(R)≠Φ的向量R称为得分向量。所有n维得分向量集合记作，它在向量间优超关系下是一个偏序集(poset)。1966年Harary和Moser证明，对于，为强(连通)的充要条件是，R被R₁所优超。称得分向量R是强的，若R被R₁优超，不是强的得分向量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被R₁优超，则；若，则，这里是正则或拟正则的。

又当n为奇数时，；当n为偶数时，1986年万宏辉和李乔证明，偏序集上的函数是Schur凹的。他们并证明，当n为奇数时，；当n为偶数时，。

竞赛图中极端问题是竞赛图理论研究的一个热点问题，它和计数问题有著密切的联系。设，。

T_n中k阶强子竞赛图的个数为σ_k(T_n)。

记σ_k(R)=max｛σ_k(T_n)：T_n∈，σ(k；n)=max｛σ_k(R)：，早在20世纪40年代，Kendall等人就证明，对，R=(r₁，r₂，…，r_n)，有σ₃。从而σ₃(T_n)=σ₃(R)，并且当时σ₃(R)取到最大值σ(3；n)。1965年Beineke和Harary证明，对正整数k，3≤k≤n，σ_k(R)在处取到最大值σ(k；n)，并给出它的值。

同样，设R是强得分向量。对，T_n中k阶传递子竞赛图的个数为τ_k(T_n)。记，；又记，。1966年Moon证明，对正整数k，3≤k≤n，定义在中所有强得分向量构成的偏序子集上的函数τ_k(R)在R=R1处取到最大值τ(k；n)，并给出它的值。

1989年Reid给出α(4；n)的下界。至于偏序集上的函数α₄(R)是否在处取到最小值α(4；n)以及它的确切值等问题仍未解决。

同年Q．Li提出如下问题：上函数σ_k(R)是否是Schur凹的?α_k(R)是否是Schur凸的?上函数τ_k(R)是否是Schur凸的?这些问题仍待解决。

竞赛图中的圈结构对于研究竞赛图的组合性质具有基本的重要性。

一个经典的结论是：竞赛图Tn为强(连通)的充要条件是Tn具有Hamilton圈。

1968年Moon将这一结论推广为：对n阶强竞赛图T_n中每个顶点u，T_n中必有过顶点u的k圈，这里k=3，4，…，n。

和Moon几乎同时，Alspach考虑了将顶点换成弧的相应问题。若对n阶竞赛图T_n中的每条弧uv，T_n必有一条由v到u(或u到v)的长为k的道路，则记T_n∈P_k(或Tn∈P′_K)。

若对每个k=2，3，…，n－1，有T_n∈P_k，则T_n称为弧泛圈的。Alspach证明，正则竞赛图是弧泛圈的。朱永津和田丰等人给出了使T_n∈P_k且(或)T_n∈Pk的一些充分条件。1982年Z．Wu、K．Zhang和Y．Zou证明T_n为弧泛圈充要条件是，T_n∈P₂且T_n∈P_n－1。

随后张克明进一步证明，对每个k=2，3，…，n－1，T_n∈P_k，的充要条件是，T_n∈P₂，且。张克明还考虑二部竞赛图的弧泛偶圈性。1991年张克明、宋增民和王建中讨论了Hamiltou二部竞赛图。

竞赛图中m王问题与体育比赛如何排名次有关。设R∈。

对于，T_n中m王的个数记为k_m(T_n)。

1953年Landau证明，k₂(T_n)≥1。1980年Maurer证明，若k₂(T_n)≠2，则k₂(T_n)≥3。

记，上函数K_m(R)与k_m(R)各具有什么性质，K_m(R)之最大值K(m；n)和k_m(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证明，M_n的秩至少是n－1，且正则竞赛矩阵是满秩的。1990年Maybee和Pullman证明，设λ是M_n的特征值，则M_n－λI_n的秩为n－1，或者λ的实部为，其中I_n是单位矩阵。1992年Caen，Maybee和Pullman证明，若λ的实部大于，则λ的几何重数与代数重数相同。

关于竞赛图的自同构群，1963年Moon证明，一个有限群为某个竞赛图的自同构群的充要条件是，其顶点数为奇数。1966年Goldberg给出了当n≤14时n阶竞赛图的自同构群的阶数之最大值g(n)，同年Goldber和Moon给出了g(n)的上界。

之后人们开始考虑子竞赛图的同构性质对母竞赛图的组合性质的影响。

对给定的k，称T_n具有D_k(或I_k)，若T_n中n－k阶子竞赛图都有相同得分向量(或都同构)。1969年Jean刻划了具有I₂的竞赛图，1974年Müller和Pelant刻划了具有D₂的竞赛图。1973年Kotzig提出刻划具有I₁的竞赛图，1987年李炯生等刻划了具有D₁的竞赛图，并给出具有I₁的竞赛图的一个必要条件。

1990年J．S．Li、D．D．Huang和Q．Pan刻划了具有D_k的有向图，k=1，2，和具有I₂的有向图。至于刻划具有I1的有向图(或竞赛图)问题尚待解决。

今后，竞赛图理论的主要研究方向是，(1)偏序集(或)上各种函数的Schur凸(Schur凹)性质；(2)对各种竞赛图的图论性质P，蕴含P(或强迫P)得分向量(m部得分序列)的刻划；(3)竞赛矩阵的组合性质；(4)竞赛图中其他有趣的问题：如m王问题，具有I₁的竞赛图的刻划等。

。

【参考文献】：

1 Moon J W. Topics on Tournaments. New York,Holt , Rine-hart and Winston, 1968.1～102

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. Annals of the New York Academy of Sciences, 1989, 576:336～343

5 张克明,宋增民,王建民,南京大学学报数学半年刊,1991,1:6-10

6 吴正声.应用数学学报,1987,10(3):284～288

7 Tan S P, Koh K M. Kings in multipartite tournaments, to appear

8 de Caen D.Gregory D A,Kirkland S J,Pullman N J,Maybee J S. Linear Algebra and its Applications, 1992,169:179 ～ 193

9 Li J S, Huang D D, Pan Q. J Combinatorial Teory,Ser B, 1990,50(2) :288～298

(中国科技大学李炯生教授撰)

上一篇：图的度序列
下一篇：现代科技综述大辞典上目录

"竞赛效应竞赛效应

---

在一切联合活动中，因竞争心理而提高个人工作效率的现象。

在联合活动中，个体之间都存在著隐蔽的竞争意识。人人都有不同程度的好胜心，它使个体之间自觉或不自觉地展开了竞争。

“逞能”行为总是在他人面前表现出来的。“竞赛”是一种自我表现，是个体在人际互动中以自我满意的方式去表现自己的过程。

因此，竞赛效应是他人在场所激发的竞争心理给个体表现带来的一种社会促进趋势。竞赛效应和观众效应是密切相关的。