11章配送運(yùn)輸-資料下載頁(yè)
2025-01-04 02:44本頁(yè)面
【正文】 結(jié)著河的兩岸和河中的兩座小島，如圖所示。當(dāng)時(shí)那里的人熱衷于這樣的游戲：一個(gè)游者怎樣才能一次連續(xù)走過(guò)這七座橋而每座橋只走一次，回到原出發(fā)點(diǎn)。沒(méi)有人想出這種走法，又無(wú)法說(shuō)明走法不存在，這就是著名的 “七橋 ”難題。 ABCD圖 1圖實(shí)際上是反映了客觀事物之間的相互關(guān)系DCA B圖 2 后來(lái)，在 1736年，瑞士的數(shù)學(xué)家 。他將四塊陸地表示成四個(gè)結(jié)點(diǎn)，凡陸地間有橋相連的，便在兩點(diǎn)間連一條線，這樣圖 1就轉(zhuǎn)化為圖 2了。此時(shí)，哥尼斯堡七橋問(wèn)題歸結(jié)為：在圖 2 所示的圖中，從 A, B, C, D 任一點(diǎn)出發(fā)，通過(guò)每條邊一次且僅一次而返回出發(fā)點(diǎn)的回路是否存在？ 歐拉斷言這樣的回路是不存在的。理由是：從圖 2中的任一點(diǎn)出發(fā)，為了要回到原來(lái)的出發(fā)點(diǎn)，要求與每個(gè)點(diǎn)相關(guān)聯(lián)的邊數(shù)均為偶數(shù)。這樣才能保證從一條邊進(jìn)入某點(diǎn)后，再?gòu)牧硪粭l邊出去，從一個(gè)點(diǎn)的不同的兩條邊一進(jìn)一出才能回到出發(fā)點(diǎn)，而圖 2中的A, B, C, D全 是與奇數(shù)條邊相連，由此可知所要求的回路是不可能存在的。 Leonhard Euler （ 17071783） 瑞士數(shù)學(xué)家v 設(shè) G = (V,E) 是無(wú)向圖。任取 v?V，稱與 v相關(guān)聯(lián)的邊的條數(shù)為 v的度。記為 deg(v)。v 1) 當(dāng) v 的度為偶數(shù)時(shí)，稱 v 為偶結(jié)點(diǎn)。v 2) 當(dāng) v 的度為奇數(shù)時(shí)，稱 v 為奇結(jié)點(diǎn)。v 3) 當(dāng) v 的度為零時(shí)，稱 v 為孤立點(diǎn)。v 4) 當(dāng) v 的度為 1時(shí)，稱 v 為懸掛點(diǎn)。與懸掛點(diǎn)關(guān)聯(lián)的邊為懸掛邊。v 點(diǎn)、（關(guān)聯(lián)）邊、點(diǎn)、（關(guān)聯(lián)）邊、點(diǎn) …… ，交替連接，中間不間斷的序列，被稱為鏈。v 若鏈中每個(gè)點(diǎn)都不同，則稱為初等鏈。v 若鏈中每條邊都不同，則稱為簡(jiǎn)單鏈。v 若鏈中每條邊都不同，則稱為簡(jiǎn)單鏈或路。v 如果一條鏈的兩個(gè)端點(diǎn)重合，則稱這條鏈為圈。v 若圈中每個(gè)點(diǎn)都不同，則稱為初等圈。v 若圈中每條邊都不同，則稱為簡(jiǎn)單圈。v 一條路若始點(diǎn)和終點(diǎn)重合，則稱這條路為回路，也即簡(jiǎn)單圈。v 若圖中任意兩點(diǎn)間都至少存在一條鏈，則稱此圖為連通圖。v 歐拉回路與道路v 定義： 連通圖 G中，若存在一條通路，經(jīng)過(guò)每邊一次且僅一次，則稱這條道路歐拉道路。若存在一條回路，經(jīng)過(guò)每邊一次且一次，則稱這條回路為歐拉回路。v 具有歐拉回路的圖稱為歐拉圖（ E圖）。v 定理： 無(wú)向連通圖 G是歐拉圖，當(dāng)且僅當(dāng) G中無(wú)奇點(diǎn)。v 定理： 已知圖無(wú)奇點(diǎn)，則最小的充分必要條件為：v 每條邊最多重復(fù)一次；v 對(duì)圖 G中每個(gè)初等圈來(lái)講，重復(fù)邊的長(zhǎng)度不超過(guò)圈長(zhǎng)的一半我國(guó)著名數(shù)學(xué)家管梅谷教授 1962年首先提出的，被稱為 “中國(guó)郵路問(wèn)題 ”。郵遞員的工作是每天在郵局里選出郵件，然后送到他所管轄的客戶中，再返回郵局。自然地，若他要完成當(dāng)天的投遞任務(wù)，則他必須要走過(guò)他所投遞郵件的每一條街道至少一次。問(wèn)怎樣的走法使他的投遞總行程為最短？這個(gè)問(wèn)題就稱為 中國(guó)郵路問(wèn)題 。 v 例 :求解圖 816所示網(wǎng)絡(luò)的中國(guó)郵路問(wèn)題。v 再檢查圖 820。條件（ 1）、（ 2）都滿足，得到最優(yōu)方案。圖中任一歐拉回路即為最優(yōu)郵遞路線。這種方法雖然比較容易，但要檢查每個(gè)初等圈，當(dāng) G中的點(diǎn)數(shù)或邊數(shù)較多時(shí)，運(yùn)算量極大。 v 求解中國(guó)郵遞員投遞問(wèn)題的算法是怎樣的？求解中國(guó)郵遞員投遞問(wèn)題的算法實(shí)際上是一種重邊添加規(guī)則。它要求添加重邊時(shí)滿足以下兩個(gè)條件：a.每條邊最多可重復(fù)添加一次；b.在原網(wǎng)絡(luò)圖中每個(gè)（簡(jiǎn)單）圈上添加的重邊權(quán)重或邊長(zhǎng)之和不超過(guò)該圈總長(zhǎng)度的一半。v 求解中國(guó)郵遞員投遞問(wèn)題添加重邊時(shí)有何技巧？一般添加重邊可考慮，a.盡量在最小邊長(zhǎng)的邊上進(jìn)行；b.盡量在兩個(gè)相鄰奇點(diǎn)間添加，以使兩個(gè)奇點(diǎn)變?yōu)榕键c(diǎn)。謝謝觀看 /歡迎下載BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES. BY FAITH I BY FAITH
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1