圖論應(yīng)用問(wèn)題探析

[摘要] 圖論從誕生至今已近300年， 但很多問(wèn)題一直沒(méi)有很好地解決。隨著計(jì)算機(jī)科學(xué)的發(fā)展， 圖論又重新成為了人們研究討論的熱點(diǎn)， 這里給出圖論在現(xiàn)實(shí)生活中的一些應(yīng)用。

[關(guān)鍵詞] 歐拉 圖論 二分圖 哈密頓回路 著色

在 18世紀(jì)30年代，一個(gè)非常有趣的問(wèn)題引起了歐洲數(shù)學(xué)家的濃厚興趣， 這個(gè)問(wèn)題要求遍歷普魯士的哥尼斯堡七橋中的每一座橋恰好一次后回到出發(fā)點(diǎn)。歐拉證明了這是不可能完成的，此后， 歐拉發(fā)表了著名的論文《依據(jù)幾何位置的解題方法》，這是圖論領(lǐng)域的第一篇論文，標(biāo)志著圖論的誕生。圖論的真正發(fā)展始于20世紀(jì)五六十年代之間， 是一門既古老又年輕的學(xué)科。

圖論極有趣味性，嚴(yán)格來(lái)講它是組合數(shù)學(xué)的一個(gè)重要分支。雖然圖論只是研究點(diǎn)和線的學(xué)問(wèn)，但其應(yīng)用領(lǐng)域十分廣闊，不僅局限于數(shù)學(xué)和計(jì)算機(jī)學(xué)科，還涵蓋了社會(huì)學(xué)、交通管理、電信領(lǐng)域等等。總的來(lái)說(shuō)， 圖論這門學(xué)科具有以下特點(diǎn)：圖論蘊(yùn)含了豐富的思想、漂亮的圖形和巧妙的證明；涉及的問(wèn)題多且廣泛，問(wèn)題外表簡(jiǎn)單樸素，本質(zhì)上卻十分復(fù)雜深刻；解決問(wèn)題的方法千變?nèi)f化，非常靈活，常常是一種問(wèn)題一種解法。由以上三個(gè)特點(diǎn)可以看出，圖論與其他的數(shù)學(xué)分支不同，它不像群論、拓?fù)涞葘W(xué)科那樣有一套完整的理論體系和解決問(wèn)題的系統(tǒng)方法。而且圖論所研究的內(nèi)容非常廣泛，例如圖的連通性、遍歷性、圖的計(jì)數(shù)、圖的著色、圖的極值問(wèn)題、圖的可平面性等等。

一、二分圖

有一類非常重要的圖，如樹(shù)，它是圖的特例，這類圖被稱作二分圖，經(jīng)常應(yīng)用在涉及匹配的問(wèn)題中。例如， 某公司現(xiàn)在正經(jīng)歷一次罷工，為了使公司在罷工中照常運(yùn)作，人事部確定了4項(xiàng)關(guān)鍵工作：銷售、維修、安全控制和會(huì)計(jì)，其中銷售需要2人。表中給出了每個(gè)人和他們能勝任的工作，判斷是否所有工作都能有人來(lái)負(fù)責(zé)， 設(shè)每人只能負(fù)責(zé)一項(xiàng)工作。

這看起來(lái)是社會(huì)學(xué)領(lǐng)域的問(wèn)題，我們可以嘗試多種方法，而其中的一種方法就是將其化為圖，建立一個(gè)圖的模型。最基本的問(wèn)題是如何描述它，什么是結(jié)點(diǎn)，什么是邊？在本問(wèn)題中，沒(méi)有太多的選擇，只有人和工作。我們可試著用集合X中的結(jié)點(diǎn)來(lái)代表人，用集合Y中的結(jié)點(diǎn)來(lái)代表工作。用邊來(lái)代表圖中結(jié)點(diǎn)之間的關(guān)系，在這里結(jié)點(diǎn)之間的關(guān)系是“人能否勝任工作”，因此，若某人能勝任工作，那么就在兩個(gè)結(jié)點(diǎn)之間加上一條邊。由于銷售需要2人，所以用2個(gè)結(jié)點(diǎn)S1和S2來(lái)表示。如此得到二分圖1，2給出了最大匹配，很容易看出每一項(xiàng)工作都有人來(lái)負(fù)責(zé)。

二、哈密頓回路

圖論中許多理論和實(shí)際問(wèn)題都需要我們以某種方法遍歷整個(gè)圖。例如在某些問(wèn)題中，我們的目標(biāo)是求出一條跡或回路，滿足經(jīng)過(guò)每條邊一次且僅一次;在另一些問(wèn)題中， 我們可能需要求出一條路或圈， 滿足經(jīng)過(guò)每個(gè)結(jié)點(diǎn)一次且僅一次。其中最著名的兩個(gè)問(wèn)題莫過(guò)于“旅行商”問(wèn)題和“中國(guó)郵路”問(wèn)題。

例如： 舉行一個(gè)國(guó)際會(huì)議， 有A，B，C，D，E，F(xiàn)，G 7個(gè)人。已知下列事實(shí)：A會(huì)講英語(yǔ)；B會(huì)講英語(yǔ)和漢語(yǔ)；C會(huì)講英語(yǔ)、意大利語(yǔ)和俄語(yǔ)；D會(huì)講日語(yǔ)和漢語(yǔ)；E會(huì)講德語(yǔ)和意大利語(yǔ)；F會(huì)講法語(yǔ)、日語(yǔ)和俄語(yǔ)；G會(huì)講法語(yǔ)和德語(yǔ)。試問(wèn)這7個(gè)人應(yīng)如何排座位， 才能使每個(gè)人都能和他身邊的人交談？我們還是用圖來(lái)解決這個(gè)問(wèn)題。依然是建立一個(gè)圖的模型， 確定結(jié)點(diǎn)和邊。這里有“人和語(yǔ)言”， 那么我們用結(jié)點(diǎn)來(lái)代表人， 于是結(jié)點(diǎn)集合V＝{A，B，C，D，E，F(xiàn)，G}對(duì)于任意的兩點(diǎn)，若有共同語(yǔ)言，就在它們之間連一條無(wú)向邊，可得邊集E，圖G＝（V，E）。

如何排座位使每個(gè)人都能和他身邊的人交談？問(wèn)題轉(zhuǎn)化為在圖G中找到一條哈密頓回路的問(wèn)題（哈密頓回路即是通過(guò)每個(gè)結(jié)點(diǎn)一次且僅一次的回路）。而A-B-D-F-G-E-C-A即是圖中的一條哈密頓回路。照這個(gè)順序排座位就可以解決問(wèn)題了。

三、著色問(wèn)題

許多由圖論描述的現(xiàn)實(shí)問(wèn)題都需要把結(jié)點(diǎn)集或邊集劃分為一些不相交的子集，使同一子集中的所有元素互不相鄰。這類問(wèn)題中比較常見(jiàn)的有：安排會(huì)議或考試的日程以免沖突，還有安排化學(xué)品的存儲(chǔ)以避免互相反應(yīng)。例如一名設(shè)計(jì)師為實(shí)驗(yàn)室設(shè)計(jì)化學(xué)藥品存儲(chǔ)倉(cāng)庫(kù)，希望建造盡量少的存儲(chǔ)間。已知某些藥品之間會(huì)起反應(yīng)，不能存儲(chǔ)在一起。作為簡(jiǎn)化，我們用字母a到n代表14種化學(xué)品；兩種化學(xué)品之間的邊代表它們可能起化學(xué)反應(yīng)。求所需最少存儲(chǔ)間，并指出每種藥品放入哪個(gè)存儲(chǔ)間。

雖然這樣給人感覺(jué)很復(fù)雜，似乎色數(shù)會(huì)有爆炸性增長(zhǎng)， 但實(shí)際上很容易就可以驗(yàn)證其色數(shù)等于3，而且是可唯一三著色的。在將其中的一個(gè)K3用3種不同顏色著色之后，我們可以繼續(xù)移動(dòng)到與該K3相鄰的結(jié)點(diǎn)為，如果這個(gè)結(jié)點(diǎn)的顏色已經(jīng)唯一確定，我們就能繼續(xù)處理直到完成整個(gè)過(guò)程。其惟一三著色圖使用了粉紅（p）、褐色（t）和白色(w）。所以可以得知， 總共需要三間存儲(chǔ)間，化學(xué)品將按如下方案存儲(chǔ):在粉紅存儲(chǔ)間中，我們存儲(chǔ) f、h、j、k和l；在褐色存儲(chǔ)間中， 我們放置b、d、e、m和n； 在白色存儲(chǔ)間中安排 a、c、g和i 。

如果能在平面內(nèi)將圖畫出且使其邊各不相交叉，那么這個(gè)圖就是可平面化的?？善矫鎴D曾經(jīng)受到了多年的廣泛關(guān)注，其原因在于一個(gè)長(zhǎng)期困惑人們的問(wèn)題“四色猜想”。這個(gè)問(wèn)題描述起來(lái)很簡(jiǎn)單，就是能否只用四種顏色來(lái)著色平面圖，相鄰的部分顏色要不相同，但最終花費(fèi)了100多年的時(shí)間才得到證明， 證明最終公布于1977年，當(dāng)時(shí)引起了強(qiáng)烈反響，國(guó)為這是第一個(gè)廣泛利用計(jì)算機(jī)做出的證明?，F(xiàn)如今，可平面圖在其應(yīng)用領(lǐng)域仍然占有很重要的地位，例如場(chǎng)地布局或是電路板設(shè)計(jì)等。

四、結(jié)論

從上面的例子我們可以看出，圖論的應(yīng)用十分廣泛，如果我們?cè)趯W(xué)習(xí)的過(guò)程中能打下堅(jiān)實(shí)的基礎(chǔ)，就有能力將圖論的思想應(yīng)用到紛亂復(fù)雜的現(xiàn)實(shí)問(wèn)題中去。