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