圖論在編譯程序中的應用

1. 運籌學中的圖論問題

很多實際的生產問題都能被抽象成一張大的圖。具體一點的例子，比如需要在若干個城市之間鋪設鐵路或者架設電網，那麼城市就是圖裡面的點，鐵路電網就是圖裡面的邊。抽象一點的例子，比如完成一個項目的過程中所有可能出現的狀態都可以視為一個點，而狀態到狀態之間的轉換就是邊。上一篇文章中我們說過運籌學是處理實際生產生活中遇到的問題的。一旦實際問題被抽象成了一個圖的模型（注意與機器學習裡面的圖模型區分開來），很多圖論裡面的演算法就可以用來解決實際問題，所以圖論是運籌學當中的一個很大的分支。今天我們就介紹一下幾個圖論的基本演算法及其在生產生活中的應用。

一最小生成樹

比如現在要在若干個村子之間架設電網，保證每個城市都通上電（先不考慮電網輸電能力大小）。雖然理論上講，任何兩個村子之間都可以架設電線，不過那樣的話成本很到，不劃算，我們需要在所有可能的連線裡面找到一組總長最短的邊，保證這些邊把每個村子都連上了。在圖論中，這是一個典型的最小生成樹問題。有兩種解決最小生成樹的方法，第一種辦法是把所有的邊按照從小到大的順序添加到圖裡面，如果產生迴路就舍棄它，直到覆蓋了所有的點。另一種方法是把圖上的邊按照從大到小的順序刪除，直到再刪下去就一定會產生離散的點為止。

二最短路徑

圖論中應用最廣的問題可能就是最短路徑問題了。地圖上很多城市之間都有道路相連，想從一個城市到另一個城市，往往有多種選擇，可是走那條路距離最短呢？如果地圖規模不大，我們可以一眼就看出來。可是隨著地圖規模變大，就很難再一眼看出來了，需要有嚴格的演算法保證找到最短路徑。目前已經有了很多種最短路徑演算法，他們的基本思想也不盡相同。以著名的Dijkstra演算法為例，它每次會選擇距離「所有已經選擇過了的點」中距離最近的下一個點，一步步的迭代下去。這個流程保證了演算法會按照距離出發點由近到遠的順序選擇每一個點。

三最大流-最小割問題

油氣輸送網路又許多不同的邊組成，每一條邊的運輸能力有限。輸送油氣資源的時候，為了最大化運輸量，需要合理安排通過每一條邊的油氣流量。這就是在一個網路尋找最大流的問題（等價於尋找最小割）。解決問題的想法很簡單，找到一組邊，它們把整個網路分成了兩部分，流的源和目的地址分屬於這兩個部分。我們稱這樣一組邊為圖的一個分割。由於所有的油氣流都要通過分割中的邊，所以最大流其實受制於分割的流通能力的。於是最大流應該等於流通能力最小的分割。剩下的問題，就是一步步調整，找到最小分割了。

2. 圖論的應用領域有哪些

圖論的應用領域有很多。凡是涉及排列組合優化問題的都免不了要用到圖論中的各種知識。比如通信編解碼，矩陣運算，任務分配，GPS路徑規劃等等。

至於圖論的經典著作，可以自己去google一下graph theory。

3. 圖論的實際應用例子

圖論的實際應用例子如下：

什麼是圖形？

大多數人對"圖形"這個術語有著非常廣泛的理解，代表了大多數數學圖形描述。然而，正如人們所期望的那樣，在數學中有一個非常清晰的定義，即圖形是什麼，我們圍繞它們建立有用的規則和計算，使它們對試圖解決的問題有用。

多圖是兩個頂點之間具有有多條邊的圖，通常描繪不同的關系。可以想像一下飛機航線路線圖，每條航線都是航班號。倫敦和紐約之間會有大量的邊（路線）。

偽圖（Pseudographs）是允許將頂點連接到自身的圖形。毋庸置疑，在描繪人際關系的圖表中通常不需要這樣做。但是，例如你需要使用圖表來描繪辦公室中的咖啡訂單以及誰正在購買適合他們的商品時，那麼採用偽圖將非常有用。

在完整的圖形中，沒有更多的邊可以添加到邊集上。所有頂點都相互連接。它可以是一個有用的數學工具來證明圖形是完整的。

樹圖也非常明顯，但它們在數學上被定義為連接且沒有循環的圖形。這意味著任何一對不同的頂點都可以通過一組邊相互連接，但不可能通過一組邊將頂點連接到自身。家譜通常就是這樣的一個例子。例如皇室成員，那麼可以看看西班牙國王查爾斯二世的家譜。

4. 圖論，演算法

我想很多學習圖論的人都知道J.A. Bondy和U.S.R. Murty著的《Graph Theory with Application》(Elsevier,1976)是圖論教材中的經典，時至今日，仍不失為初學者較好的入門書。還記得蘭州交通大學的張忠輔教授說過，國內第一屆圖論學會就是把大家集中起來學習邦迪的《Graph Theory with Application》，由此可見這本書對國內圖論屆的影響是如此之大。吳望名等人將其譯成中文版本《圖論及其應用》（北京：科學出版社，1984），1988年張克民等人編寫了該書的參考答案《圖論及其應用習題解答》（清華大學出版社，1988）。
在2008年J.A. Bondy和U.S.R. Murty出了新書《Graph Theory》(GTM 244, Springer, 2008), 大家可不妨將其看成是《Graph Theory with Application》的第二版，這本書在內容上做了重新調整，畢竟在第一版出版後的近30年裡涌現出了很多新的結果，所以《Graph Theory》在內容上加進了一些新的結果，這本書我只是讀了其中的幾章，覺得寫的非常棒，建議大家能夠讀讀，這里也值得一提的是將第一版最後提出的50個問題進行了更新，並補充了一些新的問題。總之，我個人認為，《Graph Theory》的確是一部很優秀的圖論教材。

下面給出這兩部教材及其答案的鏈接（在此對資源的提供者表示感謝，如果下列鏈接失效，請自行或者google）：
1. 《Graph Theory with Application》英文版下載：
http://old.math.org.cn/forums/index.php?showtopic=57282
http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html
2. 《Graph Theory with Application》中文版下載：http://old.math.org.cn/forums/index.php?showtopic=54871
3. 《Graph Theory with Application》答案下載：
http://old.math.org.cn/forums/index.php?showtopic=54878
4. 《Graph Theory》下載：
http://ifile.it/5kdc19/1846289696.pdf.zip

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/zhaoyang17/archive/2009/08/27/4491066.aspx

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/zhaoyang17/archive/2009/08/27/4491066.aspx

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/zhaoyang17/archive/2009/08/27/4491066.aspx