matlab最短路問題ppt課件(已修改)
2025-05-17 18:17 本頁面
【正文】 數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn) 最短路問題 實(shí)驗(yàn)?zāi)康? 實(shí)驗(yàn)內(nèi)容 會(huì)用 Matlab軟件求最短路 了解最短路的算法及其應(yīng)用 圖 論 的 基 本 概 念 最 短 路 問 題 及 其 算 法 最 短 路 的 應(yīng) 用 建模案例：最優(yōu)截?cái)嗲懈顔栴} 實(shí)驗(yàn)作業(yè) 圖 論 的 基 本 概 念 一、 圖 的 概 念 圖的定義 頂點(diǎn)的次數(shù) 子圖 二、 圖 的 矩 陣 表 示 關(guān)聯(lián)矩陣 鄰接矩陣 返回 定義 有序三元組 G=(V,E, )稱為一個(gè) 圖 . ?[ 1 ] V= },{21 nvvv ? 是有窮非空集，稱為 頂點(diǎn)集 ， 其中的元素叫圖 G 的 頂點(diǎn) .[ 2 ] E 稱為 邊集 ，其中的元素叫圖 G 的 邊 .[ 3 ] ? 是從邊集 E 到頂點(diǎn)集 V 中的有序或無序的元素 偶對(duì)的集合的映射，稱為 關(guān)聯(lián)函數(shù) .例 1 設(shè) G = ( V , E , ? ) ，其中 V = { v1 ,v2 , v3 , v4} ， E = { e1, e2 , e3, e4, e5},335414413312211)(,)(,)(,)(,)( vvevvevvevvevve ?????????? .G 的圖解如圖 .圖的定義 定義 在圖 G 中，與 V 中的有序偶 (vi ， v j ) 對(duì)應(yīng)的邊 e ，稱為圖的 有向邊 （或?。c V 中頂點(diǎn)的無序偶 v i v j 相對(duì)應(yīng)的邊 e ，稱為圖的 無向邊 . 每一條邊都是無向邊的圖，叫 無向圖 ；每一條邊都是有向邊的圖，稱為 有向圖 ；既有無向邊又有有向邊的圖稱為 混合圖 .定義 若將圖 G 的每一條邊 e 都對(duì)應(yīng)一個(gè)實(shí)數(shù) w (e ) ，稱 w (e ) 為邊的 權(quán) ，并稱圖 G 為 賦權(quán)圖 .規(guī)定用記號(hào) ? 和 ? 分別表示圖的頂點(diǎn)數(shù)和邊數(shù) .常用術(shù)語：（１） 端點(diǎn)相同的邊稱為 環(huán) ．（２） 若一對(duì)頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱為 重邊 ．（３） 有邊聯(lián)結(jié)的兩個(gè)頂點(diǎn)稱為 相鄰的頂點(diǎn) ，有一個(gè)公共端點(diǎn)的邊 稱為 相鄰的邊 ．（４） 邊和它的端點(diǎn)稱為互相 關(guān)聯(lián) 的． （５） 既沒有環(huán)也沒有平行邊的圖，稱為 簡(jiǎn)單圖 ．（６） 任意兩頂點(diǎn)都相鄰的簡(jiǎn)單圖，稱為 完備圖 ，記為 Kn，其中 n 為頂點(diǎn)的數(shù)目．( 7 ) 若 V= X?Y ， X?Y=?， X 中任兩頂點(diǎn)不相鄰， Y 中任兩頂點(diǎn)不相鄰，稱 G 為 二元圖 ；若 X 中每一頂點(diǎn)皆與 Y 中一切頂點(diǎn)相鄰，稱為 完備二元圖 ，記為 Km , n，其中 m , n 分別為 X 與 Y 的頂點(diǎn)數(shù)目．返回 頂點(diǎn)的次數(shù) 定義 （１）在無向圖中，與頂點(diǎn) v 關(guān)聯(lián)的邊的數(shù)目 （環(huán)算兩次）稱為 v 的 次數(shù) ，記為 d ( v ) ． （２）在有向圖中，從頂點(diǎn) v 引出的邊的數(shù)目稱為 v 的 出度 ，記為 d + ( v ) ，從頂點(diǎn) v 引入的邊的數(shù)目稱為的 入度 ，記為 d ( v ) ，d ( v ) = d + ( v ) + d ( v ) 稱為 v 的次數(shù)．4)( 4 ?vd5)(3)(2)(444?????vdvdvd定理１ )(2)()(GvdGVv????推論１ 任何圖中奇次頂點(diǎn)的總數(shù)必為偶數(shù)．例 在一次聚會(huì)中，認(rèn)識(shí)奇數(shù)個(gè)人的人數(shù)一定是偶數(shù)。 返回 子圖 定義 設(shè)圖 G = (V , E ,? ), G 1 = (V 1 ,E 1 , 1? )(1 ) 若 V 1 ? V ， E 1? E, 且當(dāng) e? E 1 時(shí)， 1? (e) = ? (e), 則稱 G 1 是 G 的 子圖 ．特別的，若 V 1 =V ，則 G 1 稱為 G 的 生成子圖 ．( 2 ) 設(shè) V 1 ? V ，且 V 1 ?? ，以 V 1 為頂點(diǎn)集、兩個(gè)端點(diǎn)都在 V 1 中的圖 G 的邊為邊集的圖 G 的子圖，稱為 G 的 由 V 1 導(dǎo)出的子圖 ，記為 G [ V 1 ].( 3 ) 設(shè) E 1 ? E , 且 E 1 ?? , 以 E 1 為邊集 , E 1 的端點(diǎn)集為頂點(diǎn)集的圖 G 的子圖 ,稱為 G 的 由 E 1 導(dǎo)出的子圖 , 記為 G [ E 1 ]. G G [ { v 1 ,v 4 ,v 5 }]G [ { e1 ,e 2 ,e 3 }]返回 關(guān)聯(lián)矩陣 對(duì)無向圖Ｇ，其關(guān)聯(lián)矩陣Ｍ＝ ?? ?)( ijm ，其中：不關(guān)聯(lián)與若相關(guān)聯(lián)與若jijiij e
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1