蝴蝶网络的抗毁性研究

摘要

一个非完全连通图G的毁裂度定义为r(G)=max{ω(G−X)-|X|-τ(G−X):X⊂V(G),ω(G−X)>1},其中ω(G−X)为G−X的分支数,τ(G−X)为G−X最大分支的阶数。作为网络抗毁性参数之一,毁裂度r(G)既能反映网络图G的破坏难度,又可反映破坏程度。在某种程度上,它代表了破坏网络所需的工作和破坏网络的严重程度之间的平衡。在本文中,我们确定了蝴蝶网络与增广蝴蝶网络的毁裂度。