论文部分内容阅读
在(M.E.Messinger,2008)中,作者提出了用刷子清理一个网络的问题。根据他的工作,我们知道了清理一个树所需要的刷子数。在文献中,他完全解决了路乘路,路乘圈等的最小刷子数的问题,但是对一般情况我们仍然不知道需要清理它的最小刷子数是多少。
在本文中,我们将处理一般的情况。一个切入点是仔细的分析图的结构,在这个分析过程中我们有幸得到了一个新的角度来看待图的清理序列这一概念,这帮助我们更准确的理解一个清理序列是如何形成的。因此我们能得到一般图的刷子数上界。具体上界为b(G)≤e/2+1/2[V(G)/2]。而后我们刻画出了达到上界的所有的图类,即若b(G)=e/2+1/2[V(G)/2],当且仅当图G的每一个连通分支都是完全图,并且它们当中最多有一个是奇图。