論網(wǎng)絡(luò)圖的計(jì)算機(jī)算法

摘 要：目前數(shù)學(xué)模型得到越來越廣泛的應(yīng)用，因?yàn)榻柚@一模型可以解決很多的現(xiàn)實(shí)問題。而關(guān)于針散型結(jié)構(gòu)的問題，也有越來越多的機(jī)會用到數(shù)字技術(shù)，這對于網(wǎng)絡(luò)圖理論的發(fā)展起到了極大的促進(jìn)作用。文章對相關(guān)的控制算法理論進(jìn)行了簡單的研究，還對網(wǎng)絡(luò)圖的計(jì)算機(jī)算法和顯示方法進(jìn)行了論述。

關(guān)鍵詞：網(wǎng)絡(luò)圖；計(jì)算機(jī)算法；顯示方法

中圖分類號：TP301.6

新世紀(jì)，人類已經(jīng)全面地提升了計(jì)算機(jī)水平，人類的科學(xué)也取得了長足的進(jìn)步，緊密地結(jié)合起了圖論和計(jì)算機(jī)技術(shù)。特別是有關(guān)于離散事物結(jié)構(gòu)和關(guān)系的一些方面，網(wǎng)絡(luò)圖理論很大程度上有助于優(yōu)化有關(guān)問題，不管是定性或者是定量的層面。網(wǎng)絡(luò)圖理論由此獲得了迅猛的發(fā)展，關(guān)于網(wǎng)絡(luò)的符號理論領(lǐng)域更是如此，諸如圖的標(biāo)號和顯示等方面，這是關(guān)于圖論的發(fā)展最快的分支之一。新的時代是信息化時代和，也是關(guān)于數(shù)字化的時代，圖理論隨之發(fā)展進(jìn)步，計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)也取得了很快的發(fā)展。而網(wǎng)絡(luò)圖的顯示和控制算法是其中發(fā)展最為迅速的，也是人們有著最多研究的。

1 圖論發(fā)展簡史

觀察過現(xiàn)實(shí)生活之后，我們會發(fā)現(xiàn)很多問題的本質(zhì)。實(shí)際上解決這些實(shí)際問題都是可以通過建立數(shù)學(xué)模型來進(jìn)行，也就是一個用點(diǎn)和線組成的圖形。公元1850年就開始涉及到這方面的研究，歐洲人下國際象棋時想到如何放置“皇后”的問題，既要使用最少又得是取得最少的方格，這亦能視之為網(wǎng)絡(luò)圖最早的雛形。更確切地來看，圖論真正成為一種“圖形”學(xué)科，是根據(jù)點(diǎn)、線組成的，這就得追溯到18世紀(jì)了。關(guān)于東普魯士國都哥尼斯堡無人能解的七橋問題，也就是一個假設(shè)，關(guān)于找出一次性走完七座橋并且要求不能重復(fù)。1736年歐拉通過這個假設(shè)無解，實(shí)現(xiàn)了問題的數(shù)學(xué)化，證明也極為嚴(yán)謹(jǐn)。這也被視為數(shù)學(xué)界第一篇關(guān)于圖論的論文，這也是數(shù)學(xué)界出現(xiàn)兩個新分支的標(biāo)志，這里說的也就是圖論和拓?fù)鋵W(xué)。

此后，圖論在很長的一段時間內(nèi)漸漸成了一個理論，也被應(yīng)用到了更多的研究領(lǐng)域。歐拉不僅是創(chuàng)立了經(jīng)典圖論，而且還將其結(jié)合起了很多的學(xué)科，比如代數(shù)圖論就是跟代數(shù)相結(jié)合；拓?fù)鋱D論就是按照拓?fù)鋵W(xué)視角；隨機(jī)圖論就是與概率分析相結(jié)合。在上世紀(jì)六十年代，有不少數(shù)學(xué)家研究進(jìn)項(xiàng)算法，借助的是n×n棋盤。Berge就第一次把計(jì)算機(jī)算法數(shù)這一概念引進(jìn)了圖論中。接下來Ore把控制算法數(shù)這一概念正式引了進(jìn)來，也就意味著真正形成了網(wǎng)絡(luò)圖論，而且至今還會一直應(yīng)用這一理論。為了實(shí)現(xiàn)高計(jì)算的目標(biāo)，數(shù)學(xué)普遍結(jié)合起了計(jì)算機(jī)科學(xué)。而且，不斷提升計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)，還會促使圖論數(shù)學(xué)理論進(jìn)一步發(fā)展。

2 網(wǎng)絡(luò)圖的計(jì)算機(jī)顯示理論

為了能將網(wǎng)絡(luò)圖能顯示在屏幕上，可以借助于C語言以達(dá)到來達(dá)到繪制網(wǎng)絡(luò)圖的目的。主要是從兩個人方面考慮，才選擇用到C語言。一方面是因?yàn)镃語言非常簡潔，并且它具有十分強(qiáng)大的功能，便于在屏幕上進(jìn)行作圖；另一方面是與C語言的編寫程序有關(guān)，因?yàn)槠渫徽加泻苄〉膬?nèi)存，而且在執(zhí)行方面具有很高的效率，這對于對顯示速度有著高要求的用戶是很有幫助的。

網(wǎng)絡(luò)圖是由點(diǎn)與點(diǎn)之間的連線構(gòu)成的，這里所說的點(diǎn)通常被稱作頂點(diǎn)，又或者是節(jié)點(diǎn)；而點(diǎn)之間的連線也就是稱之為弧或者是邊，弧是針對有向圖來說的，邊是針對無向圖稱來說的。這些頂點(diǎn)與邊之間存在著十分復(fù)雜的錯綜關(guān)系。點(diǎn)的度可能是1也可能大于1，并且是整數(shù)，而一些非連通圖的點(diǎn)還可能會出現(xiàn)0度數(shù)；而每一條邊必然是會包括兩個端點(diǎn)的。因此，在屏幕上進(jìn)行網(wǎng)絡(luò)圖的繪制，就可以將各個頂點(diǎn)先畫出來，接下來再畫邊，也就是添加相應(yīng)頂點(diǎn)之間的連線。

把點(diǎn)畫于屏幕之上，便可以已知圖為依據(jù)將圖上幾點(diǎn)的坐標(biāo)確定下來，我們稱之為用戶坐標(biāo)（x，y）。然而在c語言作圖的時候，需要注意的是，屏幕上用到的是物理坐標(biāo)，屏幕左上角為原點(diǎn)的位置，X軸位于水平方向，右邊呈正趨勢；Y軸位于垂直方向，向下則呈正。這種坐標(biāo)系上的點(diǎn)位置規(guī)定為坐標(biāo)（X，Y）。X，Y有一定的取值范圍且必定為整數(shù)。通常是圖形模式會影響X、Y的取值范圍，也就是關(guān)系到屏幕的分辨率。上述兩種坐標(biāo)之間存在關(guān)系式：

X軸方向：數(shù)值區(qū)間（x1，x2），屏幕點(diǎn)區(qū)間為（Xl，X2）那么，

X=X2-X1/x2-x1·x+x2·X1-x1·X2/x2-x1 （x1≤x≤x2，X1≤X≤X2） （1）

Y軸方向：

數(shù)值區(qū)間（y1，y2），屏幕點(diǎn)區(qū)間（Y1，Y2），那么

Y=Y2-Y1/y2-y1·y+Y2·y2 -Y1·y1/y2-y1 （y1≤y≤y2，Y1≤Y≤Y2） （2）

對于X、Y的計(jì)算結(jié)果，也要求是整數(shù)，若不是就估算取整。

第二步，畫邊。以一條邊所對應(yīng)的兩個頂點(diǎn)為依據(jù)，來找出頂點(diǎn)坐標(biāo)。接下來畫一條直線于兩頂點(diǎn)之間就行了。為了讓用戶可以更加清楚看清繪圖，可以選擇不同顏色來繪制新增的支路（或邊），C語言為用戶提供了16種選擇顏色，基本能滿足用戶要求。

3 網(wǎng)絡(luò)圖的計(jì)算機(jī)算法和顯示方法研究

3.1 點(diǎn)符號全控制算法的發(fā)展及研究

“點(diǎn)符號控制算法是一種研究局部占優(yōu)問題的理論?！边@一定義是J.E Dunbar在1995年進(jìn)行的第一次定義。2001年，Zelinka首次提出了符號控制算法，而點(diǎn)符號全控制算法則作為其變化形式的一種。對二者進(jìn)行比較，發(fā)現(xiàn)二者的不同有：符號控制算法對于條件的滿足需要在一定的范圍內(nèi)，即點(diǎn)的閉鄰域；Zelinka則改變了閉鄰域，使之成為開鄰域，由此將各種不同的研究空間引了出來。2003年，有部分人將最大度和最小度引了進(jìn)來，還將一般網(wǎng)絡(luò)圖的符號全控制算法數(shù)的下界計(jì)算出來。2004年，Michael A Henning進(jìn)行了進(jìn)一步的研究，從而將符號全控制算法函數(shù)新的下界得出來，還研究出了具體網(wǎng)絡(luò)圖，以便能滿足這些下界。2006年，王軍秀針對下界問題又進(jìn)行了進(jìn)一步的全面改進(jìn)，并且證明給出的界比之前更優(yōu)。2009年，呂新忠，儀明源繼續(xù)研究符號全控制算法數(shù)，并且研究關(guān)于這方面的幾種比較特殊的網(wǎng)絡(luò)圖，這就進(jìn)一步充實(shí)了符號全控制算法的內(nèi)容。徐保根針對點(diǎn)的其它變化形式，于2006年將反符號控制算法的概念提了出來，也就是改變了符號控制算法定義中的f[v]≥1的方向。徐寶根按照前面敘述的變化進(jìn)行了新的角度研究，第一次把符號全控制算法變成反符號全控制算法。研究反符號全控制算法的意義就在于可以促使作者對研究方法進(jìn)行進(jìn)一步掌握，對研究思路進(jìn)行拓展創(chuàng)新，并且找到研究的樂趣所在。

3.2 邊符號控制算法的發(fā)展及研究

2001年，徐保根最先將符號邊控制算法的概念提了出來，還取得了不少相關(guān)的研究成果。具體的研究成果有，將m邊的最小符號邊控制算法數(shù)確定了下來，這就使得網(wǎng)絡(luò)圖的控制算法理論得到了不錯的豐富和完善。Bohdan Zelinka Liberec在2002年將關(guān)于樹的一些界限研究并給定。2002年到2004年，這段時間，關(guān)于一般網(wǎng)絡(luò)圖的符號邊控制算法數(shù)，徐保根得出了其上、下界，有的特殊網(wǎng)絡(luò)圖的符號邊控制算法數(shù)，還計(jì)算出了其確切值。與此同時，還不斷改進(jìn)研究的角度和方法。2005年到2007年期間，徐保根又將一般網(wǎng)絡(luò)圖的符號邊控制算法數(shù)界限進(jìn)一步得了出來。并且，除此之外，關(guān)于這項(xiàng)研究，也有不少學(xué)者積極參與其中，將特殊網(wǎng)絡(luò)圖的符號邊控制算法數(shù)的確切值計(jì)算出來，還得出了一般網(wǎng)絡(luò)圖的界限。

相比較點(diǎn)控制算法中的減控制算法，邊上的減控制算法亦是如此。同樣作為符號邊控制算法的變化形式之一，得出減邊控制算法依據(jù)的是改變了符號邊控制算法中的函數(shù)值域，也就是把函數(shù)值域{-1，1}變成了{(lán)-1，0，1}?？紤]到減控制算法存在比較大的研究難度，且至今沒有經(jīng)過很長的研究時間，因此，迄今為止尚未出現(xiàn)很多相關(guān)的研究成果。接下來需要對減k邊控制算法進(jìn)行進(jìn)一步研究，也擴(kuò)大了研究難度。是將減邊控制算法定義中有關(guān)條件進(jìn)行改變，就是變“所有邊”為“至少有k條邊”，這對于研究者來說是一次巨大的鍛煉與考驗(yàn)。

4 結(jié)束語

當(dāng)前，人們開始掀起研究網(wǎng)絡(luò)圖理論的新高潮，并隨之開始陸續(xù)涌現(xiàn)出許許多多的新理論成果?？茖W(xué)理論是沒有國界的，我們應(yīng)該試圖努力成為研究控制算法理論的先鋒隊(duì)，關(guān)于網(wǎng)絡(luò)圖研究，我們不僅只是將重點(diǎn)局限于為計(jì)算機(jī)算法理論上的研究。網(wǎng)絡(luò)圖的控制算法理論具有十分廣泛的應(yīng)用，研究方向也不僅僅是局限于網(wǎng)絡(luò)圖論本身，在其它領(lǐng)域的應(yīng)用前景也十分廣泛，涉及的領(lǐng)域主要有計(jì)算機(jī)網(wǎng)路、編碼理論等。

參考文獻(xiàn)：

[1]馬軍，高岡忠雄.網(wǎng)絡(luò)圖的最短路徑和傳遞閉包[J].計(jì)算機(jī)學(xué)報(bào).1990（09）：706-708.

[2]BrunoR.Preiss.數(shù)據(jù)結(jié)構(gòu)與算法：面向?qū)ο蟮腃++設(shè)計(jì)模式[M].北京：電子工業(yè)出版社，2000.

[3]唐策善，梁維發(fā).并行圖論算法[M].合肥：中國科學(xué)技術(shù)大學(xué)出版社，1991.

[4]（美）陳開惠.網(wǎng)論—網(wǎng)絡(luò)流[M].北京：人民郵電出版社，1992.

[5]洪先龍.超大規(guī)模集成電路布圖理論與算法[M].北京：科學(xué)出版社，1998.

[6]孫家廣.計(jì)算機(jī)圖形學(xué)[M].北京：清華大學(xué)出版社，1998.

[7]周淑閣.模擬電路CAD[M].北京：兵器工業(yè)出版社，1997.

[8]陸潤民.C語言繪圖教程[M].北京：清華大學(xué)出版社，1996.

[9]蘭家隆，劉軍.應(yīng)用圖論及算法[M].北京：電子科技大學(xué)出版社，1995.

[10]唐策善，梁維發(fā).并行圖論算法[M].北京：中國科學(xué)技術(shù)大學(xué)出版社，1991.

[11]莊文君，李玉興.集成電路布圖設(shè)計(jì)自動化[M].上海：上海交通大學(xué)出版社，1986.

作者簡介：劉乃維（1992-），女，滿族，內(nèi)蒙古赤峰人，本科，研究方向：計(jì)算機(jī)。

作者單位：北京航空航天大學(xué)，北京 100193