張孟 張惠
摘 要:圖論一開始由著名數學家歐拉提出,屬于數學的一個分支。它是一個重要的現代數學工具,隨著圖論在自然科學、經濟管理、工程技術以及社會問題等方面的頻繁應用,對圖論的學習和研究已不局限于數學界,其他科學如電子學、計算機科學等也都越來越重視對圖論的研究。本文對圖論的算法和應用做了簡要的概述。
關鍵詞:圖論;賦權圖;神經網絡;復雜網絡
一、引言
圖論自1736年由歐拉提出以來,至今已有280年的歷史。它是數學的一個分支,屬于離散數學,因此具有離散數學的很多特征。圖論(Graph Theory),顧名思義,是研究圖形的一種理論。自然界和人類社會中的大量事物,往往存在著錯綜復雜的聯(lián)系,這些事物和事物之間的關系往往可以用圖形來表示。圖形中的點代表要研究的事物,點之間的連線代表事物之間的聯(lián)系。
把圖記為G,圖中每個點為頂點,頂點組成的集合為頂點集,記為V,點之間的連線為邊,邊組成的集合為圖的邊集,記為E。圖G指的就是一個二元組(V,E),用V(G)表示G的頂點集,E(G)表示G的邊集。一條邊e=(u,v)的意思是說,邊e和u,v兩個頂點相關聯(lián),我們稱u,v是e的端點,u和v是相鄰的。邊可分為有向邊和無向邊,e有方向為有向邊,e沒有方向則為無向邊。對于有向邊,有(u,v)≠(v,u),對于無向邊,有(u,v)=(v,u)。有向邊組成的圖為有向圖,無向邊組成的圖稱為無向圖。
對任意兩個圖,記為G,H,如果H的頂點集是G的頂點集的子集,且H的邊集是G的邊集的子集,那么我們稱H是G的子圖;如果V(H)=V(G),E(H)是E(G)的子集,則稱H是G的支撐子圖。
如果在圖的每條邊上賦以權數,就可得到賦權圖,記作G=(V,E,W),W為權集。在處理實際問題中,賦權圖非常有用,權數的確定依據實際情況而定,可以代表不同的含義。如比較常見的情況,權數代表兩地之間的距離或行程時間,也可以表示一道程序需要的加工時間等。
二、圖論的算法
在計算機科學中,圖論提供了一種簡單有效的建模方式,很多復雜的問題可以通過圖論由基本運算及規(guī)定的運算順序構成的完整的解題步驟得到簡化和解決。一個算法有五個重要特征:有窮性、確切性、輸入、輸出和可行性。有窮性是指執(zhí)行步驟有限,確切性是指算法的每一個步驟都有確切的含義,輸入是指一個算法有0個或多個輸入,輸出是指一個算法有1個或多個輸出,可行性是指這個算法在原則上是行得通的,可以精確地運行,并且人可以通過紙和筆來完成有限次運算。
圖論中一些常用的算法有并行圖論算法、閾值分割算法、最短路徑算法、最小生成樹算法、最小支撐樹聚類算法。下面選擇其中幾種算法作簡要介紹。
并行圖論算法的研究歷史比較早,上世紀八十年代中期基本成熟,其研究可以分為兩大類。第一類著重研究像無向圖的連通分支、有向圖的可達性、強連通分支、最小生成樹等一些基本圖問題,相對比較簡單。另一類是對比較復雜的圖問題的研究,如最大基數加權匹配問題、圖著色、最大流最小割等問題,這一類問題的研究相對于第一類問題的研究比較滯后。
閾值分割算法是一種圖像分割技術,利用圖像中要提取的目標和背景在灰度特性上的差異,把圖像視為具有不同灰度等級的兩類區(qū)域的組合,根據選取的合適的閾值確定圖像中的像素點屬于目標還是背景。使用該方法的關鍵點是如何確定最優(yōu)閾值,這個問題同時也是使用該方法的難點所在。
最短路徑法1959年被提出,該算法給出了從一個給定的點s到其他每一個點的最短路徑。該算法的具體操作過程在運籌學中也有涉及,被稱為Dijkstra算法。其輸入和輸出如下:
輸入:賦權圖G=(V,E,W)和s∈V,其中|V|=n,e∈E,W(e)≥0
輸出:s到G中每一點的最短路徑及距離。
最小生成樹算法應用的一個典型問題是賦權無向圖,常見的算法是避圈法,它的基本思想是在有m條邊的無向連通帶權圖中,把這m條邊按照權重的大小排序,為e1,e2,e3,…em,然后取e1在T中,依次檢查e2,e3,…em,若這些被檢查的邊與已在T中的邊不能構成回路,則把該邊放在T中,否則丟棄。算法結束后,T就是G的最小生成樹。
對于最小支撐樹聚類算法的詳細內容,這里就暫不介紹了。
三、圖論的應用
圖論是一門非常古老的學科,它誕生于十八世紀三四十年代,二十世紀四五十年代其真正興起并形成了一門獨立的學科。到目前為止,圖論已經廣泛地運用于計算機科學、數學、系統(tǒng)工程、控制工程、通訊網絡、心理學、管理學等領域。利用圖論解決問題時通常需要進行圖論建模,這樣可以簡化問題,突出研究問題要點,方便對問題的本質進行深入研究。圖論建模既可以求解最優(yōu)化問題,也可以用于求解存在性問題或者構造性問題等。在求解問題時,對研究對象的全面調查是為了將原型理想化、簡單化,降低問題解決的難度,但也不會過度簡化。
圖論的一個重要應用是在人工神經網絡方面。神經網絡諸多方面的研究中圖論發(fā)揮了重要的工具作用,例如神經網絡的結構算法、神經網絡的模型設計、神經網絡的穩(wěn)定性理論、人工神經網絡分類研究等。此外,人工神經網絡也可以作為工具應用于一些比較困難的圖論問題的研究當中。
另一個與圖論關系密切的課題是復雜網絡理論的研究。復雜網絡高度概括了復雜系統(tǒng)的重要特征,如互聯(lián)網、交通網、電力網等等。圖論在復雜網絡中的應用具有很強的生命力,尤其是代數圖論在復雜網絡中的應用。圖論方法可以應用于復雜網絡的同步估計,也可以用于研究復雜網絡建模、復雜網絡結構特征等方面的研究。
參考文獻:
[1]方富貴.圖論的算法和應用研究[J].計算機與數字工程,2012,02:115-117+132.
[2]段志生.圖論與復雜網絡[J].力學進展,2008,06:702-712.
[3]王麗麗.圖論的歷史發(fā)展研究[D].山東大學,2012.
[4]許進,保錚.神經網絡與圖論[J].中國科學E輯:技術科學,2001,06:533-555.
(作者單位:鄭州工業(yè)應用技術學院基礎教學部)