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

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

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

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

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

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

6、160;             邊遍歷問題；“歐拉回路”與“中國(guó)郵遞員問題”。 二        幾個(gè)簡(jiǎn)單的應(yīng)用例子問題一：消防設(shè)施的設(shè)置       若干條街道構(gòu)成一個(gè)居民小區(qū)，居民樓分布在街道兩側(cè)，現(xiàn)計(jì)劃在某些路口安置消防設(shè)施，使得每一街道的居民在必要時(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)比賽的排名問題問題： 支球隊(duì)參加循環(huán)比賽，兩兩交鋒，一場(chǎng)決勝，不容平局，“0、1”打分。如何排名？ 1            競(jìng)賽圖：每對(duì)頂點(diǎn)之

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

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

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

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

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

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

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

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

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

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

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

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

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

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