運(yùn)輸配送圖與網(wǎng)絡(luò)分析

圖與網(wǎng)絡(luò)分析問題提出應(yīng)用：生產(chǎn)組織，郵遞員問題，通訊網(wǎng)絡(luò)等。哥尼斯堡七橋問題1ABCD哥尼斯堡七橋問題在圖中找一條經(jīng)過每邊一次且僅一次的路——?dú)W拉回路。ADBC由點(diǎn)和邊組成2“環(huán)球旅行”問題在圖中找一條經(jīng)過每個(gè)點(diǎn)一次且僅一次的路——哈密爾頓回路?！爸袊]路問題”在圖中找一條經(jīng)過每邊的最短路——類似帶權(quán)的歐拉回路。“貨郎擔(dān)問題”在圖中找一條經(jīng)過每個(gè)點(diǎn)一次且僅一次的最短路——帶權(quán)的哈密爾頓回路。3在實(shí)際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關(guān)系，常常在紙上用點(diǎn)和線來畫出各式各樣的示意圖。

例1:圖1是我國北京、上海、重慶等十四個(gè)城市之間的鐵路交通圖，這里用點(diǎn)表示城市，用點(diǎn)與點(diǎn)之間的線表示城市之間的鐵路線。一、圖與網(wǎng)絡(luò)的基本知識(shí)太原重慶武漢南京徐州連云港上海鄭州石家莊塘沽青島濟(jì)南天津北京圖14可編輯ppt例2:有六支球隊(duì)進(jìn)行足球比賽，我們分別用點(diǎn)v1…v6表示這六支球隊(duì)。它們之間的比賽情況，也可以用圖反映出來，已知v1隊(duì)?wèi)?zhàn)勝v2隊(duì)，v2隊(duì)?wèi)?zhàn)勝v3隊(duì)，v3隊(duì)?wèi)?zhàn)勝v5隊(duì)，如此等等。這個(gè)勝負(fù)情況，可以用圖2所示的有向圖反映出來。v3v1v2v4v6v5圖2一、圖與網(wǎng)絡(luò)的基本知識(shí)5可編輯ppt1.圖的基本概念例1:鐵路交通圖例2:球隊(duì)比賽圖點(diǎn):表示研究對(duì)象.連線：表示兩個(gè)對(duì)象之間的某種特定關(guān)系。關(guān)系的對(duì)稱性：兩對(duì)象之間的關(guān)系可互換。6

邊：不帶箭頭的聯(lián)線，表示對(duì)稱關(guān)系?；。簬Ъ^的聯(lián)線，表示不對(duì)稱關(guān)系。無向圖：簡(jiǎn)稱圖，由點(diǎn)和邊組成。表示為：G=（V，E）V--點(diǎn)集合E--邊集合例：右圖V={v1，v2，v3，v4}E={e1，e2，…,e7}e1=[v1,v2]e2=[v1,v2],…,e7=[v4,v4]7

有向圖：由點(diǎn)和弧組成。表示為：D=（V，A）V--點(diǎn)集合A--弧集合點(diǎn)數(shù):p(G)或p(D)邊數(shù):q(G)弧數(shù):q(D)v1v2v3v4v5例：右圖V={v1，v2,…,v5}A={a1，a2,…,a7}a1={v1,v5},a2={v5,v4},…,a7={v1,v4}8無向圖的有關(guān)概念端點(diǎn):e=[u,v]∈E,則u,v是e的端點(diǎn),稱u,v相鄰.關(guān)聯(lián)邊:e是點(diǎn)u,v的關(guān)聯(lián)邊.環(huán):若u=v,e是環(huán).多重邊:兩點(diǎn)之間多于一條邊.簡(jiǎn)單圖:無環(huán),無多重邊的圖.多重圖:無環(huán),允許有多重邊的圖.9

次:以點(diǎn)v為端點(diǎn)的邊的個(gè)數(shù)稱為v的次.表示為:d(v)懸掛點(diǎn):次為1的點(diǎn).懸掛邊:懸掛點(diǎn)的關(guān)聯(lián)邊.孤立點(diǎn):次為0的點(diǎn).奇點(diǎn):次為奇數(shù)的點(diǎn).偶點(diǎn):次為偶數(shù)的點(diǎn).孤立點(diǎn)懸掛邊10定理1:圖G=(V,E)中,所有點(diǎn)的次之和是邊數(shù)的兩倍,即:定理2:任意一圖中,奇點(diǎn)的個(gè)數(shù)為偶數(shù).

證明:設(shè)V1--奇點(diǎn)的集合,V2--偶點(diǎn)的集合偶數(shù)偶數(shù)偶數(shù)11一、樹及其性質(zhì)在各種各樣的圖中，有一類圖是十分簡(jiǎn)單又非常具有應(yīng)用價(jià)值的圖，這就是樹。樹在自然科學(xué)和社會(huì)科學(xué),特別是在計(jì)算機(jī)科學(xué)領(lǐng)域中有廣泛的應(yīng)用。例：已知有六個(gè)城市，它們之間要架設(shè)電話線，要求任意兩個(gè)城市均可以互相通話，并且電話線的總長(zhǎng)度最短。第二節(jié)樹v6v3v4v2v5v1六個(gè)城市的一個(gè)電話網(wǎng)就作成一個(gè)圖。這個(gè)圖必須是連通圖。這個(gè)圖必須是無圈的。圖是一個(gè)不含圈的連通圖，代表了一個(gè)電話線網(wǎng)。v6v3v4v2v5v112可編輯ppt再比如，乒乓球單打比賽抽簽后的對(duì)陣形式以及企業(yè)的組織結(jié)構(gòu)圖等。ABCDEFGH總經(jīng)理市場(chǎng)總監(jiān)常務(wù)副總經(jīng)理學(xué)術(shù)總監(jiān)市場(chǎng)總學(xué)術(shù)總教質(zhì)部研發(fā)部人事部第二節(jié)樹13可編輯ppt二、圖的生成（支撐）樹定義15設(shè)圖K=(V,E’)是圖G=(V,E)的一生成（支撐）子圖,如果圖K=(V,E’)是一個(gè)樹,那么稱K是G的一個(gè)生成樹。G中屬于生成樹的邊稱為樹枝，不在生成樹上的邊稱為弦。例如,圖3b是圖3a的一個(gè)生成樹。圖3v6v5v2v3v4v1av6v5v2v3v4v1b顯然，如果圖K=(V,E’)是圖G=(V,E)的一個(gè)生成樹，那么K的邊數(shù)是n(G)-1，G中不屬于生成樹K的邊數(shù)是m(G)-n(G)+1。第二節(jié)樹14可編輯ppt圖的生成樹的求法1：定理7充分性的證明，提供了一個(gè)尋找連通圖生成樹的方法,叫做“破圈法”。就是從圖中任取一個(gè)圈，去掉一條邊。再對(duì)剩下的圖重復(fù)以上步驟，直到不含圈時(shí)為止，這樣就得到一個(gè)生成樹。例:用破圈法求下圖的一個(gè)生成樹。V5V4V2V3V1e6e5e4e3e2e1e7e8第二節(jié)樹15可編輯ppt圈(v1,v2,v3,v1)去e3；圈(v1,v2,v4,v3,v1)去e4

；圈(v3,v4v5,v3)去e6

；圈(v1,v2,v5,v4,v3,v1)去e7；得到生成樹，如圖所示。v2e1e2e5e8v1v3v4圖8-12V5V4V2V3V1e6e5e4e3e2e1e7e8第二節(jié)樹16可編輯ppt三、最小生成樹問題定義16連通圖G=（V，E），每條邊上有非負(fù)權(quán)L(e)。一棵生成樹所有樹枝上權(quán)的總和，稱為這個(gè)生成樹的權(quán)。具有最小權(quán)的生成樹稱為最小生成樹（最小支撐樹），簡(jiǎn)稱最小樹。這里所指的權(quán)，是具有廣義的數(shù)量值。根據(jù)實(shí)際研究問題的不同，可以具有不同的含義。例如長(zhǎng)度、費(fèi)用、流量等等。如前所述，在已知的幾個(gè)城市之間聯(lián)結(jié)電話線網(wǎng)，要求總長(zhǎng)度最短或總建設(shè)費(fèi)用最少，這個(gè)問題的解決可以歸結(jié)為最小支撐樹問題。再如，城市間交通線的建造等，都可以歸結(jié)為這一類問題。第二節(jié)樹17可編輯ppt求最小生成樹的常用方法有破圈法：①在網(wǎng)絡(luò)圖中尋找一個(gè)圈。若不存在圈，則已經(jīng)得到最短樹或網(wǎng)絡(luò)不存在最短樹；②去掉該圈中權(quán)數(shù)最大的邊；反復(fù)重復(fù)①②兩步，直到得到最小生成樹。例5某六個(gè)城市之間的道路網(wǎng)如圖4a所示，要求沿著已知長(zhǎng)度的道路聯(lián)結(jié)六個(gè)城市的電話線網(wǎng)，使得電話線的總長(zhǎng)度最短。v6v5v2v3v4圖4av1627535441第二節(jié)樹18可編輯ppt解：這個(gè)問題就是求賦權(quán)圖的最小支撐樹。用破圈法求解。v3v2v1v4v6v553142圖8.13bv6v5v2v3v4圖8.13av1627535441第二節(jié)樹19可編輯ppt課堂練習(xí)第二節(jié)樹20可編輯ppt主頁小島A小島B21可編輯ppt歐拉

（LeonhardEuler公元1707-1783年）22可編輯ppt判斷下列圖形能否一筆畫圖1圖5圖4圖3圖2不連通的圖形不能一筆畫

連通的圖形有可能一筆畫23可編輯ppt觀察下列圖形，完成統(tǒng)計(jì)表

圖7圖5圖1圖8圖6圖4圖3圖2可以一筆畫的圖形不能一筆畫的圖形圖形序號(hào)奇點(diǎn)個(gè)數(shù)偶點(diǎn)個(gè)數(shù)

圖形序號(hào)奇點(diǎn)個(gè)數(shù)偶點(diǎn)個(gè)數(shù)

24可編輯ppt不連通的圖形不能一筆畫

連通的圖形有可能一筆畫全都是偶點(diǎn)的連通圖可以一筆畫

奇點(diǎn)個(gè)數(shù)超過兩個(gè)的連通圖形不能一筆畫畫時(shí)以任一點(diǎn)為起點(diǎn)，最后仍回到該點(diǎn)畫時(shí)以一個(gè)奇點(diǎn)為起點(diǎn)，另一個(gè)奇點(diǎn)為終點(diǎn)有兩個(gè)奇點(diǎn)的連通圖可以一筆畫

25可編輯ppt你能筆尖不離紙，一筆畫出圖中的每個(gè)圖形嗎？26可編輯ppt判斷下列圖形能否一筆畫圖5圖4圖3圖2圖6圖127可編輯ppt下圖是一個(gè)公園的平面圖，要使游人走遍每一條路不重復(fù)，出口和入口應(yīng)設(shè)在哪兒？28可編輯ppt甲郵局

乙甲乙兩個(gè)郵遞員去送信，兩人以同樣的速度走遍所有的街道，甲從A點(diǎn)出發(fā)，乙從B點(diǎn)出發(fā)，最后都回到郵局（C）。如果要選擇最短的線路，誰先回到郵局？29可編輯ppt主頁30可編輯ppt二、奇偶點(diǎn)圖上作業(yè)法（1）找出圖G中的所有的奇頂點(diǎn)，把它們兩兩配成對(duì)，而每對(duì)奇點(diǎn)之間必有一條通路，把這條通路上的所有邊作為重復(fù)邊追加到圖中去，這樣得到的新連通圖必?zé)o奇點(diǎn)。（2）如果邊e=（u,v）上的重復(fù)邊多于一條，則可從重復(fù)邊中去掉偶數(shù)條，使得其重復(fù)邊至多為一條，圖中的頂點(diǎn)仍全部都是偶頂點(diǎn)。（3）檢查圖中的每一個(gè)圈，如果每一個(gè)圈的重復(fù)邊的總長(zhǎng)不大于該圈總長(zhǎng)的一半，則已經(jīng)求得最優(yōu)方案。如果存在一個(gè)圈，重復(fù)邊的總長(zhǎng)大于該圈總長(zhǎng)的一半時(shí)，則將這個(gè)圈中的重復(fù)邊去掉，再將該圈中原來沒有重復(fù)邊的各邊加上重復(fù)邊，其它各圈的邊不變，返回步驟（2）。31可編輯ppt判定標(biāo)準(zhǔn)1:在最優(yōu)郵遞路線上，圖中的每一條邊至多有一條重復(fù)邊。判定標(biāo)準(zhǔn)2:

在最優(yōu)郵遞路線上，圖中每一個(gè)圈的重復(fù)邊總權(quán)小于或等于該圈總權(quán)的一半。32可編輯pptABCDEGHIJKNML1111222211322122圖133可編輯ppt求解步驟：1、在線性圖中，添加?。措p線條），使得到的新圖上沒有奇點(diǎn)，如圖2所示。（注意：如果郵遞員走遍所有的路段，則路線圖上所有的點(diǎn)都必須變成偶點(diǎn)，每一個(gè)點(diǎn)至少有一進(jìn)一出。）ABCDEGHIJKNML1111222211322122圖234可編輯ppt2、調(diào)整添弧，使每個(gè)圈的添弧總長(zhǎng)度不大于圈總長(zhǎng)度的一半。ABCDEGHIJKNML1111222211322122圖3總長(zhǎng)度為6，而添弧總長(zhǎng)度為5，所以去掉原來的添弧B-H,H-I和C-I,在該圈未添弧的路段B-C上添弧。35可編輯ppt總長(zhǎng)度為8，而添弧總長(zhǎng)度為5，所以去掉原來的添弧I-K,I-M,在該圈未添弧的路段K-N,M-N上添弧。ABCDEGHIJKNML1111222211322122圖436可編輯pptABCDEGHIJKNML1111222211322122圖53、最優(yōu)解：在圖5中，所