圖論與網(wǎng)絡(luò)分析

第1頁，共29頁，2023年，2月20日，星期四第七章圖論與網(wǎng)絡(luò)分析運(yùn)用圖論中的分析技術(shù)可以解決現(xiàn)實(shí)世界的許多問題，如交通網(wǎng)、管道網(wǎng)、通信網(wǎng)的優(yōu)化以及工程進(jìn)度安排等問題。除此之外，還有很多問題，從表面上看似乎與網(wǎng)絡(luò)毫無關(guān)系，但實(shí)質(zhì)上也可以用網(wǎng)絡(luò)模型來描寫，例如設(shè)備更新的優(yōu)化問題，就可以表述為網(wǎng)絡(luò)分析中的最短路問題。通過學(xué)習(xí)本章，應(yīng)當(dāng)了解圖與網(wǎng)絡(luò)的基本概念；掌握最短路問題、最大流問題和最小費(fèi)用最大流問題的圖論解法，并會對管理中的實(shí)際問題進(jìn)行分析判別其是哪一類圖論問題；學(xué)會運(yùn)用WinQSB來求解經(jīng)濟(jì)管理中的圖與網(wǎng)絡(luò)問題。2第2頁，共29頁，2023年，2月20日，星期四第一節(jié)圖的基本概念及圖的模型一、圖的基本概念及圖的模型概述瑞士數(shù)學(xué)家歐拉(E.Euler)在1736年發(fā)表了一篇題為“依據(jù)幾何位置的解題方法”的論文，有效地解決了哥尼斯堡七橋難題，這是有記載的第一篇圖論論文，歐拉被公認(rèn)為圖論的創(chuàng)始人。18世紀(jì)的哥尼斯堡城中流過一條河(普列格河)。河上有七座橋連接著河的兩岸和河中的兩個小島，如圖7-1(a)所示。歐拉將此問題歸結(jié)為圖7-1(b)，這是一個用圖的模型來描述和解決實(shí)際問題的第一個著名例子。3第3頁，共29頁，2023年，2月20日，星期四一、圖的基本概念及圖的模型概述1857年英國數(shù)學(xué)家哈密頓(Hamilton)發(fā)明了一種游戲，他用一個實(shí)心正12面體象征地球，正12面體的20個頂點(diǎn)分別表示世界上20座城市，要求游戲者從任一城市出發(fā)，尋找一條可經(jīng)由每個城市一次且僅一次再回到原出發(fā)點(diǎn)的路，這就是“環(huán)球旅行”問題。它與七橋問題不同，前者要在圖中找一條經(jīng)過每邊一次且僅一次的路，通稱歐拉回路，而后者是要在圖中找一條經(jīng)過每個點(diǎn)一次且僅一次的路，通稱為哈密爾頓回路。哈密爾頓根據(jù)這個問題的特點(diǎn)，給出了一種解法，如圖7-2粗箭線所示。4第4頁，共29頁，2023年，2月20日，星期四二、圖模型舉例例7-1化工品的貯存問題?，F(xiàn)要求貯藏8種化工品A，B，C，D，P，R，S，T。出于安全的原因，下面各組產(chǎn)品不能放在一起：A-R，A-C，A-T，R-P，P-S，S-T，T-B，B-D，D-C，R-S，R-B，P-D，S-C，S-D。問題：貯藏這8種化工品至少需要多少間貯藏室？解（參見教材P164）例7-2農(nóng)夫、狼、羊、草過河問題。有位農(nóng)夫，攜帶一匹狼、一只羊和一挑草要過一條小河，河中只有一條小船，一次擺渡農(nóng)夫只能攜帶一樣?xùn)|西。當(dāng)農(nóng)夫不在場時，狼要吃羊，羊要吃草。試問：農(nóng)夫怎樣才能將這三樣?xùn)|西擺渡到對岸？至少要擺渡幾次？解（參見教材P165）5第5頁，共29頁，2023年，2月20日，星期四第二節(jié)圖論中的基本概念6第6頁，共29頁，2023年，2月20日，星期四第二節(jié)圖論中的基本概念在圖7-6中“相互認(rèn)識”用兩條反向的弧來表示。7第7頁，共29頁，2023年，2月20日，星期四第三節(jié)最短路問題8第8頁，共29頁，2023年，2月20日，星期四一、求解最短路問題的狄克斯托算法9第9頁，共29頁，2023年，2月20日，星期四一、求解最短路問題的狄克斯托算法10第10頁，共29頁，2023年，2月20日，星期四二、最短路問題的應(yīng)用解（參見教材P171）11第11頁，共29頁，2023年，2月20日，星期四二、最短路問題的應(yīng)用解（參見教材P173）12第12頁，共29頁，2023年，2月20日，星期四第四節(jié)最小生成樹問題樹是圖論中結(jié)構(gòu)最簡單但又十分重要的圖，在自然科學(xué)和社會科學(xué)的許多領(lǐng)域都有廣泛的應(yīng)用。例如，在架設(shè)電話線、鋪設(shè)自來水管道或暖氣管道的工程設(shè)計中會遇到如下的優(yōu)化問題：如何使通話點(diǎn)或者取水取暖點(diǎn)相互連通，但總的線路長度最短。這類問題在網(wǎng)絡(luò)分析中稱為最小生成樹問題。13第13頁，共29頁，2023年，2月20日，星期四一、求解最小生成樹問題的破圈算法和避圈算法(一)樹的概念和性質(zhì)(二)生成樹和最小生成樹14第14頁，共29頁，2023年，2月20日，星期四一、求解最小生成樹問題的破圈算法和避圈算法(三)求解最小生成樹的破圈算法和避圈算法1．破圈法具體步驟如下。(1) 在給定的賦權(quán)的連通圖上任找一個圈。(2) 在所找的圈中去掉一條權(quán)數(shù)最大的邊(如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條)。(3) 如果所余下的圖已不含圈，則計算結(jié)束，所余下的圖即為最小生成樹。否則返回步驟(1)。15第15頁，共29頁，2023年，2月20日，星期四一、求解最小生成樹問題的破圈算法和避圈算法2．避圈法初始選一條最小權(quán)的邊，以后每一步中總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈(每一步中，如果有兩條或兩條以上的邊都是權(quán)最小的邊，則從中任選一條)。具體步驟如下。(1) 在給定的賦權(quán)的連通圖上選取一條最小權(quán)的邊。(2) 從未被選取的邊中選取一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈。如果有兩條或兩條以上的邊都是權(quán)最小的邊，則從中任選一條。(3) 重復(fù)步驟(2)。如果這樣的邊不存在，則計算結(jié)束。16第16頁，共29頁，2023年，2月20日，星期四二、最小生成樹問題的應(yīng)用解（參見教材P179）17第17頁，共29頁，2023年，2月20日，星期四第五節(jié)最大流問題最大流問題是一類應(yīng)用極為廣泛的問題。例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流，供水網(wǎng)絡(luò)中有水流，金融系統(tǒng)中有現(xiàn)金流，通信系統(tǒng)中有信息流，等等。對于這些包含了流量問題的系統(tǒng)，往往要求求出其系統(tǒng)的最大流量。例如，某公路系統(tǒng)容許通過的最多車輛數(shù)、某供水系統(tǒng)的最大水流量等，以便我們加深對某個系統(tǒng)的認(rèn)識并加以改造。所謂最大流問題就是：給了一個帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱為容量，在不超過每條弧容量的前提下，求出從發(fā)點(diǎn)到收點(diǎn)的最大流量。18第18頁，共29頁，2023年，2月20日，星期四一、最大流的數(shù)學(xué)模型解（參見教材P181）19第19頁，共29頁，2023年，2月20日，星期四二、最大流問題的網(wǎng)絡(luò)圖論解法(一)對網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)(二)求最大流的基本算法20第20頁，共29頁，2023年，2月20日，星期四第六節(jié)最小費(fèi)用最大流問題在前面討論的最大流問題中沒有涉及費(fèi)用問題。但在實(shí)際生活中，各種物質(zhì)的流都是與費(fèi)用有關(guān)的。如一輛載貨汽車經(jīng)過不同的路線，可能要交不同的過路費(fèi)、過橋費(fèi)等，這樣對于司機(jī)來說就有一個到達(dá)某一目的地走哪條路線最省錢的問題。最小費(fèi)用最大流就是這樣的問題。所謂最小費(fèi)用最大流問題就是：給了一個帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，對于每條弧，除了給出了容量外，還給出了這條弧的單位流量的費(fèi)用，要求一個最大流F，并使得總運(yùn)送費(fèi)用最小。21第21頁，共29頁，2023年，2月20日，星期四一、最小費(fèi)用最大流的數(shù)學(xué)模型解（參見教材P186）22第22頁，共29頁，2023年，2月20日，星期四二、最小費(fèi)用最大流的網(wǎng)絡(luò)圖論解法(一)對網(wǎng)絡(luò)上弧的容量和單位流量費(fèi)用的表示作改進(jìn)(二)求最小費(fèi)用最大流的基本算法23第23頁，共29頁，2023年，2月20日，星期四第七節(jié)中國郵遞員問題一、哥尼斯堡七橋問題與歐拉圖定理1無向連通圖G是歐拉圖，當(dāng)且僅當(dāng)G中無奇點(diǎn)。(證明從略)定理2連通有向圖D是歐拉圖，當(dāng)且僅當(dāng)它每個頂點(diǎn)的出次等于入次。與七橋問題類似的還有一筆畫的問題。給出一個圖形，要求判定是否可以一筆畫出。一種是經(jīng)過每邊一次且僅一次到另一點(diǎn)停止，另一種是經(jīng)過每邊一次且僅一次回到原出發(fā)點(diǎn)。這兩種情況可分別用歐拉道路和歐拉回路的判定條件加以解決。24第24頁，共29頁，2023年，2月20日，星期四二、中國郵遞員問題中國郵遞員問題是歐拉回路問題的擴(kuò)展，它是由中國數(shù)學(xué)家管梅谷先生在1962年提出的，因此國際上通稱為中國郵遞員問題。一個郵遞員，負(fù)責(zé)某一地區(qū)的信件投遞。他每天要從郵局出發(fā)，走遍該地區(qū)所有街道再返回郵局，問：應(yīng)如何安排送信的路線使所走的總路程最短？用圖論的語言來描述：給定一個連通圖G，每邊有非負(fù)權(quán)，要求一條回路過每邊至少一次，且滿足總權(quán)最小。25第25頁，共29頁，2023年，2月20日，星期四三、求解中國郵遞員問題的奇偶點(diǎn)圖作業(yè)法及其改進(jìn)(一)求解中國郵遞員問題的奇偶點(diǎn)圖作業(yè)法(1) 如何構(gòu)造第一個可行方案。(2) 尋找改進(jìn)的可行方案。(二)奇偶點(diǎn)圖作業(yè)法的改進(jìn)方法26第26頁，共29頁，2023