計(jì)算機(jī)網(wǎng)絡(luò)圖顯示及控制算法分析

劉　佳

(1.安徽礦業(yè)職業(yè)技術(shù)學(xué)院自動(dòng)化與信息工程系，安徽 淮北 235000；

2. 安徽淮北煤電技師學(xué)院自動(dòng)化與信息工程系，安徽 淮北 235000)

?

計(jì)算機(jī)網(wǎng)絡(luò)圖顯示及控制算法分析

劉佳1,2

(1.安徽礦業(yè)職業(yè)技術(shù)學(xué)院自動(dòng)化與信息工程系，安徽 淮北 235000；

2. 安徽淮北煤電技師學(xué)院自動(dòng)化與信息工程系，安徽 淮北 235000)

摘要：目前，網(wǎng)絡(luò)圖的應(yīng)用極為廣泛.實(shí)現(xiàn)計(jì)算機(jī)技術(shù)和圖論的有效融合，具有定性和定量的雙重優(yōu)勢(shì).利用各種控制算法進(jìn)行網(wǎng)絡(luò)圖計(jì)算機(jī)算法顯示，是當(dāng)前實(shí)現(xiàn)計(jì)算機(jī)算法現(xiàn)代化顯示的重要手段.分析了網(wǎng)絡(luò)圖計(jì)算機(jī)算法以及其顯示方法，結(jié)合實(shí)際應(yīng)用情況，針對(duì)計(jì)算機(jī)網(wǎng)絡(luò)圖顯示中存在的問(wèn)題，提出了相應(yīng)的改進(jìn)措施.

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

隨著我國(guó)經(jīng)濟(jì)的發(fā)展以及科學(xué)技術(shù)的進(jìn)步，計(jì)算機(jī)的應(yīng)用水平也獲得了極大的提高，實(shí)現(xiàn)了圖論與計(jì)算機(jī)之間的有效結(jié)合.就離散事物而言，網(wǎng)絡(luò)圖理論在處理其結(jié)構(gòu)與關(guān)系方面，能夠在定性與定量?jī)蓚€(gè)層面上，實(shí)現(xiàn)對(duì)相關(guān)問(wèn)題更好的優(yōu)化，網(wǎng)絡(luò)圖理論也因此獲得了快速的發(fā)展.其中發(fā)展最快的圖論分支當(dāng)屬網(wǎng)絡(luò)的符號(hào)理論，包括圖的標(biāo)號(hào)以及控制等.由于信息化程度的日益加深以及數(shù)字化領(lǐng)域的飛速發(fā)展，計(jì)算機(jī)技術(shù)的應(yīng)用水平以及圖論的研究水平都得到了極大的提高，網(wǎng)絡(luò)圖理論中研究最多，同時(shí)也是最重要的內(nèi)容有兩個(gè)方面，一個(gè)是網(wǎng)絡(luò)圖的顯示問(wèn)題，另一個(gè)是控制算法問(wèn)題.

1圖論發(fā)展簡(jiǎn)史

通過(guò)對(duì)日常生活進(jìn)行觀(guān)察，我們能夠清晰地認(rèn)識(shí)到問(wèn)題的本質(zhì)所在.若要使這些問(wèn)題得以有效解決，我們可以采用建立數(shù)學(xué)模型的方法，數(shù)學(xué)模型是由點(diǎn)和線(xiàn)構(gòu)成的.早在19世紀(jì)50年代，關(guān)于建立數(shù)學(xué)模型的研究就已經(jīng)在歐洲開(kāi)始了，這一靈感來(lái)源于國(guó)際象棋，國(guó)際象棋中在放置“皇后”的時(shí)候，要兼顧兩個(gè)原則，其一是使用最少；其二是取得最少.這便是網(wǎng)絡(luò)圖的最初模型.從本質(zhì)上來(lái)看，圖論這門(mén)學(xué)科是屬于“圖形”的范疇，點(diǎn)與線(xiàn)是其組成要素，由此進(jìn)行追溯可至18世紀(jì)的東普魯士[1]，在其都城哥尼斯堡中，存在一個(gè)七橋問(wèn)題，沒(méi)有人可以解決.所謂七橋問(wèn)題就是在滿(mǎn)足兩個(gè)條件的情況下走完七座橋，其一是要一次性，其二是不能重復(fù).18世紀(jì)30年代，歐拉以這一問(wèn)題無(wú)解為假設(shè)，使這一問(wèn)題以數(shù)學(xué)化的形式得以證明，證明過(guò)程極為嚴(yán)謹(jǐn)[2].在當(dāng)今數(shù)學(xué)界中，歐拉的這一證明方式被視為圖論的第一篇論文，數(shù)學(xué)界以此為起點(diǎn)出現(xiàn)了兩個(gè)新分支，其一是圖論，其二是拓?fù)鋵W(xué).

自此之后，圖論經(jīng)過(guò)長(zhǎng)期的發(fā)展，逐漸形成了一個(gè)理論體系，研究者日益增多.歐拉作為圖論學(xué)的開(kāi)創(chuàng)者，在圖論中融合了很多學(xué)科的理論，如：其中的代數(shù)圖論，便是融合了代數(shù)學(xué)的相關(guān)知識(shí)；而其中的拓?fù)鋱D論，便是基于拓?fù)鋵W(xué)理論構(gòu)架；至于隨機(jī)圖論，自然與概率分析學(xué)是分不開(kāi)的.在20世紀(jì)60年代，存在一大部分?jǐn)?shù)學(xué)家對(duì)進(jìn)項(xiàng)算法展開(kāi)了研究，通過(guò)n×n棋盤(pán)來(lái)進(jìn)行研究.自從Berge將計(jì)算機(jī)算法首次引入圖論之后，緊接著Ore又提出了控制算法[3]，自此，網(wǎng)絡(luò)圖論才算真正得以形成，而且其應(yīng)用一直延續(xù)至今.計(jì)算機(jī)技術(shù)飛速發(fā)展的同時(shí)，也推動(dòng)著圖論數(shù)學(xué)理論體系的進(jìn)一步完善.

2圖的存儲(chǔ)以及網(wǎng)絡(luò)圖顯示

2.1圖的存儲(chǔ)結(jié)構(gòu)

對(duì)于計(jì)算機(jī)圖的運(yùn)算過(guò)程以及存儲(chǔ)，重要的是要與存儲(chǔ)圖的結(jié)構(gòu)相結(jié)合，關(guān)于存儲(chǔ)圖的基本結(jié)構(gòu)主要有以下四種，即：關(guān)聯(lián)矩陣結(jié)構(gòu)、鄰接矩陣結(jié)構(gòu)、鄰接表、十字鏈表.前兩種結(jié)構(gòu)屬于數(shù)組結(jié)構(gòu)，后兩種結(jié)構(gòu)屬于鏈表結(jié)構(gòu).鄰接表的表示方法不是唯一的，如：對(duì)于其中的邊表節(jié)點(diǎn)，在表達(dá)其連接次序時(shí)，通常都必須同鄰接表的算法相結(jié)合.在表示網(wǎng)絡(luò)圖的各種形式中，效果相對(duì)較好的當(dāng)屬鄰接多重的形式.

2.2網(wǎng)絡(luò)圖的顯示

若要使得網(wǎng)絡(luò)圖在屏幕上能夠顯示出來(lái)，可以通過(guò)采用計(jì)算機(jī)C語(yǔ)言來(lái)實(shí)現(xiàn)網(wǎng)絡(luò)圖的繪制.之所以選擇使用C語(yǔ)言，出于兩方面的考慮.第一，C語(yǔ)言具有簡(jiǎn)潔的特點(diǎn)，而且其功能比較強(qiáng)大，更方便在屏幕上繪制；第二，C語(yǔ)言程序占用的內(nèi)存較少，更重要的是，其執(zhí)行效率極高，更能滿(mǎn)足對(duì)顯示速度要求高的用戶(hù).

網(wǎng)絡(luò)圖的組成要素是點(diǎn)與線(xiàn)，點(diǎn)包括頂點(diǎn)以及節(jié)點(diǎn)；線(xiàn)包括弧和邊.弧主要存在于有向圖，邊主要存在于無(wú)向圖.而頂點(diǎn)和邊的關(guān)聯(lián)性錯(cuò)綜復(fù)雜.對(duì)于點(diǎn)的度數(shù)來(lái)說(shuō)，或許是1度，或許大于1度，而且必須是整數(shù).而對(duì)于不是連通圖的點(diǎn)而言，0度數(shù)也有可能出現(xiàn).而邊一定存在兩個(gè)端點(diǎn).所以，在計(jì)算機(jī)屏幕上繪制網(wǎng)絡(luò)圖時(shí)，可以采用這樣的方法：先標(biāo)出所有的頂點(diǎn)，然后再畫(huà)邊，即使各頂點(diǎn)之間連接起來(lái).

在計(jì)算機(jī)屏幕上把點(diǎn)繪制出來(lái)，就能夠在圖上確定其坐標(biāo)，即用戶(hù)坐標(biāo)(x,y).需要強(qiáng)調(diào)的是，采用c語(yǔ)言繪制時(shí)，所用的是物理坐標(biāo)，坐標(biāo)原點(diǎn)位于屏幕的左上角；x軸向右邊的水平方向延伸；y軸向下的垂直方向延伸.這種坐標(biāo)可以定義為(X,Y).X值和Y值都有一定的范圍，還要確保是整數(shù).圖形的模式對(duì)于X值和Y值的范圍會(huì)造成一定的影響，最終會(huì)對(duì)屏幕分辨率產(chǎn)生影響.(x,y)坐標(biāo)與(X,Y)坐標(biāo)之間存在以下關(guān)系:

X軸方向:

數(shù)值區(qū)間(x1,x2)，屏幕點(diǎn)區(qū)間(X1,X2)，由此可得：

Y軸方向:

數(shù)值區(qū)間(y1,y2)，屏幕點(diǎn)區(qū)間(Y1,Y2)，由此可得：

通過(guò)計(jì)算，X，Y的最終取值需要估算成整數(shù).接下來(lái)是邊的繪制.由于任何一條邊必有兩個(gè)端點(diǎn)，以此為依據(jù)確定頂點(diǎn)坐標(biāo)，確定之后直接連接兩個(gè)端點(diǎn)即可.為了確保所繪圖像的清晰度，以便用戶(hù)觀(guān)看，在繪制邊的時(shí)候，可以通過(guò)不同顏色來(lái)進(jìn)行繪制，C語(yǔ)言能夠提供的顏色種類(lèi)有很多，一共有十六種，完全可以滿(mǎn)足用戶(hù)的需要.

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

現(xiàn)代化網(wǎng)絡(luò)圖的應(yīng)用，結(jié)合計(jì)算機(jī)的控制算法，一共有兩種，分別是：點(diǎn)符號(hào)全控制算法、邊符號(hào)控制算法.至于網(wǎng)絡(luò)圖顯示，需要做到的是：針對(duì)其中的一種顯示方法，進(jìn)行深入的研究并有效的應(yīng)用.

3.1點(diǎn)符號(hào)全控制算法

3.2邊符號(hào)控制算法

2001年，徐保根第一次對(duì)符號(hào)邊控制算法進(jìn)行了定義，經(jīng)過(guò)長(zhǎng)期深入的鉆研，取得了一系列的研究成果.比如：使m邊的最小符號(hào)邊控制算法數(shù)得以確定，進(jìn)一步完善了網(wǎng)絡(luò)圖控制算法的理論體系.在2002-2004年間，徐保根針對(duì)一般網(wǎng)絡(luò)圖的符號(hào)邊控制算法數(shù)進(jìn)行了深入的研究和精密計(jì)算，最終確定了其上界和下界.針對(duì)特殊網(wǎng)絡(luò)圖的符號(hào)邊控制算法數(shù)，徐保根也進(jìn)行了精密的計(jì)算并得出其確切值.2005-2007年間，徐保根通過(guò)改變研究角度以及完善研究方法，對(duì)一般網(wǎng)絡(luò)圖符號(hào)邊控制算法數(shù)進(jìn)行了進(jìn)一步的研究，最終確定了其界限，而且，眾多學(xué)者都參與了這項(xiàng)研究，通過(guò)共同努力最終確立了一般網(wǎng)絡(luò)圖的界限[8].在點(diǎn)控制算法中，減控制算法只是其中的一種變化形式，而對(duì)于邊的減控制算法來(lái)說(shuō)，亦是如此.在符號(hào)邊控制算法中，得到減邊控制算法的方法是：改變其函數(shù)值域，即將{-1,1}改為{-1,0,1}.因?yàn)閷?duì)減控制算法進(jìn)行研究非常的困難，而且研究尚處于初期階段，因此，其可觀(guān)的研究成果并不多.在此基礎(chǔ)上，需要對(duì)減k邊的控制算法進(jìn)行深入的研究.對(duì)減邊控制算法的定義進(jìn)行修改，將“所有邊”的條件進(jìn)行調(diào)整，變?yōu)椤爸辽儆衚條邊”，從而增加了研究的難度，這對(duì)于研究者是一個(gè)巨大的挑戰(zhàn).

3.3網(wǎng)絡(luò)圖顯示方法

就符號(hào)的顯示以及邊符號(hào)的顯示而言，與網(wǎng)絡(luò)圖顯示方法中的一種相結(jié)合，在屏幕上繪制網(wǎng)絡(luò)圖時(shí)，需要做好兩項(xiàng)工作：第一是輸入數(shù)據(jù)；第二是添加點(diǎn).輸入數(shù)據(jù)時(shí)，關(guān)于相關(guān)指令的輸入，使用者需要在計(jì)算機(jī)輸入網(wǎng)絡(luò)圖中進(jìn)行，并輸人數(shù)據(jù)和信息.數(shù)據(jù)信息主要包括：頂點(diǎn)數(shù)目N及其坐標(biāo)、邊的數(shù)目M.構(gòu)建鄰接多重表，將相關(guān)數(shù)據(jù)輸入鄰接雙重表中，這樣才算是完成了對(duì)數(shù)據(jù)的輸出.在輸入邊以及頂點(diǎn)時(shí)，需要添加與之相關(guān)的指令，并輸入數(shù)目.關(guān)于頂點(diǎn)的添加，表現(xiàn)出孤立性.由于網(wǎng)絡(luò)連通的不完整，在繪制網(wǎng)絡(luò)圖時(shí)，需要與基礎(chǔ)性環(huán)節(jié)相結(jié)合.所以，網(wǎng)絡(luò)圖計(jì)算機(jī)算法的顯示，需要結(jié)合點(diǎn)符號(hào)全控制算法以及邊符號(hào)控制算法，網(wǎng)絡(luò)圖控制算法在實(shí)際的應(yīng)用中，應(yīng)該不斷完善網(wǎng)絡(luò)圖設(shè)計(jì)，從而提高計(jì)算機(jī)算法的速度，促使顯示系統(tǒng)能夠更加高效地運(yùn)行.

4控制算法理論下網(wǎng)絡(luò)圖計(jì)算機(jī)算法顯示的改進(jìn)

隨著經(jīng)濟(jì)發(fā)展的日新月異，科學(xué)技術(shù)也越來(lái)越先進(jìn)，計(jì)算機(jī)技術(shù)被廣泛地應(yīng)用于日常生活的各個(gè)方面.與網(wǎng)絡(luò)圖理論的有效結(jié)合，更是極大地推動(dòng)了現(xiàn)代化進(jìn)程.在理論逐漸發(fā)展完善的同時(shí)，應(yīng)該注重創(chuàng)新意識(shí)的培養(yǎng)，使得理論體系能夠與時(shí)俱進(jìn)；而且還要充分重視對(duì)相關(guān)人才的培養(yǎng)，并在培養(yǎng)的過(guò)程中，使得網(wǎng)絡(luò)圖的應(yīng)用更加的廣泛.通過(guò)計(jì)算機(jī)網(wǎng)絡(luò)圖中符號(hào)的全控制以及邊符號(hào)的控制相結(jié)合的方式，對(duì)計(jì)算機(jī)顯示進(jìn)行良好的控制，從而做好查詢(xún)和顯示相結(jié)合網(wǎng)絡(luò)圖系統(tǒng)的完善.

針對(duì)計(jì)算機(jī)算法顯示的改進(jìn)，可以利用網(wǎng)絡(luò)圖顯示方法，再以查詢(xún)系統(tǒng)作為必要的輔助.在穩(wěn)定性較差的系統(tǒng)進(jìn)行設(shè)置的過(guò)程中，應(yīng)該充分重視對(duì)網(wǎng)絡(luò)圖的修改，包括對(duì)頂點(diǎn)和邊的修改，在進(jìn)行反復(fù)修改的過(guò)程中，查詢(xún)以及核實(shí)相關(guān)數(shù)據(jù)，不但使所繪圖像免于古板，還使其更加的清晰.在此過(guò)程中，查詢(xún)系統(tǒng)也得到了不斷的完善.針對(duì)不同對(duì)象進(jìn)行分析時(shí)，應(yīng)該注重改進(jìn)系統(tǒng).

隨著社會(huì)現(xiàn)代化程度的加深，若要實(shí)現(xiàn)網(wǎng)絡(luò)圖計(jì)算機(jī)算法的有效應(yīng)用，人力投入和資金投人是必不可少的，在應(yīng)用于實(shí)踐的過(guò)程中，需要結(jié)合中國(guó)社會(huì)發(fā)展現(xiàn)狀，結(jié)合市場(chǎng)需求，找出網(wǎng)絡(luò)圖技術(shù)存在的不足，不斷改進(jìn)，逐步走向完善.在完善網(wǎng)絡(luò)圖計(jì)算機(jī)算法理論體系的過(guò)程中，需要與時(shí)代發(fā)展的主題相契和，使之能夠滿(mǎn)足社會(huì)發(fā)展的需要，從而更好地應(yīng)用于實(shí)踐.

參考文獻(xiàn)：

[1]張凡.網(wǎng)絡(luò)圖的計(jì)算機(jī)算法及顯示方法分析[J].鄭州鐵路職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2015,(2)：2-3.

[2]吳凱,李鵬,何永強(qiáng).控制算法理論及網(wǎng)絡(luò)圖計(jì)算機(jī)算法顯示研究[J].現(xiàn)代電子技術(shù)，2015,(17)：7-8.

[3] 熊芳,黃宏斌,黃玉成.一種基于語(yǔ)義相似度的信息資源語(yǔ)義聚類(lèi)算法[J].計(jì)算機(jī)工程與科學(xué)，2012,(11)：2-3.

[4] 鄒軍.基于計(jì)算機(jī)算法的新型教學(xué)模式[J]. 電子制作，2015,(8)：3-4.

[5]林新華.淺析控制算法理論和網(wǎng)絡(luò)圖計(jì)算機(jī)算法顯示[J].數(shù)字技術(shù)與應(yīng)用,2015,(9):112-113.

[6]王謝瑋.試論控制算法理論和網(wǎng)絡(luò)圖計(jì)算機(jī)算法顯示[J].中國(guó)新通信，2015,(21):10-11.

[7]付欣.網(wǎng)絡(luò)圖的計(jì)算機(jī)算法和顯示方法的研究[J].電腦知識(shí)與技術(shù)，2013,(35)：9-10.

[8]劉乃維.論網(wǎng)絡(luò)圖的計(jì)算機(jī)算法[J].計(jì)算機(jī)光盤(pán)軟件與應(yīng)用，2014,(13)：13-14.

(責(zé)任編校：晴川)

Computer Network Diagram Display and Control Algorithm Analysis

LIU Jia1,2

(1. Department of Automation and Information Engineering, Anhui College of Mining and Technology,Huaibei Anhui 235000, China;2. Department of Automation and Information Engineering,Huaibei Coal and Electricity Technicians College of Anhui, Huaibei Anhui 235000, China)

Abstract：At present, the application of the network map is extremely broad. Achieving effective integration of computer technology and graph theory has dual advantages of both qualitative and quantitative. Using various control algorithms for the computer algorithm display of network diagram is an important means to achieve the modernization of computer algorithms to display. Computer algorithm of network diagram and the display methods are analyzed, and combined with practical application situation, and in allusion to existing problems of computer network diagram display, we put forward corresponding improvement measures.

Key Words：control algorithm; computer algorithm; network diagram

作者簡(jiǎn)介：劉佳(1985— )，女，安徽淮北人，安徽礦業(yè)職業(yè)技術(shù)學(xué)院自動(dòng)化與信息工程系/安徽淮北煤電技師學(xué)院自動(dòng)化與信息工程系講師, 碩士.研究方向：圖形圖像、計(jì)算機(jī)控制技術(shù).

中圖分類(lèi)號(hào):TP393

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1008-4681(2016)02-0054-03

基金項(xiàng)目：安徽省省級(jí)質(zhì)量工程項(xiàng)目“多媒體設(shè)計(jì)與制作特色專(zhuān)業(yè)建設(shè)”(批準(zhǔn)號(hào)：2015tszy093)；安徽省教育廳人文社科重點(diǎn)研究課題“基于互聯(lián)網(wǎng)+的高校綠色校園建設(shè)”(批準(zhǔn)號(hào)：SK2016A0277).

收稿日期：2016-03-07