物流運(yùn)輸路徑規(guī)劃(編輯修改稿)
2025-03-08 03:54 本頁面
【文章內(nèi)容簡介】 e3 e45均是 v4的關(guān)聯(lián)邊。相鄰點(diǎn)相鄰點(diǎn) ：： 一條邊的兩個頂點(diǎn)，稱為相鄰點(diǎn)，如 v2與 v4， v4與 v5等是相鄰點(diǎn)，而 v2與 v5則不是。一、圖的定義一、圖的定義圖 64一、圖的定義一、圖的定義 環(huán)與多重邊環(huán)與多重邊 ：：兩個頂點(diǎn)相同的邊稱為 環(huán) ，如 e22，兩個頂點(diǎn)之間的邊數(shù) ≥2 時 ,叫多重邊 ,如 e13 ,e’ 13就是二重邊。圖 64二重邊二重邊環(huán)環(huán)次次 ：： 一個頂點(diǎn) v具有關(guān)聯(lián)邊的總數(shù)稱為該頂點(diǎn)的次，記作 d(v)（每個環(huán)視作兩條邊），如圖 64。 d(v1)= 3， d(v2)= 4， d(v5)= 1。 把次為奇數(shù)的頂點(diǎn)稱 為 奇頂點(diǎn) ，次為偶數(shù) 的頂點(diǎn)稱為 偶頂點(diǎn) 。圖 64一、圖的定義一、圖的定義一、圖的定義一、圖的定義懸掛點(diǎn)與孤立點(diǎn)懸掛點(diǎn)與孤立點(diǎn) ： 次為 1的頂點(diǎn)稱為懸掛點(diǎn) ，如 v5。次為0的頂點(diǎn)稱為 孤立點(diǎn)，如 v6。圖 54v6孤孤立立點(diǎn)點(diǎn)懸懸掛掛點(diǎn)點(diǎn)簡單圖簡單圖 ：： 無環(huán)、無多重邊的圖稱為 簡單圖 ，如圖 64(a)、(b)、 (c)，后面如無特殊說明，均指簡單圖。一、圖的定義一、圖的定義圖 64（ a） 圖 64（ b） 圖 64（ c）子圖與支撐子圖子圖與支撐子圖 ：： 在圖 G=(V， E)中，若 V1?V， E1?E，則圖 G1=(V E1)稱為 G的 子圖 ，如圖 64中的 (b)就是 (a)的子圖。特別地： V1=V， E1?E時，稱 G1是 G的 支撐子圖 (生成子圖）。如圖 64中 (c)、 (b)都是 (a)的支撐圖。一、圖的定義一、圖的定義圖 64（ a） 圖 64（ b） 圖 64（ c）定理定理 1 在任何圖中頂點(diǎn)次數(shù)總和等于邊數(shù)的 2倍。定理定理 2 任何圖中，次為奇數(shù)的頂點(diǎn)必有偶數(shù)個。 即奇頂點(diǎn)必有偶數(shù)個。一、圖的定義一、圖的定義二、連通圖二、連通圖定義定義 2 無向圖 G=(V， E)中，稱某些點(diǎn)及其關(guān)聯(lián)邊的交替序列 {v1 e1 v2 e2 … en vn }為 從 v1到 vn的一條鏈 ，v vn分別稱為鏈的 始點(diǎn) 和 終點(diǎn) ，鏈長為 n。 若一條鏈的 始點(diǎn)與終點(diǎn)重合 ，則稱為 閉鏈 (在無向圖中閉鏈又稱為回路），否則，稱為 開鏈 。點(diǎn)邊序列中若只有重復(fù)的點(diǎn)而無重復(fù)的邊，則稱為 簡單鏈 。點(diǎn)邊序列中若既沒有重復(fù)的點(diǎn)也無重復(fù)的邊，則稱為 初等鏈 （也稱為 通路 ）。例如在圖 65中： S={v6 e6 v5 e7 v1 e8 v5 e7 v1 e9 v4 e4 v3}是一條連接 v v3的鏈，鏈長為 6. S1={v6 e6 v5 e7 v1 e8 v5 e5 v4 e4 v3}是一條連接 v v3的簡單鏈，鏈長為 5.S2={v6 e6 v5 e7 v1 e9 v4 e4 v3}是一條連接 v v3的初等鏈。 e1e2 e3 e4e6 e7 e8 e9 e10 v1 v2 v3 v4v5v6e5二、連通圖二、連通圖圖圖 65連通的連通的 在無向圖中，若頂點(diǎn) vi與 vj之間存在鏈， 則稱 vi與 vj是 連通的 。規(guī)定：規(guī)定： vi與自身是連通的連通圖連通圖 若無向圖 G中的任意兩個頂點(diǎn)都是連通的， 則稱 G是 連通圖 ， 否則稱 G是 非連通圖 。二、連通圖二、連通圖3. 網(wǎng) 絡(luò) 一個圖連同定義在其邊集上的實(shí)函數(shù)一起稱為一個網(wǎng)絡(luò)．網(wǎng)絡(luò)一般是連通圖．定義在邊集上的實(shí)函數(shù)稱為邊的權(quán)數(shù)記為 wij＝ w (vi， v
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1