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

《山东大学学报(理学版)》 ›› 2026, Vol. 61 ›› Issue (4): 102-108.doi: 10.6040/j.issn.1671-9352.0.2024.245

• • 上一篇    

基于多火源燃烧连通度的网络抗毁性分析

白月蓉,魏宗田,王德莉   

  1. 西安建筑科技大学理学院, 陕西 西安 710055
  • 发布日期:2026-04-08
  • 作者简介:白月蓉(2000— ),女,硕士研究生,研究方向为图论、组合优化及其应用. E-mail:byr66778899@126.com
  • 基金资助:
    陕西数理基础科学研究项目(22JSQ029)

Analysis of network invulnerability based on the multi-fire source burning connectivity

BAI Yuerong, WEI Zongtian, WANG Deli   

  1. Department of Mathematics, Xian University of Architecture and Technology, Xian 710055, Shaanxi, China
  • Published:2026-04-08

PDF (PC)

7

摘要： 给出几类笛卡尔积图的多火源燃烧连通度,分析多火源燃烧连通度与图结构的关系,提出多火源燃烧连通度的反问题:给定正数m,确定火源,使得最多在m步内将图燃烧为不连通或空集,且所含顶点数尽可能地少(最小火源)。最后,给出一个求图的最小火源的算法。

关键词: 图, 抗毁性, 多火源燃烧连通度, 笛卡尔积图, 算法

Abstract: The multi-fire source burning connectivity is given for several types of Cartesian product graphs. The relationship between multi-fire source burning connectivity and graph structure is analyzed, and the inverse problem of multi-fire source burning connectivity is proposed, that is, given a positive number m, determine the fire source such that the graph is burned as disconnected or empty within m steps at most, and contains as few vertices as possible(the minimum fire source). Finally, an algorithm of the minimum fire source of graphs is designed.

Key words: graph, invulnerability, multi-fire source burning connectivity, Cartesian product graphs, algorithm

中图分类号: 

  • O157.5
[1] 魏宗田,刘勇,杨威,等. 网络抗毁性[M]. 西安:西安交通大学出版社,2015:34-35. WEI Zongtian, LIU Yong, YANG Wei, et al. Network invulnerability[M]. Xian: Xian Jiaotong University Press, 2015:34-35.
[2] BONATO A, JANSSEN J, ROSHANBIN E. How to burn a graph[J]. Internet Mathematics, 2016, 12(1/2):85-100.
[3] 白月蓉,魏宗田. 图的多火源燃烧连通度[J]. 纯粹数学与应用数学,2026,42(1):78-85. BAI Yuerong, WEI Zongtian. Multi-fire source burning connectivity of graphs[J]. Pure and Applied Mathematics, 2026, 42(1):78-85.
[4] 徐俊明. 图论及其应用[M]. 4版. 合肥:中国科学技术大学出版社,2018. XU Junming. Theory and applications of graphs[M]. 4th ed. Hefei: University of Science and Technology of China Press, 2018.
[5] BONDY J A, MURTY U S R. Graph theory[M]. London: Springer, 2008.
[6] 梅银珍,符惠芬. 四类运算图的 Sombor 指数[J].山东大学学报(理学版),2024,59(6):56-63. MEI Yinzhen, FU Huifeng. Sombor index on four operation graphs[J]. Journal of Shandong University(Natural Science), 2024, 59(6):56-63.
[7] 薛睿滢,魏宗田,翟美娟. 图的限制性燃烧连通度[J]. 山东大学学报(理学版),2024,59(2):91-99. XUE Ruiying, WEI Zongtian, ZHAI Meijuan. Restricted burning connectivity of graphs[J]. Journal of Shandong University(Natural Science), 2024, 59(2): 91-99.
[1] 王智玄,庞继芳,王智强,宋鹏,李茹. 融合长短期兴趣的属性增强临时群组推荐算法[J]. 《山东大学学报(理学版)》, 2026, 61(3): 54-65.
[2] 姚勋祥,刘培培,徐英城,范清兰,包芳勋,张云峰. 基于多重分形优化的图像超分辨率重建[J]. 《山东大学学报(理学版)》, 2026, 61(3): 96-110.
[3] 杨滨,孙建楠,曹恩国,李子川,周志立. 基于显著性特征的海报设计侵权检测分析[J]. 《山东大学学报(理学版)》, 2026, 61(3): 11-19.
[4] 仲尚,马丽,刘文哲,李雨豪. 融合多尺度注意力机制和改进特征融合的轻量化水面小目标检测模型[J]. 《山东大学学报(理学版)》, 2026, 61(1): 15-25.
[5] 孙清,叶军,曾广财,宋苏洋,汪一心. 结合蝙蝠算法和紧密度改进的三支K-means算法[J]. 《山东大学学报(理学版)》, 2026, 61(1): 65-75.
[6] 王军涛,黄强. 基于一般重叠函数的模糊数学形态学边缘检测方法[J]. 《山东大学学报(理学版)》, 2026, 61(1): 36-48.
[7] 杨玉,孙圣博,徐子瑞,蒋效伟,宋强,戴红伟. 基于混合变异灰狼优化算法的泊位-岸桥调度[J]. 《山东大学学报(理学版)》, 2026, 61(1): 94-102.
[8] 刘福国,刘圆梦,石玉峰,田茂再. 基于VMD-DBO-BiGRU的多因素铁矿石期货价格预测[J]. 《山东大学学报(理学版)》, 2025, 60(9): 121-132.
[9] 严莉,呼海林,王高洲,张闻彬,潘法定,张啸,郑艳伟. 基于长短时序预测的拓扑构建与控制[J]. 《山东大学学报(理学版)》, 2025, 60(9): 41-51.
[10] 刘魏岩,齐迹,梁红,林钰川. 基于混合策略的鹈鹕优化算法[J]. 《山东大学学报(理学版)》, 2025, 60(9): 52-61.
[11] 王辉,刘蒙蒙. 三圈图的Mostar指标的下界[J]. 《山东大学学报(理学版)》, 2025, 60(8): 68-77.
[12] 王江,李敬文,高鑫,孙亮晶. 若干联图的邻点可约全标号[J]. 《山东大学学报(理学版)》, 2025, 60(8): 57-67.
[13] 吴辛尧,徐计. 基于图互信息池化的分层图表示学习[J]. 《山东大学学报(理学版)》, 2025, 60(7): 84-93.
[14] 武晓军,陈怡丹,郝耀军,宋长伟,何德清. 具有标签流形和动态图约束的多标签特征选择[J]. 《山东大学学报(理学版)》, 2025, 60(7): 69-83.
[15] 钱文彬,彭嘉豪,蔡星星. 基于邻域粒度与三支决策的知识表示学习方法[J]. 《山东大学学报(理学版)》, 2025, 60(7): 94-103.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发