【正文】 的顏色。 非對稱關(guān)系：甲隊勝乙隊，用帶箭頭的連線表示， 稱為 弧 。圖的幾何實現(xiàn)有助與我們直觀的了解圖的許多性質(zhì) . ( , )e u v?u v e w e1 e u v?或設(shè) G是一個圖， ( , )G V E?1 2 3( ) { , , }V G v v v?1 2 3 4 5( ) { , , , , }E G e e e e e?1 1 2e v v?2 1 2e v v?3 1 3e v v?4 2 3e v v?5 3 3e v v?G的幾何實現(xiàn) 其中： 1e2e3e4e5e1v2v3v例 說明 一個圖的幾何實現(xiàn)并不是唯一的；表示頂點的點和表示邊的線的相對位置并不重要，重要的是圖形描繪出 邊與頂點之間保持的相互關(guān)系 。 導出子圖 G[V W]記為 GW，即 ]\)([( WGVGWG ??它是從 G中刪除 W中頂點以及與這些頂點相關(guān)聯(lián)的邊所得到的子圖。 割集： 刪除掉連通圖中的若干條必要的邊后，使得圖不連通，則這些邊的集合稱為圖的一個 割集 . 割邊 ：刪除掉這條邊后圖 G不連通。 2e3e4e5e6e7e1v2v3v4v1e1v2v3v4v1v 2v 3v 4v二、圖的矩陣表示 2. 關(guān)聯(lián)矩陣 ?????????????0211000100110000001111010011)( GM取值可能為 0、 2?；蚝喎Q為 圖 G的樹 . ? 支撐樹也稱為連通圖的 極小連通支撐子圖 。最適合于圖上作業(yè)。若全部點為 P標號 ,則停止。否則 m=m+1,轉(zhuǎn) (2). 2 2 2 3 1 1 v0 v2 v1 v3 最后解得 ： d3(v1)=1， d3(v2)= 1， d3(v3)= 2. 0 1 1 2 即 v0到 v1最短路長度為 d3(v1)=1，最短路為 v0,v3,v1 . 即 v0到 v2最短路長度為 d3(v2)= 1,最短路為 v0,v3,v1,v2 . 即 v0到 v3最短路長度為 d3(v3)= 2,最短路為 v0,v3 . Ford算法基本步驟： (1) 令 m=1,令 d1(v0)=0, d1(vi)=w(v0 ,vi). (2) 令 1 ( ) m i n { ( ) ( , ) } , 1 , 2 , , .mm iivVd v d v w v v i n??? ? ?當 vi , v 為同一個點時，有 w(v ,vi)=0. (3)若 m+1=p 則停止。 例如，每年都購置一臺新設(shè)備，則其購置費用為11+11+12+12+13=59， 而每年支付的維修費用為 5，五年合計為 25， 于是五年總的支付費用為 59+25=84. 年度 第 1年 第 2年 第 3年 第 4年 第 5年 購買費 11 11 12 12 13 使用年數(shù) 01 12 23 34 45 維修費用 5 6 8 11 18 又如，決定在第一、三、五年各購進一臺新設(shè)備，則其購置費用為 11+12+13=36， 維修費用為 5+6+5+6+5=27， 于是五年總的支付費用為 36+27=63. 可把這個問題化為最短路問題。 對每條弧 (vi ,vj)，有 弧的容量 cij ， 弧的流量 fij ， 常記做 (fij , cij ). 如 fs1 = 5， f12 = 4 ， f42 = 2. 集合 f={ fij } 稱為 網(wǎng)絡(luò) D上的一個流 . 2. 可行流與最大流 稱滿足下列條件的流 f 為 可行流： (1)容量限制條件：對所有弧 (vi ,vj) ，成立 (2)平衡條件：對所有中間頂點 v ，成立 其中， f +(v)是流出 v 的總流量， f (v)是流入 v的總流量， 對于源點 v s和匯點 vt ，流出源點 vs 的流量等于流入?yún)R點 v t的流量 . 0 ij ijfc??( ) ( )f v f v???稱之為 流 f 的值 ，記為 val f 或 v( f ). ( , )( ) ( ) ,v u Af v f v u??? ?( , ) ( ) ( ) .u v Af v f u v??? ?( , ) ( , )( ) ( ) ( ) ( ) ( )sts s t tv u A u v Av f f v f v u f v f u v????? ? ? ???可行流總是存在的。 Ford 與 Fulkerson 在 1957年提出一個求解網(wǎng)絡(luò)最大流問題的算法，稱為 Ford Fulkerson 算法 。 50年代福持 (Ford)、富克遜 (Fulkerson)建立的“網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成部分。 如果還希望給出具體的最短路經(jīng)，則在運算過程中要保留下標信息，即 等等。每次求出從出發(fā)點 v0到其余點的有限制的最短路，逐次放寬條件。 算法每一步都把某個頂點的 T 標號改為 P 標號， 當終點 vt 得到 P 標號時，計算結(jié)束。 1 2 2 4 4 3 4 2 v1 v2 v4 v5 v3 1 2 3 2 v1 v2 v4 v5 v3 評注 Kruskal算法的總計算量為 ， 有效性不太好 。 ? G連通并且每條邊都是割邊。 7 6 5 2 8 9 3 6 u v y x w 7. 有向圖 圖 G的每條邊如果有方向，稱為 有向圖 。 圈： u a v b w h y e u a b d e f g h c u v y x w 定理 ：一個圖是二分圖當且僅當圖中不存在奇圈 . 連通性 圖 G稱為 連通 的，如果 G的任意兩個頂點 u 和 v 中存在一條 (u,v)路。完全二分圖記為 Km,n X: Y: 特殊圖例 都是 極小 的 非平面圖 . K5 K3,3 （次） 3)( 2 ?vd4)( 1 ?vd3)( 3 ?vd 4)( 4 ?vd稱度為奇數(shù)的頂點為 奇點 ； 稱度為偶數(shù)的頂點為 偶點 . 設(shè) G是一個圖， G=(V(G), E(G), ?G)，定義圖 G的頂點 v 的度 為與頂點 v相關(guān)聯(lián)的邊數(shù)，記作 d(v). 2e3e4e5e6e7e1v2v3v4v1e定理 設(shè) G是一個圖，則 ()( ) 2v V Gd v q???推論 ：圖中奇點的數(shù)目為偶數(shù)。它直觀清晰，使用方便，易于掌握。 問題 ：求一個圈，過每邊至少一次，并使圈的長度最 短。第十章 圖論與網(wǎng)絡(luò)優(yōu)化 1 圖的基本概念 2 最小樹問題 3 最短路問題 4 網(wǎng)絡(luò)最大流問題 5 最小費用最大流問題 一 些 問 題 圖論中著名問題 . 1736年，圖論的創(chuàng)始人 Euler巧妙地將此問題化為圖的不重復(fù) 一筆畫問題 ，并證明了該問題不存在肯定回答，發(fā)表了第一篇論文 . 例：七橋問題 A B C D 問題：一個散步者能否走過七座橋，且每座橋只走 過一次，最后回到出發(fā)點。 例： 有甲、乙、丙、丁、戊五個球隊，各隊之間比賽 情況如表： 甲 乙 丙 丁 戊 甲 勝 負 勝 勝 乙 負 勝 丙 勝 負 勝 丁 負 負 負 戊 負 勝 點：球隊； 連線：兩個球隊之間比賽過，如甲勝乙，用 v1 v2表示。 ?應(yīng)用領(lǐng)域：物理學、化學、控制論、信息論、管理科學、通信系統(tǒng)、交通運輸系統(tǒng)、建筑、計算機科學、生產(chǎn)工藝流程以及軍事后勤保障系統(tǒng)等的問題常用圖論模型來描述。 度為 1的點稱為 懸掛點 , 連結(jié)懸掛點的邊稱為 懸掛邊 . 度為 0的點稱為 孤立點 。 不連通圖 （ 分離圖 ）至少有兩個連通分支。 有向圖的邊稱為 有向弧 （簡稱 弧 ） ,用 ai 表示 . 有向圖的各弧用邊對應(yīng)替換后所得的無向圖稱為該有向圖的 基礎(chǔ)圖 。 ? G中任意兩點都有唯一的路相連。 求最小樹的一個好的算法是 Dijkstra于 1959年提出的 ， 算法的實質(zhì)是在圖的 個獨立割集中 ， 取每個割集的一條極小邊來構(gòu)成最小樹 。最多 n1步。 即第一次逼近是找 v0到 vn的最短路，但限于最短路只允許有一條邊（?。?，其距離記為 d1(v0 ,vn).簡記為 d 1(vn). 第二次逼近，再找 v0到 vn的最短路，其限制條件放寬到允許最短路不超過兩條邊（弧），其距離記為 d 2(vn). 到第 m次逼近 ,d m(vn)表示由 v0到 vn的不超過 m條邊（?。┙M成的最短路的距離。 i k k j i k jd d d??如在 D(1)中的 是由 ( 1 )0 5 1 25 0 6 7 22 3 0 2 82 7 3 0 42 4 4 0D???????? ?????????(1)23 6d ? ( 0 ) ( 0 )2 1 1 3 5 1 6dd ? ? ? ?得到的，所以 可以寫成 . (1)23d 2136( 2 )0 5 1 2 75 0 6 7 22 3 0 2 52 7 3 0 47 2 4 4 0D??????? ????????而 D(2)中的 是由 ( 2 )35 5d ?( 1) ( 1)3 2 2 5 3 2 5dd ? ? ? ?得到的，所以 可以寫成 . (2)35d 3255( 2 )0 5 1 2 75 0 6 7 22 3 0 2 52 7 3 0 47 2 4 4 0D??????? ????????而 D(2)中的 是由 ( 2 )35 5d ?( 1) ( 1)3 2 2 5 3 2 5dd ? ? ? ?得到的，所以 可以寫成 . (2)35d 3255( 3 )0 4 1 2 65 0 6 7 22 3 0 2 52 6 3 0 46 2 4 4 0D??????? ????????而 D(3)中的 是由 ( 3 )15 6d ? ( 2 ) ( 2 )1 3 3 5 1 5 6dd ? ? ? ?得到的，而 所以 可以寫成 等 . (3)15d 13256( 2 )3 5 3 2 55d ?由此 13 2 13 14 13 2521 21 3 25 4 25( 5 )31 32 34 32 541 41 32 41 3 4553 1 52 53 540 4 1 2 65 0 6 6 22 3 0 2 52 6 3 0 46 2 4 4 0D????? ??????v1 v2 v4 v3 v5 5 1 2 2 3 10 2 8 4 4 6 2 應(yīng) 用 舉 例 例 1 設(shè)備更新問題 . 某工廠使用一臺設(shè)備，每年年初工廠都要作出決定．如果繼續(xù)使用舊的，要付維路費；若購買一臺新設(shè)備．要付購買費。 8 5 2 8 7 9 6 6 5 3 vs v1 vt v4 v3 v2 一、最大流基本概念 1. 網(wǎng)絡(luò)與流 給一個有向連通圖 D=(V,A)，在 V 中指定了一個點，稱為 發(fā)點 (或 源 ，記為 vs，其入度為 0)，和另一個點，稱為 收點 (或 匯 ，記為 vt，其出度為 0)，其余點叫 中間點 ， 對 D的每條弧 (vi ,vj)對應(yīng)有一個非負數(shù) cij ,稱為 弧的容量 ，這樣的網(wǎng)絡(luò) D稱為 容量網(wǎng)絡(luò) ，常記做 D =(V,A,C)。 Ford Fulkerson 算法步驟： 1. 標號過程 (尋找流 f 的增廣鏈 ) ?(1) 給 網(wǎng)絡(luò)賦一個初始 0流 f 0；給 vs 標號 (,∞)。 (5,8) (4,5) (2,2) (3,8) (1,7) (6