數(shù)學(xué)建模圖論方法專題圖論概述圖論(GraphTheory)是運(yùn)籌學(xué)中的一個(gè)重要分支，主要研究具有某種二元關(guān)系的離散系統(tǒng)的組合結(jié)構(gòu)和性質(zhì)。圖論應(yīng)用十分廣泛，如，物理學(xué)、化學(xué)、控制論、信息論、管理科學(xué)、通信系統(tǒng)、交通運(yùn)輸系統(tǒng)計(jì)算機(jī)科學(xué)、生產(chǎn)工藝流程以及軍事后勤保障系統(tǒng)等的問題常用圖論模型來描述。圖論中的“圖”并不是通常意義下的幾何圖形或物體的形狀圖，而是以一種抽象的形式來表達(dá)一些確定的事物及其關(guān)系的一個(gè)數(shù)學(xué)系統(tǒng)。圖論概述

圖論最早處理的問題是哥尼斯堡城的七橋問題：18世紀(jì)在哥尼斯堡城（今俄羅斯加里寧格勒）有一條名叫普萊格爾（Pregel）的河流橫經(jīng)其中，河上有7座橋，將河中的兩個(gè)島和河岸連結(jié)。后來有人請教當(dāng)時(shí)的大數(shù)學(xué)家歐拉,歐拉用圖論的方法證明這個(gè)問題無解,同時(shí)他提出并解決了更為一般的問題,從而奠定了圖論的基礎(chǔ),歐拉也被譽(yù)為“圖論之父”.

ABCD圖論起源城中的居民經(jīng)常沿河過橋散步，于是提出了一個(gè)問題：能否一次走遍7座橋，而每座橋只許通過一次，最后仍回到起始地點(diǎn)?哥尼斯堡七橋問題從某點(diǎn)出發(fā)通過每座橋且每橋只通過一次回到起點(diǎn)DABCABCD建模：點(diǎn)——陸地島嶼邊——橋

后來,英國數(shù)學(xué)家哈密爾頓在1856年提出“周游世界”的問題：一個(gè)正十二面體,20個(gè)頂點(diǎn)分別表示世界上20個(gè)大城市,要求從某個(gè)城市出發(fā),經(jīng)過所有城市一次而不重復(fù),最后回到出發(fā)地.這也是圖論中一個(gè)著名的問題.

“四色問題”也是圖論中的著名問題：地圖著色時(shí),國境線相鄰的國家需要著上不同的顏色,最少需要幾種顏色？1976年,美國人阿佩爾和哈肯用計(jì)算機(jī)運(yùn)行1200個(gè)小時(shí),證明4種顏色就夠了.但至今尚有爭議.在生產(chǎn)和日常生活中，經(jīng)常碰到各種各樣的圖。如公路或鐵路交通圖、管網(wǎng)圖、通訊聯(lián)絡(luò)圖等。對所要研究的問題確定具體對象及這些對象間的性質(zhì)關(guān)系，并用圖的形式表示出來，這就是對所研究原問題建立的模型。例如，為了反映5家企業(yè)的業(yè)務(wù)往來關(guān)系，可以用點(diǎn)表示企業(yè)，用點(diǎn)間連線表示兩家企業(yè)有業(yè)務(wù)聯(lián)系，如圖所示。又例如工作分配問題，我們可以用點(diǎn)表示工人與需要完成的工作，點(diǎn)間連線表示每個(gè)人可以勝任哪些工作，如圖所示。戊甲乙丙丁戊甲乙丙丁工人工作DCBA這樣的例子很多，物質(zhì)結(jié)構(gòu)、電路網(wǎng)絡(luò)、城市規(guī)劃、交通運(yùn)輸、信息傳遞、物資調(diào)配等也都可以用點(diǎn)和線連接起來的圖進(jìn)行模擬。這里所研究的圖與平面幾何中的圖不同。這里只關(guān)心圖中有多少個(gè)點(diǎn)，點(diǎn)與點(diǎn)之間有無連線，至于連線的方式是直線還是曲線，點(diǎn)與點(diǎn)的相對位置如何，都是無關(guān)緊要的。這里所講的圖是反映對象之間關(guān)系的一種工具。圖的理論和方法，就是從形形色色的具體的圖以及與它們相關(guān)的實(shí)際問題中，抽象出共同性的東西，找出其規(guī)律、性質(zhì)、方法，再應(yīng)用到解決實(shí)際問題中去。圖論的基本概念

所謂的圖，直觀的講就是在平面上n個(gè)點(diǎn)，把其中的一些點(diǎn)對用線連接起來，不考慮點(diǎn)的位置與曲線的曲直長短，這樣形成的一個(gè)關(guān)系結(jié)構(gòu)就是一個(gè)圖。一個(gè)圖(Graph)定義為三元有序組G=(V(G),E(G),

G)，V(G)={v1,v2,…,vn}是圖的頂點(diǎn)集合，E(G)={e1,e2,…,em}是圖的邊集合，它聯(lián)結(jié)V

中的兩個(gè)點(diǎn),如果這兩個(gè)點(diǎn)是無序的,則稱該邊為無向邊,否則,稱為有向邊.

G稱為頂點(diǎn)與邊之間的關(guān)聯(lián)函數(shù)。V(G)中的元素vi稱為頂點(diǎn),E(G)中的元素ek

稱為邊.一個(gè)圖習(xí)慣記作

G=(V,E).一、基本概念１.圖G的幾何實(shí)現(xiàn)其中：例1:設(shè)G是一個(gè)圖，圖的分類如果E的每一條邊都是無向邊,則稱G為無向圖(如圖1);如果E的每一條邊都是有向邊,則稱G為有向圖(如圖2);否則,稱G為混合圖.如果圖的每一條邊都對應(yīng)一個(gè)實(shí)數(shù)w(e)，稱w(e)為邊e的權(quán)，稱該圖為賦權(quán)圖。圖1圖2若一個(gè)圖的頂點(diǎn)集和邊集都是有限集，則稱其為有限圖.只有一個(gè)頂點(diǎn)的圖稱為平凡圖，其他的所有圖都稱為非平凡圖.端點(diǎn)重合為一點(diǎn)的邊稱為環(huán)。連接同一對頂點(diǎn)的多條邊稱為重邊。一個(gè)圖稱為簡單圖，如果它既沒有環(huán)也沒有重邊。含有重邊的圖稱為多重圖.我們只討論有限圖.圖的術(shù)語1、相鄰和關(guān)聯(lián)設(shè)圖G=(V(G),E(G))，若e

連接u和v，稱u和v是e的端點(diǎn).稱端點(diǎn)u，v與邊e是關(guān)聯(lián)的，稱兩個(gè)頂點(diǎn)u，v是鄰接（相鄰）的.兩條邊e,e1有公共端點(diǎn)v，則稱e,e1相鄰.若圖G是有向圖，稱點(diǎn)u

,v分別為邊uv的始點(diǎn)和終點(diǎn)若t∈V，t不與其他頂點(diǎn)相鄰，稱t為孤立頂點(diǎn)。uvewe1圖的術(shù)語2、頂點(diǎn)的度無向圖中與結(jié)點(diǎn)v相關(guān)聯(lián)的邊數(shù)稱為v的度數(shù)，記作deg(v)

或d(v)，有向圖中以v為起點(diǎn)的邊數(shù)稱為v的出度，記作deg+(v)或d+(v)

，以v為終點(diǎn)的邊數(shù)稱為v的入度，記作deg-(v)或d-(v)

,此時(shí)d(v)

=d+(v)

+d-(v)

。稱度為奇數(shù)的頂點(diǎn)為奇點(diǎn)；稱度為偶數(shù)的頂點(diǎn)為偶點(diǎn).（1）無向圖中所有結(jié)點(diǎn)的度數(shù)之和等于邊數(shù)的兩倍;（2）有向圖中所有結(jié)點(diǎn)的出度(入度)之和等于邊數(shù)。握手定理:推論：任何圖的奇結(jié)點(diǎn)必為偶數(shù)個(gè)。d(v1)=d(v3)=d(v4)=4,d(v2)=2.(環(huán)e6在計(jì)算d(v4)時(shí)算作兩次)圖的術(shù)語3、完全圖任意兩頂點(diǎn)都相鄰的簡單圖（既沒有環(huán)也沒有重邊）,稱為完全圖.n個(gè)定點(diǎn)的完全圖記為Kn.K4K3K5圖的術(shù)語4、二分圖（二部圖）（X,Y;E）二分圖是一個(gè)簡單圖，其頂點(diǎn)集合可分劃成兩個(gè)子集X與Y，使得每條邊的一個(gè)端點(diǎn)在X，另一個(gè)端點(diǎn)在Y;(X,Y)也稱為圖的二分劃。完全二分圖是具有二分劃(X,Y)的二分圖，并且X的每個(gè)頂點(diǎn)與Y的每個(gè)頂點(diǎn)都相連。完全二分圖記為Km,n戊甲乙丙丁工人工作DCBA圖的術(shù)語5、子圖有兩個(gè)圖G和H，如果稱圖H是圖G的子圖，記為若且稱H是G的真子圖。稱H是G的生成子圖.如果，e1e3e2Gv3v4v5v2v1H1:真子圖v3v5v2v1H2:生成子圖e1e3e2v3v4v5v2v16、頂點(diǎn)導(dǎo)出子圖設(shè)W是圖G的一個(gè)非空頂點(diǎn)子集,以W為頂點(diǎn)集，以二端點(diǎn)均在W中的邊的全體為邊集的子圖稱為由W導(dǎo)出的G的子圖，簡稱導(dǎo)出子圖，記為G[W]。導(dǎo)出子圖G[V-W]記為G-W，即它是從G中刪除W中頂點(diǎn)以及與這些頂點(diǎn)相關(guān)聯(lián)的邊所得到的子圖。e1e3e2Gv3v4v5v2v1e3e2v3v4v2G[v2,v3,v4]G-{v1,v5}e1e3e2v3v4v5v2v16、邊導(dǎo)出子圖設(shè)F是圖G的非空邊子集，以F為邊集，以F中邊的端點(diǎn)全體為頂點(diǎn)集所構(gòu)成的子圖稱為由F導(dǎo)出的G的子圖，簡稱G的邊導(dǎo)出子圖。記為G[F]。記G-F表示以E(G)\F為邊集的G的生成子圖，它是從G中刪除F中的邊所得到的子圖。e1e3e2Gv3v4v5v2v1G[e1,e2,e3]G-

e1e1e3e2v3v4v5v2v1e1e3e2v3v4v2v1說明：一個(gè)圖的幾何實(shí)現(xiàn)并不是唯一的；表示頂點(diǎn)的點(diǎn)和表示邊的線的相對位置并不重要，重要的是圖形描繪出邊與頂點(diǎn)之間保持的相互關(guān)系。在一個(gè)圖的幾何實(shí)現(xiàn)中，兩條邊的交點(diǎn)可能不是圖的頂點(diǎn)。例如下面舉幾個(gè)實(shí)際生活中的例子：例2鐵路交通圖北京天津濟(jì)南青島連云港上海南京徐州鄭州武漢用點(diǎn)表示城市用點(diǎn)與點(diǎn)之間的連線表示兩城市間的鐵路線諸如此類的還有電話線分布圖、煤氣管道圖、航空線路等等例3球隊(duì)比賽的情況v5v4v3v1v2用點(diǎn)v1v2v3v4v5代表五個(gè)球隊(duì)某兩個(gè)隊(duì)比賽過，就在這兩個(gè)隊(duì)所對應(yīng)的點(diǎn)之間連一條線，從上面的例子可知，可以用由點(diǎn)及點(diǎn)與點(diǎn)之間的連線所構(gòu)成的圖，去反映實(shí)際生活中，某些對象之間的某個(gè)特定的關(guān)系。一般情況下，圖中點(diǎn)的相對位置如何，點(diǎn)與點(diǎn)之間連線的長短曲直，對于反映對象之間的關(guān)系并不重要。所以，圖論中的圖與幾何圖、工程圖等是不同的。例3也可以用下圖表示(1)對象之間的“關(guān)系”具有“對稱性”:象上面的兩個(gè)例子

(2)對象之間的“關(guān)系”是“非對稱的” 例如人們之間的認(rèn)識(shí)關(guān)系，甲認(rèn)識(shí)乙并不意味著乙也認(rèn)識(shí)甲；比賽中的勝負(fù)關(guān)系，甲勝乙和乙勝甲不同。反映這種非對稱的關(guān)系，只用一條連線就不行了。

為了反映這種關(guān)系，我們用一條帶箭頭的連線表示。v1v2v3v4v5如例2中球隊(duì)勝了，可從v1引一條帶箭頭的連線到v2，每場比賽的勝負(fù)都用帶箭頭的連線標(biāo)出，即可反映五個(gè)球隊(duì)比賽的勝負(fù)情況。如下圖v5v4v3v1v2由圖可知，v1三勝一負(fù)，v4打了三場球，全負(fù)等等類似勝負(fù)這種非對稱性的關(guān)系，在生產(chǎn)和生活中也是常見的，如交通運(yùn)輸中的“單行線”，部門之間的領(lǐng)導(dǎo)和被領(lǐng)導(dǎo)關(guān)系，一項(xiàng)工程中各工序之間的先后關(guān)系等等。為適合使用計(jì)算機(jī)對圖進(jìn)行存儲(chǔ)和處理，需要用矩陣表示圖。常用的有：鄰接矩陣、關(guān)聯(lián)矩陣等。

圖的矩陣表示（1）鄰接矩陣(點(diǎn)點(diǎn))無向圖G有向圖G賦權(quán)圖G的權(quán)矩陣A=(aij

)

n×n

,例4：寫出右圖的鄰接矩陣：v1v2v3v4解：例5：寫出右圖的鄰接矩陣：圖的矩陣表示（2）關(guān)聯(lián)矩陣(點(diǎn)邊)無向圖G有向圖G解：例6：寫出右圖的關(guān)聯(lián)矩陣：圖的連通性1、通路與路徑在圖G中，頂點(diǎn)與邊相互交錯(cuò)的有限非空序列稱為一條從v0到vk的通路，記為;邊不重復(fù)但頂點(diǎn)可重復(fù)的通路稱為道路，記為;邊與頂點(diǎn)均不重復(fù)的通路稱為路徑，記為.通路道路路徑通路：wcxdyhwbvgy路徑：xcwhyeuavabdefghcuvyxw設(shè)G＝(V，E)，(V0，V1，…，Vk)是G中的一條道路，則稱V0到Vk連通或可達(dá)。說明：對無向圖而言，若V0到Vk可達(dá)，則Vk到V0也可達(dá)。對有向圖而言則未必。定義２：（１）任意兩點(diǎn)均有路徑的圖稱為連通圖．（２）起點(diǎn)與終點(diǎn)重合的路徑稱為圈．（３）連通而無圈的圖稱為樹．圈：uavbwhyeuabdefghcuvyxw無向圖的連通性：若Ｇ＝(Ｖ，Ｅ)中任兩個(gè)不同頂點(diǎn)都連通，則稱此無向圖是連通的。定理：任意一個(gè)連通無向圖的任兩個(gè)不同頂點(diǎn)都存在一條簡單道路。連通分圖：圖Ｇ可分為幾個(gè)不相連通的子圖，每一子圖本身都是連通的。稱這幾個(gè)子圖為Ｇ的連通分圖。有向圖的連通性：

(1)弱連通：若Ｇ＝(Ｖ，Ｅ)對應(yīng)的無向圖是連通圖，則稱Ｇ為弱連通。(2)強(qiáng)連通：若Ｇ＝(Ｖ，Ｅ)中任兩點(diǎn)間都有路，即對ａ與ｂ，ａ到ｂ可達(dá)，ｂ到ａ可達(dá)，稱Ｇ為強(qiáng)連通。用鄰接矩陣討論圖G的連通性質(zhì)：

在鄰接矩陣中，若aij＝１，表明vi到vj有一條邊，即vi到vj可達(dá)；若aij

＝０不說明vi到vj沒有道路，若通過其他點(diǎn)中轉(zhuǎn)，也有可能連通。作鄰接矩陣的普通矩陣乘法：

bij的值表示vi到vj路長為２的道路條數(shù)，一般地，就有：定理:Am的元素mij表示vi到vj長度為m的道路條數(shù)。定義3：設(shè)P(u,v)是賦權(quán)圖G中u到v的路徑，則：（1）為路徑P的權(quán)；（2）從u到v的具有最小權(quán)的路P*(u,v)，稱為u到v的最短路。76528936uvyxw如果圖G中具有一條經(jīng)過所有邊一次且僅一次的回路,稱歐拉回路,含歐拉回路的圖稱為歐拉圖；如果圖G中具有一條經(jīng)過所有邊一次且僅一次的路徑,稱歐拉路。

歐拉（Euler）圖Euler路：ydxcwhyeuavfygvbwabdefghcuvyxw定理:(1)連通無向圖G是歐拉圖的充要條件是G的每個(gè)結(jié)點(diǎn)均為偶結(jié)點(diǎn);(2)連通無向圖G含有歐拉路的充要條件是G恰有兩個(gè)奇結(jié)點(diǎn),且歐拉路必始于一個(gè)奇結(jié)點(diǎn)而終止于另一個(gè)奇結(jié)點(diǎn).

abcdef在下左圖中,所有結(jié)點(diǎn)均為偶結(jié)點(diǎn),故為歐拉圖.一條歐拉回路為：abcdefcebfa.abcde在下右圖中有一條歐拉路bcdeabe.

例6：如下圖是某街道圖形.灑水車從A點(diǎn)出發(fā)執(zhí)行灑水任務(wù).試問是否存在一條灑水路線,使灑水車通過所有街道且不重復(fù)而最后回到車庫B？

ABCDFEG解此問題即為求證圖中是否存在A到B的歐拉路.由于圖中只有A,B為奇結(jié)點(diǎn),因此這樣的灑水線路是存在的,例如,ACDEFBGCFGAB或AGFEDCFBGCAB,等等.

例7：下左圖是一幢房子的平面圖,前門進(jìn)入一個(gè)客廳b,由客廳通向四個(gè)房間.如果要求每扇門只能通過一次,現(xiàn)在由前門進(jìn)入,能否通過所有的門走遍所有的房間(包括客廳),然后從后門走出？

dacebfbfadec解將四個(gè)房間和一個(gè)客廳及室外作為結(jié)點(diǎn),門作為邊畫出上右圖.由于b和e是僅有的兩個(gè)奇結(jié)點(diǎn),故從前門進(jìn)、后門出的歐拉路是不存在的,即本題無解.

如果把“前門進(jìn)、后門出”這一條件去掉,則存在“每扇門通過一次且僅一次”的走法.請同學(xué)找出具體的走法.

有向圖的歐拉定理：

不含出/入度為０的孤立頂點(diǎn)的有向圖具有歐拉路的充要條件是：除了可能有２個(gè)頂點(diǎn)，一個(gè)入度比出度大１，一個(gè)出度比入度大１，其余頂點(diǎn)出度等于入度。推論：不含出/入度為０的孤立頂點(diǎn)的有向圖具有歐拉回路的充要條件是：所有頂點(diǎn)出度等于入度。如果圖G中具有一條經(jīng)過所有結(jié)點(diǎn)一次且僅一次的回路(稱哈密爾頓回路)簡稱Ｈ回路，則稱之為哈密爾頓圖。如果圖G中具有一條經(jīng)過所有結(jié)點(diǎn)一次且僅一次的路，稱為哈密爾頓路，簡稱Ｈ路哈密爾頓（Hamilton）圖

所謂哈密爾頓回路,起源于一個(gè)名叫“周游世界”的游戲,它是由英國數(shù)學(xué)家哈密爾頓(Hamilton)于1859年提出的.他用一個(gè)正十二面體的20個(gè)頂點(diǎn)代表20個(gè)大城市(見下左圖),這個(gè)正十二面體同構(gòu)于一個(gè)平面圖(見下右圖).要求沿著正十二面體的棱,從一個(gè)城市出發(fā),經(jīng)過每個(gè)城市恰好一次,然后回到出發(fā)點(diǎn).這個(gè)游戲曾風(fēng)靡一時(shí),它有若干個(gè)解.定理：設(shè)Ｇ＝(Ｖ，Ｅ)是ｎ個(gè)頂點(diǎn)的簡單圖，如果任何一對頂點(diǎn)的度之和≥ｎ－１，則Ｇ中一定有Ｈ道路(n>=2)。注意:

此定理?xiàng)l件顯然不是必要條件，如ｎ≥６的ｎ邊形，二個(gè)頂點(diǎn)度之和＝４，４＜ｎ－１，而ｎ邊形顯然有Ｈ道路。推論：

Ｇ＝(Ｖ，Ｅ)是ｎ≥３的簡單圖，若任何一對頂點(diǎn)的度之和≥ｎ，則Ｇ必有哈密頓回路。

要判別一個(gè)圖不存在Ｈ道路，Ｈ回路，也不是很容易的，只能對無向圖給出一些必要條件：（1）Ｈ道路存在的必要條件：１）連通２）至多只能有二個(gè)頂點(diǎn)的度＜２，其余頂點(diǎn)的度≥２。bcda（2）Ｈ回路存在必要條件：對Ｖ的任一非空真子集Ｓ，Ｇ－Ｓ的連通分圖個(gè)數(shù)≤|Ｓ|。解：取Ｓ＝｛A1，A2

｝G－Ｓ存在3個(gè)分圖

根據(jù)H道路存在的必要條件之二，可知：H道路不存在。用圖論思想求解以下各題例8、一擺渡人欲將一只狼，一頭羊，一籃菜從河西渡過河到河?xùn)|，由于船小，一次只能帶一物過河，并且，狼與羊，羊與菜不能獨(dú)處，給出渡河方法。解：用四維0-1向量表示(人,狼,羊,菜)在河西岸的狀態(tài)(在河西岸則分量取1,否則取0),共有24=16種狀態(tài).在河?xùn)|岸的狀態(tài)類似記作.由題設(shè)，狀態(tài)（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不允許的，從而對應(yīng)狀態(tài)（1,0,0,1），(1,1,0,0),(1,0,0,0)也是不允許的，人在河西：（1,1,1,1）（1,1,1,0）（1,1,0,1）（1,0,1,1）（1,0,1,0）（0,1,0,1）（0,1,0,0）（0,0,1,0）（0,0,0,1）（0,0,0,0）人在河?xùn)|：以十個(gè)向量作為頂點(diǎn)，將可能互相轉(zhuǎn)移的狀態(tài)連線，構(gòu)成一個(gè)圖,根據(jù)此圖便可找到渡河方法.問題：如何從狀態(tài)（1,1,1,1）轉(zhuǎn)移到（0,0,0,0）？方法：從（1,1,1,1）開始，沿關(guān)聯(lián)邊到達(dá)沒有到達(dá)的相鄰頂點(diǎn)，到（0,0,0,0）終止，得到有向圖即是。

將10個(gè)頂點(diǎn)分別記為A1,A2,…,A10,則渡河問題化為在該圖中求一條從A1到A10的路.

從圖中易得到兩條路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.例9:證明：在任意6人的集會(huì)上，總有3人互相認(rèn)識(shí)，或總有3人互相不認(rèn)識(shí)。解：以頂點(diǎn)表示人，以邊表示認(rèn)識(shí)，得6個(gè)頂點(diǎn)的簡單圖G。問題：3人互相認(rèn)識(shí)即G包含K3為子圖，3人互相不認(rèn)識(shí)即G包含（3,0）圖為子圖。某廠生產(chǎn)一種彈子鎖具，每個(gè)鎖具的鑰匙有5個(gè)槽，每個(gè)槽的高度從{1，2，3，4，5，6)中任取一數(shù)．由于工藝及其它原因，制造鎖具時(shí)對5個(gè)槽的高度有兩個(gè)限制：(1)至少有3個(gè)不同的數(shù)；(2)相鄰兩槽的高度之差不能為5．滿足以上條件制造出來的所有互不相同的鎖具稱為一批．我們的問題是如何確定每一批鎖具的個(gè)數(shù)?例10：1994年全國大學(xué)生數(shù)學(xué)建模競賽B題(鎖具裝箱)中關(guān)于鎖具總數(shù)的問題可敘述如下：解：該問題用圖論中的鄰接矩陣解決較為簡單。設(shè)：x表示一批鎖具的個(gè)數(shù)

，

t表示相鄰兩槽高度之差不為5的鎖具數(shù)，即：滿足限制條件(2)的鎖具數(shù)，s表示相鄰兩槽高度之差不為5且槽高僅有1個(gè)或2個(gè)的鎖具數(shù)，即：滿足限制條件(2)但不滿足限制條件(1)的鎖具數(shù)．則x=t-s我們用圖論方法計(jì)算t和s.

構(gòu)造無向圖

在G中每一條長度為4的道路對應(yīng)于一個(gè)相鄰兩槽高度之差不超過5的鎖具，即滿足限制條件（2）的鎖具，反之亦然，于是可以通過G的鄰接矩陣A來計(jì)算t的值因此，

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

其中yi表示滿足限制條件(2)但不滿足限制條件(1)且首位為i的鎖具數(shù),（i=1,2,3,4,5,6),顯然y1=y6,y2=y4=y3=y5,于是我們只需要計(jì)算y1和y2.計(jì)算y1可分別考慮槽高只有1，（1、2），（1、3），（1、4），（1、5）的情形．若只有1，這樣的鎖具效只有1個(gè)，若只有1和i(i=2,3,4,5)，這樣的鎖具數(shù)同理，計(jì)算y2時(shí)應(yīng)考慮槽高只有2,21,23,24,25,26時(shí)的情形，類似計(jì)算可得

y2=(24-1)×5+1=76．于是，s=61×2+76×4=426，x=6306-426=5880.該算法既易理解又易操作并且又可擴(kuò)展．公交線路選擇問題：在給定某城市公交線路的公交網(wǎng)信息后，求任意兩個(gè)站點(diǎn)之間的最佳出行路線，包括換乘次數(shù)最少、出行時(shí)間最短、出行費(fèi)用最低等。以下圖的簡化公交網(wǎng)為例來說明。

12345圖中由兩條公交線路組成，實(shí)線表示第一條線路，依次經(jīng)過站點(diǎn)1,3,4,5，虛線表示第二條線路，依次經(jīng)過站點(diǎn)2,3,5。首先考慮換乘次數(shù)最少的線路選擇模型，首先建立直達(dá)矩陣如下：12345計(jì)算A2得到：由于A2為非零矩陣，所以任意兩站點(diǎn)經(jīng)過換乘一次都可到達(dá)，由于問題較簡單，結(jié)果顯然正確。一般地，比較A=(aij),A2=(a(2)ij),…,Ak=(a(k)ij)中的(i,j)元夠成的向量中第一個(gè)非零向量的上標(biāo)即為出行換乘的最少次數(shù)。12345接下來考慮出行時(shí)間最短的模型，建立直達(dá)距離矩陣：下面利用Floyd矩陣算法可計(jì)算出出行時(shí)間最短的路線。定義T*T=(t(2)ij),t(2)ij=min{min1<=k<=5{tik+tkj},tij},t(2)ij表示從站點(diǎn)i到站點(diǎn)j的至多換乘一次的最短時(shí)間。

41235利用matlab編寫程序如下：T=[0inf123;inf01inf2;11011;2inf101;32110];n=length(T);T2=zeros(n);fori=1:nforj=1:nT2(i,j)=min(min(T(i,:)+T(:,j)'),T(i,j));endendT2計(jì)算結(jié)果為：T2=

0212220122110112210122110

12345類似可計(jì)算出T3，T4，實(shí)際上T2的值已為出行路線的最短時(shí)間，例如T2（2,5）=2，說明站點(diǎn)2到站點(diǎn)5的最短時(shí)間為2站路時(shí)間。思考：最