【正文】 √ √ 己 √ √ √ Page 83 圖的基本概念與模型 解：用圖來(lái)建模。把比賽項(xiàng)目作為研究對(duì)象，用點(diǎn)表示。如果 2個(gè)項(xiàng)目有同一名運(yùn)動(dòng)員參加，在代表這兩個(gè)項(xiàng)目的點(diǎn)之間連一條線，可得下圖。 A B C D E F 在圖中找到一個(gè)點(diǎn)序列，使得依次排列的兩點(diǎn)不相鄰，即能滿足要求。如： 1) A,C,B,F,E,D 2) D,E,F,B,C,A Page 84 圖的基本概念與模型 圖的矩陣描述： 如何在計(jì)算機(jī)中存儲(chǔ)一個(gè)圖呢？現(xiàn)在已有很多存儲(chǔ)的方法，但最基本的方法就是采用矩陣來(lái)表示一個(gè)圖，圖的矩陣表示也根據(jù)所關(guān)心的問(wèn)題不同而有： 鄰接矩陣、關(guān)聯(lián)矩陣、權(quán)矩陣等。 1. 鄰接矩陣 對(duì)于圖 G=（ V， E）， | V |=n， | E |=m，有 n?n階方 矩陣A=(aij) n?n， 其中 ????其它之間有關(guān)聯(lián)邊時(shí)與當(dāng)且僅檔0vv1 jiijaPage 85 圖的基本概念與模型 v5 v1 v2 v3 v4 v6 4 3 3 2 2 5 6 4 3 7 010101101001010111101010001101111010 65432166654321??????????????????????vvvvvvAvvvvvv例 下圖所表示的圖可以構(gòu)造鄰接矩陣 A如下 Page 86 對(duì)于賦權(quán)圖 G=(V,E), 其中邊 有權(quán) , 構(gòu)造矩陣 B=(bij) n?n 其中： 圖的基本概念與模型 2. 關(guān)聯(lián)矩陣 對(duì)于圖 G=(V,E), | V |=n, | E |=m, 有 m?n階 矩陣 M=(mij) m?n，其中 : ??????其他的一個(gè)端點(diǎn)是邊當(dāng)且僅當(dāng)?shù)膬蓚€(gè)端點(diǎn)是邊當(dāng)且僅當(dāng)0ev1ev2jijiijm3. 權(quán)矩陣 ),(ji vv jiw???????? EvvEvvwbjijijiji ),(0),(Page 87 樹(shù)與圖的最小樹(shù) 樹(shù)是圖論中結(jié)構(gòu)最簡(jiǎn)單但又十分重要的圖。在自然和社會(huì)領(lǐng)域應(yīng)用極為廣泛。 例 乒乓求單打比賽抽簽后，可用圖來(lái)表示相遇情況，如下圖所示。 A B C D E F G H 運(yùn)動(dòng)員 Page 88 樹(shù)與圖的最小樹(shù) 例 某企業(yè)的組織機(jī)構(gòu)圖也可用樹(shù)圖表示。 廠長(zhǎng) 人事科 財(cái)務(wù)科 總工 程師 生產(chǎn)副 廠長(zhǎng) 經(jīng)營(yíng)副 廠長(zhǎng) 開(kāi)發(fā)科 技術(shù)科 生產(chǎn)科 設(shè)備科 供應(yīng)科 銷售科 檢驗(yàn)科 動(dòng)力科 Page 89 樹(shù)與圖的最小樹(shù) 樹(shù)：無(wú)圈的連通圖即為樹(shù) 性質(zhì) 1：任何樹(shù)中必存在次為 1的點(diǎn)。 性質(zhì) 2： n 個(gè)頂點(diǎn)的樹(shù)必有 n1 條邊。 性質(zhì) 3：樹(shù)中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈。 性質(zhì) 4：樹(shù)連通，但去掉任一條邊，必變?yōu)椴贿B通。 性質(zhì) 5：樹(shù)無(wú)回圈，但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)圈。 v1 v2 v3 v4 v5 v6 Page 90 最短路問(wèn)題 問(wèn)題描述： 就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間距離最短的一條路 . 有些問(wèn)題，如選址、管道鋪設(shè)時(shí)的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃的問(wèn)題，也可以歸結(jié)為求最短路的問(wèn)題。因此這類問(wèn)題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。 Page 91 最短路問(wèn)題 求最短路有兩種算法 : 狄克斯屈拉 (Dijkstra)標(biāo)號(hào)算法 逐次逼近算法 Page 92 最短路問(wèn)題 狄克斯屈拉 (Dijkstra)標(biāo)號(hào)算法的基本思路： 若序列 { vs,v1…..v n1,vn }是從 vs到 vt間的最短路，則序列{ vs,v1…..v n1 } 必為從 vs 到 vn1的最短路。 假定 v1→v 2 →v 3 →v 4是 v1 →v 4的最短路，則 v1 →v 2 →v 3一定是 v1 →v 3的最短路， v2 →v 3 →v 4也一定是 v2 →v 4的最短路。 v1 v2 v3 v4 v5 Page 93 最短路問(wèn)題 求網(wǎng)絡(luò)圖的最短路，設(shè)圖的起點(diǎn)是 vs,終點(diǎn)是 vt ,以 vi為起點(diǎn) vj為終點(diǎn)的弧記為 (i, j) 距離為 dij P標(biāo)號(hào) (點(diǎn)標(biāo)號(hào) )： b(j) — 起點(diǎn) vs到點(diǎn) vj的最短路長(zhǎng)； T標(biāo)號(hào) (邊標(biāo)號(hào) )： k(i,j)=b(i)+dij， 步驟： 1. 令起點(diǎn)的標(biāo)號(hào)； b(s)＝ 0。 2. 找出所有 vi已標(biāo)號(hào) vj未標(biāo)號(hào)的弧集合 B={(i, j)} 如果這樣的弧不存在或 vt已標(biāo)號(hào)則計(jì)算結(jié)束； 3. 計(jì)算集合 B中弧 k(i， j)=b(i)+dij的標(biāo)號(hào) 4. 選一個(gè)點(diǎn)標(biāo)號(hào) 在終點(diǎn) vl處標(biāo)號(hào) b(l), 返回到第 2步。 ? ? ,),(|),(m i n)( Bjijiklb j ??Page 94 最短路問(wèn)題 例 求下圖 v1到 v7的最短路長(zhǎng)及最短路線 ① ② ③ ④ ⑤ ⑥ ⑦ 8 6 2 5 2 3 5 3 4 2 10 5 7 0 8 6 2 2 5 4 4 11 14 7 5 10 7 12 11 v7已標(biāo)號(hào)，計(jì)算結(jié)束。從 v1到 v7的最短路長(zhǎng)是 11, 最短路線： v1→ v4 → v6 → v7 P標(biāo)號(hào) T標(biāo)號(hào) Page 95 網(wǎng)絡(luò)的最大流 基本概念： 1. 容量網(wǎng)絡(luò)： 隊(duì)網(wǎng)絡(luò)上的每條弧 (vi,vj)都給出一個(gè)最大的通過(guò)能力，稱為該弧的 容量 ，簡(jiǎn)記為 cij。容量網(wǎng)絡(luò)中通常規(guī)定一個(gè) 發(fā)點(diǎn) (也稱源點(diǎn)，記為 s)和一個(gè) 收點(diǎn) (也稱匯點(diǎn)，記為 t)，網(wǎng)絡(luò)中其他點(diǎn)稱為 中間點(diǎn) 。 s ① ② ③ ④ t 4 8 4 4 1 2 2 6 7 9 Page 96 網(wǎng)絡(luò)的最大流 2. 網(wǎng)絡(luò)的最大流 是指網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)之間允許通過(guò)的最大流量。 3. 流與可行流 流 是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，對(duì)加在弧 (vi,vj)上的負(fù)載量記為 fij。若 fij=0，稱為零流。 滿足以下條件的一組流稱為 可行流 。 容量限制條件。容量網(wǎng)絡(luò)上所有的弧滿足： 0≤fij≤cij 中間點(diǎn)平衡條件。 ),(0),(),( tsivvfvvf ijji ???? ? 若以 v(f)表示網(wǎng)絡(luò)中從 s→ t的流量，則有： ? ? ??? 0),(),()( tjjs vvfvvffvPage 97 網(wǎng)絡(luò)的最大流 結(jié)論：任何網(wǎng)絡(luò)上一定存在可行流。（零流即是可行流） 網(wǎng)絡(luò)最大流問(wèn)題： 指滿足容量限制條件和中間點(diǎn)平衡的條件下，使 v(f)值達(dá)到最大。 Page 98 網(wǎng)絡(luò)的最大流 割與割集 割是指容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開(kāi)，并使 s→t 的流中斷的一組弧的集合。割容量是組成割集合中的各條弧的容量之和，用 表示。 ),( VVc???),(),(),(),(VVjiji vvcVVc如下圖中， AA′將網(wǎng)絡(luò)上的點(diǎn)分割成 兩個(gè)集合。并有 ，稱弧的集合 {(v1,v3),(v2,v4)}是一個(gè)割，且 的流量為 18。 VV,VtVs ?? ,VV ?Page 99 網(wǎng)絡(luò)的最大流 ● s t v1 v3 v2 v4 8(8) 9(5) 5(5) 10(9) 6(0) 2(0) 9(9) 5(3) 7(6) A A’ B B’ Page 100 網(wǎng)絡(luò)的最大流 定理 1 設(shè)網(wǎng)絡(luò) N中一個(gè)從 s 到 t 的流 f 的流量為 v(f )， (V, V180。)為任意一個(gè)割集，則 v(f ) = f(V, V180。) ? f(V180。, V) 推論 1 對(duì)網(wǎng)絡(luò) N中任意流量 v(f )和割集 (V, V180。)，有 v(f ) ? c(V, V180。) [證明 ] w= f(V, V180。) ? f(V180。, V) ? f(V, V180。) ? c(V, V180。) 推論 2 最大流量 v＊ (f )不大于最小割集的容量，即： v＊ (f ) ? min{c(V, V180。)} 定理 2 在網(wǎng)絡(luò)中 s→ t的最大流量等于它的最小割集的容量， 即： v＊ (f ) = c ＊ (V, V180。) Page 101 網(wǎng)絡(luò)的最大流 求網(wǎng)絡(luò)最大流的標(biāo)號(hào)算法： [基本思想 ] 由一個(gè)流開(kāi)始，系統(tǒng)地搜尋增廣鏈，然后在此鏈上增流，繼續(xù)這個(gè)增流過(guò)程，直至不存在增廣鏈。 [基本方法 ] (1) 找出第一個(gè)可行流，（例如所有弧的流量 fij =0。） (2) 用標(biāo)號(hào)的方法找一條增廣鏈 首先給發(fā)點(diǎn) s標(biāo)號(hào) (∞),標(biāo)號(hào)中的數(shù)字表示允許的最大調(diào)整量。 選擇一個(gè)點(diǎn) vi 已標(biāo)號(hào)并且另一端未標(biāo)號(hào)的弧沿著某條鏈向收點(diǎn)檢查： Page 102 網(wǎng)絡(luò)的最大流 如果弧的起點(diǎn)為 vi，并且有 fijCij，則給 vj標(biāo)號(hào)為 (Cij－ fij) 如果弧的方向指向 vi， 并且有 fji0，則 vj標(biāo)號(hào) (fji) (3) 重復(fù)第 (2)步，可能出現(xiàn)兩種結(jié)局： 標(biāo)號(hào)過(guò)程中斷， t無(wú)法標(biāo)號(hào)，說(shuō)明網(wǎng)絡(luò)中不存在增廣鏈，目前流量為最大流。同時(shí)可以確定最小割集， 記已標(biāo)號(hào)的點(diǎn)集為 V,未標(biāo)號(hào)的點(diǎn)集合為 V′,(V,V′)為網(wǎng)絡(luò)的最小割。 t得到標(biāo)號(hào)，反向追蹤在網(wǎng)絡(luò)中找到一條從 s到 t得由標(biāo)號(hào)點(diǎn)及相應(yīng)的弧連接而成的增廣鏈。繼續(xù)第 (4)步