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

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

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

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

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

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

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

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

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

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

11、 另外，我們注意到過河有兩種，奇數(shù)次的為從南岸到北岸，而偶數(shù)次的為北岸回到南岸，因此得到下述轉(zhuǎn)移方程， -(2.1)表示第k次狀態(tài)， 為決策向量. 圖2-12. 人、狗、雞、米過河問題，即要找到， 且滿足（2.1）式。下面用狀態(tài)轉(zhuǎn)移圖求解將10個允許狀態(tài)用10個點表示，并且僅當(dāng)某個允許狀態(tài)經(jīng)過一個允許決策仍為允許狀態(tài)，則這兩個允許狀態(tài)間存在連線，而構(gòu)成一個圖, 如圖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的邊集。 設(shè)G中有n個頂點; 為G的鄰接距陣，其中 定理1：設(shè)為圖的鄰接距陣，則中從頂點到頂點，長度為的道路的條數(shù)為中的行列元素.證： 對用數(shù)學(xué)歸納法 時，顯然結(jié)論成立; 假設(shè)時，定理成立， 考慮 的情形. 記的行列元素為 , 因為 , 所以 (2.2)而從 到 長的道路無非是從經(jīng)步到某頂,再從 走一步到；由歸納假設(shè)從到長為的道路共計條，而從到長為1的道路為條，所以長為的從經(jīng)步到再一步

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

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

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

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

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

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

20、我們通過一個例子,介紹如何使用無量綱化方法簡化模型。拋射問題：在某星球表面以初速度豎直向上發(fā)射火箭，記星球半徑為，星球表面重力加速度為，忽略阻力，討論發(fā)射高度隨時間T的變化規(guī)律.模型建立：設(shè)軸豎直向上， 時 ，火箭和星球質(zhì)量分別記為和，由牛頓第二定律和萬有引力定律可得: -（3.17）以 代入（3.17）可得 故得如下初值問題 -（3.18）(3.18)式的解可以表為 也即發(fā)射高度是以 為參數(shù)的的函數(shù),下面我們采用無量綱化方法化簡方程（3.18）, 顯然拋射問題中的基本量綱為 而 所謂無量綱化是指，對(3.18)式中的和分別構(gòu)造且有相同的參數(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)式恰為假定火箭運動過程中所受星球引力 不變的運動方程。小結(jié)：無量綱化是用數(shù)學(xué)工具研究物理問題時常用的方法，恰當(dāng)?shù)剡x擇特征尺度不僅可以減少參數(shù)的個數(shù)，而且可以幫助人們決定舍棄哪些次要因素第四節(jié) 比例與函數(shù)建模 本節(jié)介紹的幾個模型,都是利用基本的比例關(guān)系與函數(shù)建立起的數(shù)學(xué)模型。4.1 動物體型問題 問題： 某生豬收購站，需要研究如何根據(jù)生豬的體長（不包括頭尾）估計其體重？模型假設(shè)：1 將四足動物的軀干（不含頭尾）視為質(zhì)量為m的圓柱體，長度為，截面面積，直徑為d如圖4-1 圖4-12 把圓柱體的軀干看作一根支撐在四肢上的彈性梁，動物在體重f作用下的最大下垂為

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

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

25、中，再通過空氣傳導(dǎo)，再通過厚度為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）若取 ， 則 又此可見雙層玻璃的保暖效果是相當(dāng)可觀的。我國北方寒冷地區(qū)的建筑物，通常采用雙層玻璃；由（4.13）式 h=4時, , h再大，熱量傳遞的減少就不明顯了，再考慮到墻體的厚度；所以建筑規(guī)范通常

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

43、接列出所有弧的起點和終點，共需個存儲單元，因此當(dāng)網(wǎng)絡(luò)比較稀疏時比較方便。此外，對于網(wǎng)絡(luò)圖中每條弧上的權(quán)，也要對應(yīng)地用額外的存儲單元表示。例如，例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，則弧表表示如下：起點11234455終點23423534權(quán)89640367為了便于檢索，一般按照起點、終點的字典序順序存儲弧表，如上面的弧表就是按照這樣的順序存儲的。（iv）鄰接表表示法鄰接表表示法將圖以鄰接表（adjacency lists）的形式存儲在計算機(jī)中。所謂圖的鄰接表，也就是圖的所有節(jié)點

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

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

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