2023年數(shù)學(xué)建模美賽備戰(zhàn)算法參考—圖與網(wǎng)絡(luò)模型及方法

圖論的理論和方法已滲透到物理、化學(xué)、通訊科學(xué)、建筑學(xué)、運(yùn)籌學(xué)，生物遺傳學(xué)、心理學(xué)、經(jīng)濟(jì)學(xué)、社會(huì)學(xué)等學(xué)科中。圖論中所謂的“圖”是指某類具體事物和這些事物之間的聯(lián)系。如果我們用點(diǎn)表示這些具體事物，用連接兩點(diǎn)的線段（直的或曲的）表示兩個(gè)事物的特定的聯(lián)系，就得到了描述這個(gè)“圖”的幾何形象。圖論為任何一個(gè)包含了一種二元關(guān)系的離散系統(tǒng)提供了一個(gè)數(shù)學(xué)模型，借助于圖論的概念、理論和方法，可以對(duì)該模型求解。 圖與網(wǎng)絡(luò)是運(yùn)籌學(xué)（Operations Research）中的一個(gè)經(jīng)典和重要的分支，所研究的問(wèn)題涉及經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸、計(jì)算機(jī)科學(xué)與信息技術(shù)、通訊與網(wǎng)絡(luò)技術(shù)等諸多領(lǐng)域。 網(wǎng)絡(luò)優(yōu)化研究的是網(wǎng)絡(luò)上的各種優(yōu)化模型與算法。為了在計(jì)算機(jī)上實(shí)現(xiàn)網(wǎng)絡(luò)優(yōu)化的算法，首先我們必須有一種方法（即數(shù)據(jù)結(jié)構(gòu)）在計(jì)算機(jī)上來(lái)描述圖與網(wǎng)絡(luò)。一般來(lái)說(shuō)，算法的好壞與網(wǎng)絡(luò)的具體表示方法，以及中間結(jié)果的操作方案是有關(guān)系的。這里推薦計(jì)算機(jī)上用來(lái)描述圖與網(wǎng)絡(luò)的5種常用表示方法：鄰接矩陣表示法、關(guān)聯(lián)矩陣表示法、弧表表示法、鄰接表表示法和星形表示法。 鄰接表表示法將圖以鄰接表（adjacency lists）的形式存儲(chǔ)在計(jì)算機(jī)中。所謂圖的鄰接表，也就是圖的所有節(jié)點(diǎn)的鄰接表的集合；而對(duì)每個(gè)節(jié)點(diǎn)，它的鄰接表就是它的所有出弧。鄰接表表示法就是對(duì)圖的每個(gè)節(jié)點(diǎn)，用一個(gè)單向鏈表列出從該節(jié)點(diǎn)出發(fā)的所有弧，鏈表中每個(gè)單元對(duì)應(yīng)于一條出弧。為了記錄弧上的權(quán)，鏈表中每個(gè)單元除列出弧的另一個(gè)端點(diǎn)外，還可以包含弧上的權(quán)等作為數(shù)據(jù)域。圖的整個(gè)鄰接表可以用一個(gè)指針數(shù)組表示。 計(jì)劃評(píng)審方法（program evaluation and review technique, PERT）和關(guān)鍵路線法（critical path method, CPM）是網(wǎng)絡(luò)分析的重要組成部分，它廣泛的用于系統(tǒng)分析和項(xiàng)目管理。計(jì)劃評(píng)審與關(guān)鍵路線方法是在20世紀(jì)50年代提出并發(fā)展起來(lái)的，1956年，美國(guó)杜邦公司為了協(xié)調(diào)企業(yè)不同業(yè)務(wù)部門(mén)的系統(tǒng)規(guī)劃，提出了關(guān)鍵路線法。1958年，美國(guó)海軍武裝部在研制“北極星”導(dǎo)彈計(jì)劃時(shí)，由于導(dǎo)彈的研制系統(tǒng)過(guò)于龐大、復(fù)雜，為找到一種有效的管理方法，設(shè)計(jì)了計(jì)劃評(píng)審方法。由于PERT與CPM既有著相同的目標(biāo)應(yīng)用，又有很多相同的術(shù)語(yǔ)，這兩種方法已合并為一種方法，在國(guó)外稱為PERT/CPM，在國(guó)內(nèi)稱為統(tǒng)籌方法（scheduling method）。

?

? ? ?

1 ?