论文部分内容阅读
数学是一门古老的学科.但是,作为数学里的一个分支,图论是相当新的.近年来,随着社会的进步,计算机科学和通信技术的不断发展,数学的应用越来越多,图论也得到了长足的进步.图论作为一个非常有效的分析和解决问题的工具,在管理、交通运输、军事、计算机科学、互连网络、化学、物理甚至社会科学等各方面都展现出了它的能力.由于这方面的研究和实际应用之间存在着紧密的联系,而且现实的世界是一个不断变化的世界,因此我们必须关注图的变化对图的一些参数的影响.在本文中,我们主要研究了图的稳定性方面的参数,包括图的约束数和反馈数.
首先,我们研究了约束数.
我们先研究了超环面图的约束数:
如果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)满足下面的界:
最后,我们总结了上面这些工作,给出了一些不成熟的猜想,提出了有待进一步研究的几个问题.