數(shù)學(xué)建模中的圖論方法

1、1數(shù)學(xué)建模中的圖論方法一、引言一、引言我們知道，數(shù)學(xué)建模競(jìng)賽中有問題A和問題B。一般而言，問題A是連續(xù)系統(tǒng)中的問題，問題B是離散系統(tǒng)中的問題。由于我們?cè)诖髮W(xué)數(shù)學(xué)教育內(nèi)容中，連續(xù)系統(tǒng)方面的知識(shí)的比例較大，而離散數(shù)學(xué)比例較小。因此很多人有這樣的感覺，A題入手快，而B題不好下手。另外，在有限元素的離散系統(tǒng)中，相應(yīng)的數(shù)學(xué)模型又可以劃分為兩類，一類是存在有效算法的所謂P類問題，即多項(xiàng)式時(shí)間內(nèi)可以解決的問題。但是這類問題在MCM中非常少見，事實(shí)上，

2、由于競(jìng)賽是開卷的，參考相關(guān)文獻(xiàn)，使用現(xiàn)成的算法解決一個(gè)P類問題，不能顯示參賽者的建模及解決實(shí)際問題能力之大??；還有一類所謂的NP問題，這種問題每一個(gè)都尚未建立有效的算法，也許真的就不可能有有效算法來解決。命題往往以這種NPC問題為數(shù)學(xué)背景，找一個(gè)具體的實(shí)際模型來考驗(yàn)參賽者。這樣增加了建立數(shù)學(xué)模型的難度。但是這也并不是說無法求解。一般來說，由于問題是具體的實(shí)例，我們可以找到特殊的解法，或者可以給出一個(gè)近似解。圖論作為離散數(shù)學(xué)的一個(gè)重要分支

3、，在工程技術(shù)、自然科學(xué)和經(jīng)濟(jì)管理中的許多方面都能提供有力的數(shù)學(xué)模型來解決實(shí)際問題，所以吸引了很多研究人員去研究圖論中的方法和算法。應(yīng)該說，我們對(duì)圖論中的經(jīng)典例子或多或少還是有一些了解的，比如，哥尼斯堡七橋問題、中國(guó)郵遞員問題、四色定理等等。圖論方法已經(jīng)成為數(shù)學(xué)模型中的重要方法。許多難題由于歸結(jié)為圖論問題被巧妙地解決。而且，從歷年的數(shù)學(xué)建模競(jìng)賽看，出現(xiàn)圖論模型的頻率極大，比如：AMCM90B－掃雪問題；AMCM91B－尋找最優(yōu)Steine

4、r樹；AMCM92B－緊急修復(fù)系統(tǒng)的研制(最小生成樹)AMCM94B－計(jì)算機(jī)傳輸數(shù)據(jù)的最小時(shí)間(邊染色問題)CMCM93B－足球隊(duì)排名(特征向量法)CMCM94B－鎖具裝箱問題(最大獨(dú)立頂點(diǎn)集、最小覆蓋等用來證明最優(yōu)性)CMCM98B－災(zāi)情巡視路線(最優(yōu)回路)等等。這里面都直接或是間接用到圖論方面的知識(shí)。要說明的是，這里圖論只是解決問題的一種要說明的是，這里圖論只是解決問題的一種方法，而不是唯一的方法。方法，而不是唯一的方法。本文將從圖

5、論的角度來說明如何將一個(gè)工程問題轉(zhuǎn)化為合理而且可求解的數(shù)學(xué)模型，著重介紹圖論中的典型算法。這里只是一些基礎(chǔ)、簡(jiǎn)單的介紹，目的在于了解這方面的知識(shí)和應(yīng)用，拓寬大家的思路，希望起到拋磚引玉的作用，要掌握更多還需要我們進(jìn)一步的學(xué)習(xí)和實(shí)踐。3背景：背景：給定連接若干城市的鐵路網(wǎng)，尋求從指定城市v0到各城v去的最短道路。數(shù)學(xué)模型：數(shù)學(xué)模型：圖G為一賦權(quán)圖，對(duì)任給的v?V(G)，尋求軌道P(v0v)，使得W(P(v0v))=minW(P)P取自所有

6、v0到v的軌道集合其中W(P)是軌道P上各邊權(quán)之和。這一問題可用迪克斯特拉(Dijkstra)算法解決?；舅枷耄夯舅枷耄簭钠瘘c(diǎn)v0開始，逐步尋找到達(dá)各點(diǎn)的最短路，在每一步都對(duì)頂點(diǎn)記錄一個(gè)數(shù)，稱之為該點(diǎn)的標(biāo)號(hào)，它表示v0到該點(diǎn)的最短距離的上界，或就是v0到該點(diǎn)的最短距離。實(shí)際上每一步都通過把至少一個(gè)具有T標(biāo)號(hào)的點(diǎn)變成P標(biāo)號(hào)(即把一個(gè)不是最短距離標(biāo)號(hào)的頂點(diǎn)變成是最短距離標(biāo)號(hào)的頂點(diǎn))，這樣最多經(jīng)過|V(G)|1步就可完成。步驟：步驟：記l

7、(v)為v0到v的距離。(1)l(v0)=0，l(v)=?，(v?v0)；S0=v0，i=0。(2)對(duì)v?Si，minl(v)，l(vi)w(viv)代替l(v)；這樣找到點(diǎn)vi＋1使得l(v)取最小值，v(i＋1)?(Si的余集)。令S(i＋1)＝Si＋v(i1)。(3)i=|V(G)|1時(shí)停止，否則，i1，轉(zhuǎn)到(2)。實(shí)例：實(shí)例：CMCM94A－公路選址問題。32求最小生成樹求最小生成樹1克羅斯克爾(Kruskal)算法(1956年

8、)，俗稱“避圈法”背景：背景：筑路選線問題欲修筑連接n個(gè)城市的鐵路，已知i城與j城之間的鐵路造價(jià)為Cij。設(shè)計(jì)一個(gè)線路圖，使總造價(jià)最低。分析：分析：選線問題的數(shù)學(xué)模型是在連通加權(quán)圖上求權(quán)最小的連通生成子圖。顯然，權(quán)最小的連通生成子圖是一個(gè)生成樹，即求取連通加權(quán)圖上的權(quán)最小的生成樹，這就歸結(jié)為最小生成樹問題。這個(gè)問題可由克羅斯克爾(Kruskal)算法解決。思路：思路：從“邊”著手選最小生成樹。步驟：步驟：設(shè)G為由m個(gè)節(jié)點(diǎn)組成的連通賦權(quán)圖

9、。(1)先把G中所有的邊按權(quán)值大小由小到大重新排列，并取權(quán)最小的一條邊為樹T中的邊。即選e1?E，使得w(e1)＝min。(2)從剩下的邊中按(1)中的排列取下一條邊。若該邊與前面已取進(jìn)T中的邊構(gòu)成一個(gè)回路，則舍棄該邊，否則也把它取進(jìn)T中。若e1，e2，…，ei已經(jīng)選好，則從E－e1，e2，…，ei中選取ei＋1，使得G[e1，e2，…，ei，ei1]中無圈，且w(ei1)=min。(3)重復(fù)步驟(2)，直到T中有m－1條邊為止。則T為