數(shù)學建模-圖論

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

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

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

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

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

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

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

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

9、條連線（三人互不相識）即可，第二節(jié) 狀態(tài)轉移問題本節(jié)介紹兩種狀態(tài)轉移問題，解決這種問題的方法,有狀態(tài)轉移法，圖解法及用圖的鄰接距陣等。21 人、狗、雞、米問題人、狗、雞、米均要過河，船上除1人劃船外，最多還能運載一物，而人不在場時，狗要吃雞，雞要吃米，問人，狗、雞、米應如和過河？分析：假設人、狗、雞、米要從河的南岸到河的北岸，由題意，在過河的過程中，兩岸的狀態(tài)要滿足一定條件，所以該問題為有條件的狀態(tài)轉移問題。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個允許狀態(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個可取狀態(tài)向量組成的集合記為S，稱S為允許狀態(tài)集合 2、狀態(tài)轉移方程 對于一次過河，可以看成一次狀態(tài)轉移，我們用向量來表示決策，例（1，0，0，1）表示人，米過河。令D為允許決策集合， D= (1, x, y, z) : x+y+z=0 或 1

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

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

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

14、圖23，標出10種允許狀態(tài)，找出從經(jīng)由允許狀態(tài)到原點的路徑，該路徑還要滿足奇數(shù)次向左，向下；偶數(shù)次向右, 向上. 圖2-3 由圖23可得這樣的過河策略，共分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、在商人過河中若有4名商人，各帶一隨從能否過河？2、夫妻過河問題：有3對夫妻過河，船最多能載2人，條件是任一女子不能在其丈夫不在的情況下與其他男子在一起，如何安排三對夫妻過河？若船最多能載3人，5對夫妻能否過河？3、量綱分析法量

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29、，就是如何找出一個連通圖中的生成圈，近幾十年來，由于計算機技術和科學的飛速發(fā)展，大大地促進了圖論研究和應用，圖論的理論和方法已經(jīng)滲透到物理、化學、通訊科學、建筑學、生物遺傳學、心理學、經(jīng)濟學、社會學等學科中。圖論中所謂的“圖”是指某類具體事物和這些事物之間的聯(lián)系。如果我們用點表示這些具體事物，用連接兩點的線段（直的或曲的）表示兩個事物的特定的聯(lián)系，就得到了描述這個“圖”的幾何形象。圖論為任何一個包含了一種二元關系的離散系統(tǒng)提供了一個數(shù)學模型，借助于圖論的概念、理論和方法，可以對該模型求解。哥尼斯堡七橋問題就是一個典型的例子。在哥尼斯堡有七座橋將普萊格爾河中的兩個島及島與河岸聯(lián)結起來問題是要從這

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

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

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

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

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

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

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

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

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

39、個數(shù)是偶數(shù)。2.6 圖與網(wǎng)絡的數(shù)據(jù)結構網(wǎng)絡優(yōu)化研究的是網(wǎng)絡上的各種優(yōu)化模型與算法為了在計算機上實現(xiàn)網(wǎng)絡優(yōu)化的算法，首先我們必須有一種方法（即數(shù)據(jù)結構）在計算機上來描述圖與網(wǎng)絡。一般來說，算法的好壞與網(wǎng)絡的具體表示方法，以及中間結果的操作方案是有關系的。這里我們介紹計算機上用來描述圖與網(wǎng)絡的5種常用表示方法：鄰接矩陣表示法、關聯(lián)矩陣表示法、弧表表示法、鄰接表表示法和星形表示法。在下面數(shù)據(jù)結構的討論中，我們首先假設是一個簡單有向圖，并假設中的頂點用自然數(shù)表示或編號，中的弧用自然數(shù)表示或編號。對于有多重邊或無向網(wǎng)絡的情況，我們只是在討論完簡單有向圖的表示方法之后，給出一些說明。（i）鄰接矩陣表示法鄰

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

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

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

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

44、的鄰接表的集合；而對每個節(jié)點，它的鄰接表就是它的所有出弧。鄰接表表示法就是對圖的每個節(jié)點，用一個單向鏈表列出從該節(jié)點出發(fā)的所有弧，鏈表中每個單元對應于一條出弧。為了記錄弧上的權，鏈表中每個單元除列出弧的另一個端點外，還可以包含弧上的權等作為數(shù)據(jù)域。圖的整個鄰接表可以用一個指針數(shù)組表示。例如，例7所示的圖，鄰接表表示為這是一個5維指針數(shù)組，每一維（上面表示法中的每一行）對應于一個節(jié)點的鄰接表，如第1行對應于第1個節(jié)點的鄰接表（即第1個節(jié)點的所有出?。Ｃ總€指針單元的第1個數(shù)據(jù)域表示弧的另一個端點（弧的頭），后面的數(shù)據(jù)域表示對應弧上的權。如第1行中的“2”表示弧的另一個端點為2（即弧為（1,2），

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

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

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