论文部分内容阅读
数学是一门古老的学科．但是，作为数学里的一个分支，图论是相当新的．近年来，随着社会的进步，计算机科学和通信技术的不断发展，数学的应用越来越多，图论也得到了长足的进步．图论作为一个非常有效的分析和解决问题的工具，在管理、交通运输、军事、计算机科学、互连网络、化学、物理甚至社会科学等各方面都展现出了它的能力．由于这方面的研究和实际应用之间存在着紧密的联系，而且现实的世界是一个不断变化的世界，因此我们必须关注图的变化对图的一些参数的影响．在本文中，我们主要研究了图的稳定性方面的参数，包括图的约束数和反馈数．
首先，我们研究了约束数．
我们先研究了超环面图的约束数：
如果G是一个连通的超环面图，那么
我们还研究了交叉数小于4的图的约束数，主要结果如下：
G是一个连通图，那么如果G满足下面任一条件，则b(G)≤△(G)+2成立．
(a)cr(G)≤3；
(b)cr(G)=4且G不是4正则的；
(c)cr(G)=5且G不包含4度点．
其次，我们研究了反馈数．我们研究了3个著名互连网络拓扑结构的图的反馈数：
对于De Bruijn有向图B(d，n)，当d≥2和n≥2时，B(d，n)的反馈数f(d，n)满足下面的界：
对于De Bruijn无向图UB(d，n)，当d≥3和n≥1时，UB(d，n)的反馈数f(d，n)满足下面的界：
最后，我们总结了上面这些工作，给出了一些不成熟的猜想，提出了有待进一步研究的几个问题．