現(xiàn)代科技綜述知識文庫：競賽圖理論

1、現(xiàn)代科技綜述系列競賽圖理論科技是人類區(qū)別于動物的重要文明之一，是人類對自然規(guī)律研究和利用的學科。本文提供對科技基本概念“競賽圖理論”的解讀，以供大家了解。競賽圖理論競賽圖是一類特殊的有向圖，它不但是體育比賽和科學實踐中對比實驗的數(shù)學模型，也是研究有向圖時經(jīng)常使用的一種模型，它的理論非常豐富又獨具特色。競賽圖理論的研究有著悠久的歷史，不過對競賽圖的組合性質(zhì)的研究則是20世紀50年代才發(fā)展起來的。1968年出版了Moon的競賽圖理論的第1本專著，1978年Reid和Beineke的綜述文章全面論述了該名著問世以來的進展，是進一步研究競賽圖的基礎(chǔ)。競賽圖理論的研究主要圍繞得分向量、圈、王、極端問題、

2、自同構(gòu)群和鄰接矩陣等展開的。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證明，設(shè)R=(r1，r2，)是非降的非負整數(shù)向量，則的充要條件是，R被R0所優(yōu)超。使(R)的向量R稱為得分向量。所有n維得分向量集合記作，它在向量間優(yōu)超關(guān)系下是一個偏序集(poset)。1966年Harary和Moser證明，對于，為強(連通)的充要條件是，R被R1所優(yōu)超。稱得分向量R是強的，若R被R1優(yōu)超，不是強的得分

3、向量R稱為可約的。由于同構(gòu)的競賽圖具有相同的得分向量，而得分向量相同的競賽圖未必同構(gòu)，因此得分向量是競賽圖的同構(gòu)不變量，但不是全系不變量。所以得分向量的算術(shù)性質(zhì)必然部分反映競賽圖的組合性質(zhì)。這種反映的深度是一個值得研究的問題。設(shè)P是一個圖論的性質(zhì)。稱為蘊含P的，若存在具有性質(zhì)P的。稱是強迫的，叵所有都具有性質(zhì)P。20世紀80年代中期，Bagga和Beineke以及李炯生等獨立地給出了蘊含2強得分向量的刻劃。1985年JSLi等給出了蘊含k強得分向量的刻劃。他們還刻劃了強迫k強、蘊含k可約、強迫k可約、蘊含k邊強和強迫k邊強得分向量。多部競賽圖是競賽圖的自然推廣。1962年Moon將上面提到的L

4、andau定理和Harary-Moser定理推廣到多部競賽圖，得到類似的結(jié)論。Bagga和Beineke考慮了蘊含2強二部得分序列的刻劃。李炯生等刻劃了蘊含k可約和強迫k可約m部得分序列。1954年Davis考慮了不同構(gòu)競賽圖的計數(shù)問題。他應(yīng)用Plya計數(shù)定理給出了n個不同構(gòu)競賽圖的個數(shù)T(n)的計數(shù)公式，并給出T(n)的母函數(shù)和n階不同構(gòu)強競賽圖的個數(shù)t(n)的母函數(shù)間的關(guān)系：，從而解決了不同構(gòu)強競賽圖和可約競賽圖的計數(shù)問題。于是問題進一步化為，對給定的，求。1984年Brualdi和李喬證明，若是強的，即R被R1優(yōu)超，則；若，則，這里是正則或擬正則的。又當n為奇數(shù)時，；當n為偶數(shù)時，198

5、6年萬宏輝和李喬證明，偏序集上的函數(shù)是Schur凹的。他們并證明，當n為奇數(shù)時，；當n為偶數(shù)時，。競賽圖中極端問題是競賽圖理論研究的一個熱點問題，它和計數(shù)問題有著密切的聯(lián)系。設(shè)，。Tn中k階強子競賽圖的個數(shù)為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證明，對正整數(shù)k，3kn，k(R)在處取到最大值(k；n)，并給出它的值。同樣，設(shè)R是強得分向量。對，Tn中k階傳遞子競賽圖的個

6、數(shù)為k(Tn)。記，；又記，。1966年Moon證明，對正整數(shù)k，3kn，定義在中所有強得分向量構(gòu)成的偏序子集上的函數(shù)k(R)在R=R1處取到最大值(k；n)，并給出它的值。1989年Reid給出(4；n)的下界。至于偏序集上的函數(shù)4(R)是否在處取到最小值(4；n)以及它的確切值等問題仍未解決。同年QLi提出如下問題：上函數(shù)k(R)是否是Schur凹的?k(R)是否是Schur凸的?上函數(shù)k(R)是否是Schur凸的?這些問題仍待解決。競賽圖中的圈結(jié)構(gòu)對于研究競賽圖的組合性質(zhì)具有基本的重要性。一個經(jīng)典的結(jié)論是：競賽圖Tn為強(連通)的充要條件是Tn具有Hamilton圈。1968年Moon將

7、這一結(jié)論推廣為：對n階強競賽圖Tn中每個頂點u，Tn中必有過頂點u的k圈，這里k=3，4，n。和Moon幾乎同時，Alspach考慮了將頂點換成弧的相應(yīng)問題。若對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王問題與體育比賽如何排名次有關(guān)。設(shè)R。對于，Tn中m王的個數(shù)記為km(Tn)。1953年Landau證明，k2(Tn)1。1980年Maurer證明，若k2(Tn)2，則k2(Tn)3。記，上函數(shù)Km(R)與km(R)各具有什么性質(zhì)，Km(R)之最大值K(m；n)和km(R)之最小值各是多少，都是值得進一步研究的。1991年Goddar等人考慮了多部競賽圖中m王問題。他們證明，不含傳送點的二部競賽圖T同一部分頂點集中最大得分頂點一定是4王。同年P(guān)etrovic和Thomasse

9、n證明，不含傳送點的多部競賽圖至少有一個4王，而且有無數(shù)個二部競賽圖，它們不含3王。最近新加坡KMKoh等人證明，不含傳送點的二部競賽圖至少有4個4王，而不含傳送點的三部競賽圖至少有3個4王。多部競賽圖的m王問題尚待進一步研究。競賽圖的鄰接矩陣(即競賽矩陣)的代數(shù)性質(zhì)和競賽圖的組合性質(zhì)間的聯(lián)系既是競賽圖理論關(guān)注的一個問題，也是新興的組合矩陣論研究的一個熱點。從60年代末到70年代初，Brauer和Gentry以及Moon和Pullman證明，n階競賽矩陣Mn的特征值之實部在與之間，其Perron值為的充要條件是Mn為正則的。Moon和Pullman還確定了本原競賽矩陣的本原指數(shù)集。1989年C

10、ean和Hoffman證明，Mn的秩至少是n1，且正則競賽矩陣是滿秩的。1990年Maybee和Pullman證明，設(shè)是Mn的特征值，則MnIn的秩為n1，或者的實部為，其中In是單位矩陣。1992年Caen，Maybee和Pullman證明，若的實部大于，則的幾何重數(shù)與代數(shù)重數(shù)相同。關(guān)于競賽圖的自同構(gòu)群，1963年Moon證明，一個有限群為某個競賽圖的自同構(gòu)群的充要條件是，其頂點數(shù)為奇數(shù)。1966年Goldberg給出了當n14時n階競賽圖的自同構(gòu)群的階數(shù)之最大值g(n)，同年Goldber和Moon給出了g(n)的上界。之后人們開始考慮子競賽圖的同構(gòu)性質(zhì)對母競賽圖的組合性質(zhì)的影響。對給定的

11、k，稱Tn具有Dk(或Ik)，若Tn中nk階子競賽圖都有相同得分向量(或都同構(gòu))。1969年Jean刻劃了具有I2的競賽圖，1974年Mller和Pelant刻劃了具有D2的競賽圖。1973年Kotzig提出刻劃具有I1的競賽圖，1987年李炯生等刻劃了具有D1的競賽圖，并給出具有I1的競賽圖的一個必要條件。1990年JSLi、DDHuang和QPan刻劃了具有Dk的有向圖，k=1，2，和具有I2的有向圖。至于刻劃具有I1的有向圖(或競賽圖)問題尚待解決。今后，競賽圖理論的主要研究方向是，(1)偏序集(或)上各種函數(shù)的Schur凸(Schur凹)性質(zhì)；(2)對各種競賽圖的圖論性質(zhì)P，蘊含P(或

12、強迫P)得分向量(m部得分序列)的刻劃；(3)競賽矩陣的組合性質(zhì)；(4)競賽圖中其他有趣的問題：如m王問題，具有I1的競賽圖的刻劃等?！緟⒖嘉墨I】： 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 張克明,宋增民,王建民,南京大學學報數(shù)學半年刊,1991,1:6-10 6 吳正聲.應(yīng)用數(shù)學學報,1987,10(3):284288 7 Tan S P, Koh K M. Kings in multipartite tournaments, to appear 8