第四章圖論模型

1、 Zm 第四章 圖論模型現(xiàn)實世界的許多實際問題都可以用圖形來解釋或說明.例如通訊網絡就可以用圖的形式直觀的表現(xiàn)出來：點可以表示通訊中心，而邊表示通訊線路.圖論模型是應用十分廣泛的數(shù)學模型,它已經在物理、化學、控制論、信息論、科學管理和計算機等領域.由于它具有圖形直觀，方法簡單容易掌握的特點，因此在實際、生活和數(shù)學建模中，有許多問題可以運用圖論的理論和方法解決.§4.1圖論起源圖論起源于18世紀歐拉對哥尼斯堡七橋問題的研究.哥尼斯堡是18世紀東普魯士的一個城市，城中有一條普雷格爾河，河中有兩個島，河上有七座橋，如圖1所示. 圖1當時那里的居民熱終于思考這樣一個問題，一個人能否經過七座橋

2、且每座橋只走過一次，最后回到出發(fā)點.能否用數(shù)學的方法解決這個問題一貫成為當時居民的一個懸而未決的問題.1736年歐拉創(chuàng)造性的將陸地用點表示，橋用邊表示，從而將這個問題轉化為如圖2所示的一筆畫問題，即能否從某個點開始一筆畫出這個圖形，最后回到原點而不重復.歐拉證明了這個問題是不可能的. 圖2歐拉解決七橋問題時，其方法超出了常用的數(shù)學方法，充分發(fā)揮自己的想象力，用了全新的思想方法，從而使得問題得到完美解決.由于這一項開創(chuàng)性的工作，產生了“圖論”這門嶄新學科，歐拉被認為是圖論的創(chuàng)始人.歐拉路:在圖中，若存在一條路，經過每邊一次且僅一次（不會到起點），這樣的路稱作歐拉路。歐拉回路：若此路為回路（回到起

3、點）則為歐拉回路。歐拉定理：若圖中存在歐拉路則途中有兩個奇數(shù)結點或者零個奇數(shù)結點。若存在歐拉回路則不存在奇數(shù)結點。§4.2基本概念定義1 圖由兩個點集合以及邊集合組成，記為，其中：(1)是頂點構成的集合；(2)是連接某些頂點對構成的邊組成的集合.例1 ，畫出圖.圖3注：圖分為無向圖和有向圖.定義2 若圖的邊均沒有方向，這樣的圖成為無向圖.例如圖2，圖3為無向圖.無向圖的邊稱為無向邊，無向邊是由兩個頂點構成的無序對，無序對通常用圓括號表示.例2 表示一條無向邊，與是同一條邊.定義3 若圖的邊均有方向，這樣的圖稱為有向圖.有向圖的邊稱為有向邊，有向邊是由兩個頂點構成的有序對，有序對通常用

4、尖括號表示.有向邊又稱為弧.例3 表示一條有向邊，與是兩條不同的有向邊.定義4 一條邊的端點稱為與這條邊關聯(lián)，反之，一條邊稱為與它的端點關聯(lián).與同一條邊關聯(lián)的兩個端點是鄰接的.如果兩邊有一個公共端點，則這兩條邊是鄰接的。兩個端點重合為一點的邊稱為圈（環(huán)），不與任何邊關聯(lián)的點成為孤立點.例4 如圖4所示，理解定義4 圖4注：若圖中和為有限集，稱圖G為有限圖,沒有任何邊的圖為空圖（零圖），只有一個點的圖稱為平凡圖。一個圖既無圈又沒有兩邊連接同一對點（平行邊）的圖稱為簡單圖。節(jié)點度數(shù)：所關聯(lián)的邊的條數(shù)，記作deg（vi），特別的，環(huán)的度數(shù)為2。例5 結合圖5理解上述概念。 圖5定義5 無向圖中前后相

5、繼連接的一串邊的集合稱為路；在有向圖中順向首尾連接的一串有向邊的集合稱為有向路。通常用順次的結點表示路。例6如圖6所示:圖6或構成一條從到的路,但是不構成一條路。例7 如圖7所示：圖7或為從到的一條路，但是或不構成一條路。定義6設圖是一個簡單圖，若對圖的每條邊(弧)都賦一個實數(shù),并稱之為該邊(弧)的權,這樣的賦權圖稱為網絡,記為，其中為的所有邊(弧)的權構成的集合。3 網絡的最短路問題問題描述：對于一個給定的網絡,其中每邊的權表示該邊的長度，那么一個很自然的問題是如何需求網絡中某個點到另一個點之間的最短路。在引入最短路算法(Dijkstra算法)前引入以下記號：表示起點到到結點的最短路長度,

6、表示邊的邊長(若邊不存在則)。3.1Dijkstra算法Step1:令,。Step2:在中尋找一點，使得，并令，。若則算法終止，否則轉Step3。Step3:對中每個點，置，轉 step2。注：該最短路算法執(zhí)行完畢，起點到任何一點的最短路長度全部求出來。例8 如圖8，求出從到的最短路。 圖8解： 第一次迭代：第二次迭代：第三次迭代：第四次迭代：第五次迭代：第六次迭代：第七次迭代：第八次迭代：第九次迭代：迭代完畢，最短路的長度為9，最短路的路徑為或。3.2最短路問題的應用1設備更新問題某工廠使用一臺設備，每年年初工廠要作出決定：是繼續(xù)使用舊設備還是更換新設備？如果繼續(xù)使用就設備就需要支付維修費；

7、如果使用新設備就需要支付設備費。試確定一個5年計劃，使得總支出費用達到最小。設備在各年的夠買費以及機器在不同役齡的維修費如表1所示。項目第1年第2年第3年第4年第5年購買費1112131414機器役齡0-11-22-33-44-5維修費5681118殘值43210 表1解：將這個問題轉化為最短路問題。用表示第年年初夠進一臺新設備，虛設一個節(jié)點表示第6年年初(即第5年年底)，邊表示第年夠進的設備一直使用到第年年初(即第年年底)，邊上的數(shù)字表示第年夠進的設備一直使用到第年年初(即第年年底)所需要支付的費用。這樣設備更新問題就轉化為：求圖9中到的最短路問題。 圖92選址問題已知某地區(qū)的交通網絡如圖1

8、0所示，其中點代表具名小區(qū)，邊岱廟公路，邊上的數(shù)字表示小區(qū)間公路距離，問去中心醫(yī)院應建在那個小區(qū)，可使離醫(yī)院最遠的小區(qū)劇名就診時所走的路程最近？圖10解：先求出到其他各點的最短路的長度，然后取最大值，記。如在求即為所求。 表2由于最小，所以醫(yī)院應該建在，此時離醫(yī)院最遠的小區(qū)的距離為48。3求圖11中到的最短路。 圖114生產策略問題：現(xiàn)代化生產過程中，生產部門面臨的突出問題之一就是如何選取合理的生產率。生產率過高，導致產品的量積壓，使流動資金不能即時回籠；生產率過低，導致產品不能滿足市場需要，使得生產部門市去獲利機會?？梢娚a部門在生產過程中必須時刻注意市場的需求變化，以便于適時調整生產率使得

9、獲得最大收益。某個生產廠家年初要制定生產策略，已預知其產品在年初的需求量為萬單位，并以萬單位/月的速度遞增。若生產產品過剩，則需付單位產品單位時間(月)的庫存保管費元；若產品短缺，則單位產品單位時間的短期損失費為元。假設生產率每調整一次帶有固定的調整費萬元，請問工廠如何制定當年的生產策略，使工廠的總損失最??？4 網絡最大流問題問題描述：最大流問題是一類應用極為廣泛的問題，例如在交通運輸網絡中有人流、車流、物流、供水系統(tǒng)中的水流、金融系統(tǒng)中的現(xiàn)金流、通信系統(tǒng)中的信息流，等等。例如有如下一個輸油管道網，為起點，為終點，其余節(jié)點為中轉站，邊上的數(shù)字表示該管道的最大輸油能力(也稱為容量)，記為，為應該

10、如何安排各管道的輸油量才能使得管道網的總輸油能力達到最大？ 圖12鋪設一個龐大的輸油管道網是一項長期的、復雜的、艱巨的系統(tǒng)工程，需要耗費大量的人力物力才能鋪設完畢。所以我們要盡可能的充分運用當前的管道網使得網管的輸油能力最大化。這就我們需要討論的網絡最大流問題的一個最直接的應用實例。為此我們將這樣的實際問題用抽象圖論的方法，然后用相關算法解決這個問題，所以首先介紹幾個定義。定義7 有向圖中每條弧上給出的最大通過能力稱為該弧的容量。定義8 給所有弧都給出了容量的有向圖稱為容量網絡。4.1容量網絡的特征給定一個容量網絡，其中表示弧的容量，并設有一個起點和一個終點，令表示通過弧的流量。顯然 (1)另

11、外網絡上每條弧上的實際流量要遵循點守恒規(guī)則： (2)(2)式稱為點守恒方程。(2)式表明起點只有流出沒有流入，終點只有流入沒有流出，中間點的流入等于流出。定義9 如果在網絡中找一條從起點到終點的路，該條路上的每條弧的流量同時滿足(1)(2),則稱網絡上的流量為可行流。注：網絡最大流問題就是要找到一條可行流使得流量達到最大。4.2弧的分類按流量分類：在容量網絡中，若給定一個可行流，我們把網絡中的弧稱為飽和??；滿足的弧稱為非飽和??；滿足的弧稱為零流弧；滿足的弧稱為非零流弧。按方向分類：在容量網絡中，若是網絡中連接起點和終點的路，定義路的方向就是起點到終點的方向。如果弧的方向與路的方向一致，這樣的弧

12、稱為正向弧，反之稱為反向弧。定義10 設是容量網絡的可行流，是一條連接起點與終點的路，若滿足以下條件：1)每條正向弧都是非飽和?。?)每條反向弧都是非零流??；則稱為增廣路。4.3網絡最大流算法Step1:由起點到終點找到一條增廣路。Step2:確定增廣路上可調整的流量值。(增廣路上的正向弧由容量減去流量，反向弧就取弧上的流量值，然后值就取這些值的最小值。)Step3:調整增廣路上的流量(使得某個孤飽和)。(增廣路上的正向弧由原流量“+”;反向弧由流量“-”。)Step4:判定從起點到終點是否存在增廣路;若存在轉Step1,否則算法終止。例9 如圖9所示，求網絡最大流。解：第一次迭代：找增廣路，

13、可調整流為調整流量：第二次迭代：找增廣路，可調整流為調整流量：第三次迭代：找增廣路，可調整流為調整流量：第四次迭代：找增廣路，可調整流為調整流量：第五次迭代：找增廣路，可調整流為調整流量：第六次迭代：找增廣路，可調整流為調整流量：網絡中已不存在增廣路，找到最大流為20。4.4最大流問題的應用(最大匹配問題)(1)二部圖(二分圖)圖，若且使得中每條邊的兩個端點必有一個屬于X，另一個屬于，則稱為二部圖，記或。例如 圖13(2)匹配對給定的二部圖，如果并且中任意兩條邊都沒有公共端點，則稱為的一個匹配，所有匹配中邊數(shù)最多的匹配稱為最大匹配。(最大匹配不一定唯一)。求最大匹配問題的方法的方法很多，網絡最

14、大流算法可以有效解決這個問題。例：多端網絡問題設有5為待業(yè)者，5項工作，他們各自能夠勝任工作的情況如圖14所示，要求設計一個就業(yè)方案，使盡量多的人能就業(yè)。其中表示工人，表示工作。圖14上圖為二部圖，在二部圖中增加兩個虛擬節(jié)點，一個發(fā)點一個收點，構成一個網絡，令各邊上的容量均為1.當網絡流量達到最大時如果弧上的流量為1就讓從事工作。采用最大流算法求解：找增廣路，確定可調整的流量為1 ：調整流量：找增廣路，確定可調整的流量為1：調整流量：找增廣路，確定可調整的流量為1：調整流量：找增廣路，確定可調整的流量為1：調整流量：已經不存在增廣路，最大流為4，從而最多可以提供4份工作，分別是：，。5最小費用

15、流問題問題描述：對于一個以為起點為終點的容量網絡(如圖15) ，每條弧上有兩個數(shù)與之有聯(lián)系，一個為弧容量，一個為單位流量通過它的費用。最小費用流問題是指要求出流量為的可行流使得費用最小。特別的，如果要求流量達到最大的可行流使得費用最小，這樣的問題又稱為最小費用最大流問題。下面介紹最小費用流算法，需要注意的是最小費用流算法一般都要求求出流量為的可行流使得費用最小。 圖155.1最小費用流算法Step1:構造費用增廣網絡(以各邊的費用作為該邊的權值)。Step2:在費用增廣網絡中找到起點到終點的最短路。Step3:在容量網絡中確定最短路上可調整的流量值。(正向弧由容量減去流量，反向弧就取流量，這些

16、數(shù)中取最小的即為。)Step4:調整最短路上的流量。(正向弧上由原流量“+”，反向弧由原流量“-”)Step5:判斷最短路上各邊是否為飽和邊，如果為飽和邊則改邊上的流量只能減少，從而改變該邊的方向，權值為原來權值的負值；如果該邊為零流弧，該邊的方向不變；如果該邊為非零流非飽和弧，表明該邊上的流量既可可以增加又可以減少，所以補一條方向相反的邊，權值為原來權值的負值。Step6:判斷網絡的流量是否等于，若小于則轉Step2,否則算法終止。特別地，算法中的流量如果等于網絡的最大流,這樣的問題稱為最小費用最大流問題.如上圖，求流量為10的最小費用。第一次迭代：構造費用增廣網絡并求起點到終點的最短路：確

17、定可調整流量為2并調整流量：構造費用增廣網絡并求起點到終點的最短路：確定可調整的流量為4并調整流量：構造費用增廣網絡并求起點到終點的最短路：確定可調整的流量為1并調整流量：構造費用增廣網絡并求起點到終點的最短路：確定可調整的流量為3并調整流量：此時流量達到10，從而最小為：。5.2最小費用流算法的應用1.求下圖所示的網絡中，求從到的目標流值為25的最小費用流，弧上括號內的數(shù)字第一個為容量，第二個為弧上單位流的費用。(17,3) (20,5)(15,4)V2(18,3)(14,5)V3V1(20,8)(12,8)vsvt2. 求下圖所示網絡的最小費用最大流, 弧上括號內的數(shù)字第一個為容量，第二個為弧