耿顯亞

(安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001)

1 圖論的基本思想

從哥尼斯堡七橋問(wèn)題開始，圖論發(fā)展了接近300年，慢慢趨于完善[1]。圖論最本質(zhì)的內(nèi)容就是一種二元關(guān)系，這種關(guān)系可以用來(lái)表示某些抽象事物或者具體事物之間的直接聯(lián)系以及間接聯(lián)系。算法是人類運(yùn)用智慧頭腦設(shè)計(jì)的用來(lái)解決某些問(wèn)題的一些列運(yùn)算。有效的算法設(shè)計(jì)與分析可以幫助人們使問(wèn)題更高效地得到解決。數(shù)學(xué)模型主要是對(duì)實(shí)際問(wèn)題利用數(shù)學(xué)符號(hào)、式子、程序、圖形等進(jìn)行刻畫，使抽象的問(wèn)題轉(zhuǎn)化為另一種更直觀，更簡(jiǎn)單的表達(dá)方式并且為解決現(xiàn)實(shí)問(wèn)題提供了一個(gè)思考方向。數(shù)學(xué)建模是一門應(yīng)用數(shù)學(xué)，把數(shù)學(xué)理論回歸現(xiàn)實(shí)并且應(yīng)用到現(xiàn)實(shí)，從而解決生活中的實(shí)際問(wèn)題。圖論的相關(guān)理論與算法設(shè)計(jì)有著密不可分的聯(lián)系，兩者之間的完美結(jié)合可以使生活中的復(fù)雜疑難問(wèn)題能夠更高效地解決，提高效率[2]。

由于現(xiàn)代科技的飛速發(fā)展，幾乎所有的領(lǐng)域都能見到使用圖論的身影：如運(yùn)籌學(xué)、物理學(xué)、生物、經(jīng)濟(jì)、管理科學(xué)、網(wǎng)絡(luò)理論、信息論、控制論和計(jì)算機(jī)科學(xué)等領(lǐng)域。

2 數(shù)學(xué)建模的實(shí)例與圖論算法

圖論經(jīng)過(guò)300年的發(fā)展，已經(jīng)逐漸為廣大人群所熟悉。圖論的“圖”與現(xiàn)實(shí)中的“圖畫”并不是一個(gè)概念，它可以抽象化地表達(dá)事物與事物之間的具體聯(lián)系。很多人知道關(guān)于圖論的知識(shí)是從哥尼斯堡七橋問(wèn)題開始的，以及后來(lái)的一筆畫問(wèn)題。通過(guò)對(duì)圖論歷史與發(fā)展的研究，我們可以看出圖論確實(shí)在許多領(lǐng)域中有十分廣泛的應(yīng)用。實(shí)際上，結(jié)合圖論知識(shí)，我們可以解答一些比較簡(jiǎn)單的現(xiàn)實(shí)生活問(wèn)題，如簡(jiǎn)單的匹配問(wèn)題，或者安排座位問(wèn)題等。越來(lái)越多的高校將圖論看作是一門獨(dú)特的學(xué)科，許多大學(xué)生對(duì)它展示了濃厚的興趣，并開展了以圖論為主要研究對(duì)象的建模比賽[3]。

本文通過(guò)提出一些數(shù)學(xué)建模問(wèn)題，對(duì)問(wèn)題進(jìn)行思考分析，尋找問(wèn)題的本質(zhì)內(nèi)容，最后利用圖論算法來(lái)處理這些問(wèn)題。

2.1 哈密頓回路問(wèn)題

在圖G中，若存在這樣的一條路：路過(guò)每結(jié)點(diǎn)一次且只能一次，那么我們把這種略微特殊的路叫做哈密頓路。與上述定義相似，在圖G中，若存在這樣的一條回路：經(jīng)過(guò)每個(gè)結(jié)點(diǎn)一次且只能一次，那么我們把這種略微特殊的回路叫做哈密頓回路。我們把具有哈密頓回路的圖稱為哈密頓圖。之所以用哈密爾頓的名字來(lái)命名，是因?yàn)樗?857年為解釋其剛發(fā)現(xiàn)的稱為“Icosian演算”的一種非交換代數(shù)系統(tǒng)，發(fā)明了一種同名游戲[4]。與歐拉圖不太一樣的是，判斷一個(gè)圖是否為哈密爾頓圖至今還沒(méi)有一個(gè)簡(jiǎn)單的的充分必要條件，只有一些必要條件和充分條件。事實(shí)上在數(shù)學(xué)界已經(jīng)證明，判定一個(gè)給定的圖是否為哈密爾頓圖的問(wèn)題是困難的，不過(guò)，數(shù)學(xué)家們已經(jīng)得到了一些判斷關(guān)于哈密爾頓圖是否存在的充分條件。定理：設(shè)n階無(wú)向簡(jiǎn)單圖G=，如果圖G中任意兩個(gè)不同結(jié)點(diǎn)的度數(shù)之和不小于n-1(或n)，則在G中存在一條哈密頓路(或回路)。這個(gè)條件只是判斷是否有哈密頓路的充分條件，但它并不是必要條件。

例：舉行一個(gè)私人會(huì)議，有A,B,C,D,E,F,G7個(gè)人。已知如下條件：西班牙語(yǔ)；B會(huì)說(shuō)西班牙語(yǔ)和漢語(yǔ)；C會(huì)說(shuō)西班牙語(yǔ)；意大利語(yǔ)和俄語(yǔ)；D會(huì)說(shuō)韓語(yǔ)和漢語(yǔ)；E會(huì)說(shuō)羅馬語(yǔ)和意大利語(yǔ)；F會(huì)說(shuō)法語(yǔ)；韓語(yǔ)和俄語(yǔ)；G會(huì)說(shuō)法語(yǔ)和白俄羅斯語(yǔ)。試求一個(gè)解決方案，恰當(dāng)?shù)陌才胚@七個(gè)人的座位，目的是使每個(gè)人都能和他身邊的人交談？

我們還是用圖來(lái)解決這個(gè)問(wèn)題?？梢赃@么做：建立一個(gè)圖的模型，如圖1所示，根據(jù)人物與語(yǔ)言確定結(jié)點(diǎn)，根據(jù)每個(gè)人會(huì)說(shuō)的語(yǔ)言確定邊。根據(jù)圖論相關(guān)知識(shí)，用結(jié)點(diǎn)代表人物，則結(jié)點(diǎn)集合可表示為V={A,B,C,D,E,F,G}。如果在這七個(gè)人中某兩個(gè)人具有相同的共同語(yǔ)言，即這兩個(gè)人可以相互交流的話，我們就在這兩個(gè)人所代表的點(diǎn)連一條邊。問(wèn)題就可以轉(zhuǎn)化為：圖G中是否存在一條哈密頓回路？由圖G分析可以看出，我們所要找的哈密頓回路為A—B—D—F—G—E—C—A。所以該問(wèn)題的解為：按A—B—D—F—G—E—C—A的順序排座位，如圖。

2.2 最短路徑問(wèn)題

最短路徑問(wèn)題在我們的實(shí)際生活中應(yīng)用非常廣泛。例如兩個(gè)指定城市之間的道路鋪設(shè)時(shí)間最少，交通費(fèi)用最少問(wèn)題等等。兩個(gè)相連接的定點(diǎn)之間的邊上通常有一定的權(quán)值，代表時(shí)間或費(fèi)用等，一般根據(jù)具體問(wèn)題而定。這些問(wèn)題實(shí)質(zhì)上就是求權(quán)值最小。

問(wèn)題提出：在兩個(gè)特定的城市間，有一個(gè)公路線路圖，此公路線路圖中有若干城市相連接。在公路線路圖中尋找一條最短的公路線路。

問(wèn)題分析：由問(wèn)題我們可以經(jīng)過(guò)分析得到一個(gè)圖G。圖中兩個(gè)頂點(diǎn)之間的邊上的權(quán)值可以代表頂點(diǎn)表示城市之間的距離。則該問(wèn)題就轉(zhuǎn)換為求兩個(gè)指定頂點(diǎn)u1，v1間具備最小權(quán)的道路的問(wèn)題。u1，v1間的最短路就是這條路線，u1，v1間的距離就是它的權(quán)，也可以記為d(u1，v1)。

問(wèn)題求解：通過(guò)對(duì)問(wèn)題的具體分析可知，若求一個(gè)城市到其他各個(gè)城市的最短路徑用迪杰斯特拉(Dijkstra)算法進(jìn)行解決是比較有效的。迪杰斯特拉算法相對(duì)而言是一種求最短路的比較成熟的算法。算法的大致過(guò)程為：

第一步：設(shè)定一個(gè)集合S，初始狀態(tài)為空集。依次求此特定的頂點(diǎn)到各個(gè)點(diǎn)的距離，若不能到達(dá)選擇用無(wú)窮大來(lái)代替。然后通過(guò)比較選擇距離最短的一條邊，并將與此條邊關(guān)聯(lián)的頂點(diǎn)計(jì)入到S集合中。同時(shí)也要將路徑記錄下來(lái)。

第二步：將S集合中的頂點(diǎn)作為中間過(guò)渡點(diǎn)，更新特定的頂點(diǎn)到各個(gè)頂點(diǎn)的最短路徑，除去第一步中的最短路徑，繼續(xù)選擇最短的路徑，然后將最短路徑中的還未計(jì)入S集合中的頂點(diǎn)計(jì)入到S集合中。

重復(fù)上面的步驟，直到S集合中出現(xiàn)全部的頂點(diǎn)，算法結(jié)束。

2.3 最小生成樹問(wèn)題

最小生成樹問(wèn)題：樹通俗的說(shuō)就是沒(méi)有圈的連通圖，常記為T。現(xiàn)有一個(gè)圖為G，假設(shè)V(G)與V(T)完全一致，而E(T)是E(G)的子集，那么此時(shí)T為G的生成樹。最小生成樹是指具有最小權(quán)的生成樹的圖[5-6]。

問(wèn)題提出：現(xiàn)在需要在n個(gè)城市之間修建石油管道，并且兩城之間的石油管道造價(jià)已知，怎樣設(shè)計(jì)線路才能使得總造價(jià)最低。

問(wèn)題分析：這種類型問(wèn)題可被總結(jié)為最小生成樹問(wèn)題，在賦權(quán)圖中找出一個(gè)具備最小權(quán)的生成樹為此問(wèn)題對(duì)應(yīng)的數(shù)學(xué)模型。

問(wèn)題解決：Prim算法是在擁有最小成本邊的基礎(chǔ)上開始的，然后層層向外擴(kuò)展，最后得到結(jié)論。其過(guò)程是這樣的：在初始狀態(tài)中只計(jì)入了一條成本最小的邊以及與此條邊關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)。然后尋找計(jì)入的下一條邊以及相關(guān)的結(jié)點(diǎn)。需要滿足的條件為：(1)這條邊的一個(gè)結(jié)點(diǎn)已經(jīng)計(jì)入生成樹中，另一個(gè)結(jié)點(diǎn)還未計(jì)入生成樹中。(2)此條邊必須在滿足(1)的情況下成本最小。依次類推，直到所有結(jié)點(diǎn)都計(jì)入到生成樹中并形成一個(gè)連通網(wǎng)，結(jié)束運(yùn)算。

求最小生成樹的一般算法可描述為：針對(duì)圖G，從空樹T開始，往集合T中逐條選擇并加入n-1條安全邊(u,v)，最終生成一棵含n-1條邊的最小生成樹。

當(dāng)一條邊(u,v)加入T時(shí)，必須保證T∪{(u，v)}仍是MST的子集，我們將這樣的邊稱為T的安全邊。

Prim算法可以概括如下

1)首先輸入：給定一個(gè)加權(quán)連通圖G，其中頂點(diǎn)集合為V(G)，邊集合為E(G)；

2)然后初始化：Vnew={x}，其中x為集合中V(G)的任一點(diǎn)(起始點(diǎn))，Enew={ }，為空；

3)重復(fù)下列操作，直到Vnew=V：

a.在集合E(G)中選取權(quán)值最小的邊(u,v)，其中u為集合Vnew中的元素，而v不在Vnew集合當(dāng)中，并且v∈V(G)；

b.將v加入集合Vnew中，將(u,v)邊加入集合Enew中；

4)輸出：使用集合Vnew和Enew來(lái)描述所得到的最小生成樹。

由于圖中的所有關(guān)系是無(wú)限制的，即任意兩個(gè)頂點(diǎn)之間都可能會(huì)有聯(lián)系，所以圖是一種比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。而圖的應(yīng)用在生活中極為廣泛，近些年圖論的迅速發(fā)展，使得圖論已經(jīng)滲入到各個(gè)分支中。圖論搜索算法可以幫助我們解決日常生活中的棘手問(wèn)題。在數(shù)學(xué)建模中除了文中提出的應(yīng)用還有著其他的應(yīng)用，如拓?fù)渑判騿?wèn)題，二分圖問(wèn)題等?？偟膩?lái)說(shuō)，圖論算法的應(yīng)用是十分廣泛的，尤其是在研究以某種特定方式相關(guān)聯(lián)的物體間的關(guān)系時(shí)。但是問(wèn)題是具有多樣性的，這就要求我們從具體問(wèn)題出發(fā)，然后具體分析，勤于思考抽象出恰當(dāng)?shù)臄?shù)學(xué)模型，并總結(jié)規(guī)律。這樣才能更深入的研究數(shù)學(xué)建模中圖論搜索算法的應(yīng)用，更加靈活的為我們?cè)诂F(xiàn)實(shí)生活中遇到的問(wèn)題找到解決方案，數(shù)學(xué)才能最大化的發(fā)揮作用。