數(shù)學(xué)建模-圖論

1、初等數(shù)學(xué)方法建模 現(xiàn)實(shí)世界中有很多問(wèn)題，它的機(jī)理較簡(jiǎn)單，用靜態(tài),線性或邏輯的方法即可建立模型，使用初等的數(shù)學(xué)方法，即可求解，我們稱之為初等數(shù)學(xué)模型。本章主要介紹有關(guān)自然數(shù)，比例關(guān)系，狀態(tài)轉(zhuǎn)移，及量剛分析等建模例子，這些問(wèn)題的巧妙的分析處理方法，可使讀者達(dá)到舉一反三，開(kāi)拓思路，提高分析, 解決實(shí)際問(wèn)題的能力。第一節(jié) 有關(guān)自然數(shù)的幾個(gè)模型1.1鴿籠原理鴿籠原理又稱為抽屜原理，把個(gè)蘋(píng)果放入 個(gè)抽屜里，則必有一個(gè)抽屜中至少有2個(gè)蘋(píng)果。問(wèn)題1：如果有個(gè)人，其中每個(gè)人至多認(rèn)識(shí)這群人中的個(gè)人（不包括自己），則至少有兩個(gè)人所認(rèn)識(shí)的人數(shù)相等。分析：我們按認(rèn)識(shí)人的個(gè)數(shù)，將個(gè)人分為類，其中類，表示認(rèn)識(shí)個(gè)人，這樣形成

2、 個(gè)“鴿籠”。若 ，則個(gè)人分成不超過(guò) 類，必有兩人屬于一類，也即有兩個(gè)人所認(rèn)識(shí)的人數(shù)相等；若 ，此時(shí)注意到類和類必有一個(gè)為空集，所以不空的“鴿籠”至多為個(gè)，也有結(jié)論成立問(wèn)題2：在一個(gè)邊長(zhǎng)為的正三角形內(nèi)最多能找到幾個(gè)點(diǎn)，而使這些點(diǎn)彼此間的距離大于.分析：邊長(zhǎng)為1的正三角形 ，分別以為中心，為半徑圓弧，將三角形分為四個(gè)部分（如圖1-1 ），則四部分中任一部分內(nèi)兩點(diǎn)距離都小于 ，由鴿籠原理知道，在三角形內(nèi)最多能找四個(gè)點(diǎn)，使彼此間距離大于 ，且確實(shí)可找到如及三角形中心四個(gè)點(diǎn)。 圖11問(wèn)題3：能否在的方格表的各個(gè)空格中，分別填寫(xiě)這三個(gè)數(shù)中的任一個(gè)，使得每行，每列及對(duì)角線的各個(gè)數(shù)的和都不相同？為什么？分析

3、：若從考慮填法的種類入手，情況太復(fù)雜；這里我們注意到，方格表中行,列及對(duì)角線的總數(shù)為個(gè)；而用填入表格，每行,列及對(duì)角線都是個(gè)數(shù)，個(gè)數(shù)的和最小為，最大為，共有種；利用鴿籠原理，個(gè)“鴿”放入個(gè)“鴿籠”，必有兩個(gè)在一個(gè)“鴿籠”，也即必有兩個(gè)和相同。所以題目中的要求，無(wú)法實(shí)現(xiàn)。思考題：在一個(gè)邊長(zhǎng)為的正三角形內(nèi)，若要彼此間距離大于 ，最多能找到幾個(gè)點(diǎn)？1.2 “奇偶校驗(yàn)”方法 所謂 “奇偶校驗(yàn)”，即是如果兩個(gè)數(shù)都是奇數(shù)或偶數(shù)，則稱這兩個(gè)數(shù)具有相同的奇偶性；若一個(gè)數(shù)是奇數(shù)，另一個(gè)數(shù)是偶數(shù)，則稱具有相反的奇偶性。在組合問(wèn)題中，經(jīng)常使用“奇偶校驗(yàn)”考慮配對(duì)問(wèn)題。問(wèn)題1（棋盤(pán)問(wèn)題）：假設(shè)你有一張普通的國(guó)際象棋盤(pán)

4、，一組對(duì)角上的兩個(gè)方格被切掉，這樣棋盤(pán)上只剩下個(gè)方格（如圖12）。若你還有塊骨牌，每塊骨牌的大小為方格。試說(shuō)明用互不重疊的骨牌完全覆蓋住這張殘缺的棋盤(pán)是不可能的。分析：關(guān)鍵是對(duì)圖12的棋盤(pán)進(jìn)行黑白著色，使得相鄰的兩個(gè)方格有不同的顏色；用一塊骨牌覆蓋兩個(gè)方格，必是蓋住顏色不同的方格。我們計(jì)算一下黑白著色棋盤(pán)的黑格，白格個(gè)數(shù)，分別為和；因此不同能用塊骨牌蓋住這張殘缺的棋盤(pán)。用奇偶校驗(yàn)法，我們可以把黑色方格看成奇數(shù)方格，白色方格看成偶數(shù)方格；因?yàn)槠媾紓€(gè)數(shù)不同，所以不能進(jìn)行奇偶配對(duì)，故題中要求的作法是不可能實(shí)現(xiàn)的。圖1-3 圖1-2 問(wèn)題2（菱形十二面體上的H路徑問(wèn)題）：沿一菱形十二面體各棱行走，要尋

5、找一條這樣的路徑它通過(guò)各頂點(diǎn)恰好一次，該問(wèn)題被稱為Hamilton路徑問(wèn)題。分析：我們注意到菱形十二面體每個(gè)頂點(diǎn)的度或者為或者為，所謂頂點(diǎn)的度是指通過(guò)這一頂點(diǎn)的棱數(shù)，如圖13；且每度頂點(diǎn)剛好與個(gè)度頂點(diǎn)相連，而每個(gè)度頂點(diǎn)剛好與個(gè)度 頂點(diǎn)相連。因此一個(gè)Hamilton路徑必是度與度頂點(diǎn)交錯(cuò)，故若存在Hamilton 路徑，則度頂點(diǎn)個(gè)數(shù)，與度頂點(diǎn)個(gè)數(shù)要么相等，要么相差。用奇偶校驗(yàn)法度頂點(diǎn)為奇數(shù)頂點(diǎn)，度頂點(diǎn)為偶數(shù)頂點(diǎn)，奇偶配對(duì)，最多只能余個(gè)；而事實(shí)上菱形十二面體中，有度頂點(diǎn)個(gè)，度頂點(diǎn)個(gè)；可得結(jié)論，菱形十二面體中不存在Hamilton 路徑.思考題：1、設(shè)一所監(jiān)獄有間囚室，其排列類似棋盤(pán)，看守長(zhǎng)告訴關(guān)押

6、在一個(gè)角落里的囚犯，只要他能夠不重復(fù)地通過(guò)每間囚室到達(dá)對(duì)角的囚室（所有相鄰囚室間都有門(mén)相通）,他將獲釋，問(wèn)囚犯能否獲得自由？2、某班有個(gè)學(xué)生，坐成行列，每個(gè)坐位的前后左右的坐位叫做它的鄰座，要讓個(gè)學(xué)生都換到他的鄰座上去，問(wèn)是否有這種調(diào)換位置的方案？1.3 自然數(shù)的因子個(gè)數(shù)與獄吏問(wèn)題令 為自然數(shù) 的因子個(gè)數(shù)，則 有的為奇數(shù)，有的為偶數(shù)，見(jiàn)下表: n12345678910111213141516d(n)1223242434262445我們發(fā)現(xiàn)這樣一個(gè)規(guī)律，當(dāng)且僅當(dāng)為完全平方數(shù)時(shí),為奇數(shù)；這是因?yàn)榈囊蜃邮浅蓪?duì)出現(xiàn)的,也即 ; 只有為完全平方數(shù), 才會(huì)出現(xiàn) 的情形，才為奇數(shù)。下面我們利用上述結(jié)論研究一

7、個(gè)有趣的問(wèn)題. 獄吏問(wèn)題：某王國(guó)對(duì)囚犯進(jìn)行大赦，讓一獄吏n次通過(guò)一排鎖著的n間牢房，每通過(guò)一次按所定規(guī)則轉(zhuǎn)動(dòng)門(mén)鎖, 每轉(zhuǎn)動(dòng)一次, 原來(lái)鎖著的被打開(kāi), 原來(lái)打開(kāi)的被鎖上；通過(guò)n次后，門(mén)鎖開(kāi)著的，牢房中的犯人放出，否則犯人不得獲釋。轉(zhuǎn)動(dòng)門(mén)鎖的規(guī)則是這樣的，第一次通過(guò)牢房，要轉(zhuǎn)動(dòng)每一把門(mén)鎖，即把全部鎖打開(kāi)；第二次通過(guò)牢房時(shí)，從第二間開(kāi)始轉(zhuǎn)動(dòng)，每隔一間轉(zhuǎn)動(dòng)一次；第k次通過(guò)牢房，從第k間開(kāi)始轉(zhuǎn)動(dòng)，每隔k-1 間轉(zhuǎn)動(dòng)一次；問(wèn)通過(guò)n次后，那些牢房的鎖仍然是打開(kāi)的？問(wèn)題分析： 牢房的鎖最后是打開(kāi)的，則該牢房的鎖要被轉(zhuǎn)動(dòng)奇數(shù)次；如果把n間牢房用編號(hào)，則第k間牢房被轉(zhuǎn)動(dòng)的次數(shù)，取決于k是否為整除，也即k的因子個(gè)數(shù)

8、，利用自然數(shù)因子個(gè)數(shù)定理，我們得到結(jié)論：只有編號(hào)為完全平方數(shù)的牢房門(mén)仍是開(kāi)著的。14 相識(shí)問(wèn)題問(wèn)題：在6人的集會(huì)上，總會(huì)有3人互相認(rèn)識(shí)或互相不認(rèn)識(shí)。分析：設(shè)6人為;下面分二種情形，1.至多只和兩個(gè)人相識(shí)，不妨設(shè)不認(rèn)識(shí)；若互相都認(rèn)識(shí)，則結(jié)論成立，若中有兩人不認(rèn)識(shí)，則加上，有三人互不相識(shí). 2 至少和三人相識(shí)，不妨設(shè) 認(rèn)識(shí)；若互不相識(shí)結(jié)論成立，若有兩人相識(shí)，加上 則有三人互相認(rèn)識(shí) 。這樣，我們就證明了結(jié)論成立,這個(gè)問(wèn)題的討論，我們也可以采用幾何模似的方法，如圖14圖1-4在平面上畫(huà)出六個(gè)點(diǎn)，表示6個(gè)人，兩點(diǎn)間存在連線，表示兩人相識(shí)；只需說(shuō)明，圖中必有三點(diǎn)組成三角形（有三人相識(shí)），或有三點(diǎn)之間設(shè)有一

9、條連線（三人互不相識(shí)）即可，第二節(jié) 狀態(tài)轉(zhuǎn)移問(wèn)題本節(jié)介紹兩種狀態(tài)轉(zhuǎn)移問(wèn)題，解決這種問(wèn)題的方法,有狀態(tài)轉(zhuǎn)移法，圖解法及用圖的鄰接距陣等。21 人、狗、雞、米問(wèn)題人、狗、雞、米均要過(guò)河，船上除1人劃船外，最多還能運(yùn)載一物，而人不在場(chǎng)時(shí)，狗要吃雞，雞要吃米，問(wèn)人，狗、雞、米應(yīng)如和過(guò)河？分析：假設(shè)人、狗、雞、米要從河的南岸到河的北岸，由題意，在過(guò)河的過(guò)程中，兩岸的狀態(tài)要滿足一定條件，所以該問(wèn)題為有條件的狀態(tài)轉(zhuǎn)移問(wèn)題。1. 允許狀態(tài)集合 我們用（w, x, y, z），w, x, y, z=0或1，表示南岸的狀態(tài)，例如（1，1，1，1）表示它們都在南岸，（0，1，1，0）表示狗，雞在南岸，人，米在北岸；

10、很顯然有些狀態(tài)是允許的，有些狀態(tài)是不允許的，用窮舉法可列出全部10個(gè)允許狀態(tài)向量， (1, 1, 1, 1) (1, 1, 1, 0) (1, 1, 0, 1) (1, 0, 1, 1) (1, 0, 1, 0) (0, 0, 0, 0) (0, 0, 0, 1) (0, 0, 1, 0) (0, 1, 0, 0) (0, 1, 0, 1)我們將上述10個(gè)可取狀態(tài)向量組成的集合記為S，稱S為允許狀態(tài)集合 2、狀態(tài)轉(zhuǎn)移方程 對(duì)于一次過(guò)河，可以看成一次狀態(tài)轉(zhuǎn)移，我們用向量來(lái)表示決策，例（1，0，0，1）表示人，米過(guò)河。令D為允許決策集合， D= (1, x, y, z) : x+y+z=0 或 1

11、 另外，我們注意到過(guò)河有兩種，奇數(shù)次的為從南岸到北岸，而偶數(shù)次的為北岸回到南岸，因此得到下述轉(zhuǎn)移方程， -(2.1)表示第k次狀態(tài)， 為決策向量. 圖2-12. 人、狗、雞、米過(guò)河問(wèn)題，即要找到， 且滿足（2.1）式。下面用狀態(tài)轉(zhuǎn)移圖求解將10個(gè)允許狀態(tài)用10個(gè)點(diǎn)表示，并且僅當(dāng)某個(gè)允許狀態(tài)經(jīng)過(guò)一個(gè)允許決策仍為允許狀態(tài)，則這兩個(gè)允許狀態(tài)間存在連線，而構(gòu)成一個(gè)圖, 如圖21 , 在其中尋找一條從（1，1，1，1）到（0，0，0，0）的路徑，這樣的路徑就是一個(gè)解, 可得下述路徑圖,圖2-2由圖22，有兩個(gè)解都是經(jīng)過(guò)7次運(yùn)算完成，均為最優(yōu)解22 商人過(guò)河問(wèn)題 三名商人各帶一個(gè)隨從乘船渡河，現(xiàn)有一只小船

12、只能容納兩個(gè)人，由他們自己劃行，若在河的任一岸的隨從人數(shù)多于商人，他們就可能搶劫財(cái)物。但如何乘船渡河由商人決定，試給出一個(gè)商人安全渡河的方案。首先介紹圖論中的一個(gè)定理G是一個(gè)圖，V（G）為G的頂點(diǎn)集，E(G)為G的邊集。 設(shè)G中有n個(gè)頂點(diǎn); 為G的鄰接距陣，其中 定理1：設(shè)為圖的鄰接距陣，則中從頂點(diǎn)到頂點(diǎn)，長(zhǎng)度為的道路的條數(shù)為中的行列元素.證： 對(duì)用數(shù)學(xué)歸納法 時(shí)，顯然結(jié)論成立; 假設(shè)時(shí)，定理成立， 考慮 的情形. 記的行列元素為 , 因?yàn)?, 所以 (2.2)而從 到 長(zhǎng)的道路無(wú)非是從經(jīng)步到某頂,再?gòu)?走一步到；由歸納假設(shè)從到長(zhǎng)為的道路共計(jì)條，而從到長(zhǎng)為1的道路為條，所以長(zhǎng)為的從經(jīng)步到再一步

13、到的道路共有條，故從經(jīng)步到的路徑共有條.下面分析及求解 假設(shè)渡河是從南岸到北岸，（m，n）表示南岸有m個(gè)商人，n個(gè)隨從，全部的允許狀態(tài)共有10個(gè) 以為頂點(diǎn)集，考慮到奇數(shù)次渡河及偶數(shù)次渡河的不同，我們建立兩個(gè)鄰接距陣 其中 其中A表示從南岸到北岸渡河的圖的鄰接距陣，表示從北岸到南岸渡河的圖的鄰接距陣。由定理1、我們應(yīng)考慮最小的， 中1行10列的元素不為0，此時(shí)即為最少的渡河次數(shù)，而矩陣中1行10列的元素為最佳的路徑數(shù)目。經(jīng)過(guò)計(jì)算K=5時(shí), 的第1行10列元素為2，所以需11次渡河，有兩條最佳路徑.最后我們用圖解法求解： 前面我們已求出問(wèn)題的10種允許狀態(tài)，允許決策向量集合,狀態(tài)轉(zhuǎn)移方程為 , 如

14、圖23，標(biāo)出10種允許狀態(tài)，找出從經(jīng)由允許狀態(tài)到原點(diǎn)的路徑，該路徑還要滿足奇數(shù)次向左，向下；偶數(shù)次向右, 向上. 圖2-3 由圖23可得這樣的過(guò)河策略，共分11次決策 去一商一隨（2，2）（3，3）回一商（3，2）去二隨（3，0）回一隨（3，1）去二商（1，1）回一商一隨（2，2）去二商（0，2）回一隨（0，3）去二隨（0，1）回一隨（0，2）去二隨（0，0）思考題：1、在商人過(guò)河中若有4名商人，各帶一隨從能否過(guò)河？2、夫妻過(guò)河問(wèn)題：有3對(duì)夫妻過(guò)河，船最多能載2人，條件是任一女子不能在其丈夫不在的情況下與其他男子在一起，如何安排三對(duì)夫妻過(guò)河？若船最多能載3人，5對(duì)夫妻能否過(guò)河？3、量綱分析法量

15、綱分析是20世紀(jì)初提出的, 在物理領(lǐng)域中建立數(shù)學(xué)模型的一種方法，它是在經(jīng)驗(yàn)和實(shí)驗(yàn)的基礎(chǔ)上, 利用物理定律的量綱齊次原則，確定各物理量之間的關(guān)系。3.1 量綱齊次原則與Pi定理許多物理量是有量綱的，有些物理量的量綱是基本的，另一些物理量的量綱則可以由基本量綱根據(jù)其定義或某些物理定律推導(dǎo)出來(lái)。例如在動(dòng)力學(xué)中，把長(zhǎng)度, 質(zhì)量和時(shí)間的量綱作為基本量綱，記為; 而速度的量綱可表示為. 在國(guó)際單位制中，有7個(gè)基本量：長(zhǎng)度、質(zhì)量、時(shí)間、電流、溫度、光強(qiáng)度和物質(zhì)的量，它們的量綱分別為L(zhǎng)、M、T、I、J、和N；稱為基本量綱。任一個(gè)物理量q的量綱都可以表成基本量綱的冪次之積， 量綱齊次性原則：用數(shù)學(xué)公式表示一個(gè)物

16、理定律時(shí)，等式兩端必須保持量綱一致。量綱分析就是在保證量綱一致的原則下，分析和探求物理量之間關(guān)系；先看一個(gè)具體的例子，再給出量綱分析的一般方法。例31： 單擺運(yùn)動(dòng)，質(zhì)量為的小球系在長(zhǎng)度為的線的一端，線的另一端固定，小球偏離平衡位置后，在重力作用下做往復(fù)擺動(dòng)，忽略阻力，求擺動(dòng)周期的表達(dá)式。解：在這個(gè)問(wèn)題中有關(guān)的物理量有設(shè)它們之間有關(guān)系式 -（3.1）其中為待定常數(shù)，入為無(wú)量綱的比例系數(shù)，?。?1）式的量綱表達(dá)式有 整理得： -（3.2）由量綱齊次原則應(yīng)有 -（3.3）解得： 代入（31）得 -（3.4）（3.4）式與單擺的周期公式是一致的下面我們給出用于量綱分析建模的 Buckingham Pi

17、定理，定理：設(shè)n個(gè)物理量之間存在一個(gè)函數(shù)關(guān)系 -（3.5）為基本量綱，。的量綱可表示為 矩陣稱為量綱距陣，若則（3.5）式與下式等價(jià)，其中F為一個(gè)未定的函數(shù)關(guān)系，為無(wú)量綱量，且可表示為 -(3.6)而為線性齊次方程組的基本解向量. 利用Pi定理建模，關(guān)鍵是確定與該問(wèn)題相關(guān)的幾個(gè)基本量綱的無(wú)量綱量,作為量綱分析法的應(yīng)用，下面我們介紹航船阻力的建模.32 航船的阻力， 長(zhǎng)吃水深度的船以速度航行，若不考慮風(fēng)的影響，航船受到的阻力除依賴于船的諸變量以外，還與水的參數(shù)密度P，粘性系數(shù), 以及重力加速度g有關(guān)。我們利用pi定理分析f和上述物理之間的關(guān)系1 航船問(wèn)題中涉及的物理量及其量綱為我們要尋求的關(guān)系式

18、為 -（3.7）這些物理量中涉及到的基本量綱為L(zhǎng)、M、T2 寫(xiě)出量綱距陣 3 解齊次線性方程組 , 可得 個(gè)基本解向量 由（3.6）式，可給出4個(gè)無(wú)量量綱 - -（3.8） 由Pi 定理，（3.7）等價(jià)于下列方程 -（3.9）這里是未定的函數(shù)由（3.）,（.）可得阻力f的顯式表達(dá)式， -（3.10）其中是由（.）可得到的未知的函數(shù)關(guān)系,在力學(xué)上, 稱為Froude數(shù)，記為Fr ;稱為Reynold數(shù)，記為Re , 因此（3.10）又可寫(xiě)為 -（3.11）4. 下面我們利用物理模擬進(jìn)一步確定航船在水中的阻力。 設(shè):分別表示模型和原型中的各物理量,由(3.11)有 當(dāng)無(wú)量綱量 -（3.12）成立時(shí)

19、 , 可得 -（3.13）則此時(shí)由模型船的阻力，及其它的；可確定原型船的阻力.下面,我們討論一下(3.12)成立的條件,如果在實(shí)驗(yàn)中采用跟實(shí)際同樣的水質(zhì),則 又故可得 ： -（3.14）要使得(3.14)成立 , 必有；也即模型船與原型船一樣大，這顯然排除了物理模擬的可行性。若考慮選用不同的水質(zhì)，仍設(shè) 則(3.12)式化為 -（3.15）由(3.15)可得 ,若按1：20的比例，顯然無(wú)法找到如此小的粘性系數(shù)的液體實(shí)際上的一種近似處理方法是，在一定條件下Re數(shù)的影響很小，這樣可近似得到， 類似地分析，只要 即有 -（3.16）由（3.16）式就容易確定原型船的阻力3.3 無(wú)量綱化 拋射問(wèn)題 下面

20、我們通過(guò)一個(gè)例子,介紹如何使用無(wú)量綱化方法簡(jiǎn)化模型。拋射問(wèn)題：在某星球表面以初速度豎直向上發(fā)射火箭，記星球半徑為，星球表面重力加速度為，忽略阻力，討論發(fā)射高度隨時(shí)間T的變化規(guī)律.模型建立：設(shè)軸豎直向上， 時(shí) ，火箭和星球質(zhì)量分別記為和，由牛頓第二定律和萬(wàn)有引力定律可得: -（3.17）以 代入（3.17）可得 故得如下初值問(wèn)題 -（3.18）(3.18)式的解可以表為 也即發(fā)射高度是以 為參數(shù)的的函數(shù),下面我們采用無(wú)量綱化方法化簡(jiǎn)方程（3.18）, 顯然拋射問(wèn)題中的基本量綱為 而 所謂無(wú)量綱化是指，對(duì)(3.18)式中的和分別構(gòu)造且有相同的參數(shù)組合和，使得新變量 為無(wú)量綱量，其中 稱為特征尺度或

21、參考尺度；把方程（3.18）化為 對(duì) 的微分方程，即可簡(jiǎn)化模型，如何尋找特征尺度，這里我們以為例，首先寫(xiě)出參數(shù)的量綱距陣 t的量綱向量為 記為 : 求解線性方程組 得通解: 任取，即得到一種特征尺度，例如 得 得 得 同理可得的幾種特征尺度等以下，我們利用不同的和化簡(jiǎn)（3.18） 1. 令 ; 則由 , 代入(3.18)可得: -（3.19）(3.19)式的解可表為 ,含一個(gè)獨(dú)立參數(shù)且為無(wú)量綱量.2. 令 , 類似地可將(3.18)化為 : -（3.20）3. 令 可將(3.19)化為 -（3.21）按照現(xiàn)有科技能力, ,在（3.21）中令，則有 -（3.22）(3.22) 的解為: ,代回原

22、變量 得: , -（3.23）(3.23)式恰為假定火箭運(yùn)動(dòng)過(guò)程中所受星球引力 不變的運(yùn)動(dòng)方程。小結(jié)：無(wú)量綱化是用數(shù)學(xué)工具研究物理問(wèn)題時(shí)常用的方法，恰當(dāng)?shù)剡x擇特征尺度不僅可以減少參數(shù)的個(gè)數(shù)，而且可以幫助人們決定舍棄哪些次要因素第四節(jié) 比例與函數(shù)建模 本節(jié)介紹的幾個(gè)模型,都是利用基本的比例關(guān)系與函數(shù)建立起的數(shù)學(xué)模型。4.1 動(dòng)物體型問(wèn)題 問(wèn)題： 某生豬收購(gòu)站，需要研究如何根據(jù)生豬的體長(zhǎng)（不包括頭尾）估計(jì)其體重？模型假設(shè)：1 將四足動(dòng)物的軀干（不含頭尾）視為質(zhì)量為m的圓柱體，長(zhǎng)度為，截面面積，直徑為d如圖4-1 圖4-12 把圓柱體的軀干看作一根支撐在四肢上的彈性梁，動(dòng)物在體重f作用下的最大下垂為

23、，即梁的最大彎曲，根據(jù)彈性力學(xué)彎曲度理論，有: -（4.1） 3 以生物進(jìn)化學(xué)的角度，可認(rèn)為動(dòng)物的相對(duì)下垂度已達(dá)到一個(gè)最合適的數(shù)值，也即為常數(shù)模型建立： ; - -（4.2） 由（1）式 可令 為比例常數(shù)由（2）式 -（4.3） 令 由假設(shè)3，為常數(shù) -（4.4）因此生豬的體重與體長(zhǎng)的四次方成正比，在實(shí)際工作中，工作人員可由實(shí)際經(jīng)驗(yàn)及統(tǒng)計(jì)數(shù)據(jù)找出常數(shù)K，則可近似地由生豬的體長(zhǎng)估計(jì)它的體重。42 雙重玻璃的功效問(wèn)題： 房間居室的窗戶有的是雙層的，即在窗戶上裝兩層玻璃，且中間留有一定的空隙，試比較雙層玻璃窗與單層玻璃窗的熱量流失？模型假設(shè)：1。設(shè)雙層玻璃窗的兩玻璃的厚度都為d，兩玻璃的間距為L(zhǎng)；單

24、層玻璃窗的玻璃厚度為2d，所用玻璃材料相同，如圖4-22假設(shè)窗戶的封閉性能很好，兩層玻璃之間的空氣不流動(dòng)，即忽略熱量的對(duì)流，只考慮熱量的傳導(dǎo).3. 室內(nèi)溫度和室外溫度保持不變，熱傳導(dǎo)過(guò)程處于穩(wěn)定狀態(tài)，即單位時(shí)間通過(guò)單位面積的熱量為常數(shù) 4. 玻璃材料均勻，熱傳導(dǎo)系數(shù)為常數(shù). 圖4-2模型建立： 對(duì)于厚度為d的均勻介質(zhì)，兩側(cè)溫度差為，則單位時(shí)間由溫度高的一側(cè)向溫度低的一側(cè)通過(guò)單位面積的熱量Q滿足 k為熱傳導(dǎo)系數(shù) 設(shè)玻璃的熱傳導(dǎo)系數(shù)為，空氣的熱傳導(dǎo)系數(shù)為 （1） 先考慮單層玻璃的單位時(shí)間，單位面積的熱量傳導(dǎo) -（4.5）（2） 考慮雙層玻璃情形 此時(shí)熱量先通過(guò)厚度為d的玻璃傳導(dǎo)到兩層玻璃的夾層空氣

25、中，再通過(guò)空氣傳導(dǎo)，再通過(guò)厚度為d的玻璃傳導(dǎo)；設(shè)內(nèi)層玻璃的外側(cè)溫度為，外層玻璃的內(nèi)側(cè)溫度為;則有: -（4.6）由（4.6）式可得 -（4.7） 記 則 -（4.8） - -（4.9） -（4.10） -（4.11） 考慮兩者之比 -（4.12）顯然 , 也即雙層玻璃的熱量損失較小. 模型分析與應(yīng)用： 常用玻璃的熱傳導(dǎo)系數(shù) ，而不流通,干燥空氣的熱傳導(dǎo)系數(shù) ，若取 , 則 , 故 -（4.13）若取 ， 則 又此可見(jiàn)雙層玻璃的保暖效果是相當(dāng)可觀的。我國(guó)北方寒冷地區(qū)的建筑物，通常采用雙層玻璃；由（4.13）式 h=4時(shí), , h再大，熱量傳遞的減少就不明顯了，再考慮到墻體的厚度；所以建筑規(guī)范通常

26、要求 .4.3 席位分配模型問(wèn)題分析： 席位分配問(wèn)題，當(dāng)出現(xiàn)小數(shù)時(shí)，無(wú)論如何分配都是不完全公平的。那么一個(gè)比較公平的分法是應(yīng)該找到一個(gè)不公平程度最低的方法，因此首先要給出不公平程度的數(shù)量化，然后考慮使之最小的分配方案。模型建立： 一、討論不公平程度的數(shù)量化 設(shè)A，B兩方人數(shù)分別為；分別占有 和 個(gè)席位，則兩方每個(gè)席位所代表的人數(shù)分別為 和 。我們稱 為絕對(duì)不公平值。例： 則 又 則 由上例可知，用絕對(duì)不公平程度作為衡量不公平的標(biāo)準(zhǔn)，并不合理，下面我們給出相對(duì)不公平值 若 則稱 為對(duì)A的相對(duì)不公平值， 記為 若 則稱 為對(duì)B的相對(duì)不公平值 ，記為 上例中，相對(duì)不公平值分別為：0.2 和 0.02

27、，可見(jiàn)相對(duì)不公平值較合理。二、 下面我們用相對(duì)不公平值建立模型，設(shè)，A，B兩方人數(shù)分別為 ；分別占有 和 個(gè)席位現(xiàn)在增加一個(gè)席位，應(yīng)該給A還是B ？不妨設(shè) ，此時(shí)對(duì)A不公平，下面分二種情形（1） ，這說(shuō)明即使A增加1席，仍對(duì)A不公平, 故這一席應(yīng)給A。（2） ， 說(shuō)明A方增加1席時(shí)，將對(duì)B不公平，此時(shí)計(jì)算對(duì)B的相對(duì)不公平值 若這一席給B，則對(duì)A的相對(duì)不公平值為 本著使得相對(duì)不公平值盡量小的原則，若 -（4.14）則增加的1席給A方，若 -（4.15）則增加的1席給B方由（4.14）式可得 ： 由（4.15）式可得 ： 記 ： 則增加的1席，應(yīng)給Q值大的一方 第一種情形，顯然也符合該原則，現(xiàn)在將

28、上述方法推廣到方分配席位的情況方人數(shù)為已占有席 計(jì)算 則將增加的1席分配應(yīng)給值最大的一方下面考慮原問(wèn)題：前19席的分配沒(méi)有爭(zhēng)議，甲系得10席，乙系得6席，丙系得3席第20席的分配 故第20席分配給甲系第21席的分配 故第21席分配給乙系甲、乙、丙三系各分得11，6，4席，這樣丙系保住它險(xiǎn)些喪失的1席。第五章 圖與網(wǎng)絡(luò)模型及方法1 概論 圖論起源于18世紀(jì)。第一篇圖論論文是瑞士數(shù)學(xué)家歐拉于1736 年發(fā)表的“哥尼斯堡的七座橋”。1847年，克?；舴?yàn)榱私o出電網(wǎng)絡(luò)方程而引進(jìn)了“樹(shù)”的概念。1857年，凱萊在計(jì)數(shù)烷的同分異構(gòu)物時(shí)，也發(fā)現(xiàn)了“樹(shù)”。哈密爾頓于1859年提出“周游世界”游戲，用圖論的術(shù)語(yǔ)

29、，就是如何找出一個(gè)連通圖中的生成圈，近幾十年來(lái)，由于計(jì)算機(jī)技術(shù)和科學(xué)的飛速發(fā)展，大大地促進(jìn)了圖論研究和應(yīng)用，圖論的理論和方法已經(jīng)滲透到物理、化學(xué)、通訊科學(xué)、建筑學(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èn)題就是一個(gè)典型的例子。在哥尼斯堡有七座橋?qū)⑵杖R格爾河中的兩個(gè)島及島與河岸聯(lián)結(jié)起來(lái)問(wèn)題是要從這

30、四塊陸地中的任何一塊開(kāi)始通過(guò)每一座橋正好一次，再回到起點(diǎn)。當(dāng)然可以通過(guò)試驗(yàn)去嘗試解決這個(gè)問(wèn)題，但該城居民的任何嘗試均未成功。歐拉為了解決這個(gè)問(wèn)題，采用了建立數(shù)學(xué)模型的方法。他將每一塊陸地用一個(gè)點(diǎn)來(lái)代替，將每一座橋用連接相應(yīng)兩點(diǎn)的一條線來(lái)代替，從而得到一個(gè)有四個(gè)“點(diǎn)”，七條“線”的“圖”。問(wèn)題成為從任一點(diǎn)出發(fā)一筆畫(huà)出七條線再回到起點(diǎn)。歐拉考察了一般一筆畫(huà)的結(jié)構(gòu)特點(diǎn)，給出了一筆畫(huà)的一個(gè)判定法則：這個(gè)圖是連通的，且每個(gè)點(diǎn)都與偶數(shù)線相關(guān)聯(lián)，將這個(gè)判定法則應(yīng)用于七橋問(wèn)題，得到了“不可能走通”的結(jié)果，不但徹底解決了這個(gè)問(wèn)題，而且開(kāi)創(chuàng)了圖論研究的先河。圖與網(wǎng)絡(luò)是運(yùn)籌學(xué)（Operations Research

31、）中的一個(gè)經(jīng)典和重要的分支，所研究的問(wèn)題涉及經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸、計(jì)算機(jī)科學(xué)與信息技術(shù)、通訊與網(wǎng)絡(luò)技術(shù)等諸多領(lǐng)域。下面將要討論的最短路問(wèn)題、最大流問(wèn)題、最小費(fèi)用流問(wèn)題和匹配問(wèn)題等都是圖與網(wǎng)絡(luò)的基本問(wèn)題。我們首先通過(guò)一些例子來(lái)了解網(wǎng)絡(luò)優(yōu)化問(wèn)題。例1 最短路問(wèn)題（SPPshortest path problem）一名貨柜車司機(jī)奉命在最短的時(shí)間內(nèi)將一車貨物從甲地運(yùn)往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯(cuò)，因此有多種行車路線，這名司機(jī)應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運(yùn)行速度是恒定的，那么這一問(wèn)題相當(dāng)于需要找到一條從甲地到乙地的最短路。例2 公路連接問(wèn)題某一地區(qū)有若干個(gè)主要城市，現(xiàn)準(zhǔn)備修建高速公路把這

32、些城市連接起來(lái)，使得從其中任何一個(gè)城市都可以經(jīng)高速公路直接或間接到達(dá)另一個(gè)城市。假定已經(jīng)知道了任意兩個(gè)城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最??？例3 指派問(wèn)題（assignment problem）一家公司經(jīng)理準(zhǔn)備安排名員工去完成項(xiàng)任務(wù)，每人一項(xiàng)。由于各員工的特點(diǎn)不同，不同的員工去完成同一項(xiàng)任務(wù)時(shí)所獲得的回報(bào)是不同的。如何分配工作方案可以使總回報(bào)最大？例4 中國(guó)郵遞員問(wèn)題（CPPchinese postman problem）一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件。如何為他（她）設(shè)計(jì)一條最短的投遞路線（從郵局出發(fā)，經(jīng)過(guò)投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）

33、？由于這一問(wèn)題是我國(guó)管梅谷教授1960年首先提出的，所以國(guó)際上稱之為中國(guó)郵遞員問(wèn)題。例5 旅行商問(wèn)題（TSPtraveling salesman problem）一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他（她）設(shè)計(jì)一條最短的旅行路線（從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市恰好一次，最后返回駐地）？這一問(wèn)題的研究歷史十分悠久，通常稱之為旅行商問(wèn)題。例6 運(yùn)輸問(wèn)題（transportation problem）某種原材料有個(gè)產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運(yùn)往個(gè)使用這些原材料的工廠。假定個(gè)產(chǎn)地的產(chǎn)量和家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運(yùn)費(fèi)已知，那么如何安排運(yùn)輸方案可以使總運(yùn)輸成本最低？上述問(wèn)題有兩

34、個(gè)共同的特點(diǎn)：一是它們的目的都是從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學(xué)上把這種問(wèn)題稱為最優(yōu)化或優(yōu)化（optimization）問(wèn)題；二是它們都易于用圖形的形式直觀地描述和表達(dá)，數(shù)學(xué)上把這種與圖相關(guān)的結(jié)構(gòu)稱為網(wǎng)絡(luò)（network）。與圖和網(wǎng)絡(luò)相關(guān)的最優(yōu)化問(wèn)題就是網(wǎng)絡(luò)最優(yōu)化或稱網(wǎng)絡(luò)優(yōu)化 （netwok optimization）問(wèn)題。所以上面例子中介紹的問(wèn)題都是網(wǎng)絡(luò)優(yōu)化問(wèn)題。由于多數(shù)網(wǎng)絡(luò)優(yōu)化問(wèn)題是以網(wǎng)絡(luò)上的流（flow）為研究的對(duì)象，因此網(wǎng)絡(luò)優(yōu)化又常常被稱為網(wǎng)絡(luò)流（network flows）或網(wǎng)絡(luò)流規(guī)劃等。下面首先簡(jiǎn)要介紹圖與網(wǎng)絡(luò)的一些基本概念。2 圖與網(wǎng)絡(luò)的基本概念2.1

35、 無(wú)向圖一個(gè)無(wú)向圖(undirected graph)是由一個(gè)非空有限集合和中某些元素的無(wú)序?qū)蠘?gòu)成的二元組，記為。其中稱為圖的頂點(diǎn)集（vertex set）或節(jié)點(diǎn)集（node set）， 中的每一個(gè)元素稱為該圖的一個(gè)頂點(diǎn)（vertex）或節(jié)點(diǎn)（node）；稱為圖的邊集（edge set），中的每一個(gè)元素(即中某兩個(gè)元素的無(wú)序?qū)?記為或 ，被稱為該圖的一條從到的邊（edge）。當(dāng)邊時(shí)，稱為邊的端點(diǎn)，并稱與相鄰（adjacent）；邊稱為與頂點(diǎn)關(guān)聯(lián)（incident）。如果某兩條邊至少有一個(gè)公共端點(diǎn)，則稱這兩條邊在圖中相鄰。邊上賦權(quán)的無(wú)向圖稱為賦權(quán)無(wú)向圖或無(wú)向網(wǎng)絡(luò)（undirected net

36、work）。我們對(duì)圖和網(wǎng)絡(luò)不作嚴(yán)格區(qū)分，因?yàn)槿魏螆D總是可以賦權(quán)的。一個(gè)圖稱為有限圖，如果它的頂點(diǎn)集和邊集都有限。圖的頂點(diǎn)數(shù)用符號(hào)或表示，邊數(shù)用或表示。當(dāng)討論的圖只有一個(gè)時(shí)，總是用來(lái)表示這個(gè)圖。從而在圖論符號(hào)中我們常略去字母，例如，分別用和代替和。端點(diǎn)重合為一點(diǎn)的邊稱為環(huán)(loop)。一個(gè)圖稱為簡(jiǎn)單圖(simple graph)，如果它既沒(méi)有環(huán)也沒(méi)有兩條邊連接同一對(duì)頂點(diǎn)。2.2 有向圖定義 一個(gè)有向圖（directed graph或 digraph）是由一個(gè)非空有限集合和中某些元素的有序?qū)蠘?gòu)成的二元組，記為。其中稱為圖的頂點(diǎn)集或節(jié)點(diǎn)集， 中的每一個(gè)元素稱為該圖的一個(gè)頂點(diǎn)或節(jié)點(diǎn)；稱為圖的弧集（

37、arc set），中的每一個(gè)元素(即中某兩個(gè)元素的有序?qū)?記為或，被稱為該圖的一條從到的弧（arc）。當(dāng)弧時(shí)，稱為的尾（tail），為的頭（head），并稱弧為的出?。╫utgoing arc），為的入?。╥ncoming arc）。對(duì)應(yīng)于每個(gè)有向圖，可以在相同頂點(diǎn)集上作一個(gè)圖，使得對(duì)于的每條弧，有一條有相同端點(diǎn)的邊與之相對(duì)應(yīng)。這個(gè)圖稱為的基礎(chǔ)圖。反之，給定任意圖，對(duì)于它的每個(gè)邊，給其端點(diǎn)指定一個(gè)順序，從而確定一條弧，由此得到一個(gè)有向圖，這樣的有向圖稱為的一個(gè)定向圖。以下若未指明“有向圖”三字，“圖”字皆指無(wú)向圖。2.3 完全圖、二分圖每一對(duì)不同的頂點(diǎn)都有一條邊相連的簡(jiǎn)單圖稱為完全圖(comp

38、lete graph)。個(gè)頂點(diǎn)的完全圖記為。若，（這里表示集合中的元素個(gè)數(shù)），中無(wú)相鄰頂點(diǎn)對(duì)，中亦然，則稱為二分圖(bipartite graph)；特別地，若，則，則稱為完全二分圖，記成。 2.4 子圖圖叫做圖的子圖（subgraph），記作，如果，。若是的子圖，則稱為的母圖。的支撐子圖（spanning subgraph，又成生成子圖）是指滿足的子圖。2.5 頂點(diǎn)的度設(shè)，中與關(guān)聯(lián)的邊數(shù)（每個(gè)環(huán)算作兩條邊）稱為的度(degree)，記作。若是奇數(shù)，稱是奇頂點(diǎn)(odd point)；是偶數(shù)，稱是偶頂點(diǎn)(even point)。關(guān)于頂點(diǎn)的度，我們有如下結(jié)果：(i) (ii) 任意一個(gè)圖的奇頂點(diǎn)的

39、個(gè)數(shù)是偶數(shù)。2.6 圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)網(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)矩陣表示法、弧表表示法、鄰接表表示法和星形表示法。在下面數(shù)據(jù)結(jié)構(gòu)的討論中，我們首先假設(shè)是一個(gè)簡(jiǎn)單有向圖，并假設(shè)中的頂點(diǎn)用自然數(shù)表示或編號(hào)，中的弧用自然數(shù)表示或編號(hào)。對(duì)于有多重邊或無(wú)向網(wǎng)絡(luò)的情況，我們只是在討論完簡(jiǎn)單有向圖的表示方法之后，給出一些說(shuō)明。（i）鄰接矩陣表示法鄰

40、接矩陣表示法是將圖以鄰接矩陣（adjacency matrix）的形式存儲(chǔ)在計(jì)算機(jī)中。圖的鄰接矩陣是如下定義的：是一個(gè)的矩陣，即 ， 也就是說(shuō)，如果兩節(jié)點(diǎn)之間有一條弧，則鄰接矩陣中對(duì)應(yīng)的元素為1；否則為0?？梢钥闯?，這種表示法非常簡(jiǎn)單、直接。但是，在鄰接矩陣的所有個(gè)元素中，只有個(gè)為非零元。如果網(wǎng)絡(luò)比較稀疏，這種表示法浪費(fèi)大量的存儲(chǔ)空間，從而增加了在網(wǎng)絡(luò)中查找弧的時(shí)間。例7 對(duì)于右圖所示的圖，可以用鄰接矩陣表示為同樣，對(duì)于網(wǎng)絡(luò)中的權(quán)，也可以用類似鄰接矩陣的矩陣表示。只是此時(shí)一條弧所對(duì)應(yīng)的元素不再是1，而是相應(yīng)的權(quán)而已。如果網(wǎng)絡(luò)中每條弧賦有多種權(quán)，則可以用多個(gè)矩陣表示這些權(quán)。（ii）關(guān)聯(lián)矩陣表示法

41、關(guān)聯(lián)矩陣表示法是將圖以關(guān)聯(lián)矩陣（incidence matrix）的形式存儲(chǔ)在計(jì)算機(jī)中圖的關(guān)聯(lián)矩陣是如下定義的：是一個(gè)的矩陣，即 ， 也就是說(shuō)，在關(guān)聯(lián)矩陣中，每行對(duì)應(yīng)于圖的一個(gè)節(jié)點(diǎn)，每列對(duì)應(yīng)于圖的一條弧。如果一個(gè)節(jié)點(diǎn)是一條弧的起點(diǎn)，則關(guān)聯(lián)矩陣中對(duì)應(yīng)的元素為1；如果一個(gè)節(jié)點(diǎn)是一條弧的終點(diǎn)，則關(guān)聯(lián)矩陣中對(duì)應(yīng)的元素為；如果一個(gè)節(jié)點(diǎn)與一條弧不關(guān)聯(lián)，則關(guān)聯(lián)矩陣中對(duì)應(yīng)的元素為0。對(duì)于簡(jiǎn)單圖，關(guān)聯(lián)矩陣每列只含有兩個(gè)非零元（一個(gè)，一個(gè)）?？梢钥闯?，這種表示法也非常簡(jiǎn)單、直接。但是，在關(guān)聯(lián)矩陣的所有個(gè)元素中，只有個(gè)為非零元。如果網(wǎng)絡(luò)比較稀疏，這種表示法也會(huì)浪費(fèi)大量的存儲(chǔ)空間。但由于關(guān)聯(lián)矩陣有許多特別重要的理論性

42、質(zhì)，因此它在網(wǎng)絡(luò)優(yōu)化中是非常重要的概念。例8 對(duì)于例7所示的圖，如果關(guān)聯(lián)矩陣中每列對(duì)應(yīng)弧的順序?yàn)?1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，則關(guān)聯(lián)矩陣表示為同樣，對(duì)于網(wǎng)絡(luò)中的權(quán)，也可以通過(guò)對(duì)關(guān)聯(lián)矩陣的擴(kuò)展來(lái)表示。例如，如果網(wǎng)絡(luò)中每條弧有一個(gè)權(quán)，我們可以把關(guān)聯(lián)矩陣增加一行，把每一條弧所對(duì)應(yīng)的權(quán)存儲(chǔ)在增加的行中。如果網(wǎng)絡(luò)中每條弧賦有多個(gè)權(quán)，我們可以把關(guān)聯(lián)矩陣增加相應(yīng)的行數(shù)，把每一條弧所對(duì)應(yīng)的權(quán)存儲(chǔ)在增加的行中。（iii）弧表示法弧表表示法將圖以弧表（arc list）的形式存儲(chǔ)在計(jì)算機(jī)中。所謂圖的弧表，也就是圖的弧集合中的所有有序?qū)?。弧表表示法?/p>

43、接列出所有弧的起點(diǎn)和終點(diǎn)，共需個(gè)存儲(chǔ)單元，因此當(dāng)網(wǎng)絡(luò)比較稀疏時(shí)比較方便。此外，對(duì)于網(wǎng)絡(luò)圖中每條弧上的權(quán)，也要對(duì)應(yīng)地用額外的存儲(chǔ)單元表示。例如，例7所示的圖，假設(shè)弧(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)上的權(quán)分別為8，9，6，4，0，3，6和7，則弧表表示如下：起點(diǎn)11234455終點(diǎn)23423534權(quán)89640367為了便于檢索，一般按照起點(diǎn)、終點(diǎn)的字典序順序存儲(chǔ)弧表，如上面的弧表就是按照這樣的順序存儲(chǔ)的。（iv）鄰接表表示法鄰接表表示法將圖以鄰接表（adjacency lists）的形式存儲(chǔ)在計(jì)算機(jī)中。所謂圖的鄰接表，也就是圖的所有節(jié)點(diǎn)

44、的鄰接表的集合；而對(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ù)組表示。例如，例7所示的圖，鄰接表表示為這是一個(gè)5維指針數(shù)組，每一維（上面表示法中的每一行）對(duì)應(yīng)于一個(gè)節(jié)點(diǎn)的鄰接表，如第1行對(duì)應(yīng)于第1個(gè)節(jié)點(diǎn)的鄰接表（即第1個(gè)節(jié)點(diǎn)的所有出弧）。每個(gè)指針單元的第1個(gè)數(shù)據(jù)域表示弧的另一個(gè)端點(diǎn)（弧的頭），后面的數(shù)據(jù)域表示對(duì)應(yīng)弧上的權(quán)。如第1行中的“2”表示弧的另一個(gè)端點(diǎn)為2（即弧為（1,2），

45、“8”表示對(duì)應(yīng)弧(1,2)上的權(quán)為8；“3”表示弧的另一個(gè)端點(diǎn)為3（即弧為(1,3)），“9”表示對(duì)應(yīng)?。?，3）上的權(quán)為9。又如，第5行說(shuō)明節(jié)點(diǎn)5出發(fā)的弧有(5,3)、(5,4)，他們對(duì)應(yīng)的權(quán)分別為6和7。對(duì)于有向圖，一般用表示節(jié)點(diǎn)的鄰接表，即節(jié)點(diǎn)的所有出弧構(gòu)成的集合或鏈表（實(shí)際上只需要列出弧的另一個(gè)端點(diǎn)，即弧的頭）。例如上面例子，等。這種記法我們?cè)诒緯?shū)后面將會(huì)經(jīng)常用到。（v）星形表示法星形（star）表示法的思想與鄰接表表示法的思想有一定的相似之處。對(duì)每個(gè)節(jié)點(diǎn)，它也是記錄從該節(jié)點(diǎn)出發(fā)的所有弧，但它不是采用單向鏈表而是采用一個(gè)單一的數(shù)組表示。也就是說(shuō)，在該數(shù)組中首先存放從節(jié)點(diǎn)1出發(fā)的所有弧，

46、然后接著存放從節(jié)點(diǎn)2出發(fā)的所有孤，依此類推，最后存放從節(jié)點(diǎn)出發(fā)的所有孤。對(duì)每條弧，要依次存放其起點(diǎn)、終點(diǎn)、權(quán)的數(shù)值等有關(guān)信息。這實(shí)際上相當(dāng)于對(duì)所有弧給出了一個(gè)順序和編號(hào)，只是從同一節(jié)點(diǎn)出發(fā)的弧的順序可以任意排列。此外，為了能夠快速檢索從每個(gè)節(jié)點(diǎn)出發(fā)的所有弧，我們一般還用一個(gè)數(shù)組記錄每個(gè)節(jié)點(diǎn)出發(fā)的弧的起始地址（即弧的編號(hào)）。在這種表示法中，可以快速檢索從每個(gè)節(jié)點(diǎn)出發(fā)的所有弧，這種星形表示法稱為前向星形（forward star）表示法。例如，在例7所示的圖中，仍然假設(shè)?。?,2），（l,3），（2,4），（3,2），（4,3），（4,5），（5,3）和（5,4）上的權(quán)分別為8，9，6，4，0，3

47、，6和7。此時(shí)該網(wǎng)絡(luò)圖可以用前向星形表示法表示如下： 節(jié)點(diǎn)對(duì)應(yīng)的出弧的起始地址編號(hào)數(shù)組（記為）節(jié)點(diǎn)號(hào)123456起始地址134679記錄弧信息的數(shù)組弧編號(hào)12345678起點(diǎn)11234455終點(diǎn)23423534權(quán)89640367在數(shù)組中，其元素個(gè)數(shù)比圖的節(jié)點(diǎn)數(shù)多1（即），且一定有，。對(duì)于節(jié)點(diǎn)，其對(duì)應(yīng)的出弧存放在弧信息數(shù)組的位置區(qū)間為，如果，則節(jié)點(diǎn)沒(méi)有出弧。這種表示法與弧表表示法也非常相似，“記錄弧信息的數(shù)組”實(shí)際上相當(dāng)于有序存放的“弧表”。只是在前向星形表示法中，弧被編號(hào)后有序存放，并增加一個(gè)數(shù)組（）記錄每個(gè)節(jié)點(diǎn)出發(fā)的弧的起始編號(hào)。前向星形表示法有利于快速檢索每個(gè)節(jié)點(diǎn)的所有出弧，但不能快速檢索每個(gè)節(jié)點(diǎn)的所有入弧。為了能夠快速檢索每個(gè)節(jié)點(diǎn)的所有入孤，可以采用反向星形（reverse star）表示法：首先存放進(jìn)入節(jié)點(diǎn)1的所有孤，然后接著存放進(jìn)入節(jié)點(diǎn)2的所有弧，依此類推，最后存放進(jìn)入節(jié)點(diǎn)的所有孤。對(duì)每條弧，仍然依次存放其起點(diǎn)、終點(diǎn)、權(quán)的數(shù)值等有關(guān)信息。同樣，為了能夠快速檢索從每個(gè)節(jié)點(diǎn)的所有入弧，我們一般還用一個(gè)數(shù)組記錄每個(gè)節(jié)點(diǎn)的入孤的起始地址（即弧的編號(hào)）。例如，例7所示的圖，可以用反向星形