赋权图的燃烧与保护问题

兰州理工大学学报 ›› 2025, Vol. 51 ›› Issue (2): 152-158.

赋权图的燃烧与保护问题

李若彤, 魏宗田^*

西安建筑科技大学理学院, 陕西西安 710055

收稿日期:2023-05-17 出版日期:2025-04-28 发布日期:2025-04-29
通讯作者: 魏宗田(1964-),男,陕西横山人,博士,教授.Email:ztwei@xauat.edu.cn
基金资助:
国家自然科学基金(61902304)

On the problem of burning and protecting of weighted graphs

LI Ruo-tong, WEI Zong-tian

School of Science, Xi’an University of Architecture and Technology, Xi’an 710055, China

Received:2023-05-17 Online:2025-04-28 Published:2025-04-29

摘要/Abstract

摘要： 为减少网络遭到破坏所造成的损失,就要考虑网络的保护策略.将消防员问题和图燃烧相结合,提出赋权图的相对保护策略和最大保护率的概念.给出几类典型图的最大保护率计算公式和基于最大保护率的赋权极值图构造方法,设计了一般情形下半径为2,3的赋权树的最大保护率的近似算法,揭示了最大保护率与权值、赋权方式和图结构之间的关系.

关键词: 赋权图, 图燃烧, 保护策略, 最大保护率, 赋权

Abstract: In order to reduce the loss caused by network disruptions, it is necessary to consider the protection strategy. Combining the idea of the firefighter problem with graph burning, the concepts of the relative protection strategy and maximum protection rate of weighted graphs are proposed. The maximum protecting rate calculation formulas of several types of typically weighted graphs and the constructing method of extremely weighted graphs based on the maximum protecting rate are given. Additionally, an approximation algorithm is designed for computing the maximum protection rate of general trees with radius 2 and 3. The relationships between the maximum protection rate, the weight values, the way of weighting, and the structure of graphs are revealed.

Key words: weighted graph, graph burning, protection strategy, maximum protecting rate, weighting

中图分类号:

O157.5

李若彤, 魏宗田. 赋权图的燃烧与保护问题[J]. 兰州理工大学学报, 2025, 51(2): 152-158.

LI Ruo-tong, WEI Zong-tian. On the problem of burning and protecting of weighted graphs[J]. Journal of Lanzhou University of Technology, 2025, 51(2): 152-158.

参考文献

[1] 王维凡,孔将旭.图的存活率与消防员问题 [J].数学进展,2021,50(1):1-21.
[2] HARTNELL B.Firefighter! an application of domination [R].Winnipeg:University of Manitoba,1995.
[3] 翁婷婷,魏宗田.图的赋权邻域坚韧度 [J].山东大学学报(理学版),2022,57(6):36-43.
[4] 邢之尧.统计模型中若干格子图的消防员问题 [D].新疆:新疆师范大学,2022.
[5] 郭文婷,孔将旭.不含5-圈平面图的边存活率 [J].中国计量大学学报,2020,31(4):519-523.
[6] 刘佩佩,何志红.图的广义燃烧数及其界值问题 [J].烟台大学学报(自然科学与工程版),2022,35(4):385-389.
[7] 刘佩佩,何志红.图的积的广义燃烧数 [J].赤峰学院学报(自然科学版),2022,38(1):1-4.
[8] 郭文婷.图的燃烧数和存活率研究 [D].杭州:中国计量大学,2021.
[9] 卢鹏丽,周庚.基于邻介熵和邻度熵的复杂网络中心性算法 [J].兰州理工大学学报,2021,47(4):91-98.
[10] CAI L Z,WANG W F.The surviving rate of a graph for the firefighter problem [J].SIAM Journal on Discrete Mathematics,2009,23(4):1814-1826.
[11] BONDY J A,MURTY U S R.Graph theory [M].London:Springer,2008.
[12] BONATO A,JANSSEN J,ROSHANBIN E.How to burn a graph [J].Internet Mathematics,2016,12(1/2):85-100.
[13] 魏宗田,刘勇,杨威,等.网络抗毁性 [M].西安:西安交通大学出版社,2015.
[14] BONDY J A,MURTY U S R.Graph theory with applications [M].London:Macmillan,1976.
[15] 张胜贵,李学良,王力工.通信系统抗破坏能力研究 [J].西北工业大学学报,2002,20(1):100-103.
[16] COZZENS M,WU S.Edge-neighbor-integrity of trees [J].Australasian Journal of Combinatorics,1994,10(10):163-174.
[17] 杨雪.图的广义p-邻域抗毁性参数研究 [D].西安:西安建筑科技大学,2021.
[18] 杨胜良,姜美杨.混合d-元树上的模式避免问题 [J].兰州理工大学学报,2023,49(2):144-150.