圖論的算法與應(yīng)用簡(jiǎn)述

張孟 張惠

摘 要：圖論一開始由著名數(shù)學(xué)家歐拉提出，屬于數(shù)學(xué)的一個(gè)分支。它是一個(gè)重要的現(xiàn)代數(shù)學(xué)工具，隨著圖論在自然科學(xué)、經(jīng)濟(jì)管理、工程技術(shù)以及社會(huì)問題等方面的頻繁應(yīng)用，對(duì)圖論的學(xué)習(xí)和研究已不局限于數(shù)學(xué)界，其他科學(xué)如電子學(xué)、計(jì)算機(jī)科學(xué)等也都越來越重視對(duì)圖論的研究。本文對(duì)圖論的算法和應(yīng)用做了簡(jiǎn)要的概述。

關(guān)鍵詞：圖論；賦權(quán)圖；神經(jīng)網(wǎng)絡(luò)；復(fù)雜網(wǎng)絡(luò)

一、引言

圖論自1736年由歐拉提出以來，至今已有280年的歷史。它是數(shù)學(xué)的一個(gè)分支，屬于離散數(shù)學(xué)，因此具有離散數(shù)學(xué)的很多特征。圖論（Graph Theory），顧名思義，是研究圖形的一種理論。自然界和人類社會(huì)中的大量事物，往往存在著錯(cuò)綜復(fù)雜的聯(lián)系，這些事物和事物之間的關(guān)系往往可以用圖形來表示。圖形中的點(diǎn)代表要研究的事物，點(diǎn)之間的連線代表事物之間的聯(lián)系。

把圖記為G，圖中每個(gè)點(diǎn)為頂點(diǎn)，頂點(diǎn)組成的集合為頂點(diǎn)集，記為V，點(diǎn)之間的連線為邊，邊組成的集合為圖的邊集，記為E。圖G指的就是一個(gè)二元組（V，E），用V（G）表示G的頂點(diǎn)集，E（G）表示G的邊集。一條邊e=（u，v）的意思是說，邊e和u，v兩個(gè)頂點(diǎn)相關(guān)聯(lián)，我們稱u，v是e的端點(diǎn)，u和v是相鄰的。邊可分為有向邊和無向邊，e有方向?yàn)橛邢蜻?，e沒有方向則為無向邊。對(duì)于有向邊，有（u，v）≠（v，u），對(duì)于無向邊，有（u，v）=（v，u）。有向邊組成的圖為有向圖，無向邊組成的圖稱為無向圖。

對(duì)任意兩個(gè)圖，記為G，H，如果H的頂點(diǎn)集是G的頂點(diǎn)集的子集，且H的邊集是G的邊集的子集，那么我們稱H是G的子圖；如果V（H）=V（G），E（H）是E（G）的子集，則稱H是G的支撐子圖。

如果在圖的每條邊上賦以權(quán)數(shù)，就可得到賦權(quán)圖，記作G=（V，E，W），W為權(quán)集。在處理實(shí)際問題中，賦權(quán)圖非常有用，權(quán)數(shù)的確定依據(jù)實(shí)際情況而定，可以代表不同的含義。如比較常見的情況，權(quán)數(shù)代表兩地之間的距離或行程時(shí)間，也可以表示一道程序需要的加工時(shí)間等。

二、圖論的算法

在計(jì)算機(jī)科學(xué)中，圖論提供了一種簡(jiǎn)單有效的建模方式，很多復(fù)雜的問題可以通過圖論由基本運(yùn)算及規(guī)定的運(yùn)算順序構(gòu)成的完整的解題步驟得到簡(jiǎn)化和解決。一個(gè)算法有五個(gè)重要特征：有窮性、確切性、輸入、輸出和可行性。有窮性是指執(zhí)行步驟有限，確切性是指算法的每一個(gè)步驟都有確切的含義，輸入是指一個(gè)算法有0個(gè)或多個(gè)輸入，輸出是指一個(gè)算法有1個(gè)或多個(gè)輸出，可行性是指這個(gè)算法在原則上是行得通的，可以精確地運(yùn)行，并且人可以通過紙和筆來完成有限次運(yùn)算。

圖論中一些常用的算法有并行圖論算法、閾值分割算法、最短路徑算法、最小生成樹算法、最小支撐樹聚類算法。下面選擇其中幾種算法作簡(jiǎn)要介紹。

并行圖論算法的研究歷史比較早，上世紀(jì)八十年代中期基本成熟，其研究可以分為兩大類。第一類著重研究像無向圖的連通分支、有向圖的可達(dá)性、強(qiáng)連通分支、最小生成樹等一些基本圖問題，相對(duì)比較簡(jiǎn)單。另一類是對(duì)比較復(fù)雜的圖問題的研究，如最大基數(shù)加權(quán)匹配問題、圖著色、最大流最小割等問題，這一類問題的研究相對(duì)于第一類問題的研究比較滯后。

閾值分割算法是一種圖像分割技術(shù)，利用圖像中要提取的目標(biāo)和背景在灰度特性上的差異，把圖像視為具有不同灰度等級(jí)的兩類區(qū)域的組合，根據(jù)選取的合適的閾值確定圖像中的像素點(diǎn)屬于目標(biāo)還是背景。使用該方法的關(guān)鍵點(diǎn)是如何確定最優(yōu)閾值，這個(gè)問題同時(shí)也是使用該方法的難點(diǎn)所在。

最短路徑法1959年被提出，該算法給出了從一個(gè)給定的點(diǎn)s到其他每一個(gè)點(diǎn)的最短路徑。該算法的具體操作過程在運(yùn)籌學(xué)中也有涉及，被稱為Dijkstra算法。其輸入和輸出如下：

輸入：賦權(quán)圖G=（V，E，W）和s∈V，其中|V|=n，e∈E，W（e）≥0

輸出：s到G中每一點(diǎn)的最短路徑及距離。

最小生成樹算法應(yīng)用的一個(gè)典型問題是賦權(quán)無向圖，常見的算法是避圈法，它的基本思想是在有m條邊的無向連通帶權(quán)圖中，把這m條邊按照權(quán)重的大小排序，為e1，e2，e3，…em，然后取e1在T中，依次檢查e2，e3，…em，若這些被檢查的邊與已在T中的邊不能構(gòu)成回路，則把該邊放在T中，否則丟棄。算法結(jié)束后，T就是G的最小生成樹。

對(duì)于最小支撐樹聚類算法的詳細(xì)內(nèi)容，這里就暫不介紹了。

三、圖論的應(yīng)用

圖論是一門非常古老的學(xué)科，它誕生于十八世紀(jì)三四十年代，二十世紀(jì)四五十年代其真正興起并形成了一門獨(dú)立的學(xué)科。到目前為止，圖論已經(jīng)廣泛地運(yùn)用于計(jì)算機(jī)科學(xué)、數(shù)學(xué)、系統(tǒng)工程、控制工程、通訊網(wǎng)絡(luò)、心理學(xué)、管理學(xué)等領(lǐng)域。利用圖論解決問題時(shí)通常需要進(jìn)行圖論建模，這樣可以簡(jiǎn)化問題，突出研究問題要點(diǎn)，方便對(duì)問題的本質(zhì)進(jìn)行深入研究。圖論建模既可以求解最優(yōu)化問題，也可以用于求解存在性問題或者構(gòu)造性問題等。在求解問題時(shí)，對(duì)研究對(duì)象的全面調(diào)查是為了將原型理想化、簡(jiǎn)單化，降低問題解決的難度，但也不會(huì)過度簡(jiǎn)化。

圖論的一個(gè)重要應(yīng)用是在人工神經(jīng)網(wǎng)絡(luò)方面。神經(jīng)網(wǎng)絡(luò)諸多方面的研究中圖論發(fā)揮了重要的工具作用，例如神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)算法、神經(jīng)網(wǎng)絡(luò)的模型設(shè)計(jì)、神經(jīng)網(wǎng)絡(luò)的穩(wěn)定性理論、人工神經(jīng)網(wǎng)絡(luò)分類研究等。此外，人工神經(jīng)網(wǎng)絡(luò)也可以作為工具應(yīng)用于一些比較困難的圖論問題的研究當(dāng)中。

另一個(gè)與圖論關(guān)系密切的課題是復(fù)雜網(wǎng)絡(luò)理論的研究。復(fù)雜網(wǎng)絡(luò)高度概括了復(fù)雜系統(tǒng)的重要特征，如互聯(lián)網(wǎng)、交通網(wǎng)、電力網(wǎng)等等。圖論在復(fù)雜網(wǎng)絡(luò)中的應(yīng)用具有很強(qiáng)的生命力，尤其是代數(shù)圖論在復(fù)雜網(wǎng)絡(luò)中的應(yīng)用。圖論方法可以應(yīng)用于復(fù)雜網(wǎng)絡(luò)的同步估計(jì)，也可以用于研究復(fù)雜網(wǎng)絡(luò)建模、復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)特征等方面的研究。

參考文獻(xiàn)：

[1]方富貴.圖論的算法和應(yīng)用研究[J].計(jì)算機(jī)與數(shù)字工程，2012，02：115-117+132.

[2]段志生.圖論與復(fù)雜網(wǎng)絡(luò)[J].力學(xué)進(jìn)展，2008，06：702-712.

[3]王麗麗.圖論的歷史發(fā)展研究[D].山東大學(xué)，2012.

[4]許進(jìn)，保錚.神經(jīng)網(wǎng)絡(luò)與圖論[J].中國(guó)科學(xué)E輯：技術(shù)科學(xué)，2001，06：533-555.

（作者單位：鄭州工業(yè)應(yīng)用技術(shù)學(xué)院基礎(chǔ)教學(xué)部）