A New Measure for Vulnerability of Network on Links

图的边毁裂度作为描述图的连通性的又一参数, 是通过讨论网络链路受损程度和恢复难度来刻画网络抗毁性的重要参数之一.下面围绕一些重要图类展开相关讨论.

定理1  设G为p阶非完全图, 则:

(ⅰ) γ′(G)≤0;

(ⅱ) γ′(G)≥p-|E(G)|-1;

(ⅲ) γ′(G)≥3-λ(G)-p;

(ⅳ) γ′(G)≥3-δ(G)-p.

证  (ⅰ)设S为G的任一边割集, 令|S|=r≥1, 则ω(G-S)≤r+1且m(G-S)≥1.因此

由边毁裂度的定义有γ′(G)≤0.

(ⅱ)设S为G的边集E(G), 则|S| = |E(G)|, 那么ω(G-S)=p且m(G-S)=1.因此

由边毁裂度的定义有γ′(G)≥p-|E(G)|-1.

(ⅲ)设S为G的最小边割集, 则|S|=λ(G), ω(G-S)≥2, m(G-S)≤p-1.因此

所以由边毁裂度的定义有γ′(G)≥3-λ-p.

(ⅳ)注意到κ(G)≤λ(G)≤δ(G), 由(ⅲ)直接可得(ⅳ)成立.

定理2  设G是p阶单圈图, 则γ′(G)=-1.

证  首先, 由定理1(ⅱ), 有γ′(G)≥p-|E(G)|-1=-1.设S是G的任一边割集且C_k为G中的唯一圈, 下面估计数值ω(G-S)-|S|-m(G-S).

如S∩E(C_k)=Ø, 则ω(G-S)≤|S|+1且m(G-S)≥3.因此

如S∩E(C_k)≠Ø, 则ω(G-S)≤|S|且m(G-S)≥1.因此

这表明:对于G的任一边割集S, 总有ω(G-S)-|S|-m(G-S)≤-1.从而有γ′(G)≤-1.

因此γ′(G)=-1.

定理3  p阶连通图G是树当且仅当γ′(G)=0.

证  首先, 假设G是p阶树.根据定理1(ⅰ), 有γ′(G)≤0.根据定理1(ⅱ), 有γ′(G)≥p-q-1=0.即有γ′(G)=0.

其次, 假设|V(G)| =p, |E(G)|=q且γ′(G)=0.根据定理1(ⅱ), 有p-q-1≤0.事实上, p-q-1=0.反之, 假设p-q-1 < 0, 考虑到G的连通性, 则G中含圈.再由定理2的证明可知γ′(G)≤-1, 矛盾.所以有p-q-1=0, 即G是树.

定理4  设G是p阶双圈图.则γ′(G)=-2.

证  首先, 取S₀=E(G), 即|S₀|=|E(G)|=q=p+1, 此时ω(G-S₀)=P且m(G-S₀)=1.因此

所以有γ′(G)≥-2.

下面分情形证明γ′(G)≤-2.设S是图G的任一边割集, C_k和C_s是G的两个圈.

情形1   若S∩E(C_k∪C_s)=Ø, 则ω(G-S)≤|S|+1, 且m(G-S)≥3.因此

情形2  若S∩E(C_k)≠Ø但S∩E(C_s)=Ø, 或者若S∩E(C_k)=Ø但S∩E(C_s)≠Ø, 均有ω(G-S)≤|S|且m(G-S)≥3.因此

情形3  若S∩E(C_k)≠Ø且S∩E(C_s)≠Ø, 则ω(G-S)≤|S|-1, 且有m(G-S)≥1.因此

显然, 对于G的任一边割集S, 总有ω(G-S)-|S|-m(G-S)≤-2.因此γ′(G)≤-2.

综上所述, 有γ′(G)=-2.

定理5  设G是p(p≥2)阶完全图, 则

证  显然γ′(K₂)=0, γ′(K₃)=-1.至于G=K₄, 对于任一边割集S, 不难发现

所以由定义有γ′(K₄)=-3.这些表明:对于2≤p≤4, 有

下面考虑一般情形p≥5.

一方面, 由于K_p的最小度为δ(k)=p-1, 由定理1(ⅳ)有

另一方面, 设S是图G的任一边割集, 并设|S|=s, 则

现在检查数值ω(G-S)和m(G-S):

通过观察, ω(G-S)的值ω满足(p-1)+(p-2)+…+(p-ω+1)=s.因此

显然, 逐个破坏与各点关联的边是最好的破坏策略, 从而有

因此

令

因

当s=p-1时, 通过比较数值f(p-1)和$f\left( {\frac{{p\left( {p-1} \right)}}{2}} \right)$可知, f(s)最大值为f(p-1)=4-2p.即得r′(K_p)≤4-2p.

通过以上分析, 即得

定理6  设G是完全二部图K_{s, t}(1≤s≤t), 则

证  分两种情形证明:

情形1   s=1, 2, 3且t≤4.

首先, 取S=E(G), 即|S|=st, ω(G-S)=s+t且m(G-S)=1.所以有

由定义得γ′(G)≥(s+t)-st-1.

设S是图G的任一边割集, 下面考察数值ω(G-S)-|S|-m(G-S)并讨论其最大值.由完全二部图的结构知:有效边割S应满足|S|是s的整数倍, 不妨设|S|=sx.因此有

下面讨论$\left( {2-s} \right)x + 2\left( {s-1} \right)\left\lfloor {\frac{x}{t}} \right\rfloor-s - t + 1$的最大值, 这里整数x满足1≤x≤t.

显然, 当s=1时, 函数f(x)=x-t在[1, t]上递增; 当s=2时, 函数$g\left( x \right) = 2\left\lfloor {\frac{x}{t}} \right\rfloor-t-1$在[1, t]上递增; 当s=3且t≤4时, 函数$h\left( x \right) = 4\left\lfloor {\frac{x}{t}} \right\rfloor-x-t-2$在[1, t]上递增.所以, 当x=t时, ω(G-S)-|S|-m(G-S)取得最大为s+t-st-1.

由定义有

综上即证γ′(G) =(s+t)-st-1.

情形2   s=3, t≥5或4≤s≤t.

首先, 由于图G的最小度为δ(G)=s, 根据定理1(ⅳ)可得

设S是图G的任一边割集且|S|=s.类似于情形1, 考察数值ω(G-S)-|S|-m(G-S)并讨论其最大值.同理可得

整数x满足1≤x≤t.显然, 当s=3且t≥5时, $\omega \left( {G-S} \right)-\left| S \right|-m\left( {G - S} \right) = - x + 4\left\lfloor {\frac{x}{t}} \right\rfloor - 2 - t$在[1, t]上递减; 当4≤s≤t时, $\omega \left( {G-S} \right)-\left| S \right|-m\left( {G - S} \right) = \left( {2 - s} \right)x + 2\left( {s - 1} \right)\left\lfloor {\frac{x}{t}} \right\rfloor - s - t + 1$在上[1, t]递减.所以, 当x=1时ω(G-S)-|S|-m(G-S)取得最大值为3-2s-t.即由定义有

综上即证γ′(G)=3-2s-t.

本节讨论边毁裂度与边完整度、边粘连度等其它边连通参数的关系.

定义1^[11]   图G的边完整度定义为

定义2^[12]   图G的边粘连度定义为

定理7  设G是p(p≥2)阶连通图.若G的边完整度为I′(G), 则

证  设S是图G的任一边割集, 则2≤ω(G-S)≤p, 因此

因此

这意味着

因此

注1  显然, 定理7中的上、下界是最好可能的.下界可在p(p≥2)阶完全图G=K_p上取得; 上界可在星图G=K_{1, P-1}上取得.

定理8  设G是p阶连通图.若|E(G)|=q, 且G的边连通度、边粘连度分别为κ′(G), t′(G), 则

证  首先证明$\gamma '\left( G \right) \le \frac{{q + 1}}{{t'\left( G \right)}}-2t'\left( G \right)$.由边粘连度的定义有

考虑G连通性, 有|S|+m(G-S)≤q+1.则

这说明$\omega \left( {G-S} \right) \le \frac{{q + 1}}{{t'\left( G \right)}}$.结合2≤ω(G-S)≤p可得

据边毁裂度的定义, 有$\gamma '\left( G \right) \le \frac{{q + 1}}{{t'\left( G \right)}}-2t'\left( G \right)$.

类似地, 由γ′(G)的定义有γ′(G)≥ω(G-S)-|S|-m(G-S), 因此

从而ω(G-S)≤q+1+γ′(G).考虑到$m\left( {G-S} \right) \ge \frac{p}{{\omega \left( {G-S} \right)}}$和|S|≥κ′, 于是有

因此$t'\left( G \right) \ge \frac{{\kappa ' + \frac{p}{{q + 1 + \gamma '\left( G \right)}}}}{{q + 1 + \gamma '\left( G \right)}}$, 即得