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

關(guān)鍵詞：圖；網(wǎng)絡(luò)抗毀性；混合邊鄰域粘連度；界；極值圖

中圖分類(lèi)號(hào)：O157.5 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：0253-2395（2024）05-0923-12

0 引言

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

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

設(shè)G = （V，E ） 是一個(gè)簡(jiǎn)單圖，分別稱(chēng)N （ e ）={ f | f ∈ E （G ），且e和 f 相鄰} 和N [ e ] = N （ e ）∪{ e } 為e 的開(kāi)鄰域和閉鄰域。

若X ? E （G ），則分別稱(chēng)N （ X ） = { f |X ∈ E （G ），f ∈ E/X且存在e ∈ X，使得e和f 相鄰} 和N [ X ] =N （ X ）∪ X 為X 的開(kāi)鄰域和閉鄰域。若將N [ X ] 中的邊和與X 中的邊關(guān)聯(lián)的點(diǎn)均從G 中刪除，則稱(chēng)X 為G 的一個(gè)邊顛覆策略，記剩余子圖為G/X。對(duì)連通圖G，設(shè)X ? E （G ），若G/X 不連通，或孤立點(diǎn)或空集?，則稱(chēng)X 為G 的一個(gè)鄰域邊割集。

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

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

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

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

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

定義4［12］ 設(shè)G 是連通圖，其邊鄰域堅(jiān)韌度的定義為：

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

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

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

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

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

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

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

為了更好地刻畫(huà)邊失效情形下的網(wǎng)絡(luò)抗毀性，本文提出圖的混合邊鄰域粘連度概念。

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

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

其中X 為G 的鄰域邊割集，m （G/X ） 和ω（G/X ） 分別為G/X 的最大連通分支的階和連通分支數(shù)。若有X ?，使得MENT （G ） = |X ?| + m （G/X ? ）／ω（G/X ? ），則稱(chēng)X ? 為G 的一個(gè)混合邊鄰域粘連集，簡(jiǎn)記為MENT-集。顯然，混合邊鄰域粘連度越大，網(wǎng)絡(luò)抗毀性越好。

混合邊鄰域粘連度和邊鄰域毀裂度在衡量網(wǎng)絡(luò)的抗毀性方面作用不同。

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

下文主要研究幾類(lèi)圖的混合邊鄰域粘連度計(jì)算公式、一般圖的參數(shù)上、下界和該參數(shù)的極值問(wèn)題。

本文所討論的圖，均是簡(jiǎn)單無(wú)向圖，未定義的概念和術(shù)語(yǔ)參見(jiàn)文獻(xiàn)［17-18］。

1 幾類(lèi)基本圖的混合邊鄰域粘連度

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

4 結(jié)論

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

關(guān)于圖的邊鄰域抗毀性參數(shù)研究，目前已有邊鄰域連通度（Λ）、邊鄰域離散數(shù)（ENS）、邊鄰域堅(jiān)韌度（tEN）、邊鄰域完整度（ENI）、邊鄰域毀裂度（ENR）。表1 是對(duì)7 類(lèi)11 階圖的邊鄰域抗毀性參數(shù)值的比較。

由表中的參數(shù)值可知：

Λ（ 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 ）。

因此有以下結(jié)論（對(duì)表中所舉實(shí)例而言）：

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

（2）邊鄰域抗毀性最強(qiáng)的是K11，最弱的是S1，10。

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

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

參考文獻(xiàn)：

[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叉樹(shù)的粘連度[J]. 純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)， 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] 楊靜婷. 圖的鄰域堅(jiān)韌度研究[D]. 西安： 西安建筑科技大學(xué)， 2017.

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

[12] 楊玉成. 圖的邊鄰域堅(jiān)韌度研究[D]. 西安： 西安建筑科技大學(xué)， 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] 魏宗田， 劉勇， 楊威. 網(wǎng)絡(luò)抗毀性[M]. 西安： 西安交通大學(xué)出版社， 2015.

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

[19] 毛華， 趙小娜， 史田敏， 等. 多部圖的最大匹配算法[J].鄭州大學(xué)學(xué)報(bào)（ 理學(xué)版）， 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.

基金項(xiàng)目：國(guó)家自然科學(xué)基金（61902304）