您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2023, Vol. 58 ›› Issue (6): 40-45, 76.doi: 10.6040/j.issn.1671-9352.0.2021.454

•   • 上一篇    下一篇

基于邻域连通度优化的图的N[S]-T重构

常乐(),魏宗田   

  1. 西安建筑科技大学理学院, 陕西 西安 710055
  • 收稿日期:2021-06-28 出版日期:2023-06-20 发布日期:2023-05-23
  • 作者简介:常乐(1996—)，女，硕士研究生，研究方向为图论、组合优化及其应用. E-mail: 18735125362@163.com
  • 基金资助:
    国家自然科学基金资助项目(61902304)

Graph N[S]-T reconstruction based on neighbor connectivity optimization

Le CHANG(),Zongtian WEI   

  1. School of Science, Xi'an University of Architecture and Technology, Xi'an 710055, Shaanxi, China
  • Received:2021-06-28 Online:2023-06-20 Published:2023-05-23

RichHTML

1

PDF (PC)

150

摘要：

基于最优化的思想考虑一个被破坏的网络的邻域抗毁性恢复, 提出图的邻域颠覆策略和重构的概念。研究了基于邻域连通度优化的图的重构问题, 给出了两个完全图的笛卡尔积图关于最佳邻域颠覆策略下的最优重构方法和算法。

关键词: 邻域颠覆策略, 重构, 最优重构, 完全图, 笛卡尔积图

Abstract:

Considering the neighbor invulnerability recovery of a damaged network based on the optimization idea, the neighbor subversion strategy and the concept of reconstruction are proposed. The problem of graph reconstruction based on neighbor connectivity optimization is studied. An optimal reconstruction method and an algorithm of Cartesian product graph of two complete graphs under the optimal neighbor subversion strategy are presented.

Key words: neighbor subversion strategy, reconstruction, optimal reconstruction, complete graph, cartesian product graph

中图分类号: 

  • O157.5

图1

(a) 圈C9, (b)C9颠覆后, (c)C9的最优重构"

图2

(a) 树G, (b)G颠覆后和(c)G的一个最优重构"

图3

(a) 路P8, (b)P8颠覆后, (c)和(d)P8的2个不同的最优重构"

图4

笛卡尔积图K9×K3的一个最优重构"

图5

笛卡尔积图K9×K6的一个最优重构"

1 COZZENS M B , WU S . Extreme values of the edge-neighbor-connectivity[J]. ARS Combinatoria-Waterloo then Winnipeg-, 1995, 39 (1): 199- 210.
2 GUNTHER G , HATNELL B L . On m-connected and k-neighbor-connected graphs[J]. Graph Theory, Combinatorics and Applications, 1991, 2, 585- 596.
3 TUTTE W T . The reconstruction problem in graph theory[J]. British Polymer Journal, 1977, 9 (3): 180- 183.
doi: 10.1002/pi.4980090302
4 ABDALLAH M , HUNG C N . Neighbor connectivity of the alternating group graph[J]. Journal of Interconnection Networks, 2021, 2150014.
5 SHANG Y J , HAO R X , GU M M . Neighbor connectivity of two kinds of cayley graphs[J]. Acta Mathematicae Applicatae Sinica, English Series, 2018, 34 (2): 386- 397.
doi: 10.1007/s10255-018-0739-9
6 WANG M , LIN Y , WANG S . The 1-good-neighbor connectivity and diagnosability of Cayley graphs generated by complete graphs[J]. Discrete Applied Mathematics, 2017, 246 (9): 108- 118.
7 GUNTHER G . Neighbour-connectivity in regular graphs[J]. Discrete Applied Mathematics, 1985, 11 (3): 233- 243.
8 BONDY J A , MURTY U S R . Graph theory with applications[M]. London: Springer, 2008.
9 魏宗田, 刘勇. 网络抗毁性[M]. 西安: 西安交通大学出版社, 2015.
WEI Zongtian , LIU Yong . Network invulnerability[M]. Xi'an: Xi'an Jiaotong University Press, 2015.
10 WEI Zongtian , MAI Anchan , ZHAI Meijuan . Vertex-neighbor-scattering number of graphs[J]. ARS Combinatoria: An Australian-Canadian Journal of Combinatorics, 2011, 102, 417- 426.
[1] 王力工,郁志明,周枫,陶丽杰,邢露淇. 基于完全图构造的两类整图[J]. 《山东大学学报(理学版)》, 2023, 58(11): 155-159.
[2] 王淑娟,杨火根,柴莹. 过Bézier三边形测地线的有理多项式Coons曲面片重构[J]. 《山东大学学报(理学版)》, 2022, 57(6): 102-110.
[3] 索孟鸽,陈京荣,张娟敏. 笛卡尔乘积图的k-路点覆盖[J]. 《山东大学学报(理学版)》, 2022, 57(12): 103-110.
[4] 杨瑞,刘成立,武楠楠. n棱柱的完美匹配计数及其k-共振性[J]. 《山东大学学报(理学版)》, 2022, 57(11): 37-41.
[5] 张生桂,陈祥恩. 近完全图的点可区别Ⅰ-全染色及Ⅵ-全染色[J]. 《山东大学学报(理学版)》, 2021, 56(5): 23-25.
[6] 刘静姝,王莉,刘惊雷. 基于循环矩阵投影的Nyström扩展[J]. 《山东大学学报(理学版)》, 2020, 55(7): 55-66.
[7] 苏阳. 对称密码中有限域乘法运算的可重构设计[J]. 山东大学学报（理学版）, 2017, 52(6): 76-83.
[8] 张晓东,董唯光,汤旻安,郭俊锋,梁金平. 压缩感知中基于广义Jaccard系数的gOMP重构算法[J]. 山东大学学报（理学版）, 2017, 52(11): 23-28.
[9] 张本慧, 唐元生, 陈文兵. 密钥重构过程中的通信率[J]. 山东大学学报（理学版）, 2015, 50(05): 7-11.
[10] 王文华,曹怀信*,李玮. (A,B)-量子测量[J]. J4, 2012, 47(4): 70-76.
[11] 蒋华,李明珍,王鑫. 一种基于概率包标记的PPM算法改进方案[J]. J4, 2011, 46(9): 85-88.
[12] 袁秀华. 完全图的全符号控制数[J]. J4, 2010, 45(8): 43-46.
[13] 袁秀华. 图的符号边全控制数[J]. J4, 2009, 44(8): 21-24.
[14] 刘海英 马成刚 王志平. 刺图乘积上的Graham猜想[J]. J4, 2009, 44(8): 25-30.
[15] 王文丽,刘西奎,周 薇 . 关于图的广义Mycielski图的邻点可区别关联着色[J]. J4, 2008, 43(10): 77-79 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 唐风琴1,白建明2. 一类带有广义负上限相依索赔额的风险过程大偏差[J]. J4, 2013, 48(1): 100 -106 .
[2] 程智1,2,孙翠芳2,王宁1,杜先能1. 关于Zn的拉回及其性质[J]. J4, 2013, 48(2): 15 -19 .
[3] 汤晓宏1，胡文效2*，魏彦锋2，蒋锡龙2，张晶莹2，. 葡萄酒野生酿酒酵母的筛选及其生物特性的研究[J]. 山东大学学报（理学版）, 2014, 49(03): 12 -17 .
[4] 罗斯特,卢丽倩,崔若飞,周伟伟,李增勇*. Monte-Carlo仿真酒精特征波长光子在皮肤中的传输规律及光纤探头设计[J]. J4, 2013, 48(1): 46 -50 .
[5] 田学刚, 王少英. 算子方程AXB=C的解[J]. J4, 2010, 45(6): 74 -80 .
[6] 霍玉洪,季全宝. 一类生物细胞系统钙离子振荡行为的同步研究[J]. J4, 2010, 45(6): 105 -110 .
[7] 杨伦，徐正刚，王慧*，陈其美，陈伟，胡艳霞，石元，祝洪磊，曾勇庆*. RNA干扰沉默PID1基因在C2C12细胞中表达的研究[J]. J4, 2013, 48(1): 36 -42 .
[8] 刘婷婷,陈志勇,李晓琴*,杨文志. 随机变量序列的Berry-Esseen界[J]. 山东大学学报（理学版）, 2014, 49(03): 101 -106 .
[9] 刘艳萍,吴群英. 优化权重下高斯序列最大值几乎处处中心极限定理[J]. 山东大学学报（理学版）, 2014, 49(05): 50 -53 .
[10] 冒爱琴1, 2, 杨明君2, 3, 俞海云2, 张品1, 潘仁明1*. 五氟乙烷灭火剂高温热解机理研究[J]. J4, 2013, 48(1): 51 -55 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发