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

摘 要：现阶段,越来越多对实际问题需要借助数学模型得以解决,这也使得人们在针对离散型结构问题上使用数字技术的概率越来越大,这极大地促进了网络图理论的向前发展.该文所研究的恰恰就是其中的控制算法理论,并简单阐述了网络图的计算机算法和显示方法,希望能给予同行参考.

关 键 词：网络图；显示方法；计算机算法

中图分类号：TP393文献标识码：A文章编号：1009-3044（2013）35-7946-02

如今,随着计算机水平的全面提升与人类科学的向前发展,促使了图论与计算机技术紧密结合,尤其是在针对离散事物的结构与关系问题上,网络图理论无论是在定性还是定量上都能很好地对相关问题进行优化.这使得网络图理论飞速发展,尤其是在网络的符号理论领域,比如图的标号、控制和显示等领域,俨然是图论中发展最快的分支之一.伴随着信息化和数字化时代的到来,计算机网络技术与图理论不断进步,这其中发展最快,被人们研究最多的主要就是网络图的显示和控制算法问题,这已经成为网络图理论中两个重要的研究内容.

1图论发展简史

通过对现实生活的观察,我们可以发现,其实很多问题其本质都可以通过一个由点和线组成的图形来建立数学模型并解决之.该研究可以追溯到公元1850年,当时欧洲人在下国际象棋时考虑到一个问题,怎么放置“皇后”可以使用最少并且又能控制算法所有的方格.这大概也是网络图的最早雏形.但确切来说,图论正式作为一种由点、线组成的“图形”学科,还应该追溯到18世纪东普鲁士国都哥尼斯堡的七桥问题,当时就一次性、不重复地走完七座桥的检测设无人能解,一直到1736年大数学家欧拉采用抽象分析法才将这个问题数学化,并极其严谨地证明了哥尼斯堡七桥问题无解,这可以说是数学界第一篇关于图论的论文,同时也标志着数学界又多了两个分支,即图论和拓扑学.

在欧拉之后的两百多年里,图论逐渐成为一个理论并越来越多的应用研究领域,除了欧拉所创立的经典图论外,图论可以与和许多学科进行结合,比如说与代数结合形成了代数图论,拓扑学视角下拓扑图论,结合概率分析之后的随机图论,结合谱几何理论形成的谱图理论等.到上世纪六十年代,很多数学家通过n×n棋盘对图论进项算法研究.1958年Berge首次在图论中引入了计算机算法数这一概念,1962年Ore则正式引入了控制算法数这一概念,这意味着网络图论的形成,该理论一直应用到今天.一直以来,为满足高计算的目标,数学被广泛地与计算机科学相结合,在一代又一代科学家手中收获了一批批成果,而图论的产生无疑给计算机的诞生铺平了道路；此外,伴随着计算机网络技术的提升,它也将促进图论中数学理论的向前发展.

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

2.1点符号全控制算法的发展及研究

点符号控制算法是一种研究局部占优问题的理论.它是由J.EDunbar于1995年首次定义的.而点符号全控制算法是它的一种变化形式,符号全控制算法是由Zelinka于2001年第一次提出的,符号全控制算法与符号控制算法的不同之处在于：符号控制算法要求在点的闭邻域上满足条件,而Zelinka将闭邻域改为开邻域,从而引出了不同的研究空间.2003年,刑化明等人引入了最大度和最小度给出了一般网络图的符号全控制算法数的下界.2004年,MichaelAHenning通过对符号全控制算法函数的研究得出了一些新的下界,并给出了满足这些下界的具体网络图.2006年,王军秀在对上述定理关于网络图的符号全控制算法数的下界作出了全面的改进,得到了优于已给出的界.2009年,吕新忠,仪明源得出了几类特殊网络图的符号全控制算法数,使得符号全控制算法的内容进一步得到了充实.对于点的其它变化形式,徐保根于2006年将符号控制算法定义中的f[v]≥1的方向改变,提出了反符号控制算法的概念.该文根据上述变化首次将符号全控制算法变化为反符号全控制算法,对反符号全控制算法的研究,使作者能够进一步掌握研究方法,扩展创新思路,发现其中的研究乐趣.

2.2边符号控制算法的发展及研究

2001年徐保根首先提出了符号边控制算法的概念,并得出了一系列的研究成果,如确定了m边的最小符号边控制算法数,很大程度上丰富和完善了网络图的控制算法理论的内容.2002年BohdanZelinkaLiberec给出了有关树的一些界限.徐保根于2002年到2004年期间得到了一般网络图的符号边控制算法数的上界和下界以及一些特殊网络图的符号边控制算法数的确切值.在研究角度和方法的不断改进中,2005年到2007年期间徐保根进一步得到了一般网络图的符号边控制算法数的界限,此外,许多学者也积极参与研究,得到了一些特殊网络图的符号边控制算法数的确切值和一般网络图的界限.

与点控制算法中的减控制算法一样,边上的减控制算法也是符号边控制算法的一种变化形式,减边控制算法是对符号边控制算法中的函数值域改变得到的,即将函数值域{-1,1}改为{-1,0,1}.由于减控制算法的研究难度相对大些,而且研究时间不长,所以目前为止还没有太多的关于它的研究成果.下一步,将研究减k边控制算法,它是将减边控制算法定义中要求满足条件的“所有边”改为“至少有k条边”,难度的进一步扩大也是对作者的一种锻炼与考验.

3结束语

如今,网络图的理论被掀起了浓厚的研究,新的理论成果如雨后春笋不断涌现,并且没有国界,作为控制算法理论研究的先锋队,我们不仅要在网络图的计算机算法理论上进行研究,还应引领那些年轻的学者在浩瀚的研究大海中寻找方向和明确目标.网络图的控制算法理论不仅在网络图论本身的研究方向上有着广泛的应用,而且在其它学科,如计算机网路、拓扑结构及编码理论等领域也显出了广阔的应用背景.