運(yùn)籌學(xué)圖與網(wǎng)絡(luò)ppt課件-wenkub
2023-05-27 13:31:59 本頁(yè)面
【正文】 其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列稱為 鏈 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 定理 ? 若圖 G中所有點(diǎn)都是孤立點(diǎn)，則稱圖 G為 空?qǐng)D 。 ? 無(wú)環(huán)也無(wú)多重邊的圖稱作 簡(jiǎn)單圖 。 ? 例如在圖中 v1和 v2為相鄰點(diǎn)， v1和 v5不相鄰；e1與 e5為相鄰邊， e1和 e7不相鄰。 ? 邊數(shù) 集合 E中元素的個(gè)數(shù)，記作 q(G)。第十一章 圖與網(wǎng)絡(luò)規(guī)劃 Graph Theory and Network Analysis 圖與網(wǎng)絡(luò)的基本概念 最短路問(wèn)題 網(wǎng)絡(luò)最大流問(wèn)題 最小費(fèi)用最大流問(wèn)題 內(nèi)容簡(jiǎn)介 ? 是近幾十年來(lái)運(yùn)籌學(xué)領(lǐng)域中發(fā)展迅速、而且十分活躍的一個(gè)分支． ? 對(duì)實(shí)際問(wèn)題的描述具有直觀性 ? 廣泛應(yīng)用于物理學(xué)、化學(xué)、信息論、控制論、計(jì)算機(jī)科學(xué)、社會(huì)科學(xué)以及現(xiàn)代經(jīng)濟(jì)管理科學(xué)等許多科學(xué)領(lǐng)域． ? 圖與網(wǎng)絡(luò)分析的內(nèi)容十分豐富．本章只介紹圖與網(wǎng)絡(luò)的基本概念以及圖論在路徑問(wèn)題、網(wǎng)絡(luò)流問(wèn)題等領(lǐng)域中的應(yīng)用．重點(diǎn)講明方法的物理概念、基本原理及計(jì)算步驟． 圖與網(wǎng)絡(luò)的基本概念 ? 圖的理論研究已有 200多年的歷史了．早期圖論與“數(shù)學(xué)游戲”有著密切關(guān)系．所謂“哥尼斯堡七橋”問(wèn)題就是其中之一． 200多年前的東普魯士有一座哥尼斯堡城，城中有一條河叫普雷格爾河，河中有兩個(gè)島嶼共建七座橋．平時(shí)城中居民大都喜歡來(lái)這里散步，并提出這樣一個(gè)問(wèn)題：一個(gè)散步者能否經(jīng)過(guò)每座橋恰恰一次再回到原出發(fā)點(diǎn)． 圖與網(wǎng)絡(luò)的基本概念 ? 當(dāng)時(shí)有許多人都探討了這個(gè)問(wèn)題，但不得其解． ? 著名數(shù)學(xué)家歐拉（ Euler）將這個(gè)問(wèn)題簡(jiǎn)化為一個(gè)如右圖所示圖形．圖 4個(gè)點(diǎn) A、 B、 C、 D表示兩岸和小島．兩兩點(diǎn)間連線表示橋． 圖與網(wǎng)絡(luò)的基本概念 ? 于是問(wèn)題轉(zhuǎn)化為一筆畫(huà)問(wèn)題，即能否從某一點(diǎn)開(kāi)始一筆畫(huà)出這個(gè)圖形，不許重復(fù)，最后回到原出發(fā)點(diǎn)． ? 歐拉否定了這種可能性． ? 原因是圖中與每一個(gè)點(diǎn)相關(guān)聯(lián)的線都是奇數(shù)條． ? 為此他寫(xiě)下了被公認(rèn)為世界第一篇有關(guān)圖論方面的論文（ 1736年） 圖與網(wǎng)絡(luò)的基本概念 ? 1859年哈密爾頓提出了另一種游戲：在一個(gè)實(shí)心的 12面體（見(jiàn)圖）的20個(gè)頂點(diǎn)上標(biāo)以世界上著名的城市名稱，要求游戲者從某一城市出發(fā)，遍歷各城市恰恰一次而返回原地，這就是所謂“繞行世界問(wèn)題”． 圖與網(wǎng)絡(luò)的基本概念 ? 作圖，此問(wèn)題變成在從某一點(diǎn)出發(fā)尋找一條路徑，過(guò)所有 20個(gè)點(diǎn)僅僅一次，再回到出發(fā)點(diǎn)． ? 解決這個(gè)問(wèn)題可以按序號(hào)1—2—3—4一 … 一 20—1所形成的一個(gè)閉合路徑，并稱此路徑為哈密爾頓圈． ? 具有哈密爾頓圈的圖稱為哈密爾頓圖． 圖與網(wǎng)絡(luò)的基本概念 ? 由此可見(jiàn)，圖論中所研究的圖是由實(shí)際問(wèn)題抽象出來(lái)的邏輯關(guān)系圖． ? 這種圖與幾何中的圖形和函數(shù)論中所研究的圖形是不相同的． ? 這種圖的畫(huà)法具有一定的隨意性，在保持相對(duì)位置和相互關(guān)系不變的前提下，點(diǎn)的位置不一定要按實(shí)際要求畫(huà)，線的長(zhǎng)度也不一定表示實(shí)際的長(zhǎng)度．而且畫(huà)成直線或曲線都可以． ? 通俗地說(shuō)，這種圖是一種關(guān)系示意圖． 圖與網(wǎng)絡(luò)的基本概念 ? 圖的概念 ? 所謂圖，就是頂點(diǎn)和邊的集合，點(diǎn)的集合記為 V，邊的集合記為 E，則圖可以表示為： G＝（ V， E），點(diǎn)代表被研究的事物，邊代表事物之間的聯(lián)系，因此，邊不能離開(kāi)點(diǎn)而獨(dú)立存在，每條邊都有兩個(gè)端點(diǎn)。 ? 若 e=[u,v]∈ E，則稱 u和 v為 e的端點(diǎn) ，而稱 e為 u和 v的 關(guān)聯(lián)邊 ，也稱 u， v與邊 e相 關(guān)聯(lián) 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 簡(jiǎn)單圖 ? 若一條邊的兩個(gè)端點(diǎn)是同一個(gè)頂點(diǎn) ， 則稱該邊為 環(huán) ；又若兩上端點(diǎn)之間有多于一條邊 ， 則稱為 多重邊 或 平行邊 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 圖的次 ? 次 點(diǎn) v作為邊的端點(diǎn)的次數(shù)，記作 d(v)，如圖中，d(v1)=5, d(v4)=6等 ? 端點(diǎn)次為奇數(shù)的點(diǎn)稱作奇點(diǎn) ；次為偶數(shù)的點(diǎn)稱作 偶點(diǎn) 。 ? 定理 1 所有頂點(diǎn)的次的和，等于所有邊數(shù)的 2倍。 ? v0稱為鏈的 起點(diǎn) ， vn稱為鏈的 終點(diǎn) 。 ? 例如圖中 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 是一條鏈，且是開(kāi)鏈，也是簡(jiǎn)單鏈，但不是初等鏈，因?yàn)?v1出現(xiàn)兩次。 143746211 , ????? eeee連通性 ? 若一個(gè)圖 G的任意兩點(diǎn)之間均至少有一條通路（初等鏈）連接起來(lái)，則稱這個(gè)圖 G是一個(gè) 連通圖 ，否則稱作不連通圖 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1