王國興

(蘭州商學(xué)院信息工程學(xué)院，甘肅蘭州 730020）

圖論在大學(xué)生數(shù)學(xué)建模競賽中的應(yīng)用*

王國興

(蘭州商學(xué)院信息工程學(xué)院，甘肅蘭州 730020）

隨著圖論的發(fā)展，圖論的理論和方法廣泛應(yīng)用于大學(xué)生數(shù)學(xué)建模競賽中.討論了大學(xué)生數(shù)學(xué)建模競賽中如下圖論問題的應(yīng)用:二分圖的最大匹配，最大點(diǎn)獨(dú)立集;最佳推銷員回路，哈密爾頓圖;最小生成樹等.

圖論;二分圖;最佳推銷員回路;哈密爾頓圖;最小生成樹;大學(xué)生;數(shù)學(xué)建模競賽

圖論是數(shù)學(xué)的一個重要分支，它廣泛地應(yīng)用于物理學(xué)、現(xiàn)代控制論、信息論、管理科學(xué)、計(jì)算機(jī)技術(shù)等諸多領(lǐng)域.對于自然科學(xué)、工程技術(shù)、經(jīng)濟(jì)管理和社會現(xiàn)象等諸多方面的問題，利用圖論的理論和方法能夠提供有力的數(shù)學(xué)模型使問題得到解決.在國內(nèi)外大學(xué)生數(shù)學(xué)建模競賽中，與圖論的知識和方法有關(guān)的問題已出現(xiàn)多次.這里有針對性地討論圖論在大學(xué)生數(shù)學(xué)建模競賽中的應(yīng)用.

圖的基本概念如下［1～2］.

一個圖G是指一個有序三元組(V(G))，E(G)，φG)，其中V(G)是非空的頂點(diǎn)集，E(G)是不與V(G)相交的邊集，而φG是關(guān)聯(lián)函數(shù)，它使G的每條邊對應(yīng)于G的無序頂點(diǎn)對.若e是一條邊，而u和v是使得φG(e)=uv的頂點(diǎn)，則稱e連接u和v;頂點(diǎn)u和v稱為e的端點(diǎn).

圖G中與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目，稱為v(在G中)的度，記作dG(v).

圖G中的頂點(diǎn)數(shù)用符號v(G)或|v(G)|表示，邊數(shù)用符號ε(G)表示.

1 二分圖的最大匹配、最大點(diǎn)獨(dú)立集在大學(xué)生數(shù)學(xué)建模競賽中的應(yīng)用

定義1 若V(G)=X∪Y，X∩Y=φ，X、Y均非空，且圖G的每一條邊都有一個頂點(diǎn)在Y中，則稱圖G為二分圖.

定義2 圖G的互不相鄰的頂點(diǎn)子集稱為點(diǎn)獨(dú)立集.

問題1 某鎖具廠生產(chǎn)一批彈子鎖具，每個鎖具的鑰匙有個5槽，每個槽的高度從(1，2，3，4，5，6)6個數(shù)(單位略)中任取一個，由于工藝及其它原因，制造鎖具時對5個槽的高度還有兩個限制:至少有三個不同的數(shù);相鄰兩槽的高度之差不能是5.滿足以上條件的所有互不相同的鎖具稱為一批.另外，若兩個鎖具對應(yīng)的5個槽高中有4個相同，另一個槽高只相差1，則可能互開;其它情形不可能互開.現(xiàn)在的問題是:一批鎖具有多少個?若60個裝一箱，團(tuán)體購買多少箱不會出現(xiàn)互開現(xiàn)象?

分析 6種高度5個槽的鑰匙最多可能有65=777 6，通過排列組合，除去不滿足條件的各種情況，可以算出一批鎖具的總數(shù)為5 880件.

由于兩個鎖具對應(yīng)的5個槽高中有4個相同，另一個只相差1，被視為互開，那么它們各自槽高之和必為一個奇數(shù)、一個偶數(shù).另外，槽高之和為奇數(shù)和偶數(shù)的鎖具可以一一對應(yīng)，因而各占一半:2 940件，槽高之和為奇數(shù)(或偶數(shù))的兩鎖具之間不可能互開，所以若60個裝一箱，2 940個鎖具可以裝49箱，49箱槽高之和為奇數(shù)或偶數(shù)的鎖具，肯定不能互開.現(xiàn)在的問題是49箱是不是最大可能的?

建立模型 將鎖具的互開關(guān)系用圖表示，鎖具集合用V=V1∪V2表示，其中V1和V2分別表示槽高之和為奇數(shù)和偶數(shù)的鎖具集合.若vi∈V1，vj∈V2能夠互開，則兩點(diǎn)連一邊.這樣構(gòu)成一個二分圖G=(V1∪V2，E)，V1和V2都是點(diǎn)獨(dú)立集，因?yàn)樗鼈儍?nèi)部的點(diǎn)互不相鄰.為了說明它們都是最大的獨(dú)立集，引入點(diǎn)覆蓋的概念.圖G的頂點(diǎn)子集K稱為一個點(diǎn)覆蓋，如果圖G的每一條邊，至少有一個頂點(diǎn)包含在K里.點(diǎn)獨(dú)立集與點(diǎn)覆蓋有互補(bǔ)的關(guān)系［3～4］.

設(shè)α(G)，β(G)分別表示圖G的最大點(diǎn)獨(dú)立集所含點(diǎn)數(shù)，最小點(diǎn)覆蓋所含點(diǎn)數(shù)，簡記為點(diǎn)獨(dú)立數(shù)和點(diǎn)覆蓋數(shù).由上面的討論有:

定理1 α(G)+β(G)=|V(G)|.

類似地給出邊獨(dú)立集(匹配)和邊覆蓋的概念與關(guān)系.圖G的邊子集E1稱為邊覆蓋，如果圖G的任何一個頂點(diǎn)至少是E1當(dāng)中一條邊的頂點(diǎn).設(shè)α'(G)、β'(G)分別表示圖G的最大匹配所含邊數(shù)、最小邊覆蓋所含邊數(shù)，簡記為邊獨(dú)立數(shù)和邊覆蓋數(shù).它們之間有如下數(shù)量關(guān)系:

定理2 若圖G沒有孤立頂點(diǎn)，即頂點(diǎn)的最小度δ＞0，則α'(G)+β'(G)=|V(G)|.

對于任何的匹配M和任何的點(diǎn)覆蓋K，因?yàn)镵至少要覆蓋M當(dāng)中的每一條邊，所以|M|≤|K|，當(dāng)然最大匹配與最小點(diǎn)覆蓋之間也有關(guān)系，α'(G)≤β'(G).特別地:

定理3 對于二分圖G，有α'(G)=β(G).

推論1 對于二分圖G，如果頂點(diǎn)的最小度δ＞0，則α(G)=β'(G).

引理1 二分圖G=(V1∪V2，E)存在飽和V1的每個頂點(diǎn)的匹配?對所有S?V1，有|NG(S)|≥S.其中NG(S)表示S在圖G中的鄰點(diǎn)集合.

模型求解 對問題1構(gòu)造的二分圖，由于奇數(shù)類鎖具與偶數(shù)類鎖具的對稱性，引理1滿足，所以存在飽和V1的每個頂點(diǎn)的匹配M，而V1的頂點(diǎn)互不相鄰，因此2 940=|V1|≤|M|≤α'(G)=β(G)=|V|－α(G)，從而點(diǎn)獨(dú)立數(shù)α(G)≤|V|－2 940=2 940.由于奇數(shù)類點(diǎn)獨(dú)立集和偶數(shù)類點(diǎn)獨(dú)立集都有2 940個點(diǎn)，所以α(G)=2 940，說明奇數(shù)類點(diǎn)集和偶數(shù)類點(diǎn)集都是最大的點(diǎn)獨(dú)立集，因此49箱是不能互開的最大可能.

2 哈密爾頓圖、最佳推銷員回路在大學(xué)生數(shù)學(xué)建模競賽中的應(yīng)用

定義3 經(jīng)過圖G的每個頂點(diǎn)正好一次的圈，稱為圖G的哈密爾頓圈，簡稱H圈.

定義4 在加權(quán)圖G=(V，E)中，1)權(quán)最小的哈密爾頓圈稱為最佳H圈;2)經(jīng)過每個頂點(diǎn)至少一次且權(quán)最小的閉通路稱為最佳推銷員回路.

問題2 1998年全國大學(xué)生數(shù)學(xué)建模競賽B題:災(zāi)情巡視路線問題.題目給出了某縣的鄉(xiāng)(鎮(zhèn))、村公路網(wǎng)示意圖，今年夏天該縣遭受水災(zāi).為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)帶領(lǐng)有關(guān)部門負(fù)責(zé)人到全縣各鄉(xiāng)(鎮(zhèn))、村巡視.巡視路線指從縣政府出發(fā)，走遍各鄉(xiāng)(鎮(zhèn))、村，最后回到縣政府的路線.問題是:若分三組巡視，試設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線.

分析 災(zāi)情巡視路線問題是一個尋求最佳推銷員回路的問題.最佳推銷員回路的問題可轉(zhuǎn)化為最佳H圈的問題.

建立模型 求最佳推銷員回路的方法是由給定的圖G=(V，E)構(gòu)造一個以V為頂點(diǎn)集的完備圖G'=(V，E')，E'中每條邊(x，y)的權(quán)等于頂點(diǎn) x與 y在圖 G 中最短路徑的權(quán)，即?(x，y)∈E'，ω(x，y)=mindG(x，y).

在圖論中有以下定理［1～2］:

定理4 加權(quán)圖G的最佳推銷員回路的權(quán)和G'的最佳H圈的權(quán)相同.

定理5 在加權(quán)完備圖中求最佳H圈的問題是NP——完全問題.

定理6 G是v(G)≥3的圖，且?u，v∈V(G)，dG(u)+dG(v)≥v(G)，則G中有哈密爾頓圈.

模型求解 下面給出求加權(quán)圖G=(V，E)的最佳推銷員回路的近似算法:

1)用圖論軟件包求出G中任意兩個頂點(diǎn)間的最短路，構(gòu)造出完備圖G'=(V，E')，?(x，y)∈E'，ω(x，y)=mindG(x，y);

2)輸入圖G'的一個初始H圈;

3)用對角線完全算法產(chǎn)生一個初始H圈;

4)隨機(jī)搜索出G'中若干個H圈;

5)對2)、3)、4)步所得每個H圈，用二邊逐次修正法進(jìn)行優(yōu)化，得到近似最佳H圈;

6)在5)求出的所有H圈中，找出權(quán)最小的一個，此即要找的最佳H圈的近似解.

然后用這個方法求解得出問題的解.

再看一個簡單問題:

問題3 圍圓桌至少有5人相聚，怎樣調(diào)整他們的座位，使得每個人兩側(cè)出現(xiàn)新的鄰座.

求解 若恰好5人，設(shè)原來座次為ABCDEA，可調(diào)整為ADBECA.若超過5人，則以人為頂點(diǎn)，僅當(dāng)兩人原來不相鄰座時，在此相應(yīng)的兩頂點(diǎn)間連一邊，得一圖G，由于每個頂點(diǎn)的度都是|V(G)|－3，于是任意兩頂點(diǎn)度之和為2v(G)－6，又v(G)＞5，故2v(G)－6≥v(G)，由定理6，G是哈密爾頓圖，可按哈密爾頓圈上的次序重新入席，即得到每個人有兩個新的鄰座.

3 最小生成樹在大學(xué)生數(shù)學(xué)建模競賽中的應(yīng)用

問題4 有一石油公司計(jì)劃為它擁有的許多存儲站設(shè)計(jì)一個管道連接系統(tǒng)，它共有9個存儲站，如果兩個存儲站之間可以修管道，就用一條邊連接起來，用一個數(shù)表示修這兩站之間的管道所需的費(fèi)用，這樣這個公司所有的存儲站和可能修管道的情況，如圖1表示.

圖1 石油公司所有的存儲站和可能修管道的情況

設(shè)計(jì)計(jì)劃要求:管道網(wǎng)可以把任意兩個存儲站都連接起來，且修管道的費(fèi)用最低.

分析 從圖論的角度來說，圖1是一個連通圖，每一個邊都被賦予了一個數(shù)，稱之為賦權(quán)圖.問題是確定出另一個連通圖，其頂點(diǎn)集與原圖的頂點(diǎn)集一樣，僅保留原圖中的一部分邊，把這一確定的新圖稱作原圖的生成子圖，并且使子圖的所有邊的權(quán)之和最小.

建立模型 要找的子圖必須是連通的，直觀地說子圖具有的邊應(yīng)盡量地少，即這個子圖不能含有任何回路，因?yàn)槿サ艋芈分械娜魏芜叾疾粫绊懰倪B通性質(zhì)，我們把不包含回路的生成子圖稱為原圖的生成樹.不含回路的連通圖，又稱樹.

樹圖中的頂點(diǎn)有兩類，一類是度為1的頂點(diǎn)，稱為懸掛點(diǎn)，另一類是度大于1的頂點(diǎn)，稱為割點(diǎn).一旦去掉割點(diǎn)及與之相連的邊，圖就不連通了.

容易得出以下結(jié)論:

定理7 一個具有n個頂點(diǎn)的連通圖，1)連通子圖是生成樹的充要條件為它具有n－1條邊;2)子圖是生成樹的充要條件為它有n－1條邊且無回路.

現(xiàn)在的問題變成了求權(quán)重最小的生成樹了，簡稱為最小生成樹.下面給出一個求最小生成樹的算法:

第一步:我們把所有的邊按其權(quán)重從小到大排列起來;

第二步:先選定第一條邊;

第三步:邊序列中選擇下一條邊的原則是此邊與前面的邊全在一起不構(gòu)成回路;

第四步:直到選出n－1條邊.

模型求解 通過上述方法得到了一個生成樹，關(guān)于它一定是最小生成樹的證明這里省略.這個算法是1956年由Kruskal提出的又稱作Kruskal算法.由于在不出現(xiàn)回路的前提下取權(quán)小的邊，故又稱作“貪婪算法”.下面用Kruskal算法討論問題4.

第一步:我們按權(quán)重從小到大把邊排列為:

第二步:確定h為第一條邊;

第三步:h(90)→g(90)→f(90)→e(100)→a(100)→b(100)→d(100)→i(150);

第四步:上面八條邊組成了最小生成樹.

除了以上的應(yīng)用，很多圖論理論和方法在大學(xué)生數(shù)學(xué)建模競賽中都有廣泛應(yīng)用.如歐拉圖、染色、最短路等.最后列出歷年大學(xué)生數(shù)學(xué)建模競賽中能用圖論理論和方法求解的問題.

1993年B題:足球隊(duì)排名;1994年A題:逢山開路;1994年B題:鎖具裝箱問題;1995年B題:天車與冶煉爐的作業(yè)調(diào)度;1997年B題:截?cái)嗲懈畹淖顑?yōu)化排列;1998年B題:災(zāi)情巡視的最佳路線;1999年B題:鉆井布局;2004年A題:奧運(yùn)會臨時超市網(wǎng)點(diǎn)設(shè)計(jì);2007年B題:乘公交，看奧運(yùn);2011年B題:交巡警服務(wù)平臺的設(shè)置與調(diào)度.

［1］Bondy J A，Murty U S R.Graph Theory with Applications［M］.New York:The Macmillan Press Ltd，1976.

［2］王朝瑞.圖論［M］.北京:北京理工大學(xué)出版社，2000.

［3］邊馥萍，侯文華，梁馮珍.數(shù)學(xué)模型方法與算法［M］.北京:高等教育出版社，2005.

［4］葉其孝.大學(xué)生數(shù)學(xué)建模競賽輔助教材(二)［M］.長沙:湖南教育出版社，1997.

The Usage of Graph Theory in the Mathematical Modelling Contest

WANG Guo－xing

(School of Information Engineering，Lanzhou University of Finance and Economics，Lanzhou Gansu 730020，China)

With the development of the graph theory，its theories and methods are widely used in the Mathematical Modelling Contest.The discussion about the application of graphic problems in the Mathematical Modelling Contest:maximum matching of bipartite graph，maximum independent set;optimal travelling salesman loop，Hamilton graph;Solve Minimum Spanning Tree and so on.

graph theory;bipartite graph;optimal travelling salesman loop;Hamilton graph;Solve Minimum Spanning Tree(SMST);college student;the Mathematical Modelling Contest

O 157.6

A

1673－2103(2012)02－0108－04

2012－04－08

國家自然科學(xué)基金資助項(xiàng)目(61163037，61163054);蘭州商學(xué)院科研資助項(xiàng)目(LZ201121)

王國興(1976－)，男，甘肅天水人，副教授，碩士，研究方向:圖論及其應(yīng)用.