運(yùn)籌學(xué)第06章圖論概述-文庫吧資料
2025-05-22 22:15本頁面
【正文】 例 () ?由于 dj(4)=dj(3) (j=s,a,b,c,d,t)，停止計(jì)算 ?s到 t 的最短路線長度為 16 ?最短路線為 s a c d t s a b c d t 5 8 3 9 1 4 9 5 4 3 最小生成樹問題 ?一般針對(duì)賦權(quán)連通圖，求該圖權(quán)值之和為最小的生成樹 ?求解該問題一般有兩種方法 ?破圈法 ?生長法 破圈法求最小生成樹 ?假設(shè)原圖為賦權(quán)連通圖 ?破圈法依據(jù)樹的定義給出求最小生成樹算法 ?破圈法步驟如下 ?在圖中找到一個(gè)圈，進(jìn)入下一步；若無圈則停止，此時(shí)的圖就是原圖的最小生成樹 ?查看該圈與其它圈是否有公共邊 ?若沒有公共邊，在該圈中選權(quán)值最大的邊，去掉該邊；對(duì)新的圖返回上一步 ?若有公共邊，將這些有公共邊的若干個(gè)圈合在一起看作一個(gè)回路，在該回路中選權(quán)值最大的邊，去掉該邊；對(duì)新的圖返回上一步 示例 () 3 3 5 4 7 2 6 4 3 2 ?用破圈法求下圖的最小生成樹 生長法求最小生成樹 (1) ?生長法依據(jù) ?根據(jù)動(dòng)態(tài)規(guī)劃最優(yōu)性原理，劃分 n1個(gè)階段 ?x1=S1 ?從圖中任選一點(diǎn) vi，令 S1={vi}， S2=VS1， k=1 ?uk 為 k 階段選中的權(quán)值最小的邊 (vi, vj)， vi∈ S1，vj∈ S2 ?xk+1=xk+{uk}+{vj} ?S1=S1 +{(vi, vj)}+{vj}， S2=S2{vj} ?xn 狀態(tài)結(jié)束 ?此時(shí)， S1 就是要求的最小生成樹的點(diǎn)邊集合， S2 是空集 生長法求最小生成樹 (2) ?假設(shè)原圖為賦權(quán)連通圖 ?生長法步驟如下 ?從圖中任選一點(diǎn) vi，令 S1={vi}， S2=VS1 ?從 S1中的各點(diǎn)到 S2中各點(diǎn)的邊中選擇權(quán)值最小的邊 (vi, vj)， vi∈ S1， vj∈ S2 ?令 S1=S1+{(vi, vj)}+{vj}， S2=S2{vj} ?若 S2 是空集，則停止， S1 就是要求的最小生成樹的點(diǎn)邊集合；否則轉(zhuǎn)第二步 示例 () 3 3 5 4 7 2 6 4 3 2 ?用生長法求下圖的最小生成樹 作業(yè) (17) ?書上 218頁 51的 (b) ?補(bǔ)充： 3和 8之間權(quán)值為 13 ?破圈法或生長法皆可 最大流問題 (1) ?一般針對(duì)賦權(quán)連通有向圖，每條弧的權(quán)值表示該弧允許流過的最大流量，每個(gè)頂點(diǎn)的流入量之和等于流出量之和，求圖上兩定點(diǎn)之間允許流過的最大流量 ?最大流 最小割定理 ?最大流量等于最小割集 (容量最小的割集 )的容量 ?注： 將圖 G中頂點(diǎn)集合 V分為兩個(gè)集合 S1和 S2，其中起點(diǎn) vs∈ S終點(diǎn) vt∈ S2，且 S1∪ S2 =V、 S1∩S2 = ，則把集合 C ={(vi, vj) | vi∈ S1, vj∈ S2 } 稱為圖 G的一個(gè) 割集 割集中弧的權(quán)值之和稱為該 割集的容量 ?最大流問題 (2) ?利用最大流 最小割定理，福德和富克遜提出了求解最大流問題的標(biāo)號(hào)法 可行流 最大流 結(jié)束 改變流量 是 否 最大流問題 (3) ?標(biāo)號(hào)法相關(guān)概念 ?若弧 (vi , vj )上的流量 xij=bij，則稱該弧為飽和弧，否則稱為非飽和弧 ?若弧 (vi , vj )上的流量 xij=0，則稱該弧為零流弧，否則稱為非零流弧 ?在一條從 vs 到 vt 的點(diǎn)邊交錯(cuò)序列中，與 vs 到 vt 方向一致的弧稱為正向弧，與 vs 到 vt方向相反的弧稱為逆向弧 ?若從 vs 到 vt 的某個(gè)點(diǎn)邊交錯(cuò)序列中，正向弧均為非飽和弧，逆向弧均為非零流弧，則稱該點(diǎn)邊交錯(cuò)序列為一條流量增廣鏈 最大流問題 (4) ?流量增廣鏈的作用 ?它是用來增加正向總流量的 ?使增廣鏈上正向弧的流量增大 ?使增廣鏈上逆向弧的流量減小 ?若找不到，表示不能再增大正向總流量，即當(dāng)前的正向總流量就是最大流量 最大流問題 (5) ?標(biāo)號(hào)法步驟如下 ?分配 vi 到 vj 的初始流 xij ?尋找增廣鏈，若不存在，則已經(jīng)最優(yōu)；否則進(jìn)入下一步調(diào)整。其中 v0稱為路的起點(diǎn)， vn稱為路的終點(diǎn) ?若 v0≠vn，稱為 開鏈 ；反之，稱為 閉鏈 (對(duì)于無向圖而言，也稱為回路 ) ?若鏈中所含的邊均不相同，稱為 簡單鏈 ?若鏈中所含的頂點(diǎn)均不相同，稱為 初等鏈 (對(duì)于無向圖而言，也稱為通路 ) ?除起點(diǎn)和終點(diǎn)外均不相同的閉鏈，稱為 圈 (對(duì)于無向圖而言，也稱為初等回路 ) 以上概念 (除特別標(biāo)注的外 )對(duì)無向圖和有向圖均適用 圖的基本概念 (7) ?在有向圖中，點(diǎn)邊交錯(cuò)序列 v0, e1, v1, e2, v2, … , vn1, en, vn (其中 ek=(vk1, vk) )稱為 路 ?若 v0≠vn，稱為 開路 ；反之，稱為 回路 (注意和無向圖的回路區(qū)分開來 ) ?若路中所含的邊均不相同，稱為 簡單路 ?若路中所含的頂點(diǎn)均不相同，稱為 初等路 ?除起點(diǎn)和終點(diǎn)外均不相同的回路，稱為 初等回路(注意和無向圖的初等回路區(qū)分開來 ) 本頁概念都是針對(duì)有向圖 圖的基本概念 (8) ?若一個(gè)圖 (無向圖或有向圖 )中任意兩點(diǎn)之間至少有一條初等鏈連接，則稱該圖為 連通圖 ，否則稱為不連通圖 ?在一個(gè)有向圖中，若任意兩點(diǎn) u和 v， u到 v和 v到 u之間都至少有一條初等路連接，則稱該圖為 強(qiáng)連通圖 ，否則稱為非強(qiáng)連通圖 圖的基本概念 (9) ?子圖： 設(shè) G1=(V1, E1 )， G2=(V2, E2 )，若 V1 V2， E1 E2，則稱 G1是 G2的子圖 ???注： 生成子圖時(shí)，可以只選頂點(diǎn)不選與該頂點(diǎn)相關(guān)聯(lián)的邊，但不能只選邊不選與該邊相關(guān)聯(lián)的頂點(diǎn) ?如下圖，右圖是左圖的子圖 圖的基本概念 (10) ?如下圖，右圖是左圖的真子圖 ?真子圖： 若 V1 V2， E1 E2，稱 G1是 G2的真子圖 ? ??部分圖： 若 V1=V2， E1 E2，稱 G1是 G2的部分圖 ?圖的基本概念 (11) ?導(dǎo)出子圖： 若 V1 V2， E1={(ui, vj) E2 | ui V1, vj V1}，稱 G1是 G2中由 V1導(dǎo)出的導(dǎo)出子圖，記作 G(V1) ? ? ???如下圖，右圖是左圖的導(dǎo)出子圖 圖的基本概念 (12) ?一個(gè)沒有圈
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1