關(guān)于教材中雙向連通競(jìng)賽圖的排名方法的思考

秦小二

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

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

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

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

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

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

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

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

二、應(yīng)用舉例

對(duì)一般性，記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í)的得分作為排名依據(jù)。利用著名的Perron-Frobenius定理求出鄰接矩陣A的最大特征根λ對(duì)應(yīng)的正特征向量s，以s作為排名的依據(jù)。下面以4個(gè)隊(duì)比賽結(jié)果的雙向連通競(jìng)賽圖為例說(shuō)明如何應(yīng)用這種方法。

圖1 雙向連通競(jìng)賽圖

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

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

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

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

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

三、應(yīng)用反例

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

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

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

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

二、應(yīng)用舉例

對(duì)一般性，記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í)的得分作為排名依據(jù)。利用著名的Perron-Frobenius定理求出鄰接矩陣A的最大特征根λ對(duì)應(yīng)的正特征向量s，以s作為排名的依據(jù)。下面以4個(gè)隊(duì)比賽結(jié)果的雙向連通競(jìng)賽圖為例說(shuō)明如何應(yīng)用這種方法。

圖1 雙向連通競(jìng)賽圖

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

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

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

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

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

三、應(yīng)用反例

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

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

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

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

二、應(yīng)用舉例

對(duì)一般性，記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í)的得分作為排名依據(jù)。利用著名的Perron-Frobenius定理求出鄰接矩陣A的最大特征根λ對(duì)應(yīng)的正特征向量s，以s作為排名的依據(jù)。下面以4個(gè)隊(duì)比賽結(jié)果的雙向連通競(jìng)賽圖為例說(shuō)明如何應(yīng)用這種方法。

圖1 雙向連通競(jìng)賽圖

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

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

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

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

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

三、應(yīng)用反例

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

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

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

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

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

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

參考文獻(xiàn)：

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

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