【正文】 布 ,由該 廠所生產(chǎn)的雙色布中 ,每一種顏色至少和其他三種顏色搭 配 .證明 可以挑選出三種不同的雙色布 ,它們含有所有的 6 種顏色 . 證明 :構(gòu)造圖 G=V,E,其中 V={v1,v2,v3,v4,v5,v6}表示 6種顏 色 ,工廠生產(chǎn)出一種顏色 vi與 vj搭配而成的雙色布 ?邊 {vi,vj} ?E(G).由題意知 ,G為簡單圖 ,且每個(gè)結(jié)點(diǎn)的度數(shù)至少為 3,下證 G中含有一個(gè)完美匹配 . 今設(shè) {v1,v2}?E(G),由于 d(v3) ≥3,所以存在一個(gè)不同于 v1和 v2的頂點(diǎn) vi(4≤i≤6),使 {v3,vi}?E(G),不妨設(shè) vi=4, 即 {v3,v4}?E(G). 如果邊 {v5,v6}?E(G),由于 d(v5)≥3,v1,v2,v3,v4中至少有 3個(gè)頂點(diǎn)與 v5相鄰 ,即 v5與邊 {v1,v2},{v3,v4}中的每一邊的某一個(gè)端點(diǎn)相鄰 ,不妨設(shè) {v1,v5}?E(G)和{v3,v5}?E(G). 對于頂點(diǎn) v6,同樣與 v1,v2,v3,v4中至少 3個(gè)頂點(diǎn)相鄰 ,即在 v2和 v4中至少有一個(gè)頂點(diǎn)與 v6相鄰 .如果{v2,v6}?E(G),則邊 {v1,v5},{v3,v4},{v2,v6}是 G的一個(gè)完美匹配 。 X X X X X Xb r b r r r1 2 1 3 4 1 5 2 6 3? ? ? ? ?( ) ( ) ( ) ( ) 因此，計(jì)劃為第一、第三年初購置新設(shè)備，或第一、第四年初購置新設(shè)備， 五年費(fèi)用均最省，為 53 . 也可構(gòu)造加權(quán)有向圖 G 2( V , E ) . （ 1 ）頂點(diǎn)集 V ={ V V V V V V1 2 3 4 5 6, , , , ,} ，V i 表第 i 年初購置新設(shè)備的決策， V 6 表第五年底 . （ 2 ）弧集 E ={( , )V Vi j， i = 1,2,3,4, 5。 k= 1,2, … , i 1} ∪ {( , ),( )X Xib i r? 11, i =1,2,3,4 ,5} ∪ {( , )( ) ,( )X Xir k i rk? ?1 1, i= 1,2,3,4,5 。 由 v 4 向 v 1 追溯 ： 141 ?r 所以從 v 5 到 v 1 的最短路徑為： 1435 ??? .返回 最 短 路 的 應(yīng) 用 一、 可化為最短路問題的多階段決策問題 二、 選 址 問 題 1． 中心問題 2． 重心問題 返回 可化為最短路問題的多階段決策問題 例 1 設(shè)備更新問題：企業(yè)使用一臺(tái)設(shè)備，每年年初，企業(yè)領(lǐng)導(dǎo)就要確定是購置新的，還是繼續(xù)使用舊的 . 若購置新設(shè)備，就要支付一定的購置費(fèi)用；若繼續(xù)使用，則需支付一定的維修費(fèi)用 . 現(xiàn)要制定一個(gè)五年之內(nèi)的設(shè)備更新計(jì)劃，使得五年內(nèi)總的支付費(fèi)用最少 . 已知該種設(shè)備在每年年初的價(jià)格為： 第一年 第二年 第三年 第四年 第五年 11 11 12 12 13 使用不同時(shí)間設(shè)備所需維修費(fèi)為： 使用年限 0 － 1 1 － 2 2 － 3 3 － 4 4 － 5 維修費(fèi) 5 6 8 11 18 構(gòu)造加權(quán)有向圖 G 1( V , E ) （ 1 ）頂點(diǎn)集 V ＝ { Xib , i =1,2, 3,4, 5} ∪ { X ir k( ) , i =2,3, 4,5, 6。 ? 18世紀(jì)東普魯士哥尼斯堡被普列戈?duì)柡臃譃樗膲K ,它們通過七座橋相互連接 ,如下圖 .當(dāng)時(shí)該城的市民熱衷于這樣一個(gè)游戲 :“一個(gè)散步者怎樣才能從某塊陸地出發(fā)，經(jīng)每座橋一次且僅一次回到出發(fā)點(diǎn)？” S N A B 七橋問題的分析 ? 七橋問題看起來不難，很多人都想試一試，但沒有人找到答案 .后來有人寫信告訴了當(dāng)時(shí)的著名數(shù)學(xué)家歐拉 .千百人的失敗使歐拉猜想 ,也許那樣的走法根本不可能 .1876年 ,他證明了自己的猜想 . ? Euler把南北兩岸和四個(gè)島抽象成四個(gè)點(diǎn) ,將連接這些陸地的橋用連接相應(yīng)兩點(diǎn)的一條線來表示 ,就得到如下一個(gè)簡圖 : S N A B 歐拉的結(jié)論 ? 歐拉指出 :一個(gè)線圖中存在通過每邊一次僅一次回到出發(fā)點(diǎn)的路線的充要條件是 : ? 1)圖是連通的 ,即任意兩點(diǎn)可由圖中的一些邊連接起來 。 ? 2)與圖中每一頂點(diǎn)相連的邊必須是偶數(shù) . ? 由此得出結(jié)論 :七橋問題無解 . 歐拉由七橋問題所引發(fā)的研究論文是圖論的開篇之作 ,因此稱歐拉為圖論之父 . 圖是一種表示工具 .改變問題的描述方式 ,往 往是創(chuàng)造性的啟發(fā)式解決問題的手段 .一種描述 方式就好比我們站在一個(gè)位置和角度觀察目標(biāo) , 有的東西被遮擋住了 ,但如果換一個(gè)位置和角度 , 原來隱藏著的東西就可能被發(fā)現(xiàn) .采用一種新的 描述方式 ,可能會(huì)產(chǎn)生新思想 .圖論中的圖提供 了一種直觀 ,清晰表達(dá)已知信息的方式 .它有時(shí) 就像小學(xué)數(shù)學(xué)應(yīng)用題中的線段圖一樣 ,能使我們 用語言描述時(shí)未顯示的或不易觀察到的特征、 關(guān)系 ,直觀地呈現(xiàn)在我們面前 ,幫助我們分析和 思考問題 ,激發(fā)我們的靈感 . 圖的應(yīng)用是非常廣泛的 ,在工農(nóng)業(yè)生產(chǎn)、交通運(yùn)輸、通訊和電力領(lǐng)域經(jīng)常都能看到許多網(wǎng)絡(luò) ,如河道網(wǎng)、灌溉網(wǎng)、管道網(wǎng)、公路網(wǎng)、鐵路網(wǎng)、電話線網(wǎng)、計(jì)算機(jī)通訊網(wǎng)、輸電線網(wǎng)等等 .還有許多看不見的網(wǎng)絡(luò) ,如各種關(guān)系網(wǎng) ,像狀態(tài)轉(zhuǎn)移關(guān)系、事物的相互沖突關(guān)系、工序的時(shí)間先后次序關(guān)系等等 ,這些網(wǎng)絡(luò)都可以歸結(jié)為圖論的研究對象 —— 圖 .其中存在大量的網(wǎng)絡(luò)優(yōu)化問題需要我們解決 .還有象生產(chǎn)計(jì)劃、投資計(jì)劃、設(shè)備更新等問題也可以轉(zhuǎn)化為網(wǎng)絡(luò)優(yōu)化的問題 . 基本的網(wǎng)絡(luò)優(yōu)化問題有 :最短路徑問題、最小生成樹問題、最大流問題和最小費(fèi)用問題 .圖論作為數(shù)學(xué)的一個(gè)分支 ,已經(jīng)有有效的算法來解決這些問題 .當(dāng)然這當(dāng)中的有些問題也可以建立線性規(guī)劃的模型 ,但有時(shí)若變量特別多 ,約束也特別多 ,用線性規(guī)劃的方法求解效率不高甚至不能在可忍受的時(shí)間內(nèi)解決 .而根據(jù)這些問題的特點(diǎn) ,采用網(wǎng)絡(luò)分析的方法去求解可能會(huì)非常有效 . 例如 ,在 1978年 ,美國財(cái)政部的稅務(wù)分析部門在對卡特爾稅制改革做評估的過程中 ,就有一個(gè)100,000個(gè)約束以上 ,25,000,000個(gè)變量的問題 ,若用普通的線性規(guī)劃求解 ,預(yù)計(jì)要花 7個(gè)月的時(shí)間 .他們利用網(wǎng)絡(luò)分析的方法 ,將其分解成 6個(gè)子問題 ,利用特殊的網(wǎng)絡(luò)計(jì)算機(jī)程序 ,花了大約 7個(gè)小時(shí)問題就得到了解決 . 數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn) 主講：陳六新 最短路徑與最優(yōu)匹配問題 實(shí)驗(yàn)?zāi)康? 實(shí)驗(yàn)內(nèi)容 2．會(huì)用 MATLAB軟件求最短路與最優(yōu)匹配 1．了解最短路與最優(yōu)匹配的算法及其應(yīng)用 1．圖 論 的 基 本 概 念 2．最 短 路 問 題 及 其 算 法 3．最 短 路 的 應(yīng) 用 5．建模案例：最優(yōu)截?cái)嗲懈顔栴} 6．實(shí)驗(yàn)作業(yè) 4．最優(yōu)匹配及算法 圖 論 的 基 本 概 念 一、 圖 的 概 念 1．圖的定義 2．頂點(diǎn)的次數(shù) 3．子圖 二、 圖 的 矩 陣 表 示 1． 關(guān)聯(lián)矩陣 2． 鄰接矩陣 返回 定義 有序三元組 G=(V,E, )稱為一個(gè) 圖 ,如果： ?[ 1] V =},{ 21 nvvv ?是有限非空集， V 稱為 頂點(diǎn)集 ， 其中的元素叫圖 G 的 頂點(diǎn) . [ 2] E 稱為 邊集 ，其中的元素叫圖 G 的 邊 . [ 3] ? 是從邊集 E 到頂點(diǎn)集 V 中的有序或無序的元素 偶對構(gòu)成 集合的映射，稱為 關(guān)聯(lián)函數(shù) . 例 1 設(shè) G =( V , E , ? ) ，其中 V ={ v 1 ,v 2 , v 3 , v 4 } ， E ={ e 1 , e 2 , e 3 , e 4 , e 5 }, 1 1 2 2 1 3 3 1 4 4 1 4 5 4 4( ) , ( ) , ( ) , ( ) , ( )e v v e v v e v v e v v e v v? ? ? ? ? ? ? ? ? ?. G 的圖解如圖 圖的定義 定義 在圖 G 中，與 V 中的有序偶 (vi ， v j ) 對應(yīng)的邊 e ，稱為圖的 有向邊（或?。?，而與 V 中頂點(diǎn)的無序偶 v i v j 相對應(yīng)的邊 e ，稱為圖的 無向邊 . 每一條邊都是無向邊的圖，叫 無向圖 ；每一條邊都是有向邊的圖，稱為 有向圖 ；既有無向邊又有有向邊的圖稱為 混合圖 . 定義 若將圖 G 的每一條邊 e 都對應(yīng)一個(gè)實(shí)數(shù) w ( e ) ， 則 稱 w ( e ) 為邊的權(quán) ，并稱圖 G 為 賦權(quán)圖 . 規(guī)定用記號 ? 和 ? 分別表示圖的頂點(diǎn)數(shù)和邊數(shù) .常用術(shù)語： （１） 端點(diǎn)相同的邊稱為 環(huán) ． （２） 若一對頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱為 重邊 （或平行邊） ． （３