資源描述：
《網(wǎng)絡(luò)優(yōu)化模型ppt課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第七章網(wǎng)絡(luò)優(yōu)化模型圖與網(wǎng)絡(luò)的基本概念最短路徑問題最大流問題最小費(fèi)用最大流問題哥尼斯堡七橋問題ABDC簡(jiǎn)捷表示事物之間的本質(zhì)聯(lián)系，歸納事物之間的一般規(guī)律ACDB在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來表示。(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e57.1圖與網(wǎng)絡(luò)的基本概念7.1圖與網(wǎng)絡(luò)的基本概念7.1.1圖與網(wǎng)絡(luò)的概念及分類1、圖：圖由點(diǎn)和邊組成G=(V,E)點(diǎn)集V={vi}邊集E={ei}vjvie每一條邊和兩個(gè)端點(diǎn)關(guān)聯(lián)，一條邊可以用兩個(gè)端點(diǎn)表示（vi
2、，vj）邊數(shù)：m(G)=
3、E
4、點(diǎn)數(shù)：n(G)=
5、V
6、7.1圖與網(wǎng)絡(luò)的基本概念無向邊：有向邊：無向圖：由無向邊構(gòu)成的圖有向圖：由有向邊構(gòu)成的圖2、無向圖和有向圖7.1圖與網(wǎng)絡(luò)的基本概念3、簡(jiǎn)單圖和多重圖環(huán)：e9多重邊：e6和e7簡(jiǎn)單圖：不含環(huán)和多重邊多重圖：含多重邊判斷下列哪些圖是簡(jiǎn)單圖，哪些圖是多重圖？7.1圖與網(wǎng)絡(luò)的基本概念7.1圖與網(wǎng)絡(luò)的基本概念4、次：以點(diǎn)v為端點(diǎn)的邊數(shù)叫做點(diǎn)v的次，d(v)奇點(diǎn)：次為奇數(shù)偶點(diǎn)：次為偶數(shù)懸掛點(diǎn)：d(v)=1孤立點(diǎn)：d(v)=0定理7.1：任何圖，Σd(vi)=2m定理
7、7.2：任何圖，奇點(diǎn)有偶數(shù)個(gè)7.1圖與網(wǎng)絡(luò)的基本概念出次d+(vi)：有向圖中，以vi為始點(diǎn)的邊數(shù)入次d-(vi)：有向圖中，以vi為終點(diǎn)的邊數(shù)Σd+(v)=Σd-(v)=m7.1圖與網(wǎng)絡(luò)的基本概念5、連通圖：鏈：無向圖G=（V,E）前后相繼的點(diǎn)邊序列稱為鏈初等鏈：點(diǎn)邊序列中沒有重復(fù)的點(diǎn)和重復(fù)邊的鏈稱為初等鏈(v1,e1,v2,e6,v4,e3,v3,e8,v5)7.1圖與網(wǎng)絡(luò)的基本概念5、連通圖：圈：無向圖G=（V,E）中起點(diǎn)和終點(diǎn)重合的鏈稱為圈初等圈：沒有重復(fù)點(diǎn)和重復(fù)邊的鏈圈稱為初等圈(v1,e1,v
8、2,e6,v4,e3,v3,e5,v1)7.1圖與網(wǎng)絡(luò)的基本概念5、連通圖：對(duì)于有向圖來說，如果鏈和圈中邊的方向與有向圖中所標(biāo)方向相同，那么鏈就稱為道路，圈就稱為回路。連通圖：任意兩個(gè)點(diǎn)之間至少有一條鏈相連的圖稱為連通圖7.1圖與網(wǎng)絡(luò)的基本概念6、子圖與生成子圖：子圖：圖G=(V,E)，E’是E的子集，V’是V的子集，且E’的邊與V’的頂點(diǎn)想關(guān)聯(lián)，G’=(V’,E’)是圖G的一個(gè)子圖。生成子圖：若V’=V，則G’是G的生成子圖7.1圖與網(wǎng)絡(luò)的基本概念6、網(wǎng)絡(luò)：網(wǎng)絡(luò)（賦權(quán)圖）：由點(diǎn)、邊以及與點(diǎn)邊相關(guān)聯(lián)的權(quán)數(shù)
9、所構(gòu)成的圖稱為網(wǎng)絡(luò)，記作N={V,E,W}v4v2v3v16215846v4v2v3v16215846無向網(wǎng)絡(luò)有向網(wǎng)絡(luò)7.1圖與網(wǎng)絡(luò)的基本概念7.1.2樹的概念及性質(zhì)1、樹（T）：無圈的連通圖稱為樹樹葉分枝點(diǎn)7.1圖與網(wǎng)絡(luò)的基本概念7.1.2樹的概念及性質(zhì)2、樹的性質(zhì)性質(zhì)7.1樹中任意兩點(diǎn)之間有且只有一條鏈。性質(zhì)7.2如圖G中任意兩點(diǎn)之間，有且只有一條鏈，則該圖G是一個(gè)樹。性質(zhì)7.3一個(gè)樹，則m=n-1。性質(zhì)7.4樹中任意兩個(gè)不相鄰的點(diǎn)之間增加一條邊，則形成唯一的圈。性質(zhì)7.5一個(gè)樹如果去掉任何一條邊，該
10、圖就不再連通。7.1圖與網(wǎng)絡(luò)的基本概念7.1.2樹的概念及性質(zhì)3、圖的生成樹生成樹（支撐樹）：圖G的生成子圖是一棵樹，則稱該樹為G的生成樹圖G中屬于生成樹的邊稱為樹枝，不屬于生成樹的邊稱為弦定理7.3：圖G=（V,E）,有生成樹的充分必要條件為G是連通圖4、最小生成樹：圖G=(V，E)的生成樹所有樹枝上的權(quán)數(shù)的總和,稱為生成樹的權(quán)。權(quán)數(shù)最小的生成樹稱為最小生成樹。尋找最小生成樹的方法：避圈法、破圈法最小生成樹權(quán)=115、根樹有向樹：若一個(gè)有向圖在不考慮邊的方向時(shí)是一棵樹，則稱這個(gè)有向圖為有向樹。根樹：有向
11、樹T，恰有一個(gè)結(jié)點(diǎn)入次d-(vi)=0，其余各點(diǎn)入次d-(vi)=1，則稱T為根樹根樹中入次d-(vi)=0的點(diǎn)稱為根出次d+(vi)=0稱為葉其他點(diǎn)稱為分枝點(diǎn)7.1圖與網(wǎng)絡(luò)的基本概念在根樹中，若每個(gè)頂點(diǎn)的出次d-(vi)≤m，稱這棵樹為m叉樹。若每個(gè)頂點(diǎn)的出次d-(vi)=m或0，則稱這棵樹為完全m叉樹7.1圖與網(wǎng)絡(luò)的基本概念v2v3v7v1v8v4v5v66134105275934682求從v1到v8的最短路徑標(biāo)號(hào)：T標(biāo)號(hào)（試探性標(biāo)號(hào)）P標(biāo)號(hào)（永久性標(biāo)號(hào)）1、狄克斯托算法（Dijkstra）:標(biāo)號(hào)法7
12、.2最短路問題V2V3V7V1V8V4V5V66134105275934682S={v1}P(v1)=0,T(vi)=∞T(v2)=2,T(v4)=1,T(v6)=3min{T(v2),T(v4),T(v6)}=min{2，1，3}=1P(v4)=1S={v1,v4}P(v1)=0L12=2L14=1L16=3P(v4)=1v2v3v7v1v8v4v5v66134105275934682S={v1,v4}P(v2)=2P(v1
