图的弱毁裂度

为了刻画具有相同毁裂度的图在抗毁性上的差异,引入一个新的网络抗毁性参数—弱毁裂度。运用组合优化和类比分析方法研究并给出了若干具有特殊结构图的弱毁裂度计算公式以及一般图的弱毁裂度上、下界。几类典型图的抗毁性分析表明,该参数具有比毁裂度更高的精确性。

图的弱毁裂度与网络抗毁性

图的弱毁裂度是刻画网络抗毁性的一个重要参数,它将破坏网络的难易程度和网络被破坏的严重程度相结合,并在剩余子图中考虑了边数的因素.为了揭示该参数与网络结构的内在关系,更加精确地量化网络抗毁性,本文首先研究并给出弱毁裂度的若干基本性质.在此基础上,用组合优化和类比的方法研究了该参数与图的若干重要参数之间的关系.这些关系以弱毁裂度的上、下界形式给出,本质上反映了弱毁裂度意义下的网络结构特征,即抗毁性.所得结果表明,弱毁裂度在刻画某些网络抗毁性上具有明显的优势.文中使用的方法对网络抗毁性分析研究具有重要借鉴作用,所得结论对网络抗毁性设计有一定推广与应用价值.

毁裂度的Nordhaus-Gaddum型结果

给出了图的毁裂度的界,进而讨论了图的毁裂度的Nordhaus-Gaddum型问题。

网络结构的边毁裂度

在毁裂度的基础上,研究图的边的毁裂度.通过优化组合、归纳假设的方法界定了图的边毁裂度的值,如笛卡尔积图:Pm×Pn,Pm×Cn,Cm×Cn,Km×Kn,并界定了G=G1×G2的边毁裂度的界.最后给出了一些基本图,如路、圈、星图、完全二部图Km,n的线图边毁裂度.

包含k-树图的毁裂度条件

连通图G的一个k-树是指图G的一个最大度至多是k的生成树.对于连通图G来说,其毁裂度定义为r(G)=max{ω(G-X)-|X|-m(G-X)|X■V(G),ω(G-X)>1}其中ω(G-X)和m(G-X)分别表示G-X中的分支数目和最大分支的阶数.本文结合毁裂度给出连通图G包含一个k-树的充分条件;利用图的结构性质和毁裂度的关系逐步刻画并给出图G包含一个k-树的毁裂度条件.

卡氏积图的抗毁性(英文)

为了描述一些常用网络结构的抗毁性,为网络设计者设计高效网络结构提供有价值的方法和依据,通过界定完全图的卡氏积和网格图等一些常用网络图的毁裂度来刻画它们的抗毁性.

完全k叉树的粘连度

相对于其他网络抗毁性的描述指标来说,图的粘连度是比较理想,也是比较合理的刻画参数.而完全k叉树作为重要的网络结构被广泛地应用在通信网和嵌入式系统芯片的优化设计方面.本文通过优化组合方法界定了完全k叉树的粘连度和毁裂度.从某种程度刻画了网络的抗毁性,为网络设计提供了一种客观的理论依据.完全k叉树的粘连度为1/k+1(kh+1-1),如h是奇数;1/k+1(kh+1+1),如h是偶数.完全k叉树的毁裂度为(2k-1)kh-1/2-1/k-1,如h是奇数;k h+2/2-1/k-1,如h是偶数.

链路意义下网络抗毁性的一种新刻画

随着元器件性能的大幅提高,网络故障多因链路受阻或破坏所引发,为了更好地刻画和分析网络抗毁性,从链路角度引入新的连通性参数——图的边毁裂度.运用组合优化和类比分析方法研究并给出了若干具有特殊结构的图的边毁裂度的计算公式和一般图的边毁裂度的界,同时讨论了图的边毁裂度与其它参数的关系,并举例表明结果是最好的.

蝴蝶网络的抗毁性研究

一个非完全连通图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的破坏难度,又可反映破坏程度。在某种程度上,它代表了破坏网络所需的工作和破坏网络的严重程度之间的平衡。在本文中,我们确定了蝴蝶网络与增广蝴蝶网络的毁裂度。