《運(yùn)籌學(xué)圖與網(wǎng)絡(luò)》ppt課件-預(yù)覽頁(yè)
【正文】 V中元素的個(gè)數(shù) ，記作 p(G)。 ? 在畫(huà)圖時(shí)，頂點(diǎn)的位置、邊和長(zhǎng)短形狀都是無(wú)關(guān)緊要的，只要兩個(gè)圖的頂點(diǎn)及邊是對(duì)應(yīng)相同的，則兩個(gè)圖相同。 ? 例如圖中的圖 G， p(G)=6，q(G)=9， ? v1， v2是 e1和 e2的端點(diǎn)， e1和 e2都是 v1和 v2的關(guān)聯(lián)邊。 ? 例如圖的 e8為環(huán) ， e1， e2為兩重邊 ， e4， e5也是兩重邊 。 ? 次為 1的點(diǎn)稱為 懸掛點(diǎn) ，與懸掛點(diǎn)連接的邊稱作懸掛邊 ； ? 次為 0的點(diǎn)稱為 孤立點(diǎn) 。即 qdV2)( ?????e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 ? 定理 2 在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。 ? 若 v0 ≠vn則稱該鏈為開(kāi)鏈 ，反之稱為 閉鏈 或 回路 。 4312211 , ???? eee圈 ? 若鏈中所含的邊均不相同，則稱為 簡(jiǎn)單鏈 ；若點(diǎn)均不相同，則稱為 初等鏈 或 通路 。 ? 例如圖中， v1和 v6之間沒(méi)有通路，因此它不是連通圖，而如果去掉 v6，則構(gòu)成一個(gè)連通圖。 特殊子圖 ? 當(dāng) G1中不包含 G2中所有的頂點(diǎn)和邊，則稱 G1是G2的 真子圖 。 ? 而有些關(guān)系是不對(duì)稱的，例如父子關(guān)系、上下級(jí)關(guān)系、加工工序的先后順序等都具有單向性，用圖來(lái)表示這些關(guān)系時(shí)，得到的邊是具有方向的，用帶箭頭的線來(lái)表示，稱為 弧 。 ? 頂點(diǎn)全不相同的路稱為 初等路 。 定理 以下關(guān)于樹(shù)的六種不同描述是等價(jià)的： 1. 無(wú)圈連通圖 。 5. 連通 ， 但若任意舍棄一條邊 ， 圖便不連通 。 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 網(wǎng)絡(luò)概念 ? 節(jié)點(diǎn)與（有向）邊 每一條邊和兩個(gè)節(jié)點(diǎn)關(guān)聯(lián)，一條邊可以用兩個(gè)節(jié)點(diǎn)的標(biāo)號(hào)表示（ i， j） j i ■ 路徑（ Path） 前后相繼并且方向相同的邊序列 P={(1,2),(2,3),(3,4)} 4 2 3 1 4 2 3 1 ■ 網(wǎng)絡(luò)由節(jié)點(diǎn)和邊組成 網(wǎng)絡(luò)概念 ■ 回路（ Circuit） 起點(diǎn)和終點(diǎn)重合的路徑稱為 回路 μ={(1,2),(2,4),(4,1)} 回路中各條邊方向相同 4 2 3 1 ■ 鏈（ Chain） 前后相繼并且方向不一定相同的邊序列稱為 鏈 C={(1,2),(3,2),(3,4)} 4 2 3 1 網(wǎng)絡(luò)概念 ■ 連通圖 任意兩個(gè)節(jié)點(diǎn)之間至少有一條鏈的圖稱為 連通圖 2 4 3 5 1 ■ 圈 (Cycle) 起點(diǎn)和終點(diǎn)重合的鏈稱為 圈 ρ ={(1,2),(2,4),(3,4),(1,3)} 圈中各條邊方向不一定相同 4 2 3 1 ■ 樹(shù) (Tree) 無(wú)圈的連通圖稱為樹(shù) 樹(shù)中只與一條邊關(guān)聯(lián)的節(jié)點(diǎn)稱為 懸掛節(jié)點(diǎn) 網(wǎng)絡(luò)概念 ? 平面圖 (planar graph)，若在平面上可以畫(huà)出該圖而沒(méi)有任何邊相交 ? 走過(guò)圖中所有邊且每條邊僅走一次的閉行走稱為歐拉回路 ? 定理 ：偶圖一定存在歐拉回路 (一筆畫(huà)定理 ) ? 圖中都是偶點(diǎn)的圖稱為偶圖 (even graph) 哈密爾頓回路 ( Hamiltonian circuit)問(wèn)題 ? 連通圖 G(V,E)中的回路稱為哈密爾頓回路，若該回路包括圖中所有的點(diǎn)。 ? 求最短樹(shù)的方法 ， 依據(jù)的是樹(shù)的特點(diǎn) ， 即無(wú)圈和連通 ， 加上最短的要求 ， 方法主要有兩種：一種稱為破圈法 ， 一種稱為 避圈法 最短路問(wèn)題 ? 最短路問(wèn)題的一般提法是：欲尋找網(wǎng)絡(luò)中從起點(diǎn) υ 1到終點(diǎn) υ n的最短路線 ， 即尋求連接這兩點(diǎn)的邊的總長(zhǎng)度為最小的通路 ， 最短路線中的網(wǎng)絡(luò)大都是有向網(wǎng)絡(luò) ， 也可以是無(wú)向網(wǎng)絡(luò) 。如果 vt 未標(biāo)號(hào)，則可以斷言不存在從 vs到 vt的有向路。不妨設(shè)此弧為（ Vc,Vd），則給此弧的終點(diǎn)以雙標(biāo)號(hào)（ scd,c） ,返回步驟 2?？梢园褵o(wú)向圖的每一邊（ vi,vj）都用方向相反的兩條?。?vi,vj）和（ vj,vi）代替，就化為有向圖，即可用 Dijkstra算法來(lái)求解。某公司使用一臺(tái)設(shè)備，在每年年初，公司就要決定是購(gòu)買新的設(shè)備還是繼續(xù)使用舊設(shè)備。 ? 已知：設(shè)備每年年初的價(jià)格表 ? 設(shè)備維修費(fèi)如下表 年份 1 2 3 4 5 年初價(jià)格 11 11 12 12 13 使用年數(shù) 01 12 23 34 45 每年維修費(fèi)用 5 6 8 11 18 ? 例 3的解：將問(wèn)題轉(zhuǎn)化為最短路問(wèn)題，如下圖： 用 vi表示“第 i年年初購(gòu)進(jìn)一臺(tái)新設(shè)備” ,?。?vi,vj）表示第 i年年初購(gòu)進(jìn)的 設(shè)備一直使用到第 j年年初。 若以 bij表示由 υi到 υj的弧上允許流過(guò)的最大流量 ，以 xij表示實(shí)際流過(guò)該弧的流量 ， 則 0≤ xij ≤bij 4) 網(wǎng)絡(luò)中 ， 除起點(diǎn) υs和終點(diǎn) υt之外的任何頂點(diǎn) ， 流入量總和應(yīng)該等于流出量的總和 。如果不存在這樣的路，則已經(jīng)求得最大流。由于管道的直徑的變化，它的各段管道（ vi,vj）的流量 cij（容量）也是不一樣的。如圖
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1