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

數(shù)學(xué)建模圖論講稿第一頁(yè)，共八十六頁(yè)，編輯于2023年，星期三圖論方法專題一圖的基本概念二三最短路問(wèn)題及其算法四最小生成樹(shù)問(wèn)題五E圖與H圖圖的矩陣表示第二頁(yè)，共八十六頁(yè)，編輯于2023年，星期三

數(shù)學(xué)建模-圖論32023年6月10日

一、圖的基本概念第三頁(yè)，共八十六頁(yè)，編輯于2023年，星期三數(shù)學(xué)建模-圖論42023年6月10日

一、圖的基本概念第四頁(yè)，共八十六頁(yè)，編輯于2023年，星期三

一、圖的基本概念次數(shù)為奇數(shù)頂點(diǎn)稱為奇點(diǎn)，否則稱為偶點(diǎn)。52023年6月10日數(shù)學(xué)建模-圖論第五頁(yè)，共八十六頁(yè)，編輯于2023年，星期三常用d(v)表示圖G中與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目,

d(v)稱為頂點(diǎn)v的度數(shù).與頂點(diǎn)v出關(guān)聯(lián)的邊的數(shù)目稱為出度，記作d

+(v)，與頂點(diǎn)v入關(guān)聯(lián)的邊的數(shù)目稱為入度，記作d

-(v)。用N(v)表示圖G中所有與頂點(diǎn)v相鄰的頂點(diǎn)的集合.任意兩頂點(diǎn)都相鄰的簡(jiǎn)單圖稱為完全圖.有n個(gè)頂點(diǎn)的完全圖記為Kn。

一、圖的基本概念數(shù)學(xué)建模-圖論第六頁(yè)，共八十六頁(yè)，編輯于2023年，星期三幾個(gè)基本定理：

一、圖的基本概念數(shù)學(xué)建模-圖論第七頁(yè)，共八十六頁(yè)，編輯于2023年，星期三若將圖G的每一條邊e都對(duì)應(yīng)一個(gè)實(shí)數(shù)F(e),則稱F(e)為該邊的權(quán),并稱圖G為賦權(quán)圖,記為G=(V,E,F

).

設(shè)G=(V,E)是一個(gè)圖,v0,v1,…,vk∈V,且“1≤i≤k,vi－1vi∈E,則稱v0v1…

vk是G的一條通路.

如果通路中沒(méi)有相同的頂點(diǎn),則稱此通路為路徑,簡(jiǎn)稱路.始點(diǎn)和終點(diǎn)相同的路稱為圈或回路.

一、圖的基本概念數(shù)學(xué)建模-圖論第八頁(yè)，共八十六頁(yè)，編輯于2023年，星期三頂點(diǎn)u與v稱為連通的，如果存在u到v通路，任二頂點(diǎn)都連通的圖稱為連通圖，否則，稱為非連通圖。極大連通子圖稱為連通分圖。

連通而無(wú)圈的圖稱為樹(shù),常用T表示樹(shù).樹(shù)中最長(zhǎng)路的邊數(shù)稱為樹(shù)的高，度數(shù)為1的頂點(diǎn)稱為樹(shù)葉。其余的頂點(diǎn)稱為分枝點(diǎn)。樹(shù)的邊稱為樹(shù)枝。設(shè)G是有向圖，如果G的底圖是樹(shù)，則稱G是有向樹(shù)，也簡(jiǎn)稱樹(shù)。

一、圖的基本概念數(shù)學(xué)建模-圖論第九頁(yè)，共八十六頁(yè)，編輯于2023年，星期三鄰接矩陣（結(jié)點(diǎn)與結(jié)點(diǎn)的關(guān)系）關(guān)聯(lián)矩陣（結(jié)點(diǎn)與邊的關(guān)系）路徑矩陣（任意兩結(jié)點(diǎn)之間是否有路徑）可達(dá)性矩陣直達(dá)矩陣等等……二、圖的矩陣表示數(shù)學(xué)建模-圖論第十頁(yè)，共八十六頁(yè)，編輯于2023年，星期三1有向圖的鄰接矩陣

A=(aij)n×n

（n為結(jié)點(diǎn)數(shù)）

例1：寫出右圖的鄰接矩陣：解：二、圖的矩陣表示數(shù)學(xué)建模-圖論第十一頁(yè)，共八十六頁(yè)，編輯于2023年，星期三2有向圖的權(quán)矩陣A=(aij)n×n

（n為結(jié)點(diǎn)數(shù)）

例2：寫出右圖的權(quán)矩陣：解：二、圖的矩陣表示數(shù)學(xué)建模-圖論第十二頁(yè)，共八十六頁(yè)，編輯于2023年，星期三3有向圖的關(guān)聯(lián)矩陣A=(aij)n×m

（n為結(jié)點(diǎn)數(shù)m為邊數(shù)）

有向圖：無(wú)向圖：

二、圖的矩陣表示數(shù)學(xué)建模-圖論第十三頁(yè)，共八十六頁(yè)，編輯于2023年，星期三例3：分別寫出右邊兩圖的關(guān)聯(lián)矩陣解：分別為：

二、圖的矩陣表示

數(shù)學(xué)建模-圖論第十四頁(yè)，共八十六頁(yè)，編輯于2023年，星期三

二、圖的矩陣表示4應(yīng)用實(shí)例某廠生產(chǎn)一種彈子鎖具，每個(gè)鎖具的鑰匙有5個(gè)槽，每個(gè)槽的高度從{1，2，3，4，5，6)中任取一數(shù)．由于工藝及其它原因，制造鎖具時(shí)對(duì)5個(gè)槽的高度有兩個(gè)限制：(1)至少有3個(gè)不同的數(shù)；(2)相鄰兩槽的高度之差不能為5．滿足以上條件制造出來(lái)的所有互不相同的鎖具稱為一批．我們的問(wèn)題是如何確定每一批鎖具的個(gè)數(shù)?1994年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B題(鎖具裝箱)中關(guān)于鎖具總數(shù)的問(wèn)題可敘述如下：數(shù)學(xué)建模-圖論第十五頁(yè)，共八十六頁(yè)，編輯于2023年，星期三該問(wèn)題用圖論中的鄰接矩陣解決較為簡(jiǎn)單易見(jiàn)，x=t-s，其中，t代表相鄰兩槽高度之差不為5的鎖具數(shù)，即：滿足限制條件(2)的鎖具數(shù)，s代表相鄰兩槽高度之差不為5且槽高僅有1個(gè)或2個(gè)的鎖具數(shù)，即：滿足限制條件(2)但不滿足限制條件(1)的鎖具數(shù)．我們用圖論方法計(jì)算t和s.數(shù)學(xué)建模-圖論二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）第十六頁(yè)，共八十六頁(yè)，編輯于2023年，星期三在G中t每一條長(zhǎng)度為4的道路對(duì)應(yīng)于一個(gè)相鄰兩槽高度之差不超過(guò)5的鎖具，即滿足限制條件（2）的鎖具，反之亦然，于是可以通過(guò)G的鄰接矩陣A來(lái)計(jì)算t的值，具體步驟如下：數(shù)學(xué)建模-圖論二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）構(gòu)造無(wú)向圖

124356第十七頁(yè)，共八十六頁(yè)，編輯于2023年，星期三因此，

數(shù)學(xué)建模-圖論二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）第十八頁(yè)，共八十六頁(yè)，編輯于2023年，星期三又令

其中yi表示滿足限制條件(2)但不滿足限制條件(1)且首位為i的鎖具數(shù),（i=1,2,3,4,5,6),顯然y1=y6,y2=y4=y3=y5,于是我們只需要計(jì)算y1和y2.計(jì)算y1可分別考慮槽高只有1，12，13，14，15的情形．若只有1，這樣的鎖具效只有1個(gè)，若只有1和i(i=2,3,4,5)，這樣的鎖具數(shù)=G中以1和i為頂點(diǎn)，長(zhǎng)度為3的道路數(shù)，此數(shù)可通過(guò)A的子矩陣A1i計(jì)算得到．?dāng)?shù)學(xué)建模-圖論

二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）124356第十九頁(yè)，共八十六頁(yè)，編輯于2023年，星期三

二、圖的矩陣表示（應(yīng)用實(shí)例解法分析）事實(shí)上，因?yàn)?/p>

其中i=2,3,4,5,顯然y1=1+(4+4+4+4-1)

4=61.同理，計(jì)算y2時(shí)應(yīng)考慮槽高只有2,21,23,24,25,26時(shí)的情形，類似計(jì)算可得

y2=1+(4+4+4+4-1)×5=76．于是，s=61×2+76×4=426，x=6306-426=5880.該算法既易理解又易操作并且又可擴(kuò)展．?dāng)?shù)學(xué)建模-圖論第二十頁(yè)，共八十六頁(yè)，編輯于2023年，星期三

二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）公交線路選擇問(wèn)題：在給定某城市公交線路的公交網(wǎng)信息后，求任意兩個(gè)站點(diǎn)之間的最佳出行路線，包括換乘次數(shù)最少、出行時(shí)間最短、出行費(fèi)用最低等。以下圖的簡(jiǎn)化公交網(wǎng)為例來(lái)說(shuō)明。

數(shù)學(xué)建模-圖論12345圖中由兩條公交線路組成，實(shí)線表示第一條線路，依次經(jīng)過(guò)站點(diǎn)1,3,4,5，虛線表示第二條線路，依次經(jīng)過(guò)站點(diǎn)2,3,5。首先考慮換乘次數(shù)最少的線路選擇模型，首先建立直達(dá)矩陣如下：第二十一頁(yè)，共八十六頁(yè)，編輯于2023年，星期三

二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）數(shù)學(xué)建模-圖論12345計(jì)算A2得到：由于A2為非零矩陣，所以任意兩站點(diǎn)經(jīng)過(guò)換乘一次都可到達(dá)，由于問(wèn)題較簡(jiǎn)單，結(jié)果顯然正確。一般地，比較A=(aij),A2=(a(2)ij),…,Ak=(a(k)ij)中的(i,j)元夠成的向量中第一個(gè)非零向量的上標(biāo)即為出行換乘的最少次數(shù)。第二十二頁(yè)，共八十六頁(yè)，編輯于2023年，星期三

二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）數(shù)學(xué)建模-圖論12345接下來(lái)考慮出行時(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í)間。

第二十三頁(yè)，共八十六頁(yè)，編輯于2023年，星期三

二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）數(shù)學(xué)建模-圖論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

第二十四頁(yè)，共八十六頁(yè)，編輯于2023年，星期三

二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）數(shù)學(xué)建模-圖論12345類似可計(jì)算出T3，T4，實(shí)際上T2的值已為出行路線的最短時(shí)間，例如T2（2,5）=2，說(shuō)明站點(diǎn)2到站點(diǎn)5的最短時(shí)間為2站路時(shí)間。思考：最省乘車費(fèi)用的最佳出行路線該如何考慮呢？？？（分情況討論）（1）按路程收費(fèi)；（出行時(shí)間最短）（2）按換乘次數(shù)收費(fèi)。（最少換乘次數(shù)）

第二十五頁(yè)，共八十六頁(yè)，編輯于2023年，星期三

二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）數(shù)學(xué)建模-圖論商人過(guò)河問(wèn)題：假如有三個(gè)商人各帶一名隨從要過(guò)河，只有一條船，每次最多只能坐兩個(gè)人。為安全起見(jiàn)，商人數(shù)不能少于隨從數(shù)，否則隨從會(huì)殺人越貨。船過(guò)一次河需要5分鐘，問(wèn)最短幾分鐘能使他們都過(guò)去？用鄰接矩陣來(lái)解決：設(shè)(m,n,l)表示左岸商人m人，隨從n人；設(shè)(m,n,r)表示右岸有商人m人，隨從n人。從左岸到右岸去，所有可能的狀態(tài)為：v1=(3,3,l),v2=(3,2,l),v3=(3,1,l),v4=(3,0,l),v5=(2,2,l),v6=(1,1,l),v7=(0,3,l),v8=(0,2,l),v9=(0,1,l),v10=(3,3,r),v11=(3,2,r),v12=(3,1,r),v13=(3,0,r),v14=(2,2,r),v15=(1,1,r),v16=(0,3,r),v17=(0,2,r),v18=(0,1,r).第二十六頁(yè)，共八十六頁(yè)，編輯于2023年，星期三

二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）數(shù)學(xué)建模-圖論V10v11v12v13v14v15v16v17v18v1

v2v3v4v5v6v7v8v9渡河可以理解為上面狀態(tài)的轉(zhuǎn)移，例如狀態(tài)v1渡河一次可以轉(zhuǎn)化為其他狀態(tài)v15v17v18，其他狀態(tài)也易列出。以V={v1,

v2,...v18}為頂點(diǎn)集，當(dāng)兩種狀態(tài)可以互相轉(zhuǎn)化時(shí)，就在相應(yīng)的來(lái)那個(gè)頂點(diǎn)間連一邊，從而建立一個(gè)二分圖G=<V,E>，如右圖所示。G=<V,E>的鄰接矩陣為：第二十七頁(yè)，共八十六頁(yè)，編輯于2023年，星期三

二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）數(shù)學(xué)建模-圖論V10v11v12v13v14v15v16v17v18v1

v2v3v4v5v6v7v8v9其中，矩陣B為：記a(k)ij為Ak中的（i,j）元，目標(biāo)是使a(k)1,10不等于0的最小的自然數(shù)k.

利用matlab容易計(jì)算出k=11，且a(11)1,10=4,即小船至少11次才能把所有人全部運(yùn)到右岸，說(shuō)明共有4種不同的過(guò)河方案。繼續(xù)計(jì)算可得出a(19)1,10=45060，如果允許小船過(guò)河19次的話，共有45060中不同的方案。第二十八頁(yè)，共八十六頁(yè)，編輯于2023年，星期三若將圖G的每一條邊e都對(duì)應(yīng)一個(gè)實(shí)數(shù)F(e),則稱F(e)為該邊的權(quán),并稱圖G為賦權(quán)圖,記為G=(V,E,F

).

設(shè)G=(V,E)是一個(gè)圖,v0,v1,…,vk∈V,且“1≤i≤k,vi－1vi∈E,則稱v0v1…

vk是G的一條通路.如果通路中沒(méi)有相同的頂點(diǎn),則稱此通路為路徑,簡(jiǎn)稱路.對(duì)于賦權(quán)圖，路的長(zhǎng)度（即路的權(quán)）通常指路上所有邊的權(quán)之和。最短路問(wèn)題：求賦權(quán)圖上指定點(diǎn)之間的權(quán)最小的路。

三、最短路問(wèn)題及其算法數(shù)學(xué)建模-圖論第二十九頁(yè)，共八十六頁(yè)，編輯于2023年，星期三重要性質(zhì)：若v0v1…

vm是G中從v0到vm的最短路,則對(duì)1≤k≤m,v0v1…

vk必為G中從v0到vk的最短路.即：最短路是一條路，且最短路的任一段也是最短路。數(shù)學(xué)建模-圖論

三、最短路問(wèn)題及其算法第三十頁(yè)，共八十六頁(yè)，編輯于2023年，星期三

設(shè)有給定連接若干城市的公路網(wǎng)，尋求從指定城市到各城市的最短路線。

2、應(yīng)用實(shí)例：最短路問(wèn)題

問(wèn)題的數(shù)學(xué)模型:

三、最短路問(wèn)題及其算法312023年6月10日數(shù)學(xué)建模-圖論第三十一頁(yè)，共八十六頁(yè)，編輯于2023年，星期三322023年6月10日

三、最短路問(wèn)題及其算法數(shù)學(xué)建模-圖論254647109137106648第三十二頁(yè)，共八十六頁(yè)，編輯于2023年，星期三332023年6月10日

三、最短路問(wèn)題及其算法數(shù)學(xué)建模-圖論第三十三頁(yè)，共八十六頁(yè)，編輯于2023年，星期三342023年6月10日

三、最短路問(wèn)題及其算法數(shù)學(xué)建模-圖論第三十四頁(yè)，共八十六頁(yè)，編輯于2023年，星期三352023年6月10日

三、最短路問(wèn)題及其算法數(shù)學(xué)建模-圖論第三十五頁(yè)，共八十六頁(yè)，編輯于2023年，星期三362023年6月10日

三、最短路問(wèn)題及其算法數(shù)學(xué)建模-圖論254647109137106648第三十六頁(yè)，共八十六頁(yè)，編輯于2023年，星期三372023年6月10日

三、最短路問(wèn)題及其算法數(shù)學(xué)建模-圖論第三十七頁(yè)，共八十六頁(yè)，編輯于2023年，星期三382023年6月10日

三、最短路問(wèn)題及其算法數(shù)學(xué)建模-圖論第三十八頁(yè)，共八十六頁(yè)，編輯于2023年，星期三392023年6月10日

三、最短路問(wèn)題及其算法數(shù)學(xué)建模-圖論第三十九頁(yè)，共八十六頁(yè)，編輯于2023年，星期三402023年6月10日

三、最短路問(wèn)題及其算法數(shù)學(xué)建模-圖論254647109137106648第四十頁(yè)，共八十六頁(yè)，編輯于2023年，星期三412023年6月10日

三、最短路問(wèn)題及其算法數(shù)學(xué)建模-圖論第四十一頁(yè)，共八十六頁(yè)，編輯于2023年，星期三422023年6月10日

三、最短路問(wèn)題及其算法數(shù)學(xué)建模-圖論第四十二頁(yè)，共八十六頁(yè)，編輯于2023年，星期三432023年6月10日

三、最短路問(wèn)題及其算法數(shù)學(xué)建模-圖論254647109137106648第四十三頁(yè)，共八十六頁(yè)，編輯于2023年，星期三442023年6月10日

三、最短路問(wèn)題及其算法數(shù)學(xué)建模-圖論第四十四頁(yè)，共八十六頁(yè)，編輯于2023年，星期三452023年6月10日數(shù)學(xué)建模-圖論

三、最短路問(wèn)題及其算法第四十五頁(yè)，共八十六頁(yè)，編輯于2023年，星期三462023年6月10日數(shù)學(xué)建模-圖論求v1到v6的最短路問(wèn)題.

三、最短路問(wèn)題及其算法第四十六頁(yè)，共八十六頁(yè)，編輯于2023年，星期三472023年6月10日數(shù)學(xué)建模-圖論從上圖中容易得到v1到v6只有兩條路：v1v3v6和v1v4v6.

而這兩條路都是v1到v6的最短路.

三、最短路問(wèn)題及其算法第四十七頁(yè)，共八十六頁(yè)，編輯于2023年，星期三482023年6月10日

三、最短路問(wèn)題及其算法數(shù)學(xué)建模-圖論第四十八頁(yè)，共八十六頁(yè)，編輯于2023年，星期三頂點(diǎn)u與v稱為連通的，如果存在u-v通路，任二頂點(diǎn)都連通的圖稱為連通圖，否則，稱為不連通圖。極大連通子圖稱為連通分圖。

連通而無(wú)圈的圖稱為樹(shù),常用T表示樹(shù).樹(shù)中最長(zhǎng)路的邊數(shù)稱為樹(shù)的高的度為1的頂點(diǎn)稱為樹(shù)葉。其余的頂點(diǎn)稱為分枝點(diǎn)。樹(shù)的邊稱為樹(shù)枝。設(shè)G是有向圖，如果G的底圖是樹(shù)，則稱G是有向樹(shù)，也簡(jiǎn)稱樹(shù)。

四、最小生成樹(shù)問(wèn)題及其算法數(shù)學(xué)建模-圖論第四十九頁(yè)，共八十六頁(yè)，編輯于2023年，星期三若任意一個(gè)連通的圖G=<V,E>的生成子圖T=<V’,E’>(V’=V,E’為E的子集)為樹(shù),這棵樹(shù)T稱為圖G的生成樹(shù).設(shè)T是圖G的一棵生成樹(shù),用F(T)表示樹(shù)T中所有邊的權(quán)數(shù)之和,F(T)稱為樹(shù)T的權(quán).一個(gè)連通圖G的生成樹(shù)一般不止一棵,圖G的所有生成樹(shù)中權(quán)數(shù)最小的生成樹(shù)稱為圖G的最小生成樹(shù).數(shù)學(xué)建模-圖論

四、最小生成樹(shù)問(wèn)題及其算法第五十頁(yè)，共八十六頁(yè)，編輯于2023年，星期三怎樣找出最小生成樹(shù)？？？G

T1T2T3T4T5T6T7T8T1至T8是圖G的生成樹(shù)數(shù)學(xué)建模-圖論

四、最小生成樹(shù)問(wèn)題及其算法第五十一頁(yè)，共八十六頁(yè)，編輯于2023年，星期三Kruskal算法思想：在不形成圈得條件下，優(yōu)先挑選權(quán)小的邊形成生成樹(shù)。76788334245v1v2v3v4v5v6v7683324v1v2v3v4v5v6v7數(shù)學(xué)建模-圖論

四、最小生成樹(shù)問(wèn)題及其算法第五十二頁(yè)，共八十六頁(yè)，編輯于2023年，星期三注：算法構(gòu)造的最小生成樹(shù)的邊集為E1；標(biāo)號(hào)l

具有性質(zhì)：當(dāng)且僅當(dāng)u、v之間有一條僅由E1

中的邊形成的路時(shí)，l(u)=l(v)，因此在步驟(2)發(fā)現(xiàn)l(u)=l(v)時(shí)，(u,v)不能放入E1，否則會(huì)形成一個(gè)圈。

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

四、最小生成樹(shù)問(wèn)題及其算法第五十三頁(yè)，共八十六頁(yè)，編輯于2023年，星期三542023年6月10日

四、最小生成樹(shù)問(wèn)題及其算法數(shù)學(xué)建模-圖論第五十四頁(yè)，共八十六頁(yè)，編輯于2023年，星期三552023年6月10日

四、最小生成樹(shù)問(wèn)題及其算法數(shù)學(xué)建模-圖論第五十五頁(yè)，共八十六頁(yè)，編輯于2023年，星期三562023年6月10日

四、最小生成樹(shù)問(wèn)題及其算法數(shù)學(xué)建模-圖論運(yùn)行結(jié)果如下：T=135163266674c=26上述例題的matlab程序如下：b=[11223334556;26364677677;24458378376];Krusf(b,1);76788334245v1v2v3v4v5v6v7683324v1v2v3v4v5v6v7第五十六頁(yè)，共八十六頁(yè)，編輯于2023年，星期三572023年6月10日

四、最小生成樹(shù)問(wèn)題及其算法數(shù)學(xué)建模-圖論

第五十七頁(yè)，共八十六頁(yè)，編輯于2023年，星期三582023年6月10日

四、最小生成樹(shù)問(wèn)題及其算法數(shù)學(xué)建模-圖論第五十八頁(yè)，共八十六頁(yè)，編輯于2023年，星期三592023年6月10日

四、最小生成樹(shù)問(wèn)題及其算法數(shù)學(xué)建模-圖論第五十九頁(yè)，共八十六頁(yè)，編輯于2023年，星期三602023年6月10日

四、最小生成樹(shù)問(wèn)題及其算法數(shù)學(xué)建模-圖論

運(yùn)行結(jié)果如下：T=116663263574c=24336876788334245v1v2v3v4v5v6v7第六十頁(yè)，共八十六頁(yè)，編輯于2023年，星期三64686865505061456054例：分別利用Kruskal算法和Prim算法如圖G的最小生成樹(shù)：

四、最小生成樹(shù)問(wèn)題及其算法數(shù)學(xué)建模-圖論第六十一頁(yè)，共八十六頁(yè)，編輯于2023年，星期三稱經(jīng)過(guò)圖G=(V,E)的每條邊恰好一次的路為Euler路徑，經(jīng)過(guò)G的每條邊恰好一次的回路為Euler回路。稱有Euler回路的圖為

Euler圖

五、E圖與H圖問(wèn)題數(shù)學(xué)建模-圖論命題：G是Euler圖當(dāng)且當(dāng)G連通且沒(méi)有度數(shù)為奇數(shù)的點(diǎn)；

G有Euler路徑當(dāng)且僅當(dāng)G連通且沒(méi)有或只有二個(gè)度數(shù)為基數(shù)的點(diǎn)。ABCD4個(gè)點(diǎn)的度數(shù)皆為奇數(shù)，不存在Euler路第六十二頁(yè)，共八十六頁(yè)，編輯于2023年，星期三中國(guó)郵遞員問(wèn)題：

一個(gè)郵遞員從郵局取出郵件后，需要到他管轄區(qū)域內(nèi)的每條街道進(jìn)行投遞，送完郵件后返回郵局，問(wèn)如何選擇一條總路程最短的投遞路線？以街道為邊，街道的交叉口或端點(diǎn)為點(diǎn)，街道的長(zhǎng)度為權(quán)，構(gòu)造賦權(quán)圖G=(V,E,w)。投遞路線應(yīng)是一條經(jīng)過(guò)G的每條邊至少一次的回路。數(shù)學(xué)建模-圖論

五、E圖與H圖問(wèn)題第六十三頁(yè)，共八十六頁(yè)，編輯于2023年，星期三將G的度數(shù)為奇數(shù)的點(diǎn)（必為偶數(shù)個(gè)）兩個(gè)一組、兩個(gè)一組用最短路連結(jié)起來(lái)。43334333a

2

b

2

c

2

de3f2g2hi4

j2k2l24322如何分組可以使得重復(fù)路徑的總長(zhǎng)度最短？23222數(shù)學(xué)建模-圖論

五、E圖與H圖問(wèn)題第六十四頁(yè)，共八十六頁(yè)，編輯于2023年，星期三數(shù)學(xué)建模-圖論

五、E圖與H圖問(wèn)題若G是Euler圖，則任何一條Euler回路是最短投遞路線,都滿足條件，針對(duì)這種情況，F(xiàn)leury提出一種算法，能夠在Euler圖中找出Euler路徑，解決了郵遞員問(wèn)題；若G不是Euler圖，則投遞路線將重復(fù)經(jīng)過(guò)某些街道，最優(yōu)投遞路線應(yīng)使得重復(fù)經(jīng)過(guò)的街道的總長(zhǎng)度最短。例如，確定右圖是否Euler圖，若是，找出圖中的Euler回路。236

5

41第六十五頁(yè)，共八十六頁(yè)，編輯于2023年，星期三662023年6月10日數(shù)學(xué)建模-圖論

五、E圖與H圖問(wèn)題第六十六頁(yè)，共八十六頁(yè)，編輯于2023年，星期三672023年6月10日數(shù)學(xué)建模-圖論

五、E圖與H圖問(wèn)題第六十七頁(yè)，共八十六頁(yè)，編輯于2023年，星期三682023年6月10日數(shù)學(xué)建模-圖論

五、E圖與H圖問(wèn)題第六十八頁(yè)，共八十六頁(yè)，編輯于2023年，星期三692023年6月10日數(shù)學(xué)建模-圖論

五、E圖與H圖問(wèn)題第六十九頁(yè)，共八十六頁(yè)，編輯于2023年，星期三702023年6月10日數(shù)學(xué)建模-圖論

五、E圖與H圖問(wèn)題第七十頁(yè)，共八十六頁(yè)，編輯于2023年，星期三712023年6月10日數(shù)學(xué)建模-圖論

五、E圖與H圖問(wèn)題上述例題的Matlab程序如下：cleard=[011111;101111;110111;111011;111101;111110];T=Fleuf1(d);236

5

41第七十一頁(yè)，共八十六頁(yè)，編輯于2023年，星期三例：確定所示的賦權(quán)圖是否Euler圖，若是，找出圖中的Euler回路。數(shù)學(xué)建模-圖論

五、E圖與H圖問(wèn)題第七十二頁(yè)，共八十六頁(yè)，編輯于2023年，星期三732023年6月10日數(shù)學(xué)建模-圖論

五、E圖與H圖問(wèn)題運(yùn)行結(jié)果如下：T=1543554321c=5d=0100110100010100010110010第七十三頁(yè)，共八十六頁(yè)，編輯于2023年，星期三稱經(jīng)過(guò)圖G=(V,E)的每個(gè)點(diǎn)恰好一次的路為Hamilton路，經(jīng)過(guò)G的每個(gè)點(diǎn)恰好一次的回路為Hamilton回路。稱有Hamilton回路的圖為Hamilton圖。1112345678910121314151617181920十二面體的平面嵌入為Hamilton圖Hamilton圖與Euler圖在定義上很相似，但判斷一個(gè)圖是否Hamilton圖較判斷它是否Euler圖要困難得多，目前還沒(méi)有易驗(yàn)證的充要條件。數(shù)學(xué)建模-圖論

五、E圖與H圖問(wèn)題第七十四頁(yè)，共八十六頁(yè)，編輯于2023年，星期三在國(guó)際象棋中，馬跳動(dòng)一次只能沿著一個(gè)2×3的長(zhǎng)方形的對(duì)角線從一個(gè)角跳到另一個(gè)角，問(wèn)是否存在一串符合規(guī)定的著法使得馬可以從任一格子出發(fā)跳遍8×8的整個(gè)棋盤，并只到達(dá)每個(gè)格子一次？

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

五、E圖與H圖問(wèn)題第七十五頁(yè)，共八十六頁(yè)，編輯于2023年，星期三旅行推銷員問(wèn)題（貨郎擔(dān)問(wèn)題）一個(gè)推銷員要去一些城市訪問(wèn)他的客戶然后返回出發(fā)城市，問(wèn)如何選擇旅行路線可以使得總路程最短？

以城市為點(diǎn)，以兩個(gè)城市之間的旅行距離為權(quán)，構(gòu)造一個(gè)賦權(quán)完全圖G=(V,E,w)。推銷員的旅行路線應(yīng)是G

的一條經(jīng)過(guò)每個(gè)點(diǎn)至少一次的回路，且回路的長(zhǎng)度盡可能短。

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

五、E圖與H圖問(wèn)題第七十六頁(yè)，共八十六頁(yè)，編輯于2023年，星期三與最短路問(wèn)題相反，至今未找到有求解旅行商問(wèn)題的有效算法，我們?cè)噲D尋找一個(gè)比較好的方法，但不一定是最優(yōu)解；首先給出近似最優(yōu)的改良后的最鄰近算法，稱為改良圈算法，改良圈算法是一種近似算法，給出的結(jié)果不一定是最優(yōu)的，但是有理由認(rèn)為它常常是比較好的。該算法的matlab程序?yàn)椋簲?shù)學(xué)建模-圖論

五、E圖與H圖問(wèn)題第七十七頁(yè)，共八十六頁(yè)，編輯于2023年，星期三782023年6月10日數(shù)學(xué)建模-圖論

五、