圖與網(wǎng)絡(luò)

1圖論與網(wǎng)絡(luò)圖論是運(yùn)籌學(xué)中應(yīng)用十分廣泛的分支，也是和其它分支相互交融最多的分支。有大量的問題都可用圖論的方法解決：如工藝流程的設(shè)計(jì)，通信網(wǎng)絡(luò)的設(shè)計(jì)，交通網(wǎng)絡(luò)的設(shè)計(jì)，電網(wǎng)設(shè)計(jì)，城市供水、供氣網(wǎng)絡(luò)的設(shè)計(jì)以及大型商業(yè)連鎖集團(tuán)的銷售網(wǎng)絡(luò)設(shè)計(jì)，物流方案的設(shè)計(jì)等等。圖論與網(wǎng)絡(luò)的研究起源

18世紀(jì)，普魯士哥尼斯堡城中有一條河，叫普雷格爾河，河中有兩個(gè)島，并有七座橋?qū)蓚€(gè)島與河兩岸相連。當(dāng)時(shí)那里的居民熱衷于這樣一個(gè)問題：一個(gè)散步者能否走過七座橋，且每座橋只走過一次，最后回到起點(diǎn)。（哥尼斯堡七橋問題）圖論與網(wǎng)絡(luò)的研究起源

18世紀(jì)，普魯士哥尼斯堡城中有一條河，叫普雷格爾河，河中有兩個(gè)島，并有七座橋?qū)蓚€(gè)島與河兩岸相連。當(dāng)時(shí)那里的居民熱衷于這樣一個(gè)問題：一個(gè)散步者能否走過七座橋，且每座橋只走過一次，最后回到起點(diǎn)。（哥尼斯堡七橋問題）1736年歐拉將此問題歸結(jié)為如圖所示的一筆畫問題，并從理論上證明此不可行。圖論與網(wǎng)絡(luò)的研究起源1847年，Kirobhhoff（克希霍夫）在研究關(guān)于電流的一組線性方程時(shí)，把電路圖中的電阻、電容、電感等抽象化得到點(diǎn)邊形式的網(wǎng)絡(luò)圖。在此基礎(chǔ)上，他不僅發(fā)展了圖論中樹的概念，而且使求解的過程變得極為容易。1857年，bayley（凱萊）在計(jì)算有n個(gè)碳原子的飽和碳?xì)浠衔锏耐之悩?gòu)物的數(shù)目時(shí)，采用點(diǎn)邊的圖來表示，點(diǎn)表示原子，邊表示共價(jià)鍵，從而容易地解出了這個(gè)化學(xué)問題。1976年，美國的Appel等人，依靠計(jì)算機(jī)求解了最著名的數(shù)學(xué)問題之一，四色問題，開拓了圖論的新的研究方法。圖論與網(wǎng)絡(luò)的應(yīng)用電氣和電力網(wǎng)絡(luò)為我們的家庭帶來照明和娛樂。電話網(wǎng)絡(luò)使我們能夠在本地社區(qū)內(nèi)以及跨區(qū)域和國際邊界之間幾乎毫不費(fèi)力地相互溝通。國家公路系統(tǒng)、鐵路網(wǎng)絡(luò)和航空服務(wù)網(wǎng)絡(luò)為我們提供了跨越遙遠(yuǎn)地理距離完成工作、見到親人、參觀新地方和享受新體驗(yàn)的途徑。制造和分銷網(wǎng)絡(luò)使我們能夠獲得生活必需的食品和消費(fèi)品。計(jì)算機(jī)網(wǎng)絡(luò)，如航空公司預(yù)訂系統(tǒng)，已經(jīng)改變了我們共享信息、開展業(yè)務(wù)和個(gè)人生活的方式。圖論與網(wǎng)絡(luò)的應(yīng)用物理、化學(xué)、控制論、信息論、計(jì)算機(jī)科學(xué)、經(jīng)濟(jì)管理、工程建設(shè)、交通和物流管理等諸多領(lǐng)域在我們?nèi)粘Ｉ钪械拿恳惶?，網(wǎng)絡(luò)都是顯而易見的。圖論與網(wǎng)絡(luò)Graphsaremathematicalstructuresusedtomodelpairwise

relationsbetweenobjects.——Wikipedia

Networkflow:Wewishtomovesomeentity(electricity,aconsumerproduct,apersonoravehicle,amessage)fromonepointtoanotherinanunderlyingnetwork,andtodosoasefficientlyaspossible,bothtoprovidegoodservicetotheusersofthenetworkandtousetheunderlying(andtypicallyexpensive)transmissionfacilitieseffectively.

——Ahuja,Magnanti,Orlin.NetworkFlows:Theory,Algorithms,andApplications

圖與網(wǎng)絡(luò)圖與網(wǎng)絡(luò)的基本概念樹圖中國郵遞員問題最短路徑問題網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最小費(fèi)用最大流問題

圖與網(wǎng)絡(luò)圖與網(wǎng)絡(luò)的基本概念對(duì)象之間的關(guān)系：點(diǎn)與邊/弧無向圖、有向圖樹圖中國郵遞員問題最短路徑問題網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最小費(fèi)用最大流問題圖與網(wǎng)絡(luò)的基本概念

對(duì)象之間關(guān)系的示意圖例如，我國北京、上海等十個(gè)城市間的鐵路交通圖，反映了鐵路分布情況。用點(diǎn)代表城市，用點(diǎn)和點(diǎn)之間的連線代表兩個(gè)城市之間的鐵路線。電話線分布圖、煤氣管道圖、航空線圖等空間位置連接關(guān)系圖與網(wǎng)絡(luò)的基本概念

圖與網(wǎng)絡(luò)的基本概念

圖與網(wǎng)絡(luò)的基本概念

圖：由點(diǎn)及點(diǎn)與點(diǎn)的連線（邊/?。?gòu)成，反映了實(shí)際生活中某些對(duì)象之間的某些特定關(guān)系圖：反映對(duì)象之間關(guān)系的一種工具圖中點(diǎn)的相對(duì)位置如何，點(diǎn)與點(diǎn)之間連線的長短曲直，并不重要例如，5個(gè)球隊(duì)比賽情況圖圖與網(wǎng)絡(luò)的基本概念

比賽情況圖比賽勝負(fù)圖圖與網(wǎng)絡(luò)的基本概念

圖與網(wǎng)絡(luò)的基本概念

圖與網(wǎng)絡(luò)的基本概念

圖的概念——重要術(shù)語和記號(hào)

初等鏈上點(diǎn)不同，則邊必定不同；簡單鏈上邊不同，但點(diǎn)可以重復(fù)。

圖與網(wǎng)絡(luò)的基本概念

圖的概念定理：對(duì)于任意一個(gè)圖，所有點(diǎn)的次之和，是邊數(shù)的2倍。因?yàn)橐粭l邊有兩個(gè)端點(diǎn)，在這兩個(gè)端點(diǎn)計(jì)數(shù)次的時(shí)候該邊都會(huì)被計(jì)一次。定理：對(duì)于任意一個(gè)圖，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。如果奇點(diǎn)的個(gè)數(shù)是奇數(shù)，那么所有點(diǎn)的次之和就是奇數(shù)，矛盾。圖與網(wǎng)絡(luò)的基本概念

圖的概念——重要術(shù)語和記號(hào)

圖與網(wǎng)絡(luò)的基本概念

圖的概念——重要術(shù)語和記號(hào)

圖與網(wǎng)絡(luò)的基本概念

圖的概念——重要術(shù)語和記號(hào)

圖與網(wǎng)絡(luò)的基本概念

圖的概念——重要術(shù)語和記號(hào)

圖與網(wǎng)絡(luò)的基本概念

例題：甲乙丙丁戊己6位運(yùn)動(dòng)員，他們參加6個(gè)項(xiàng)目的情況如表所示，問：能否安排項(xiàng)目順序，使每位運(yùn)動(dòng)員不用連續(xù)參賽。項(xiàng)目運(yùn)動(dòng)員ABCDEF甲√√√乙√√√丙√√丁√√戊√√√己√√√圖與網(wǎng)絡(luò)的基本概念

項(xiàng)目運(yùn)動(dòng)員ABCDEF甲√√√乙√√√丙√√丁√√戊√√√己√√√

例題圖與網(wǎng)絡(luò)的基本概念

例題圖與網(wǎng)絡(luò)的基本概念

例題

圖與網(wǎng)絡(luò)的基本概念

例題

圖與網(wǎng)絡(luò)的基本概念

圖與網(wǎng)絡(luò)圖與網(wǎng)絡(luò)的基本概念樹圖無圈連通圖、性質(zhì)（最?。┲螛渲袊]遞員問題最短路徑問題網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最小費(fèi)用最大流問題樹圖

樹圖的應(yīng)用背景因?yàn)闃鋱D可以清楚地反映系統(tǒng)中一組事物間的層次關(guān)系，所以一些決策過程（如決策樹），以及傳統(tǒng)的組織結(jié)構(gòu)圖都可以用樹圖表示。樹圖

樹圖的應(yīng)用背景因?yàn)闃鋱D可以清楚地反映系統(tǒng)中一組事物間的層次關(guān)系，所以一些決策過程（如決策樹），以及傳統(tǒng)的組織結(jié)構(gòu)圖都可以用樹圖表示。樹圖

樹圖

樹的定義一個(gè)無圈的連通圖稱為樹。對(duì)比：計(jì)算機(jī)中的樹結(jié)構(gòu)：根、父/子節(jié)點(diǎn)、葉子（圖論中任意一點(diǎn)都可作為根節(jié)點(diǎn)，葉節(jié)點(diǎn)對(duì)應(yīng)懸掛點(diǎn)）1246357樹圖

樹的性質(zhì)連通且無圈一個(gè)圖是樹的充要條件是：任意兩個(gè)頂點(diǎn)之間恰有一條鏈。2435124351樹圖

樹的性質(zhì)連通且無圈一個(gè)圖是樹的充要條件是：任意兩個(gè)頂點(diǎn)之間恰有一條鏈。如果從樹中去掉任一條邊，則圖不連通。2435124351樹圖

樹的性質(zhì)連通且無圈一個(gè)圖是樹的充要條件是：任意兩個(gè)頂點(diǎn)之間恰有一條鏈。如果從樹中去掉任意一條邊，則圖不連通。在樹的任意兩個(gè)不相鄰的節(jié)點(diǎn)之間增加一條邊，則形成唯一的圈。（再在這個(gè)圈上去掉任意一條邊，又形成了樹）2435124351樹圖

24351樹圖

樹的性質(zhì)如果樹的節(jié)點(diǎn)個(gè)數(shù)為n，則邊的個(gè)數(shù)為n-1（歸納法證明）一個(gè)節(jié)點(diǎn)數(shù)為n的圖是樹的充要條件是：它不含圈，且邊的數(shù)量是n-1。（反證法：假如不連通，則可分出連通子圖，均是樹）一個(gè)節(jié)點(diǎn)數(shù)為n的圖是樹的充要條件是：它是連通的，且邊的數(shù)量是n-1。（歸納法證明）Recall：一個(gè)樹上每添加一條邊就多一個(gè)圈，減少一條邊就不連通。樹圖

4231423142314231423142314231樹圖

樹圖

支撐樹（生成樹）破圈法：在圖中任取一個(gè)圈，移除其中任意一條邊，不斷重復(fù)這個(gè)步驟，直至沒有圈。（注意：一直保持連通性）BACSE樹圖

支撐樹（生成樹）破圈法：在圖中任取一個(gè)圈，移除其中任意一條邊，不斷重復(fù)這個(gè)步驟，直至沒有圈。（從原圖開始做減法）BACSEBACSEBACSEBACSE

樹圖

BACSE樹圖

BACSEBACSEBACSE樹圖

BACSEBACSEBACSE

樹圖

樹圖

最小支撐樹問題——破圈法貪心(greedy)的思想：任取一個(gè)圈，每次移除圈中權(quán)最大的邊，（若圈中有多條權(quán)相等且最大的邊，則任意移除一條），直到無圈為止。（每一步不需要找權(quán)最大的邊所在的圈）BACSDTE245127534157樹圖

最小支撐樹問題——破圈法BACSDTE245127534157BACSDTE24512534157BACSDTE2412534157BACSDTE2412315BACSDTE241253157BACSDTE24125315樹圖

最小支撐樹問題——破圈法BACSDTE2412315BACSDTE212315

樹圖

最小支撐樹問題——破圈法為什么每一步“任意找一個(gè)圈”，最終都能得到最小支撐樹？理解：1.每個(gè)圈都要去掉，先去掉哪個(gè)都一樣2.如圖所示：BACSDTE245127534157樹圖

最小支撐樹問題——Kruskal避圈法貪心(greedy)的思想：從空樹開始選權(quán)最小的邊添加入樹，之后每一步在【與已選邊不構(gòu)成圈的邊】中選擇權(quán)最小的邊添加入樹，直到連通每個(gè)點(diǎn)為止。每一步中，若有多條權(quán)相同且最小的邊，則任意移除一條。BACSDTE245127534157樹圖

最小支撐樹問題——Kruskal避圈法BACSDTE245127534157BACSDTE245127534157BACSDTE245127534157BACSDTE245127534157BACSDTE245127534157BACSDTE245127534157樹圖

最小支撐樹問題——Kruskal避圈法BACSDTE245127534157BACSDTE245127534157

樹圖

圖與網(wǎng)絡(luò)圖與網(wǎng)絡(luò)的基本概念樹圖中國郵遞員問題歐拉圈（七橋問題）奇偶點(diǎn)圖上作業(yè)法最短路徑問題網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最小費(fèi)用最大流問題中國郵遞員問題

中國郵遞員問題郵遞員在某一地區(qū)的信件投遞路程問題。郵遞員每天從郵局出發(fā)，走遍該地區(qū)所有街道再返回郵局，問題是他應(yīng)如何安排送信的路線可以使所走的總路程最短。我國學(xué)者管梅谷在1960年首先提出，并給出了解法——“奇偶點(diǎn)圖上作業(yè)法”，在國際上被稱為中國郵遞員問題ChinesePostmanProblem(CPP)中國郵遞員問題

中國郵遞員問題

中國郵遞員問題

歐拉圈定義一個(gè)（多重）圖中，若存在一條過每條邊恰好一次的鏈，則稱它為歐拉鏈Eulerwalk/trail（每條邊都要經(jīng)過的簡單鏈）。若存在一個(gè)過每條邊恰好一次的圈，則稱它為歐拉圈Eulercircuit

（每條邊都要經(jīng)過的簡單圈）。一個(gè)圖若有歐拉圈，則為歐拉圖

歐拉圈問題：問一個(gè)圖是否有歐拉圈

（一筆畫問題、哥尼斯堡七橋問題）中國郵遞員問題Gr?tschelM,YuanY.Euler,Mei-kokwan,k?nigsberg,andaChinesepostman[J].OptimizationStories,2012,43.Ehler’sdrawingofK?nigsberg,1736歐拉圈問題中國郵遞員問題

問題對(duì)比旅行商問題TSP：經(jīng)過每個(gè)點(diǎn)恰好一次的最短圈（TSP定義在完全圖上）哈密頓圈Hamiltoncircuit：經(jīng)過每個(gè)點(diǎn)恰好一次哈密頓圈問題：一個(gè)圖中是否存在哈密頓圈（NP類）中國郵遞員問題CPP：經(jīng)過每條邊至少一次的最短圈（CPP定義在任意圖上）歐拉圈Eulercircuit：經(jīng)過每條邊恰好一次歐拉圈問題：一個(gè)圖中是否存在歐拉圈（P類）中國郵遞員問題

中國郵遞員問題歐拉圈性質(zhì)Recall：在任意一個(gè)圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。奇點(diǎn)個(gè)數(shù)是否有歐拉鏈?zhǔn)欠裼袣W拉圈0否是2是否4,6,8…否否1,3,5…不存在這樣的圖中國郵遞員問題

歐拉圈——無奇點(diǎn)的圖中找歐拉圈Hierholzer'sAlgorithm(1873)不斷找無公共邊的簡單圈拼接Fleury’sAlgorithm(1883)不斷去掉非“割邊”添加至鏈中EBAGFDCH中國郵遞員問題

歐拉圈——無奇點(diǎn)的圖中找歐拉圈Hierholzer'sAlgorithm(1873)不斷找無公共邊的簡單圈(1)EBAGFDCH(2)(3)(4)(7)(4)(5)(6)(1)EBAGFDCH(2)(3)(8)(8)(1)EBAGFDCH(2)(3)(4)(5)(6)(7)(9)(10)(11)中國郵遞員問題

中國郵遞員問題

EBAGFDCHEBAGFDCHEBAGFDCH

中國郵遞員問題

歐拉圈——無奇點(diǎn)的圖中找歐拉圈Fleury’sAlgorithm(1883)不斷去掉非“割邊”添加至鏈中（除非迫不得已）EBAGFDCH

EBAGFDCH

EBAGFDCH

中國郵遞員問題

歐拉圈——無奇點(diǎn)的圖中找歐拉圈Fleury’sAlgorithm(1883)不斷去掉非“割邊”添加至鏈中（除非迫不得已）EBAGFDCH

EBAGFDCH

中國郵遞員問題

中國郵遞員問題

歐拉圈——無奇點(diǎn)的圖中找歐拉圈思考：如何在有兩個(gè)奇點(diǎn)的圖中找歐拉鏈？Hierholzer'sAlgorithm(1873)Fleury’sAlgorithm(1883)中國郵遞員問題

歐拉圈——無奇點(diǎn)的圖中找歐拉圈在有兩個(gè)奇點(diǎn)的圖中找歐拉鏈：Hierholzer'sAlgorithm(1873)在兩個(gè)奇點(diǎn)間添加一條邊，找歐拉圈，最后刪掉這條邊。Fleury’sAlgorithm(1883)從兩個(gè)奇點(diǎn)中其中一個(gè)開始，因?yàn)椴蛔吒钸叄宰詈蟛诺竭_(dá)另一個(gè)奇點(diǎn)。中國郵遞員問題

中國郵遞員問題

奇偶點(diǎn)圖上作業(yè)法（歐拉化）1.

確定一個(gè)可行方案（構(gòu)造出一個(gè)歐拉圖）消除奇點(diǎn)：偶數(shù)個(gè)奇點(diǎn)任意兩兩配對(duì)，每對(duì)奇點(diǎn)之間有一條簡單鏈，將鏈上的每條邊復(fù)制一份作為重復(fù)邊添加入圖中，得到的新圖為歐拉圖。2.

調(diào)整可行方案至最優(yōu)（降權(quán)至“最小權(quán)”歐拉圖）3.

在“最小權(quán)”歐拉圖中使用Hierholzer算法或