1.3 競賽圖應用

問題描述 某錦標賽采用循環賽制，若干選手兩兩互相競賽.得出競賽成績后，應該怎樣排列參賽者的名次呢?

思路分析 如表1.3所示是一次比賽中6位選手之間的比賽成績，我們用數字1～6來表示這6名選手，其中“勝”字所在行的選手戰勝所在列的選手，“負”字所在行的選手輸給了所在列的選手.

模型建立 我們用點來表示運動員，對于任意兩名運動員的比賽結果，我們用一條由勝者到負者的有向邊表示.這樣我們就得到了圖1.14所示的這張有向圖，記為D，該圖中任意兩點之間都由唯一一條有向邊連接，我們可以將它看作對完全圖中各條邊的一個定向，即為競賽圖.

一個自然的想法是排名靠前的選手應該擊敗了排名靠后的選手，因此排參賽者名次的一個可能的辦法是尋找這個競賽圖中的哈密頓路（由1.1.2節，我們知道這樣的路是存在的），然后按照參加者對應的頂點在這條路中的位置排列名次.例如，有向哈密頓路（3,1，2,4,5,6）表明選手3是冠軍，選手1是亞軍，等等.可是這種排名顯然經不起進一步推敲，因為一個競賽圖一般有許多條有向哈密頓路；我們的例子中就有（1,2,4,5,6,3）,（1,4,6,3,2,5）以及若干別的有向路.另外，這樣給出的排名會出現在兩兩對決中獲勝的選手排在了落敗的選手之后的情況.

另一個辦法看似很合理，即計算得分（即獲勝場次的數目），并對其進行比較，根據得分由高到低給出排名.在上面的例子中這樣做，按照選手順序分別寫出其獲勝場數，得到得分向量

s1=（4,3,3,2,2,1），

然后按照該向量各位選手的得分大小給出對應的排名，比如在s1中第一個位置的數最大，因此1號選手應該為冠軍，這里讀者立刻就發現這個排名法是有缺陷的，即這個向量不能區別選手2和選手3的得分高低，盡管選手3打敗了得分高的選手.于是我們導出第二級得分向量

s2=（8,5,9,3,4,3），

其中每個選手的第二級得分是被他打敗的選手的得分之和，例如，3號選手在二級分量中的數值是計算了他所擊敗的選手在第一級得分分量中的數值之和，即9=4+3+2.我們可以看出3號選手的得分在第二級得分向量中最大，因此名列第一.繼續進行該過程，選手下一級得分分量中的得分等于上一級得分向量中被他擊敗的選手的得分之和，進一步地，我們得到了如下向量

s3=（15,10,16,7,12,9），

s4=（38,28,32,21,25,16），

s5=（90,62,87,41,48,32），

s6=（183,121,193,80,119,87）.

看來選手名次的排列有點波動，例如選手3和選手1競爭第一名的情況就是這樣.但是，由圖論知識我們知道，如果競賽圖是雙連通的，并且至少有4個頂點時，這個程序總是收斂于一個固定的排列.這將導出在任何競賽中排選手名次的一個好方法.

模型求解 我們看到競賽圖的等級得分向量由

si=AiJ

給出，這里A是D的鄰接矩陣，J是由1組成的列向量.有向圖D的鄰接矩陣A（D）=（aij）中各項元素的取值滿足如果連接點vi和vj的有向弧是從vi指向vj,aij=1，否則為0.在本例中，圖D的鄰接矩陣為

由于A是本原的，根據Perron-Frobenius定理（參見參考文獻[4]），設A具有最大絕對值的特征值是正實數r，則

這里s是對應于r的正特征向量.在上例中，我們近似地求得

r=2.232,s=（0.238,0.164,0.231,0.150,0.104）

于是，用這個方法給出的選手的名次排列為1,3,2,5,4,6.

若競賽圖不是雙連通的，它的各個雙向連通分支可以按優勝順序排列.于是在一般的循環賽中可以按下列程序排出名次.

（1）在4個或者更多個頂點的各個雙向分支中，利用特征向量s排選手的名次；在3個頂點的雙向分支中，3個選手的排名采用其他方式.

（2）把這些雙向連通分支按優勝次序排列成D1,D2,…,Dm，即若i＜j，則凡是一個端點在Di中，另一個端點在Dj中的每條弧，其頭部都在Dj中.

（3）綜合（1）和（2）的排名，得到總排名.