圖論應用問題探析

[摘要] 圖論從誕生至今已近300年， 但很多問題一直沒有很好地解決。隨著計算機科學的發展， 圖論又重新成為了人們研究討論的熱點， 這里給出圖論在現實生活中的一些應用。

[關鍵詞] 歐拉 圖論 二分圖 哈密頓回路 著色

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

圖論極有趣味性，嚴格來講它是組合數學的一個重要分支。雖然圖論只是研究點和線的學問，但其應用領域十分廣闊，不僅局限于數學和計算機學科，還涵蓋了社會學、交通管理、電信領域等等?？偟膩碚f， 圖論這門學科具有以下特點：圖論蘊含了豐富的思想、漂亮的圖形和巧妙的證明；涉及的問題多且廣泛，問題外表簡單樸素，本質上卻十分復雜深刻；解決問題的方法千變萬化，非常靈活，常常是一種問題一種解法。由以上三個特點可以看出，圖論與其他的數學分支不同，它不像群論、拓撲等學科那樣有一套完整的理論體系和解決問題的系統方法。而且圖論所研究的內容非常廣泛，例如圖的連通性、遍歷性、圖的計數、圖的著色、圖的極值問題、圖的可平面性等等。

一、二分圖

有一類非常重要的圖，如樹，它是圖的特例，這類圖被稱作二分圖，經常應用在涉及匹配的問題中。例如， 某公司現在正經歷一次罷工，為了使公司在罷工中照常運作，人事部確定了4項關鍵工作：銷售、維修、安全控制和會計，其中銷售需要2人。表中給出了每個人和他們能勝任的工作，判斷是否所有工作都能有人來負責， 設每人只能負責一項工作。

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

二、哈密頓回路

圖論中許多理論和實際問題都需要我們以某種方法遍歷整個圖。例如在某些問題中，我們的目標是求出一條跡或回路，滿足經過每條邊一次且僅一次;在另一些問題中， 我們可能需要求出一條路或圈， 滿足經過每個結點一次且僅一次。其中最著名的兩個問題莫過于“旅行商”問題和“中國郵路”問題。

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

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

三、著色問題

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

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

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

四、結論

從上面的例子我們可以看出，圖論的應用十分廣泛，如果我們在學習的過程中能打下堅實的基礎，就有能力將圖論的思想應用到紛亂復雜的現實問題中去。