徐瑾

【摘 要】隨著科學技術(shù)的發(fā)展，生活中越來越多的實際問題，需要借助數(shù)學模型進行分析、解決，所以人們在離散型結(jié)構(gòu)問題上對數(shù)字技術(shù)的應(yīng)用越來越高，有力的促進了網(wǎng)絡(luò)圖理論的發(fā)展，解決人們生產(chǎn)、生活中很多困難，提高工作效率，促進科技的進一步發(fā)展。本文主要從網(wǎng)絡(luò)圖的計算機算法和顯示方法等方面進行研究、分析。

【關(guān)鍵詞】網(wǎng)絡(luò)圖;計算機算法;顯示方法

21世紀是網(wǎng)絡(luò)信息技術(shù)加速發(fā)展的時期，計算機技術(shù)已經(jīng)成熟，人類科技得到了長足的發(fā)展，為圖論和計算機技術(shù)的緊密結(jié)合提供了有利的條件，特別是在圖形結(jié)構(gòu)以及圖形關(guān)系方面，網(wǎng)絡(luò)圖論在定量和定性方面都能夠較好的優(yōu)化網(wǎng)絡(luò)圖。近幾年，在信息技術(shù)和數(shù)字技術(shù)的帶動下，圖理論發(fā)展迅速，其中網(wǎng)絡(luò)圖的顯示和控制算法發(fā)展最為迅速，也是近幾年人們研究的熱點。

一、圖論發(fā)展概括

現(xiàn)實生活中國很多實際問題都能夠應(yīng)用建立數(shù)學模型的方式進行解決，人類早在公元1850年就開始涉及這方面的研究，比如歐洲在國際象棋中就有對“皇后”這一問題的研究，在這個問題上既要使用最少，又要取得最少的方格，這就是網(wǎng)絡(luò)圖最早的雛形。到18世紀人們利用點、線問題研究圖論，根據(jù)點和線的組合形成一種圖形科學。1736年歐拉通過“在不重復(fù)的情況下，找出一次性走完七座橋的方法”，假設(shè)這一問題無解，并對其結(jié)論進行嚴密的證明，實現(xiàn)了抽象問題的數(shù)字化轉(zhuǎn)變，此后圖論被演變成一種理論應(yīng)用于很多領(lǐng)域。直到20世紀60年代，Berge第一次把計算機算法數(shù)概念引進圖論中，再經(jīng)過Ore把控制算法數(shù)引進圖論中，至此真正的形成了網(wǎng)絡(luò)圖論，促進了數(shù)學與計算機網(wǎng)絡(luò)技術(shù)的結(jié)合發(fā)展。

二、網(wǎng)絡(luò)圖的計算機算法和顯示方法分析

（一）點符號控制算法分析

點符號控制算法是1995年J.E Dunbar首次定義的，它主要研究局部占優(yōu)問題，點符號控制算法也只是研究局部占優(yōu)理論一種變化形式;2011年Michael A Henning在點符號控制算法研究的基礎(chǔ)上進一步研究，提出了符號全控制算法，二者之間有著本質(zhì)的區(qū)別，符號控制算法要求在點的閉鄰域上滿足條件，而符號全控制算法要求在點的開鄰域上滿足條件。我國圖論研究者邢化明等人于2003年引入最小度和最大度問題，分析出了符號全控制算法下界范圍;Michael A Henning對符號全控制算法下界實施更進一步的分析、研究，在此基礎(chǔ)上總結(jié)出具體網(wǎng)絡(luò)圖;王軍秀2006年對下界問題進行全面改進，提出了一種更加完美的界比;2009年，呂新中等對符號全控制算法進行進一步研究，進一步充實了符號全控制算法的內(nèi)容，徐寶根也在前人研究的基礎(chǔ)上精心研究第一次把符號全控制算法變成反符號全控制算法，促進此研究的進一步發(fā)展。

（二）邊符號控制算法

本世紀初，許保根第一次提出了邊符號控制算法，確定了邊控制算法;而后許保根繼續(xù)對邊符號控制算法進行研究、分析，2002年又分析得出了一般網(wǎng)絡(luò)圖的符號邊控制算法的上界、下界以及一些特殊的網(wǎng)絡(luò)圖符號邊控制算法的確切值。減邊控制算法是由符號邊控制算法變形而來，減邊控制算法與符號邊控制算法之間的不同在于函數(shù)值域，減邊控制算法將符號邊控制算法{-1，1}的函數(shù)值域變成了{-1，0，1}。在實際研究中，減控制算法比其他控制算法具有一定的難度，人們在這方面的研究成果比較少。

（三）網(wǎng)絡(luò)圖的顯示

網(wǎng)絡(luò)圖一般要通過計算機進行顯示，為了在屏幕上顯示網(wǎng)絡(luò)圖，人們一般采用語言程序?qū)崿F(xiàn)網(wǎng)絡(luò)圖的繪制，在這里我們采用C語言對網(wǎng)絡(luò)圖進行繪制，C語言能夠較為簡便、快捷的完成網(wǎng)絡(luò)圖的繪制，提高顯示速度。

網(wǎng)絡(luò)圖一般是由點和點之間的連線構(gòu)成，組成點和邊的關(guān)系圖形，這些點和邊的關(guān)系錯綜復(fù)雜，有些點的讀數(shù)可能為1，也有些點的讀數(shù)可能大于1，同時也有些點的讀數(shù)為0。但是每添邊肯定有2個端點，所以在屏幕上繪制網(wǎng)絡(luò)圖，首先要畫出各個頂點，然后在相應(yīng)的頂點間添加連線，從而完成各個圖形的繪制。

先在計算機屏幕上畫出點，然后根據(jù)一只圖形先確定圖上各個點的坐標（x，y），在此過程中要注意屏幕上采用的是物理坐標，也就是在屏幕的左上角，水平方向為X軸，向右為正;垂直方向為Y軸，向下為正。

在這個坐標系中，屏幕上每個點的位置均可以由坐標（X，Y）進行確定，另外要注意這里的X，Y一定是整數(shù)，而且會有一定的取值范圍，其取值范圍與設(shè)置的圖形模式有著密切的聯(lián)系，和屏幕的分辨率有著主要的關(guān)系。在計算過程中如果X，Y的結(jié)果不是整數(shù)，也應(yīng)該去小數(shù)點取整數(shù)，確定坐標后就可以在屏幕上畫邊，找到一條邊的兩個頂點，然后在兩個頂點間畫出一條直線。如果需要在屏幕上任意添加頂點，也可以利用同樣的方法進行繪制，但是要注意對新增的點用不同的顏色進行繪制，以便于使用戶能夠一目了然，C語言一般有16種不同的顏色可供選擇，一般情況下能夠滿足繪圖需求。

三、結(jié)語

近幾年，在信息技術(shù)和數(shù)學技術(shù)的發(fā)展下，人們對網(wǎng)絡(luò)圖的研究更加深入，不斷涌現(xiàn)出新的控制算法和圖形顯示方法，研究方向也有了大的拓展，不再僅僅局限在網(wǎng)絡(luò)圖本身，也開始向其他領(lǐng)域發(fā)展，比如其在編碼理論、計算機網(wǎng)絡(luò)等領(lǐng)域應(yīng)用十分廣泛，不僅促進了網(wǎng)絡(luò)計算機技術(shù)的發(fā)展，而且為人們提供了豐富多彩的生活內(nèi)容。另外，對網(wǎng)絡(luò)圖顯示的研究也取得了較大的成績，通過計算機屏幕和計算機軟件進行圖形的繪制、修改、處理和顯示，完成整個圖形顯示過程，促進網(wǎng)絡(luò)圖形的進一步的發(fā)展。

【參考文獻】

[1]付欣.網(wǎng)絡(luò)圖的計算機算法和顯示方法的研究[J].電腦知識與技術(shù).2013.（35）：7946-7947

[2]彭中.網(wǎng)絡(luò)圖的計算機算法和顯示方法的研究[D].南京理工大學.2004

[3]劉乃維.論網(wǎng)絡(luò)圖的計算機算法[J].計算機光盤軟件與應(yīng)用.2014.（13）：95-96

（作者單位：蘇州大學計算機科學與技術(shù)學院）