网络图的计算机算法和显示方法的研究

文/徐 瑾

【摘 要】随着科学技术的发展，生活中越来越多的实际问题，需要借助数学模型进行分析、解决，所以人们在离散型结构问题上对数字技术的应用越来越高，有力的促进了网络图理论的发展，解决人们生产、生活中很多困难，提高工作效率，促进科技的进一步发展。本文主要从网络图的计算机算法和显示方法等方面进行研究、分析。

教育期刊网 http://www.jyqkw.com
关键词 网络图；计算机算法；显示方法

21世纪是网络信息技术加速发展的时期，计算机技术已经成熟，人类科技得到了长足的发展，为图论和计算机技术的紧密结合提供了有利的条件，特别是在图形结构以及图形关系方面，网络图论在定量和定性方面都能够较好的优化网络图。近几年，在信息技术和数字技术的带动下，图理论发展迅速，其中网络图的显示和控制算法发展最为迅速，也是近几年人们研究的热点。

一、图论发展概括

现实生活中国很多实际问题都能够应用建立数学模型的方式进行解决，人类早在公元1850年就开始涉及这方面的研究，比如欧洲在国际象棋中就有对“皇后”这一问题的研究，在这个问题上既要使用最少，又要取得最少的方格，这就是网络图最早的雏形。到18世纪人们利用点、线问题研究图论，根据点和线的组合形成一种图形科学。1736年欧拉通过“在不重复的情况下，找出一次性走完七座桥的方法”，假设这一问题无解，并对其结论进行严密的证明，实现了抽象问题的数字化转变，此后图论被演变成一种理论应用于很多领域。直到20世纪60年代，Berge第一次把计算机算法数概念引进图论中，再经过Ore把控制算法数引进图论中，至此真正的形成了网络图论，促进了数学与计算机网络技术的结合发展。

二、网络图的计算机算法和显示方法分析

（一）点符号控制算法分析

点符号控制算法是1995年J.E Dunbar首次定义的，它主要研究局部占优问题，点符号控制算法也只是研究局部占优理论一种变化形式；2011年Michael A Henning在点符号控制算法研究的基础上进一步研究，提出了符号全控制算法，二者之间有着本质的区别，符号控制算法要求在点的闭邻域上满足条件，而符号全控制算法要求在点的开邻域上满足条件。我国图论研究者邢化明等人于2003年引入最小度和最大度问题，分析出了符号全控制算法下界范围；Michael A Henning对符号全控制算法下界实施更进一步的分析、研究，在此基础上总结出具体网络图；王军秀2006年对下界问题进行全面改进，提出了一种更加完美的界比；2009年，吕新中等对符号全控制算法进行进一步研究，进一步充实了符号全控制算法的内容，徐宝根也在前人研究的基础上精心研究第一次把符号全控制算法变成反符号全控制算法，促进此研究的进一步发展。

（二）边符号控制算法

本世纪初，许保根第一次提出了边符号控制算法，确定了边控制算法；而后许保根继续对边符号控制算法进行研究、分析，2002年又分析得出了一般网络图的符号边控制算法的上界、下界以及一些特殊的网络图符号边控制算法的确切值。减边控制算法是由符号边控制算法变形而来，减边控制算法与符号边控制算法之间的不同在于函数值域，减边控制算法将符号边控制算法{-1,1}的函数值域变成了{-1,0,1}。在实际研究中，减控制算法比其他控制算法具有一定的难度，人们在这方面的研究成果比较少。

（三）网络图的显示

网络图一般要通过计算机进行显示，为了在屏幕上显示网络图，人们一般采用语言程序实现网络图的绘制，在这里我们采用C语言对网络图进行绘制，C语言能够较为简便、快捷的完成网络图的绘制，提高显示速度。

网络图一般是由点和点之间的连线构成，组成点和边的关系图形，这些点和边的关系错综复杂，有些点的读数可能为1，也有些点的读数可能大于1，同时也有些点的读数为0。但是每添边肯定有2个端点，所以在屏幕上绘制网络图，首先要画出各个顶点，然后在相应的顶点间添加连线，从而完成各个图形的绘制。

先在计算机屏幕上画出点，然后根据一只图形先确定图上各个点的坐标（x,y),在此过程中要注意屏幕上采用的是物理坐标，也就是在屏幕的左上角，水平方向为X轴，向右为正；垂直方向为Y轴，向下为正。

在这个坐标系中，屏幕上每个点的位置均可以由坐标（X,Y)进行确定，另外要注意这里的X,Y一定是整数，而且会有一定的取值范围，其取值范围与设置的图形模式有着密切的联系，和屏幕的分辨率有着主要的关系。在计算过程中如果X,Y的结果不是整数，也应该去小数点取整数，确定坐标后就可以在屏幕上画边，找到一条边的两个顶点，然后在两个顶点间画出一条直线。如果需要在屏幕上任意添加顶点，也可以利用同样的方法进行绘制，但是要注意对新增的点用不同的颜色进行绘制，以便于使用户能够一目了然，C语言一般有16种不同的颜色可供选择，一般情况下能够满足绘图需求。

三、结语

近几年，在信息技术和数学技术的发展下，人们对网络图的研究更加深入，不断涌现出新的控制算法和图形显示方法，研究方向也有了大的拓展，不再仅仅局限在网络图本身，也开始向其他领域发展，比如其在编码理论、计算机网络等领域应用十分广泛，不仅促进了网络计算机技术的发展，而且为人们提供了丰富多彩的生活内容。另外，对网络图显示的研究也取得了较大的成绩，通过计算机屏幕和计算机软件进行图形的绘制、修改、处理和显示，完成整个图形显示过程，促进网络图形的进一步的发展。

教育期刊网 http://www.jyqkw.com
参考文献

[1]付欣.网络图的计算机算法和显示方法的研究[J].电脑知识与技术.2013.(35):7946-7947

[2]彭中.网络图的计算机算法和显示方法的研究[D].南京理工大学.2004

[3]刘乃维.论网络图的计算机算法[J].计算机光盘软件与应用.2014.(13):95-96

（作者单位：苏州大学计算机科学与技术学院）