【正文】 ???????????????????????????????????????)2()3()2(1最小連接問題 作為最小樹的應(yīng)用問題之一是所謂的連接問題：欲建造一個連接若干城鎮(zhèn) （ 礦區(qū)或工業(yè)區(qū) ） 的鐵路網(wǎng) ， 給定城鎮(zhèn) i和 j之間直通線路的造價為 cij， 試設(shè)計一個總造價最小的鐵路運輸圖 。 這時圈起來的元素代表最小樹的邊 ，所有圈起來的元素之和就是最小樹的權(quán) 。 Step1：在畫橫線的元素中找一個最小的 w ij ， 用圓圈起來 ，把第 j列其他元素畫掉 ， 并把第 j行沒有畫掉的元素畫上橫線 。若 vi vj不是 G的邊 ， 則令 wij 等于無窮大 。 為了便于計算機計算 ， 下面介紹 Dijkstra的表上算法 。 算例 3 圖 720展示了利用破圈法求最小樹的迭代過程 。 Step1 若 G不含圈，則停止；否則在 G中找一個圈 C，取圈 C的一條邊 e ，滿足 )(m ax)( )( fwew CEf ??最小樹算法 3 破圈法 Step2：置 G = G e ，返回 Step1。最適合于圖上作業(yè)。 v1 v2 v4 v5 v3 1 2 2 4 4 3 4 2 v1 v2 v4 v5 v3 1 2 2 4 4 3 4 2 圖 719 利用 Dijkstra算法求最小樹的迭代過程 。 求最小樹的一個好的算法是 Dijkstra于 1959年提出的 ， 算法的實質(zhì)是在圖的 個獨立割集中 ， 取每個割集的一條極小邊來構(gòu)成最小樹 。 算例 圖 718展示了利用 Kruskal算法求最小樹的迭代過程 。 算法步驟如下 ?Step0 把邊按權(quán)的大小從小到大排列得： meee ?, 101,0, ???? jiS置 Step1 若 ，則停，此時 G[S]即為所求的最小樹； 否則，轉(zhuǎn)向 Step2。 定理 6 ? 設(shè) T是 G的支撐樹，則 T是 G的最小樹的充分必要條件為對任意邊 ， Te?)(m i n)( fwew ?eTe ??? )(其中 為 G的唯一割集。是 eTf ?設(shè) G是一個賦權(quán)圖， T為 G的一個支撐樹。 ?定理 3 設(shè) T是連通圖 G的一棵支撐樹， e是 T的任意一條邊，則： T （ 1） 不包含 G的割集 eT ?（ 2） 包含 G的唯一的割集。 定理 ? 定理 4 設(shè) T1 和 T2 是 G的兩個支撐樹，令 則 T1 經(jīng)過 k次迭代后可得到 T2。 ? 每個連通圖都有支撐樹 ? 支撐樹也稱為連通圖的極小連通支撐子圖。 ? G無圈，但在任意一對不相鄰的頂點之間加連一條邊，則構(gòu)成唯一的一個圈。 ? G連通并且每條邊都是割邊。 ? 無圈且 m=n1。 1?? r?定理 1 設(shè) G是一個簡單圖， ，則下列六個命題是等價的。 性質(zhì) 1 設(shè) G是一棵樹，則： G中任意兩點均有唯一的路連接。 ?下圖列出了具有六個頂點的不同構(gòu)的樹。 樹 ? 樹（ tree）是一個不包含圈的簡單連通圖。 ω表示 G的連通分支數(shù)。 ?不連通圖至少有兩個連通分支。 ? 推論 1 設(shè) G是一個連通圖，則 G有 Euler鏈當(dāng)且僅當(dāng) G最多有兩個奇數(shù)次數(shù)的頂點。 Euler鏈 :ydxcwheuavfygvbw u v w x y a b d e f g h c 圖例 ? 下例給出了一個圖的徑，鏈和路。 Euler圈 ? Euler圈是指過所有邊一次且恰好一次的 閉途徑 。 ? 稱一個圈是偶圈（奇圈），如果它的圈長是偶數(shù)（奇數(shù)）。 鏈長是 W中邊的個數(shù) k。 其中 vi與 vi+1是邊 ei的頂點 。 ?在簡單圖中，徑可由頂點序列表示。 如 F={ e }，則記 。記為 G[F]。 如果 W僅含一個頂點 v，則把 簡記為 。 頂點導(dǎo)出子圖 ]\)([( WGVGWG ??}{vG ? vG?設(shè) W是圖 G的一個非空頂點子集 ,以 W為頂點集，以二端點均在 W中的邊的全體為邊集的子圖稱為由 W導(dǎo)出的 G的子圖，簡稱導(dǎo)出子圖，記為 G[W]。 (X,Y)也稱為圖的二分劃。 同構(gòu) 稱 G和 H是同構(gòu)的，記為 ， )),(),(( GGEGVG ?? )),(),(( HHEHVH ??HG ?)()(: HVGV ?? )()(: HEGE ??)()())(( vueH ???? ?uveG ?)(?),( ??使得 給定兩個圖 如果存在兩個一一對應(yīng) 同構(gòu)圖例 ? 圖 G與圖 H是同構(gòu)的。 本書只限于討論有限簡單圖， 即頂點集與邊集都是有限集的圖。2( m o d0)()()(11)(1001??????????????????????VVvvdvdvdvdvdvdVvVvVvVvGVv??簡單圖 一個圖稱為 簡單圖 ，如果它既沒有環(huán)也沒有多重邊。2( m o d0)()。2( m o d0)(),({0 ??? vdGVvV) } 。 定理 設(shè) G是一個圖，則 ?2)()(??? GVvvd推論 圖中奇點的數(shù)目為偶數(shù)。 例 ?????????????0211000100110000001111010011)( GM2e3e4e5e6e7e1v2v3v4v1e4)( 1 ?vd3)( 2 ?vd3)( 3 ?vd4)( 4 ?vd2 2 2 2 2 2 2 4+3+3+4=14=2 7 關(guān)聯(lián)矩陣性質(zhì) 圖 G的關(guān)聯(lián)矩陣 M=(mij)為 m n矩陣；則每行元 素之和等于相應(yīng)頂點的度；每列元素之和等于 2。 關(guān)聯(lián)矩陣和鄰接矩陣統(tǒng)稱圖的矩陣表示。 其中 關(guān)聯(lián)矩陣 ?????????????0211000100110000001111010011)( GM2e3e4e5e6e7e1v2v3v4v1e設(shè) G是一個圖， G=(V(G),E(G)) 定義圖 G的關(guān)聯(lián)矩陣 M=(mij)為 m n矩陣； 其中 mij是頂點 vi與邊 ej相關(guān)聯(lián)的次數(shù)， 取值可能為 0、 2。 在右圖中， e5 是一個環(huán)， e1 與 e2 是多重邊， v1和 e1,e2,e3是關(guān)聯(lián)的， v1與 v2,v3是鄰接的。 1e2e 3e4e5e6e1v 2v4v基本概念 端點重合為一點的邊稱為 環(huán) 。 4e1e2e3e5e6e1v2v3v4v4e1e2e3e4v5e6e1v2v3v 4v平面圖 一個圖稱為平面圖，如它有一個平面圖形，使得邊與邊僅在 頂點相交。 幾何實現(xiàn)圖例 在一個圖的幾何實現(xiàn)中，兩條邊的交點可能不是圖的頂點。 我們常常把一個圖的圖形當(dāng)作這個抽象圖自身 . 并稱圖形的點為頂點，圖形的線為邊。 圖的幾何實現(xiàn)有助與我們直觀的了解圖的許多性質(zhì)。 若 稱端點 u， v與邊 e是 關(guān)聯(lián)的 ， 稱兩個頂點 u， v是 鄰接 的。,)(。 167。 1736年， Euler巧妙 地將此問題化為圖的不重復(fù)一筆畫問題，并證明了 該問題不存在肯定回答。 網(wǎng)絡(luò)規(guī)劃概述 ? 網(wǎng)絡(luò)規(guī)劃 (Network Programming )是圖論與線性規(guī)劃的交叉學(xué)科，具有廣泛的應(yīng)用背景，比如，最短路問題、最小樹問題、最大流問題、最優(yōu)匹配問題等。第十章 圖與網(wǎng)絡(luò)優(yōu)化 圖論概述 ?圖論 (Graph Theory)是運籌學(xué)中的一個重要分支，主要研究具有某種二元關(guān)系的離散系統(tǒng)的組合結(jié)構(gòu)和性質(zhì)。 如，通信系統(tǒng)、交通運輸系統(tǒng)、信息網(wǎng)絡(luò)系統(tǒng)、生產(chǎn)工藝流程以及軍事后勤保障系統(tǒng)等的問題常用圖論模型來描述。 七橋問題 七橋問題圖形 原 理 及 方 法 七橋問題是圖論中的著名問題。原因在于該圖形有頂點連 接奇數(shù)條邊。 圖的基本概念 一個圖 (Graph) 定義為三元有序組 V(G)是圖的頂點集合 E(G)是 圖 的邊集合 。,)(的邊數(shù)的頂點數(shù)GGEnGGVm????記 )),(),(( GGEGV ?Ψ 是關(guān)聯(lián)函數(shù) 圖的端點 設(shè) G是一個圖 (Graph) G=(V(G),E(G))， uveGVvuGEe G ??? )(),(,),( ?則稱 e連接 u和 v，稱 u和 v是 e的端點。 設(shè) G是一個圖， )),(),(( GGEGVG ??},{)( 321 vvvGV ?},{)( 54321 eeeeeGE ?1e2e3e4e5e1v2v3v圖 10－３ G的幾何實現(xiàn) 圖的幾何實現(xiàn) 一個圖可用一個幾何圖形表示 ,稱為圖的幾何實現(xiàn)，其中 每個頂點用點表示， 每條邊用連接端點的線表示。 說明 一個圖的幾何實現(xiàn)并不是唯一的；表示頂點的點和表示邊的線的相對位置并不重要，重要的是圖形描繪出 邊與頂點之間保持的相互關(guān)系 。 圖論中大多數(shù)概念是根據(jù)圖的表示形式提出的，例如：頂點、邊、多重邊、環(huán)、路、圈、樹等。例如下圖 中，它共有 4個頂點， 6條邊；而 e 3 與 e 4 的交點不是這個圖的頂點。下圖就是一個平面圖。 連接同一對頂點的多條邊稱為 多重邊 。 1e2e3e4e5e1v2v3v鄰接矩陣 設(shè) G是一個圖， G=(V(G),E(G))，定義圖 G的鄰接矩陣 A(G) =(aij)為 m m矩陣 , 2e3e4e5e6e7e1v2v3v4v1e???????????????110110110102