數(shù)學(xué)建模第九章

1、第九章                   圖論方法建模§9.1  圖論課程簡介一 基本概念1.         哥尼斯堡七橋問題：居民從某處出發(fā)，試圖發(fā)現(xiàn)這樣的路線，經(jīng)過所有的橋，且對每一座橋只經(jīng)過一次，并最終回到原處。 有人請教了當(dāng)時的大數(shù)學(xué)家歐拉，歐拉將之轉(zhuǎn)化為如

2、下的一副“圖”，僅包含“點”、“線”的一類拓?fù)浣Y(jié)構(gòu)：   1.         圖：稱由若干個點  以及以這些點為端點的若干條邊  形成的一種拓?fù)浣Y(jié)構(gòu)為圖。記之為，其中為頂點集，為邊集，為邊集到“頂點集與頂點集自身的笛卡兒積集”上的一個映射，稱之為關(guān)聯(lián)關(guān)系。簡記為 邊與頂點的關(guān)系有如下幾種典型情況： 2.         簡單圖

3、：無自回環(huán)，無重邊的圖。無向圖：邊沒有指向，.此時稱邊與頂點、關(guān)聯(lián)，稱頂點與頂點鄰接。       有向圖：邊有指向，頂點的度：與一個頂點關(guān)聯(lián)的邊的個數(shù)；若是有向圖，則分為頂點的出度和入度。 （以上，左圖為一無向圖，右圖為一有向圖，它們均為簡單圖；七橋問題對應(yīng)的圖為一無向圖，但由于存在重邊，故不是簡單圖） 3.         圖的關(guān)聯(lián)矩陣，若為無向圖，；若為有向圖， 4.   

4、;     圖的鄰接矩陣，若為無向圖，； 若為有向圖，。 例如、，分別為下圖的關(guān)聯(lián)矩陣和鄰接矩陣。l                  無向圖的鄰接矩陣為一對稱矩陣。 5.         歐拉回路與歐拉定理：l    

5、              歐拉回路：若存在序列滿足：，對，均有，且對不同的數(shù)對應(yīng)圖中的邊不同；，則稱圖存在歐拉回路，稱序列為圖的歐拉回路。l                  歐拉定理：無向圖存在歐拉回路圖是一頂點的度均為偶數(shù)的連通圖。l   &#

6、160;             邊遍歷問題；“歐拉回路”與“中國郵遞員問題”。 二        幾個簡單的應(yīng)用例子問題一：消防設(shè)施的設(shè)置       若干條街道構(gòu)成一個居民小區(qū)，居民樓分布在街道兩側(cè)，現(xiàn)計劃在某些路口安置消防設(shè)施，使得每一街道的居民在必要時都可在該街道的某一路口得到設(shè)施利用。問題：如何利用

7、盡可能少的設(shè)施達(dá)到以上目標(biāo)？ 問題二：監(jiān)獄看守的設(shè)置       一座監(jiān)獄的幾間牢室有通道相連，監(jiān)獄的看守要設(shè)在通過道路能直接監(jiān)視到所有牢室的地方。問題，如何設(shè)置盡可能少的哨崗達(dá)到以上目標(biāo)？§9.2  循環(huán)比賽的排名問題問題： 支球隊參加循環(huán)比賽，兩兩交鋒，一場決勝，不容平局，“0、1”打分。如何排名？ 1            競賽圖：每對頂點之

8、間有且只有一條有向邊相連的有向圖；有向邊指向負(fù)方。 2            路徑與完全路徑：稱有向圖的一個頂點序列為圖的一條步長為的路徑，若滿足：對，均有；若還滿足，則稱之為圖的一條步長為的回（或閉）路徑。而若頂點集的一個全排列構(gòu)成圖的一條路徑，也稱之為圖的一條完全路徑。l                &

9、#160; 圖1中：、l                  子路徑、閉的完全路徑  3            定理：任一階競賽圖都存在完全路徑。證明（數(shù)學(xué)歸納法）：時，如圖3-0，命題真； ：設(shè)時命題真；：當(dāng)時，設(shè)為頂點集，記，為圖關(guān)于的生成子圖；由歸納假設(shè)，

10、在中存在完全路徑，不失一般性，設(shè)為中的一條完全路徑，考慮頂點與的鄰接關(guān)系，有如下三種情形： 圖3-1：為中的一條完全路徑；圖3-2：為中的一條完全路徑 圖3-3：為中的一條完全路徑。 4            定理：存在唯一完全路徑的階競賽圖在同構(gòu)的意義下唯一。進(jìn)一步講，若設(shè)為中的唯一的一條完全路徑，則。證明（數(shù)學(xué)歸納法）：時，如圖3-1，命題真；：設(shè)時命題真；：當(dāng)時，設(shè)為頂點集，不妨設(shè)為中的唯一的一條完全路徑；記，為圖關(guān)于的生成子圖；此時為中的

11、唯一的一條完全路徑，否則，由（3.定理）的論證可得不同于的中的另一條完全路徑，這與題設(shè)矛盾；以下只須證明負(fù)于任意：（反證）設(shè)勝某 ，如下圖，可以找到一條不同于的中的另一條完全路徑，這同樣與題設(shè)矛盾。 l                  這一性質(zhì)表明，利用完全路徑法進(jìn)行競賽圖排名是不可行（完善）的。  5      &

12、#160;     簡單積分法：簡單積分法與完全路徑法排名在完全路徑唯一的情形下二者是一致的。以下試圖通過低階的競賽圖說明簡單積分法的缺陷：  l                  在以上組圖的每一幅圖的下方所標(biāo)示向量既表示該圖各頂點的簡單積分，同時，對于3、4階競賽圖，在同構(gòu)的意義下可以作為該類圖的標(biāo)識。我們通過簡單分析發(fā)現(xiàn)圖 按照簡單

13、積分的方法對各頂點排序是不合適的：假設(shè)不然（即簡單積分是適用的），、，同時；這時看，按照簡單積分法二者均只得1分，但其份量不同，所得1分為其勝，按照簡單積分法，為一弱隊；但所得1分為其勝，按照簡單積分法，為一強隊因此，通常認(rèn)為強于。類似分析，可以得出強于。l                  盡管在以上組圖中，除了圖外，我們看不出簡單積分法的缺陷，但隨著競賽圖階數(shù)的增加，簡單積分的局限將尤為凸顯。 

14、0;6            雙向連通圖：稱有向圖為雙向連通的，若對任意兩個不同頂點，在該有向圖中既有從頂點到頂點的有向路徑，也有從頂點到頂點的有向路徑。7            雙向連通圖的鄰接矩陣為素陣：即存在整數(shù)，使得。8           

15、 Perron-Frobenius定理：素陣的最大特征根為正單根，對應(yīng)正特征向量，且有（為所有分量均為1的維向量，也可以被表示為）。 l                  對以上定理的理解可以參見層次分析法一章中對正互反矩陣性質(zhì)的討論。  9           

16、60;對于雙向連通的競賽圖，可以計算其鄰接矩陣的最大特征根以及相應(yīng)的正特征向量，按照該特征向量分量的數(shù)值大小對各個頂點（參賽隊）排名。        下面是一個雙向連通的四階競賽圖，通過前面的討論，該算例不論完全路徑法還是簡單積分法均不適宜，我們分別采用與對之進(jìn)行分析考察不難發(fā)現(xiàn)，的分量表示以相應(yīng)頂點為起點產(chǎn)生的步長為的路徑數(shù)，而的分量則表示以相應(yīng)頂點為起點產(chǎn)生的步長不超過的路徑數(shù)。如下圖，從不同頂點（作為最底層）出發(fā)，只要存在以該頂點為起點的有向邊，則向上生長出枝杈，將響應(yīng)邊的終點畫在第二層，在以第二層上的點為基

17、點向第三層生長，如此直到無窮，將最終得到四棵“參天大樹”，直觀上，的分量為表示相應(yīng)頂點生長出的“樹”介于第層與第層之間的枝杈數(shù)，而的分量為表示相應(yīng)頂點生長出的“樹”在第層下方部分的枝杈數(shù)。顯然，一個“有實力的頂點（參賽隊）”對應(yīng)的“樹”應(yīng)當(dāng)更為粗壯。         按照Perron-Frobenius定理，只要足夠大，可以將作為實力向量來對各個頂點排序，通過具體計算，事實上反映出完全相同的結(jié)果這正是Perron-Frobenius定理在競賽圖排名中的應(yīng)用。 10  

18、0;     從直觀上講，以作為一個實力向量用于競賽圖排名將更為適宜，當(dāng)然我們在這里愿意強調(diào)具有如下的優(yōu)點：l                  它并不只局限于雙向連通的競賽圖；l                

19、;  從對競賽圖的分析看，計算需要一直計算到，之后從排名的角度講，的值才算穩(wěn)定下來；而的計算在時就具備如上提及的特點。l                  你能從中發(fā)掘有關(guān)值更多的優(yōu)點嗎？嘗試著準(zhǔn)確表述你的發(fā)現(xiàn)或猜想，能從理論上加以論證嗎？§9.3   紅綠燈調(diào)節(jié)問題：圖1所示的十字路口共有六條車道，其中是4條直道，是2條左轉(zhuǎn)彎道，每條車道設(shè)有紅綠燈，制定其

20、調(diào)節(jié)方案。 1            相容圖與區(qū)間圖相容圖：用圖中的頂點表示交通流，當(dāng)兩條交通流相容時將代表交通流的兩頂點連接而得到的圖。 區(qū)間圖：稱圖G=（V，E）為區(qū)間圖，若存在從頂點到區(qū)間的對應(yīng)關(guān)系，使得對于任意的，有。 2            可行調(diào)節(jié)：通過刪除（非）區(qū)間圖某些邊，構(gòu)造一個區(qū)間圖子圖。 3&#

21、160;           有效性調(diào)節(jié)：對于給定的子圖所對應(yīng)的交通流，設(shè)計有效的紅綠燈調(diào)節(jié)程序（比方使在一個紅綠燈調(diào)節(jié)周期中總的綠燈時間最長），盡可能利于路口的車輛通行。 4            在要求滿足條件1）一個紅綠燈調(diào)節(jié)周期=60秒；2） 四個時段；3） 六個車流流量；4）每一車流連續(xù)通行時間不少于10秒，可得如下線性規(guī)劃模型：1l                  滿足約束條件的任一均為其解；  5 &#