圖論模型：最短路ppt課件-展示頁(yè)
2025-05-15 23:19本頁(yè)面
【正文】 或回路；如果通路中既沒(méi)有相同的邊，又沒(méi)有相同的頂點(diǎn)，則稱此通路為路徑，簡(jiǎn)稱路。 ? 定義 2 若將圖 G的每條邊 e都對(duì)應(yīng)一個(gè)實(shí)數(shù) F(e)，則稱 F（ e） 為該邊的權(quán)，并稱圖 G為賦權(quán)圖，記為 G=(V,E,F)。 ? },{},V 4342324131214321 vvvvvvvvvvvvEvvvv ?，＝設(shè)例如 e 6 e 2 e 3 e 5 e 4 e 1 v 3 v 1 v 2 v 4 e5e6e2e1e3e4v3v4v1v2 ? 由邊連接的兩個(gè)點(diǎn)稱為相鄰的點(diǎn)；有一個(gè)公共端點(diǎn)的邊稱為相鄰邊；邊和它的端點(diǎn)稱為互相關(guān)聯(lián)。 ? 稱點(diǎn) vi,vj為邊 vivj的端點(diǎn)。凡是有向圖，在圖解上用箭頭標(biāo)明其方向。否則稱 G為混合圖。 ? 如果 V＝｛ v1,v2,… ,vn}是有限非空點(diǎn)集，則稱 G為有限圖或 n階圖。第六章 圖論方法 167。 圖論的基本概念 ? 定義 1 一個(gè)有序二元組（ V,E）稱為一個(gè)圖，記為 G=（ V,E），其中① V稱為 G的頂點(diǎn)集， V≠Φ ， V中的元素稱為頂點(diǎn)或結(jié)點(diǎn)，簡(jiǎn)稱點(diǎn)；② E稱為 G的邊集，其元素稱為邊，它連接 V中的兩個(gè)點(diǎn)，如果這兩個(gè)點(diǎn)是無(wú)序的，則稱該邊為無(wú)向邊；否則，稱為有向邊。 ? 如果 G的每條邊都是無(wú)向邊，則稱 G為無(wú)向圖；如果 G的每條邊都是有向邊，則稱 G為有向圖。并且常記 E＝ {e1,e2,… ,em}, ? (ek=vivj,i,j=1,2,… ,n), ? 對(duì)于一個(gè)圖 G=（ V,E），人們通常用一個(gè)圖形來(lái)表示，稱其為圖解。 則 G＝（ V,E）是一個(gè)有 4個(gè)頂點(diǎn)、 6條邊的圖，其圖解如下圖： 一個(gè)圖會(huì)有許多外形不同的圖解，如上圖。在有向圖中，稱點(diǎn) vi,vj分別為有向邊 vivj的始點(diǎn)和終點(diǎn)；稱邊 vivj為點(diǎn) vi的出邊，為點(diǎn) vj入邊。常用 d(v)表示圖G中與頂點(diǎn) v關(guān)聯(lián)的邊的數(shù)目， d(v)稱為頂點(diǎn) v的度數(shù)；用 N（ v）表示圖 G中所有與頂點(diǎn) v相鄰的頂點(diǎn)的集合。 ? 定義 3 設(shè) G=(V,E)是一個(gè)圖， ， ? 則稱是 G的一個(gè)通路。 ? 定義 4 任意兩點(diǎn)都有通路的圖稱為連通圖。 EvvkiVvvvv iik ????? ? 1210 ,1, 且? 167。如管道的鋪設(shè)、運(yùn)輸網(wǎng)絡(luò)的設(shè)計(jì)、線路安排、設(shè)備更新、廠區(qū)布局等。 ? 定義 2 若 P0(u,v)是 G中連接 u,v的路徑，且對(duì)任意在G中連接 u,v的路徑 P(u,v)，都有 F(P0)≤F(P), 則稱P0(u,v)是 G中連接 u,v的最短路徑。 T標(biāo)號(hào)為試探性標(biāo)號(hào)， P標(biāo)號(hào)為永久性標(biāo)號(hào)。凡沒(méi)有得到 P標(biāo)號(hào)的點(diǎn)都標(biāo)有 T標(biāo)號(hào)。其具體步驟如下： ? （ 1）賦初值：給起點(diǎn) v0以 P標(biāo)號(hào)， P(v0)＝ 0，其余各點(diǎn) vi均為 T標(biāo)號(hào) ,T（ vi）＝ +∞ ； ? （ 2）更新所有的 T標(biāo)號(hào)：若 vi點(diǎn)為剛得到的 P標(biāo)號(hào)的點(diǎn) ,考慮這樣的點(diǎn) vj，邊 vivj∈E ，且 vj為 T標(biāo)號(hào)，對(duì)vj的 T標(biāo)號(hào)進(jìn)行如下的更改： ? （ 3）比較所有 T標(biāo)號(hào)的點(diǎn)，把最小者改為
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1