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

徐瑾

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

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

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

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

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

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

（一）點(diǎn)符號控制算法分析

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

（二）邊符號控制算法

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

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

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

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

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

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

三、結(jié)語

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

【參考文獻(xiàn)】

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

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

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

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