摘要：為了定量刻畫邊失效情形下的網絡抗毀性，提出圖的混合邊鄰域粘連度概念。給出了幾類圖的參數計算公式和最好可能的上、下界，用組合優(yōu)化方法研究了該參數的極值問題。通過比較幾類邊鄰域抗毀性參數的區(qū)分度，指出混合邊鄰域粘連度刻畫某些網絡的抗毀性更為精確。

關鍵詞：圖；網絡抗毀性；混合邊鄰域粘連度；界；極值圖

中圖分類號：O157.5 文獻標志碼：A 文章編號：0253-2395（2024）05-0923-12

0 引言

間諜網絡的概念是由Gunther 和Hartnell 提出的［1］，他們通過一個圖來模擬間諜網絡，其中圖的頂點代表間諜或站點，邊代表通訊方式。間諜網絡最重要的特性是：如果間諜被捕，與他們直接接觸的間諜是不可靠的。當交通、輸電等網絡中的某一條線路被破壞或失效后，會影響其周圍站點和線路；當新冠感染等高危病毒傳播網絡中的某一條傳播途徑得到控制時，其周邊感染的風險也會降低?；谏鲜霰尘暗目箽詤?，稱為鄰域抗毀性參數。

在網絡鄰域抗毀性分析中，主要考慮三個因素［2］：（1）破壞網絡的難易程度；（2）網絡被破壞的嚴重程度；（3）有多少頂點仍然保持連通。因此，鄰域連通度［3］、邊鄰域連通度［4-5］、鄰域完整度［6］、邊鄰域完整度［7］、鄰域離散數［8］、邊鄰域離散數［9-10］、鄰域堅韌度［11］、邊鄰域堅韌度［12-13］、鄰域毀裂度［14］、邊鄰域毀裂度［15-16］等參數被引入，以衡量網絡在“鄰域”情形下的抗毀性。

設G = （V，E ） 是一個簡單圖，分別稱N （ e ）={ f | f ∈ E （G ），且e和 f 相鄰} 和N [ e ] = N （ e ）∪{ e } 為e 的開鄰域和閉鄰域。

若X ? E （G ），則分別稱N （ X ） = { f |X ∈ E （G ），f ∈ E/X且存在e ∈ X，使得e和f 相鄰} 和N [ X ] =N （ X ）∪ X 為X 的開鄰域和閉鄰域。若將N [ X ] 中的邊和與X 中的邊關聯的點均從G 中刪除，則稱X 為G 的一個邊顛覆策略，記剩余子圖為G/X。對連通圖G，設X ? E （G ），若G/X 不連通，或孤立點或空集?，則稱X 為G 的一個鄰域邊割集。

定義1［4］ 設G 是連通圖，其邊鄰域連通度的定義為：Λ（G ） = min{|X|：X ? E （G ）}，其中X 為G的鄰域邊割集。

邊鄰域連通度是基于因素（1）考慮的。

定義2［7］ 設G 是連通圖，其邊鄰域完整度的定義為：ENI （G ） = min{|X| + m （G/X ）：X ? E （G ）}，其中m （G/X ） 為G/X 的最大連通分支的階。

邊鄰域完整度是基于因素（1）和因素（3）考慮的。

定義3［9］ 設G 是連通圖，其邊鄰域離散數的定義為：ENS（G ） = min{ω（G/X ）- |X|：X ? E （G ）}，其中X 為G 的鄰域邊割集，ω（G/X ） 為G/X 的連通分支數。

定義4［12］ 設G 是連通圖，其邊鄰域堅韌度的定義為：

tEN （G ）= min ｛|X|／ω（G/X ）：X ? E （G ）｝，

其中X 為G 的鄰域邊割集，ω（G/X ） 為G/X 的連通分支數。

邊鄰域離散數和邊鄰域堅韌度是基于因素（1）和因素（2）考慮的。邊鄰域堅韌度是邊鄰域離散數的除法形式，盡管這兩個參數在定義上有一些相似之處，但在衡量網絡的抗毀性方面作用不同。

定義5［15］ 設G 是連通圖，其邊鄰域毀裂度的定義為：

ENR（G ）= min{ω（G/X ）- |X| - m （G/X ）：X ? E （G ）}，

其中X 為G 的鄰域邊割集，m （G/X ） 和ω（G/X ） 分別為G/X 的最大連通分支的階和連通分支數。

邊鄰域毀裂度是基于因素（1）、（2）和（3）考慮的。是視角較為全面的抗毀性參數。

為了更好地刻畫邊失效情形下的網絡抗毀性，本文提出圖的混合邊鄰域粘連度概念。

定義6 設G 是連通圖，其混合邊鄰域粘連度定義為

MENT （G ）= min ｛|X| + m （G/X ）／ω（G/X ）：X ? E （G ）｝，

其中X 為G 的鄰域邊割集，m （G/X ） 和ω（G/X ） 分別為G/X 的最大連通分支的階和連通分支數。若有X ?，使得MENT （G ） = |X ?| + m （G/X ? ）／ω（G/X ? ），則稱X ? 為G 的一個混合邊鄰域粘連集，簡記為MENT-集。顯然，混合邊鄰域粘連度越大，網絡抗毀性越好。

混合邊鄰域粘連度和邊鄰域毀裂度在衡量網絡的抗毀性方面作用不同。

例1 設K8，7，P15 表示同階的完全二部分圖和路，則它們的邊鄰域毀裂度均為1，而MENT （ K8，7 ） =87，MENT （ P15 ） =65，混合邊鄰域粘連度不相等。

下文主要研究幾類圖的混合邊鄰域粘連度計算公式、一般圖的參數上、下界和該參數的極值問題。

本文所討論的圖，均是簡單無向圖，未定義的概念和術語參見文獻［17-18］。

1 幾類基本圖的混合邊鄰域粘連度

本節(jié)討論并給出幾類基本圖的混合邊鄰域粘連度計算公式。

4 結論

從混合邊鄰域粘連度的計算公式可以看出，對于路、圈、星圖、雙星圖等，其頂點數越大，參數值越小，抗毀性越弱；對于完全圖，其頂點數越大，參數值越大，抗毀性越強；對于彗星圖，其Pn - k的頂點數越大，S1，k 的頂點數越小，參數值越大，抗毀性越強；對于完全二部分圖，二部劃分的頂點數相差越大，參數值越大，抗毀性越強；對于完全p 部分圖，最大劃分與其余劃分的頂點數相差越大，參數值越大，抗毀性越強。

關于圖的邊鄰域抗毀性參數研究，目前已有邊鄰域連通度（Λ）、邊鄰域離散數（ENS）、邊鄰域堅韌度（tEN）、邊鄰域完整度（ENI）、邊鄰域毀裂度（ENR）。表1 是對7 類11 階圖的邊鄰域抗毀性參數值的比較。

由表中的參數值可知：

Λ（ S1，10 ） = Λ（T11，6 ） = Λ（ P11 ） lt; Λ（ C11 ） lt; （ K4，3，3，1 ） lt; Λ（ K11 ） = Λ（ K5，6 ）；ENS（ K11 ） lt; ENS（ C11 ） = ENS（ K5，6 ） = ENS（ K4，3，3，1 ） lt; ENS（ P11 ） lt; ENS（T11，6 ） lt; ENS（ S1，10 ）；tEN （ S1，10 ） lt; tEN （T11，6 ） lt; tEN （ P11 ） lt; tEN （ C11 ） = tEN （ K4，3，3，1 ） = tEN （ K5，6 ） lt; tEN （ K11 ）；ENI （ S1，10 ） lt; ENI （T11，6 ） lt; ENI （ P11 ） = ENI （ K4，3，3，1 ） = ENI （ C11 ） lt; ENI （ K5，6 ） = ENI （ K11 ）；ENR（ K11 ） lt; ENR（ C11 ） lt; ENR（ P11 ） = ENR（ K4，3，3，1 ） = ENR（ K5，6 ） lt; ENR（T11，6 ） lt; ENR（ S1，10 ）；MENT （ S1，10 ）lt; MENT （T11，6 ）lt; MENT （ K5，6 ）lt; MENT （ P11 ）lt; MENT （ C11 ）lt; MENT （ K11 ）。

因此有以下結論（對表中所舉實例而言）：

（1）區(qū)分度最好的是MENT，其余依次是tEN，ENS，ENR，ENI，Λ；

（2）邊鄰域抗毀性最強的是K11，最弱的是S1，10。

上述研究表明，混合邊鄰域粘連度的區(qū)分度較好，刻畫某些網絡的抗毀性更為精確。

一般圖的混合邊鄰域粘連度計算是比較復雜的，但介于特殊與一般之間的圖，如樹，區(qū)間圖等的混合邊鄰域粘連度算法是一個值得研究的問題。

參考文獻：

[1] GUNTHER G， HARTNELL B. On Minimizing the Effectsof Betrayals in A Resistancemovement[C]//Proceedingsof the Eighth Manitoba Conference on Numericalmathematicsand Computing. Winnipeg： Utilitas MathematicaPublishing Inc. Ⅵ， 1978： 285-306.

[2] 陳忠， 李銀奎. 完全k叉樹的粘連度[J]. 純粹數學與應用數學， 2013， 29（5）： 484-488. DOI： 10.3969/j. issn.1008-5513.2013.05.007.

CHEN Z， LI Y K. The Tenacity and Rupture Degree of theComplete K-ary Tree[J]. Pure Appl Math， 2013， 29（5）：484-488. DOI： 10.3969/j.issn.1008-5513.2013.05.007.

[3] GU M M， PAI K J， CHANG J M. Subversion Analysesof Hierarchical Networks Based on （Edge） NeighborConnectivity[J]. J Parallel Distributed Comput， 2023，171： 54-65. DOI： 10.1016/j.jpdc.2022.09.010.

[4] COZZENS M B， WU S S Y. Extreme Values of Edgeneighbor-Connectivity[J]. Ars Combinatoria， 1995， 39：199-210.

[5] ZHAO X B， ZHANG Z， REN Q. Edge Neighbor Connectivityof Cartesian Product Graph G × K2[J]. Appl MathComput， 2011， 217（12）： 5508-5511. DOI： 10.1016/j.amc.2010.12.022.

[6] BACAK-TURAN G， KIRLANGIC A. Neighbor Integrityof Transformation Graphs[J]. Int J Found Comput Sci， 2013，24（3）： 303-317. DOI： 10.1142/s0129054113500056.

[7] COZZENS M B， WU S S Y. Bounds of Edge-neighborintegrityof Graphs[J]. Australas J Comb， 1997， 15（15）：71-80.

[8] WEI Z T， QI N N， YUE X K. Vertex-neighbor-scatteringNumber of Bipartite Graphs[J]. Int J Found Comput Sci，2016， 27（4）： 501-509. DOI： 10.1142/s012905411650012x.

[9] WEI Z T， QI N N， YUE X K. Computing the Edgeneighbour-scattering Number of Graphs[J]. ZeitschriftFür Naturforschung A， 2013， 68（10/11）： 599-604. DOI：10.5560/zna.2013-0059.

[10] LIU Y， WEI Z T， SHI J R， et al. A Polynomial Algorithmof Edge-neighbor-scattering Number of Trees[J].Appl Math Comput， 2016， 283： 1-5. DOI： 10.1016/j.amc.2016.02.021.

[11] 楊靜婷. 圖的鄰域堅韌度研究[D]. 西安： 西安建筑科技大學， 2017.

YANG J T. Study on neighborhood toughness of graphs[D]. Xi'an： Xi'an University of Architecture andTechnology， 2017.

[12] 楊玉成. 圖的邊鄰域堅韌度研究[D]. 西安： 西安建筑科技大學， 2019.

YANG Y C. Study on Edge Neighborhood Toughnessof Graphs[D]. Xi'an： Xi'an University of Architectureand Technology， 2019.

[13] FENG X， WEI Z T， YANG Y C. Edge Neighbor Toughnessof Graphs[J]. Axioms， 2022， 11（6）： 248. DOI：10.3390/axioms11060248.

[14] BACAK-TURAN G， OZ E. Neighbor Rupture Degree ofTransformation Graphs Gxy-[J]. Int J Found Comput Sci，2017， 28（4）： 335-355. DOI： 10.1142/s0129054117500216.

[15] ASLAN E. Edge-neighbor-rupture Degree of Graphs[J].J Appl Math， 2013， 2013： 1-5. DOI： 10.1155/2013/783610.

[16] KüRK?ü ? K， ASLAN E. A Comparison between EdgeNeighbor Rupture Degree and Edge Scattering Number inGraphs[J]. Int J Found Comput Sci， 2018， 29（7）： 1119-1142. DOI： 10.1142/s0129054118500247.

[17] BONDY J A， MURTY U S R. Graph theory[M]. NewYork： Springer， 2008.

[18] 魏宗田， 劉勇， 楊威. 網絡抗毀性[M]. 西安： 西安交通大學出版社， 2015.

WEI Z T， LIU Y， YANG W. Network invulnerability[M]. Xi'an： Xi'an Jiaotong University Press， 2015.

[19] 毛華， 趙小娜， 史田敏， 等. 多部圖的最大匹配算法[J].鄭州大學學報（ 理學版）， 2013， 45（1）： 27-29. DOI：10.3969/j.issn/1671-6841.2013.01.007

MAO H， ZHAO X N， SHI T M， et al. An Algorithm onMaximum Matching of Multipartite Graph[J]. JZhengzhou Univ Nat Sci Ed， 2013， 45（1）： 27-29. DOI：10.3969/j.issn/1671-6841.2013.01.007.

基金項目：國家自然科學基金（61902304）