论文部分内容阅读
图论是一门新兴的学科,但由于它在很多领域都有着广泛应用,图论近几十年来发展十分迅速.其中,控制理论经过了三十年的发展,已经成为了图论研究中的一个重要领域,究其原因,也是因为控制不仅在理论上,还在实际问题中有着重要的应用.正是由于这方面的研究和实际应用之间有着紧密的联系,在本文中我们将研究图在边改变下的控制稳定性,即考虑图中边的改变对控制有何影响.之所以采用这种动态的视角,是因为图作为很多现实问题的模型,时常要做一些改变,才能适应现实的变化;于是,我们必须关注图的变化对一些参数和性质有何影响.具体到本文,我们主要研究三个参数——约束数,加强数和控制收缩数,它们分别反映了图在三种基本的边改变:删去,增加和收缩下的控制稳定性.
对于约束数b(G),我们首先对交叉数较小的图得到了~系列结果,它们包含了前人得到的平面图约束数的若干上界.在这些结果种最重要的两个是b(G)≤min{8,△(c)4-2}在cr(G)≤3时成立,然后我们考虑de Bruijn图S(d,n)和Kautz图K(d,n).这两类图作为互连网络的拓扑结构,有很多好的性质,因此已经超越经典的超立方体网络成为下一代并行系统体系结构的首选.
我们还确定了这两类图的全约束数(约束数的变形,对应于全控制数)最后我们证明了K正则的点可迁图G我们得到了一些常见网络的约束数,包括双环网,圆环和立方连通圈.对于加强数r(G),我们对有向图给出了定义,并且得到了很多和无向图情形类似的结果.我们还研究了无向图和有向图的加强数之间的关系.然后我们考虑在一篇加强数的综述文章中提出的两个问题:
受到近年来关于(全)控制细分数的研究的启发,我们提出了(全)控制收缩数的概念,并给出了它的实际意义.我们证明了对所有的图这个参数的取值只能是0,1,2或3,并且刻画了分别取这些值的四个图类.
最后,我们总结了上面这些工作,并给出了关于平面图约束数的若干猜想的一些不成熟结果,还提出了很多有待进一步深入研究的问题。