數(shù)學(xué)建模案例分析-圖與網(wǎng)絡(luò)方法建模2競(jìng)賽排名

§2競(jìng)賽排名一、競(jìng)賽圖及其性質(zhì)1、競(jìng)賽圖在每條邊上都標(biāo)出方向的圖稱(chēng)為有向圖。每對(duì)頂點(diǎn)間都有一條邊相連的有向圖稱(chēng)為競(jìng)賽圖。如何由競(jìng)賽圖排出頂點(diǎn)的名次。（1）兩個(gè)頂點(diǎn)的競(jìng)賽圖只有一種形式12（2）三個(gè)頂點(diǎn)的競(jìng)賽圖只有兩種形式221313(1)(2)對(duì)（1），頂名次排序?yàn)閧1,2,3}；對(duì)（2），三個(gè)頂點(diǎn)名次相同。（3）四個(gè)頂點(diǎn)的競(jìng)賽圖只有四種形式1111222243434343(1)(2)(3)(4)對(duì)（1），有唯一的通過(guò)全部頂點(diǎn)的有向路徑1234，稱(chēng)為完全路徑。頂點(diǎn)名次排序是{1,2,3,4}。對(duì)（2），頂點(diǎn)2排第1，其余3點(diǎn)名次相同。對(duì)（3），頂點(diǎn)2排最后，其余3點(diǎn)名次相同。對(duì)（4），有不只一有（1）~（3）沒(méi)有的性質(zhì)：對(duì)于任何一條完全路徑，如1234，3412，無(wú)法立即排出名次，具對(duì)頂點(diǎn)，存在兩條有向路徑，使兩頂點(diǎn)可以相互連通，這種有向圖稱(chēng)為雙向連通圖。一般n個(gè)頂點(diǎn)(n4)的競(jìng)賽圖基本類(lèi)型有三種：10、具有唯一的完全路徑，這時(shí)頂點(diǎn)排名順序與路徑方向一致；20、雙向連通圖；30、不屬于10和20。2、雙向連通圖的名次排序以下討論n(n4)個(gè)頂點(diǎn)的雙向連通圖名次排序。重新定義鄰接矩陣A(a)如下：ijnn1存在從頂點(diǎn)i到j(luò)的有向邊aij0否則例如：124301100011A的鄰接矩陣為00011000記頂點(diǎn)的得分向量為SSS(1)(,,,S)T，其中是頂點(diǎn)i的得分。S12ni記S(2)AS(1),,SAS(k1)Ak1S(1)，(k1,2,)。如果k時(shí)，S(k)收斂于某個(gè)k()極限向量，則用這個(gè)向量中分量的大小作為排名次的依據(jù)。當(dāng)k時(shí)將趨向A的對(duì)應(yīng)于最大特征根的特征向量S。定理：S(k)二、應(yīng)用舉例6支球隊(duì)比賽結(jié)果用下圖表示，為雙向連通圖。12KKKK63K5K4鄰接矩陣為010111000111110100A0000110010010010002.232，特征向量S(0.238,0.164,0.231,0.113,0.15,0.104)。于是可排出最大特征根名次為{1,3,2,5,4,6}。12三、其他情況（不屬于和）下的名次排序00對(duì)于既沒(méi)有唯一完全路徑，又不是雙向連通的競(jìng)賽圖，通?？煞纸鉃槿舾蓚€(gè)雙向連通的子競(jìng)賽圖。例如下圖8個(gè)頂點(diǎn)的競(jìng)賽圖分解為3個(gè)雙向連通子競(jìng)賽圖G，G，G。2131G12435GG38276G,G,G子圖之間的邊被簡(jiǎn)化了，實(shí)際上兩子圖的每對(duì)頂點(diǎn)之間都有邊相連，而這些邊的方向123必是一致的，否則相應(yīng)的子圖可以合并為更大的雙向連通子競(jìng)賽圖。在每個(gè)這樣的圖中按上面介紹的方法排名次，而子圖之間的名次不難由它們相連邊的方向決定