赋权图的燃烧与保护问题  

On the problem of burning and protecting of weighted graphs

作　　者：李若彤 魏宗田[1] LI Ruo-tong;WEI Zong-tian(School of Science,Xi’an University of Architecture and Technology,Xi’an 710055,China)

机构地区：[1]西安建筑科技大学理学院,陕西西安710055

出　　处：《兰州理工大学学报》2025年第2期152-158,共7页Journal of Lanzhou University of Technology

基　　金：国家自然科学基金(61902304)。

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

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

分 类 号：O157.5[理学—数学]