1、循環(huán)比賽的名次循環(huán)比賽的名次 n支球隊循環(huán)賽，每場比賽支球隊循環(huán)賽，每場比賽只計勝負，沒有平局。只計勝負，沒有平局。 根據(jù)比賽結(jié)果排出各隊名次根據(jù)比賽結(jié)果排出各隊名次方法方法1：尋找按箭頭方向通尋找按箭頭方向通過全部頂點的路徑。過全部頂點的路徑。123456312456146325方法方法2：計算得分：計算得分：1隊勝隊勝4場，場，2, 3隊各勝隊各勝3場，場，4, 5隊各勝隊各勝2場，場， 6隊勝隊勝1場。場。無法排名無法排名2, 3隊，隊， 4, 5隊無法排名隊無法排名6支球隊比賽結(jié)果支球隊比賽結(jié)果32，4 5排名排名 132456 合理嗎合理嗎123(1)123(2)1234(1)123

2、4(2)1234(3)1234(4)循環(huán)比賽的結(jié)果循環(huán)比賽的結(jié)果競賽圖競賽圖每對頂點間都有邊相連的有向圖每對頂點間都有邊相連的有向圖3個頂點個頂點的競賽圖的競賽圖名次名次1，2，3(1,2,3)并列并列1, 2, 3, 42,(1,3,4)(1,3,4), 24個頂點個頂點的競賽圖的競賽圖名次名次(1,2),(3,4)1, 2, 3, 4?123412341234(1)(2)(3)1234(4)競賽圖的競賽圖的3種形式種形式 具有唯一的完全路徑，如具有唯一的完全路徑，如(1)； 雙向連通圖雙向連通圖任一對頂點存在兩條有任一對頂點存在兩條有向路徑相互連通，如向路徑相互連通，如(4)； 其他，如其

3、他，如(2)， (3) 。競賽圖競賽圖的性質(zhì)的性質(zhì) 必存在完全路徑；必存在完全路徑； 若存在唯一的完全路徑，則由它確定的頂若存在唯一的完全路徑，則由它確定的頂點順序與按得分排列的順序一致，如點順序與按得分排列的順序一致，如(1) 。TeAes)1 , 1 , 1 (,級得分向量1)1 , 1 ,2,2()1(TAes級得分向量2)2 , 1 , 2 , 3()1()2(TAss0001100011000110AEvvEvvajijiij, 0, 11234(4)雙向連通競賽圖雙向連通競賽圖G=(V,E)的名次排序的名次排序鄰接矩陣鄰接矩陣Tnssss),(21得分向量得分向量TTss)3 ,

4、3 , 5 , 5(,)3 ,2, 3 , 3()4()3(eAAsskkk ) 1()(?,)(kskTTss)8 , 5 , 8 , 9(,)5 , 3 , 6 , 8()6()5(TTss)13, 9 ,17,21(,)9 , 8 ,13,13()8()7(雙向連通競賽圖的名次排序雙向連通競賽圖的名次排序 對于對于n(3)個頂點的雙向連通競賽圖，存在個頂點的雙向連通競賽圖，存在正整數(shù)正整數(shù)r，使鄰接矩陣，使鄰接矩陣A 滿足滿足Ar 0，A稱稱素陣素陣seAkkklim 素陣素陣A的最大特征根為正單的最大特征根為正單根根 ，對應正特征向量，對應正特征向量s，且，且eAAsskkk ) 1()(0001100011000110A排名為排名為1，2，4，3sskk)(,)(歸一化后Ts)230. 0 ,167. 0 ,280. 0 ,323. 0(, 4 . 1用用s排名排名1234(4)1, 2, 3, 4?000100100100110000001010111000111010ATTTTssss)16,25,21,32,28,38(,)9 ,12,7 ,16,10,15()3 , 4, 3 , 9 , 5 , 8(,)1 , 2, 2, 3 , 3 , 4()4()3()2()1(1234566支球隊比賽結(jié)果支球隊比賽結(jié)果Ts