秦小二

摘 要： 作者通過一個(gè)反例說明雙向連通競賽圖的一種排名方法的局限性。

關(guān)鍵詞： 雙向連通競賽圖 排名 得分向量

若干支球隊(duì)參加單循環(huán)比賽，各隊(duì)兩兩交鋒，假設(shè)每場比賽只計(jì)勝負(fù)，不計(jì)比分，在比賽結(jié)束后排名次。數(shù)學(xué)模型教材說比賽結(jié)果如果可以用雙向連通競賽圖表示出來，就可以用該圖對應(yīng)的鄰接矩陣A對應(yīng)的最大特征根的特征向量s作為排名依據(jù)的得分向量。筆者經(jīng)過研究發(fā)現(xiàn)，這種方法并不是對所有雙向連通競賽圖都適用。

一、相關(guān)基礎(chǔ)知識

定義：1：雙向連通競賽圖：對于任何一對頂點(diǎn)，存在兩條有向路徑，使兩頂點(diǎn)可以互相連通，這種有向圖稱為雙向連通競賽圖。

定義2：對于n（n≥4）個(gè)頂點(diǎn)的雙向連通競賽圖的鄰接矩陣A，一定存在正整數(shù)r，使得A■>0，這樣的A就稱為素陣。

定理：Perron—Frobenius定理：素陣的最大特征根為正單根λ，λ對應(yīng)正特征向量s，且有

■■=s？搖？搖？搖？搖？搖？搖？搖？搖（2）

二、應(yīng)用舉例

對一般性，記s■=A·e，s■=A·s■，…，s■=A·s■。則有：

s■=A·s■=A■·e（k=1，2，…）？搖？搖？搖？搖？搖？搖？搖？搖？搖？搖？搖？搖？搖（1）

當(dāng)?shù)螖?shù)越多，名次排定順序越穩(wěn)定。可將其較高級的得分作為排名依據(jù)。利用著名的Perron-Frobenius定理求出鄰接矩陣A的最大特征根λ對應(yīng)的正特征向量s，以s作為排名的依據(jù)。下面以4個(gè)隊(duì)比賽結(jié)果的雙向連通競賽圖為例說明如何應(yīng)用這種方法。

圖1 雙向連通競賽圖

其對應(yīng)的鄰接矩陣為：

A=0？搖 1？搖 1？搖 00？搖 0？搖 1？搖 10？搖 0？搖 0？搖 11？搖 0？搖 0？搖 0

矩陣A的最大特征值及對應(yīng)特征向量有：

λ■=1.3953，對應(yīng)特征向量為（0.6256，0.5516，0.3213，0.4484）

我們?nèi)菀椎贸銎渑琶麨椋?->2->4->3。

三、應(yīng)用反例

圖2 5個(gè)頂點(diǎn)的雙向連通競賽圖

其對應(yīng)的鄰接矩陣為：

0？搖 0？搖 1？搖 1？搖 11？搖 0？搖 0？搖 0？搖 00？搖 1？搖 0？搖 1？搖 00？搖 1？搖 0？搖 0？搖 10？搖 1？搖 1？搖 0？搖 0

矩陣A的最大特征值及對應(yīng)特征向量有：

λ=1.8637，對應(yīng)特征向量為（0.6394，0.3431，0.3972，0.3972，0.3972）

此例說明這種方法不是對所有雙向連通競賽圖都適用，這種類型的圖是無法排名的，從整體看3，4，5這三個(gè)頂點(diǎn)的實(shí)力相當(dāng)。

參考文獻(xiàn)：

[1]姜啟源，謝金星，葉俊.數(shù)學(xué)模型（第三版）.北京：高等教育出版社，2003.8.

[2]劉來福等.數(shù)學(xué)模型與數(shù)學(xué)建模.北京師范大學(xué)出版社，1997.9.endprint

摘 要： 作者通過一個(gè)反例說明雙向連通競賽圖的一種排名方法的局限性。

關(guān)鍵詞： 雙向連通競賽圖 排名 得分向量

若干支球隊(duì)參加單循環(huán)比賽，各隊(duì)兩兩交鋒，假設(shè)每場比賽只計(jì)勝負(fù)，不計(jì)比分，在比賽結(jié)束后排名次。數(shù)學(xué)模型教材說比賽結(jié)果如果可以用雙向連通競賽圖表示出來，就可以用該圖對應(yīng)的鄰接矩陣A對應(yīng)的最大特征根的特征向量s作為排名依據(jù)的得分向量。筆者經(jīng)過研究發(fā)現(xiàn)，這種方法并不是對所有雙向連通競賽圖都適用。

一、相關(guān)基礎(chǔ)知識

定義：1：雙向連通競賽圖：對于任何一對頂點(diǎn)，存在兩條有向路徑，使兩頂點(diǎn)可以互相連通，這種有向圖稱為雙向連通競賽圖。

定義2：對于n（n≥4）個(gè)頂點(diǎn)的雙向連通競賽圖的鄰接矩陣A，一定存在正整數(shù)r，使得A■>0，這樣的A就稱為素陣。

定理：Perron—Frobenius定理：素陣的最大特征根為正單根λ，λ對應(yīng)正特征向量s，且有

■■=s？搖？搖？搖？搖？搖？搖？搖？搖（2）

二、應(yīng)用舉例

對一般性，記s■=A·e，s■=A·s■，…，s■=A·s■。則有：

s■=A·s■=A■·e（k=1，2，…）？搖？搖？搖？搖？搖？搖？搖？搖？搖？搖？搖？搖？搖（1）

當(dāng)?shù)螖?shù)越多，名次排定順序越穩(wěn)定。可將其較高級的得分作為排名依據(jù)。利用著名的Perron-Frobenius定理求出鄰接矩陣A的最大特征根λ對應(yīng)的正特征向量s，以s作為排名的依據(jù)。下面以4個(gè)隊(duì)比賽結(jié)果的雙向連通競賽圖為例說明如何應(yīng)用這種方法。

圖1 雙向連通競賽圖

其對應(yīng)的鄰接矩陣為：

A=0？搖 1？搖 1？搖 00？搖 0？搖 1？搖 10？搖 0？搖 0？搖 11？搖 0？搖 0？搖 0

矩陣A的最大特征值及對應(yīng)特征向量有：

λ■=1.3953，對應(yīng)特征向量為（0.6256，0.5516，0.3213，0.4484）

我們?nèi)菀椎贸銎渑琶麨椋?->2->4->3。

三、應(yīng)用反例

圖2 5個(gè)頂點(diǎn)的雙向連通競賽圖

其對應(yīng)的鄰接矩陣為：

0？搖 0？搖 1？搖 1？搖 11？搖 0？搖 0？搖 0？搖 00？搖 1？搖 0？搖 1？搖 00？搖 1？搖 0？搖 0？搖 10？搖 1？搖 1？搖 0？搖 0

矩陣A的最大特征值及對應(yīng)特征向量有：

λ=1.8637，對應(yīng)特征向量為（0.6394，0.3431，0.3972，0.3972，0.3972）

此例說明這種方法不是對所有雙向連通競賽圖都適用，這種類型的圖是無法排名的，從整體看3，4，5這三個(gè)頂點(diǎn)的實(shí)力相當(dāng)。

參考文獻(xiàn)：

[1]姜啟源，謝金星，葉俊.數(shù)學(xué)模型（第三版）.北京：高等教育出版社，2003.8.

[2]劉來福等.數(shù)學(xué)模型與數(shù)學(xué)建模.北京師范大學(xué)出版社，1997.9.endprint

摘 要： 作者通過一個(gè)反例說明雙向連通競賽圖的一種排名方法的局限性。

關(guān)鍵詞： 雙向連通競賽圖 排名 得分向量

若干支球隊(duì)參加單循環(huán)比賽，各隊(duì)兩兩交鋒，假設(shè)每場比賽只計(jì)勝負(fù)，不計(jì)比分，在比賽結(jié)束后排名次。數(shù)學(xué)模型教材說比賽結(jié)果如果可以用雙向連通競賽圖表示出來，就可以用該圖對應(yīng)的鄰接矩陣A對應(yīng)的最大特征根的特征向量s作為排名依據(jù)的得分向量。筆者經(jīng)過研究發(fā)現(xiàn)，這種方法并不是對所有雙向連通競賽圖都適用。

一、相關(guān)基礎(chǔ)知識

定義：1：雙向連通競賽圖：對于任何一對頂點(diǎn)，存在兩條有向路徑，使兩頂點(diǎn)可以互相連通，這種有向圖稱為雙向連通競賽圖。

定義2：對于n（n≥4）個(gè)頂點(diǎn)的雙向連通競賽圖的鄰接矩陣A，一定存在正整數(shù)r，使得A■>0，這樣的A就稱為素陣。

定理：Perron—Frobenius定理：素陣的最大特征根為正單根λ，λ對應(yīng)正特征向量s，且有

■■=s？搖？搖？搖？搖？搖？搖？搖？搖（2）

二、應(yīng)用舉例

對一般性，記s■=A·e，s■=A·s■，…，s■=A·s■。則有：

s■=A·s■=A■·e（k=1，2，…）？搖？搖？搖？搖？搖？搖？搖？搖？搖？搖？搖？搖？搖（1）

當(dāng)?shù)螖?shù)越多，名次排定順序越穩(wěn)定?？蓪⑵漭^高級的得分作為排名依據(jù)。利用著名的Perron-Frobenius定理求出鄰接矩陣A的最大特征根λ對應(yīng)的正特征向量s，以s作為排名的依據(jù)。下面以4個(gè)隊(duì)比賽結(jié)果的雙向連通競賽圖為例說明如何應(yīng)用這種方法。

圖1 雙向連通競賽圖

其對應(yīng)的鄰接矩陣為：

A=0？搖 1？搖 1？搖 00？搖 0？搖 1？搖 10？搖 0？搖 0？搖 11？搖 0？搖 0？搖 0

矩陣A的最大特征值及對應(yīng)特征向量有：

λ■=1.3953，對應(yīng)特征向量為（0.6256，0.5516，0.3213，0.4484）

我們?nèi)菀椎贸銎渑琶麨椋?->2->4->3。

三、應(yīng)用反例

圖2 5個(gè)頂點(diǎn)的雙向連通競賽圖

其對應(yīng)的鄰接矩陣為：

0？搖 0？搖 1？搖 1？搖 11？搖 0？搖 0？搖 0？搖 00？搖 1？搖 0？搖 1？搖 00？搖 1？搖 0？搖 0？搖 10？搖 1？搖 1？搖 0？搖 0

矩陣A的最大特征值及對應(yīng)特征向量有：

λ=1.8637，對應(yīng)特征向量為（0.6394，0.3431，0.3972，0.3972，0.3972）

此例說明這種方法不是對所有雙向連通競賽圖都適用，這種類型的圖是無法排名的，從整體看3，4，5這三個(gè)頂點(diǎn)的實(shí)力相當(dāng)。

參考文獻(xiàn)：

[1]姜啟源，謝金星，葉俊.數(shù)學(xué)模型（第三版）.北京：高等教育出版社，2003.8.

[2]劉來福等.數(shù)學(xué)模型與數(shù)學(xué)建模.北京師范大學(xué)出版社，1997.9.endprint